ANTLR (2) antlr4-parseで構文解析
あけましておめでとうございます。今年もゆるく楽しく活動していきます。
前回の記事でantlr4-tools
の導入が終わりました。今回はantlr4-parse
コマンドを使って構文解析してみます。
antlr4-tools
の導入の仕方と使い方は次のドキュメントに記載されています。
antlr4-parse
実行してみる前にこのコマンドの中身を調べてみることにします。このコマンドはPythonスクリプトになっていました。
import re import sys from antlr4_tool_runner import interp if __name__ == '__main__': sys.argv[0] = re.sub(r'(-script\.pyw?|\.exe)?$', '', sys.argv[0]) sys.exit(interp())
interp()
は次のようにrg.antlr.v4.gui.Interpreter
を実行しています。
def interp(): ... p = subprocess.Popen([java, '-cp', jar, 'org.antlr.v4.gui.Interpreter']+args, stdout=subprocess. PIPE, stderr=subprocess.PIPE) ...
Interpreterクラスのコメントには次のように書いてありました。構文木のツリーとプロファイル情報を表示できるようです。
/** Interpret a lexer/parser, optionally printing tree string and dumping profile info * * $ java org.antlr.v4.runtime.misc.Intrepreter [X.g4|XParser.g4 XLexer.g4] startRuleName inputFileName * [-tree] * [-gui] * [-trace] * [-encoding encoding] * [-tokens] * [-profile filename.csv] */
文法ファイルの作成
antlr4-toolsのREADMEに記載されているサンプルの文法を使います。次の内容のファイルを作成します。このときgrammer
で指定した名前とファイル名のベース名は同じ名前にする必要があります。ここではExpr.g4
というファイル名になります。
grammar Expr; prog: expr EOF ; expr: expr ('*'|'/') expr | expr ('+'|'-') expr | INT | '(' expr ')' ; NEWLINE : [\r\n]+ -> skip; INT : [0-9]+ ;
構文解析してみる
次の式を構文解析してみます。
599+73+77
トークン情報の表示
まずトークンの情報を表示してみます。次のように実行すると標準入力から入力を受け付けます。上の式を入力後、Ctrl-Dを入力すると解析が始まります。
$ antlr4-parse Expr.g4 prog -tokens 599+73*77 [@0,0:2='599',<INT>,1:0] [@1,3:3='+',<'+'>,1:3] [@2,4:5='73',<INT>,1:4] [@3,6:6='*',<'*'>,1:6] [@4,7:8='77',<INT>,1:7] [@5,10:9='<EOF>',<EOF>,2:0]
トークンに分割されたものが表示されました。各行の内容はCommonToken
クラスのtoString()
で次のように出力されています。入力テキストの先頭からの位置や、行の中でのカラムの位置がわかります。
return "[@"+getTokenIndex()+","+start+":"+stop+"='"+txt+"',<"+typeString+">"+channelStr+","+line+":"+getCharPositionInLine()+"]";
構文木の表示
次に構文木を表示してみます。
$ antlr4-parse Expr.g4 prog -tree 599+73*77 (prog:1 (expr:2 (expr:3 599) + (expr:1 (expr:3 73) * (expr:3 77))) <EOF>)
これはTrees
クラスのtoStringTree()
でLISPフォームの形式で表示されています。
トレースの表示
最後にトレースを表示します。
antlr4-parse Expr.g4 prog -trace 599+73*77 enter prog, LT(1)=599 enter expr, LT(1)=599 consume [@0,0:2='599',<8>,1:0] rule expr enter expr, LT(1)=+ consume [@1,3:3='+',<3>,1:3] rule expr enter expr, LT(1)=73 consume [@2,4:5='73',<8>,1:4] rule expr enter expr, LT(1)=* consume [@3,6:6='*',<1>,1:6] rule expr enter expr, LT(1)=77 consume [@4,7:8='77',<8>,1:7] rule expr exit expr, LT(1)=<EOF> exit expr, LT(1)=<EOF> exit expr, LT(1)=<EOF> consume [@5,10:9='<EOF>',<-1>,2:0] rule prog exit prog, LT(1)=<EOF>
これはParser
抽象クラスのインナークラスTraceListener
が表示しているようです。構文木を辿っているときに非終端記号のノードに入ったときにenter
、出るときにexit
、終端記号に出会ったらconsume
を表示しているようです。