ANTLR (2) antlr4-parseで構文解析

あけましておめでとうございます。今年もゆるく楽しく活動していきます。

前回の記事でantlr4-toolsの導入が終わりました。今回はantlr4-parseコマンドを使って構文解析してみます。

ji1jdi.hatenablog.com

antlr4-toolsの導入の仕方と使い方は次のドキュメントに記載されています。

github.com github.com

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を表示しているようです。