[解決済み】lexical Analyzerの作成

質問

私は今、Javaを使って、字句解析のプログラムを作っています。この問題に対する回答を探していますが、今まで何も見つけることができませんでした。以下は私の問題です。

入力

System.out.println ("Hello World");

希望する出力

Lexeme----------------------Token

System [Key_Word]

.       [Object_Accessor]

out   [Key_Word]

. [Object_Accessor]

println  [Key_Word]

(  [left_Parenthesis]

"Hello World"    [String_Literal]

)   [right_Parenthesis]

;  [statement_separator]

まだまだ初心者なので、皆さんのお力をお借りできればと思います。ありがとうございます。

どのように解決するのですか？

ANTLRもDragon bookもなくても、簡単な字句解析器を手書きで書くことができます。Javaなど、より充実した言語の字句解析器でさえ、手で書くのはそれほど複雑ではありません。もちろん、産業用のタスクであれば、ANTLRやlexのような強力なツールを検討すべきですが、字句解析の仕組みを学ぶには、手作業で書くことが有効な練習になることが多いでしょう。あなたはまだ初心者とのことなので、このようなケースを想定しています。

この質問を見てから書いた、Schemeに似た言語のサブセットのための、Javaで書かれた簡単な字句解析器を紹介します。字句解析器を見たことがない人でも比較的理解しやすいコードだと思います。単に文字のストリーム(この場合は String )をトークン(この場合は List<Token> は、それほど難しいことではありません。もし質問があれば、もっと詳しく説明しますよ。

import java.util.List;
import java.util.ArrayList;

/*
 * Lexical analyzer for Scheme-like minilanguage:
 * (define (foo x) (bar (baz x)))
 */
public class Lexer {
    public static enum Type {
        // This Scheme-like language has three token types:
        // open parens, close parens, and an "atom" type
        LPAREN, RPAREN, ATOM;
    }
    public static class Token {
        public final Type t;
        public final String c; // contents mainly for atom tokens
        // could have column and line number fields too, for reporting errors later
        public Token(Type t, String c) {
            this.t = t;
            this.c = c;
        }
        public String toString() {
            if(t == Type.ATOM) {
                return "ATOM<" + c + ">";
            }
            return t.toString();
        }
    }

    /*
     * Given a String, and an index, get the atom starting at that index
     */
    public static String getAtom(String s, int i) {
        int j = i;
        for( ; j < s.length(); ) {
            if(Character.isLetter(s.charAt(j))) {
                j++;
            } else {
                return s.substring(i, j);
            }
        }
        return s.substring(i, j);
    }

    public static List<Token> lex(String input) {
        List<Token> result = new ArrayList<Token>();
        for(int i = 0; i < input.length(); ) {
            switch(input.charAt(i)) {
            case '(':
                result.add(new Token(Type.LPAREN, "("));
                i++;
                break;
            case ')':
                result.add(new Token(Type.RPAREN, ")"));
                i++;
                break;
            default:
                if(Character.isWhitespace(input.charAt(i))) {
                    i++;
                } else {
                    String atom = getAtom(input, i);
                    i += atom.length();
                    result.add(new Token(Type.ATOM, atom));
                }
                break;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        if(args.length < 1) {
            System.out.println("Usage: java Lexer \"((some Scheme) (code to) lex)\".");
            return;
        }
        List<Token> tokens = lex(args[0]);
        for(Token t : tokens) {
            System.out.println(t);
        }
    }
}

使用例です。

~/code/scratch $ java Lexer ""
~/code/scratch $ java Lexer "("
LPAREN
~/code/scratch $ java Lexer "()"
LPAREN
RPAREN
~/code/scratch $ java Lexer "(foo)"
LPAREN
ATOM<foo>
RPAREN
~/code/scratch $ java Lexer "(foo bar)"
LPAREN
ATOM<foo>
ATOM<bar>
RPAREN
~/code/scratch $ java Lexer "(foo (bar))"
LPAREN
ATOM<foo>
LPAREN
ATOM<bar>
RPAREN
RPAREN

このような簡単なレキサーを1つか2つ書けば、この問題がどのように分解されるのか、かなりよくわかるようになるでしょう。そうなると、lexのような自動化ツールの使い方を探ってみるのも面白いかもしれません。正規表現ベースのマッチャーの理論はそれほど難しいものではありませんが、完全に理解するのには時間がかかります。正規表現を有限オートメーションに変換する理論（まずNFA、次にNFAからDFA）などに飛び込むよりも、手でレキサを書いた方がその勉強のモチベーションになり、問題を把握するのに役立つと思います。

個人的には、ドラゴンの本はとても丁寧で良いのですが、網羅性を目指しているため、必ずしもわかりやすいとは言えないかもしれません。ドラゴンの本を開く前に、他のコンパイラのテキストを試してみるのもいいかもしれません。以下に無料の本をいくつか紹介しますが、これらは入門書としてはかなり良い内容だと思います。

http://www.ethoberon.ethz.ch/WirthPubl/CBEAll.pdf

http://www.diku.dk/~torbenm/Basics/

正規表現の実装に関するいくつかの記事（自動字句解析には通常正規表現が使われます）

http://swtch.com/~rsc/regexp/

お役に立てれば幸いです。幸運を祈ります。