コンパイラ・コンパイラ,あるいは夢見るパーザジェネレータ
JavaCCとANTLRとSableCCとCUPとnotavaccの比較ってだれかやってくんない?
禿同.こういうのの使い勝手と原理の第三者によるサマリーってアカデミアの人は書かないのかな.ついでに書籍情報.中身は知らないので誰か買え(ぉ
夏学期の計算機プログラミングII*1の最終課題にはJavaによるパーザジェネレータのおもちゃを提出した.エンジンはLL(1)で内部で動的にFIRSTだのFOLLOWだのを求める.余り考えずにHashMapを使いまくり.セマンティックアクションはなく,単に文法に合致しているかどうかを調べるだけ(ぉ だって再帰下降構文解析に適合するセマンティックアクションは各再帰呼出しの間毎に実行したり,複雑なんだもん. 私がLALRを理解すれば,もちろん対応する文法の集合は広がるし,しかもセマンティックアクション機構の実装が容易になるのでほんもののパーザが自作ライブラリ上に実現できるかもしれない.しかし物理と数学で息の上がっている今となっては...
ちなみにメインのコードはこんな感じになった.
public static void main(String[] args) { try { Lexer lexer; if (args.length > 0) { lexer = new Lexer(new FileInputStream(args[0])); } else { lexer = new Lexer(System.in); } /* lexer = new Lexer(new StringReader("100 + 2 * 3")); */ lexer.addRule("\\s+", new LexicalAction() { Token action() { return null; } }); lexer.addRule("\\d+", new LexicalAction() { Token action() { return new Digits(matched); } }); lexer.addRule("\\(", new LexicalAction() { Token action() { return Token.lParen_; } }); lexer.addRule("\\)", new LexicalAction() { Token action() { return Token.rParen_; } }); lexer.addRule("\\+", new LexicalAction() { Token action() { return Token.plus_; } }); lexer.addRule("-", new LexicalAction() { Token action() { return Token.minus_; } }); lexer.addRule("\\*", new LexicalAction() { Token action() { return Token.asterisc_; } }); lexer.addRule("/", new LexicalAction() { Token action() { return Token.slashDotJapan_; } }); // an LL(1) grammar for arithmetic expressions Grammar grammar = new Grammar(); Nonterminal E = grammar.newNonterminal("E"); Nonterminal E_ = grammar.newNonterminal("E_"); Nonterminal T = grammar.newNonterminal("T"); Nonterminal T_ = grammar.newNonterminal("T_"); Nonterminal F = grammar.newNonterminal("F"); // E ::= T E_ | "-" T E_ E.produces(new GrammaticalSymbol[][] { { T, E_, }, { new Terminal(Token.minus_), T, E_, }, } ); // E_ ::= "+" T E_ | "-" T E_ | \epsilon E_.produces(new GrammaticalSymbol[][] { { new Terminal(Token.plus_), T, E_, }, { new Terminal(Token.minus_), T, E_, }, { Epsilon.epsilon, }, } ); // T ::= F T_ T.produces(new GrammaticalSymbol[][] { { F, T_, }, } ); // T_ ::= "*" F T_ | "/" F T_ | \epsilon T_.produces(new GrammaticalSymbol[][] { { new Terminal(Token.asterisc_), F, T_, }, { new Terminal(Token.slashDotJapan_), F, T_, }, { Epsilon.epsilon, }, } ); // F ::= digits | "(" E ")" F.produces(new GrammaticalSymbol[][] { { new Terminal(new Digits()), }, { new Terminal(Token.lParen_), E, new Terminal(Token.rParen_), }, } ); System.out.println("Compiling parser."); Parser parser = E.getParser(lexer); // E as an initial symbol System.out.println("Begin parsing."); System.out.println(parser.parse()); System.out.println("Finished parsing."); // System.out.println(parser.parse().eval()); } catch (Exception exception) { exception.printStackTrace(); } }
*1:もうずいぶん経つな... 繰り返すようだが,何でこんなに時間の流れが速いんだ?