読者です 読者をやめる 読者になる 読者になる

cloverrose's blog

Python, Machine learning, Emacs, CI/CD, Webアプリなど

ANTLRの左結合・右結合について

ANTLR ANTLRv4

追記 2013/5/22

演算子をTOKENにする方法も間違っていました。
訂正ANTLRで演算子をTOKENにしない方がいい - cloverrose's blog

ruleにする場合とTOKENにする場合で挙動が違うというところや
ANTLRv3とANTLRv4の違いについては参考になりそうなので、一応変更せず残しておきます。

追記終わり


ANTLR v4でやったー左再帰が書けるって喜んで書きましたが。落とし穴がありました。

コンパイラー詳しい人はこんなミスしないと思うけど、LexerとParserの区別ができていないため落とし穴に落ちました。

演算子が右結合になってしまったダメな例

演算子をTOKENではなくてruleとして定義しています。

Expr1.g4

grammar Expr1;

// PARSER ======================================================================
prog
    :  (expr ';')+
    ;

expr:  INT
    |  '(' expr ')'
    |  unMinusOp expr
    |  expr multOp expr
    |  expr plusOp expr
    ;

unMinusOp
    :  '-'
    ;

multOp
    :  ('*' | '/' | '%')
    ;

plusOp
    :  ('+' | '-')
    ;

// LEXER =======================================================================
INT :  ('0' | '1'..'9' DIGIT*)
    ;
fragment
DIGIT
    :  '0'..'9'
    ;

WS  :  [ \r\t\u000C\n]+ -> channel(HIDDEN)
    ;
$ antlr4 Expr1.g4
$ javac *.java
$ grun Expr prog -gui
10+6/2*5*3;

f:id:cloverrose:20130520010719p:plain

図を見て解るように演算子が右結合になってしまっています。

演算子が左結合になった正しい例

演算子をTokenとして定義して書き直しました。

Expr2.g4

grammar Expr2;

// PARSER ======================================================================
prog
    :  (expr ';')+
    ;

expr:  INT
    |  '(' expr ')'
    |  UN_MINUS_OP expr
    |  expr MULT_OP expr
    |  expr PLUS_OP expr
    ;

// LEXER =======================================================================
UN_MINUS_OP
    :  '-'
    ;

MULT_OP
    :  ('*' | '/' | '%')
    ;

PLUS_OP
    :  ('+' | '-')
    ;

INT :  ('0' | '1'..'9' DIGIT*)
    ;
fragment
DIGIT
    :  '0'..'9'
    ;

WS  :  [ \r\t\u000C\n]+ -> channel(HIDDEN)
    ;

f:id:cloverrose:20130520010729p:plain
これで左結合に出来ました。

おまけ(ANTLR v3とv4の違い)

この変更過程でANTLR v3までとの変更箇所にいくつか出くわしました。

tokensの定義の仕方が変わった

ANTLR v3では

tokens{
   UN_MINUS_OP;
   MULT_OP;
   PLUS_OP;
}

でしたが、ANTLR v4では

tokens{UN_MINUS_OP, MULT_OP, PLUS_OP}

になっています。
PLUS_OPのあとにカンマを入れるとエラーが出ます。
改行は任意です。ただ最後にカンマ入れれないしセミコロンじゃないので短ければ1行で書きたい雰囲気になりました。


またQuick Starter on Parser Grammars - No Past Experience Required - ANTLR 3 - ANTLR ProjectのHow to define tokensに書いてあるように、
ANTLR v3では

tokens {
   IMAGINERY_TOKEN;
   EQUALS='=';
}

といったように対応付けることができましたが、ANTLR v4ではできなくなりました。

ただANTLR v4親切なので、v3の書き方をしているとどう直せばいいか教えてくれました。

setTypeが無くなった

ANTLR v3では明示的にASTを指定するので.setTypeが使えましたが、ANTLR v4では.setTypeはなくなりました。Token (ANTLR 4 Runtime 4.0 API)

ANTLR v3でsetTypeを使った例を載せておきます。

grammar Expr3;
options {
  output = AST;
  backtrack=true;
}
tokens{
    PLUS;
    MINUS;
    MULT;
    DIV;
    MOD;
    UNARY_MINUS;
}

// PARSER ======================================================================
prog
    :  (expr ';'!)+
    ;

expr
    :   addE
    ;

addE:   multE
        ((r1='+'^ {$r1.setType(PLUS);}
        | r2='-'^ {$r2.setType(MINUS);})
         multE )*
    ;

multE
    :   unaryE
        ((r1='*'^ {$r1.setType(MULT);}
        | r2='/'^ {$r2.setType(DIV);}
        | r3='%'^ {$r3.setType(MOD);})
        unaryE)*
    ;

unaryE
    :   (r1='-'^ {$r1.setType(UNARY_MINUS);})? atomE
    ;

atomE
    :   INT
    |   '('! addE ')'!
    ;

// LEXER =======================================================================
INT :  ('0' | '1'..'9' DIGIT*)
    ;
fragment
DIGIT
    :  '0'..'9'
    ;

WS  :   (' '|'\t'|'\r'|'\n')+ {$channel=HIDDEN;}
    ;

ANTLR v3ではgrunの代わりにANTLR Works使えそうですが、自分の環境だと上手く動かなかったので確認用のプログラムを書いてASTを確認してみます。

Main.java

import java.io.IOException;
import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;

public class Main {
    public static void main(String[] args) throws IOException, RecognitionException {
        CharStream input = new ANTLRInputStream(System.in);
        Expr3Lexer lex = new Expr3Lexer(input);
        CommonTokenStream tokens = new CommonTokenStream(lex);
        Expr3Parser p = new Expr3Parser(tokens);
        RuleReturnScope r = p.prog();
        CommonTree t = (CommonTree)r.getTree();
        System.out.println(t.toStringTree());
    }
}
$ wget http://www.antlr3.org/download/antlr-3.5-complete.jar
$ java -cp antlr-3.5-complete.jar org.antlr.Tool Expr3.g
$ javac *.java
$ echo '10+6/2*5*3;' | java Main
(+ 10 (* (* (/ 6 2) 5) 3))

ちょうどうでもいいおまけ(落とし穴にはまっていった過程)

IDやINTに.getText()あってソレ使ってたのに、選択( | のこと)あるからruleにしないとダメだ!って思ってしまったんだと思います。


あと最初は、こんな感じで別にruleにもTOKENにも吐き出さず定義していました。

expr:  INT
    |  '(' expr ')'
    |  '-' expr
    |  expr ('*' | '/' | '%') expr
    |  expr ('+' | '-') expr
    ;

このうな文法ファイルから作られたパーサーでは、実際に*,/,%の内どれが選ばれたかが普通はわかりません。
汚い方法としては、ParserRuleContext (ANTLR 4 Runtime 4.0 API)あたりを使って頑張ると、*とか/とかのTOKEN番号とかがわかるんですが、その番号も文法ファイル変更したら変わってしまいます。

さらに、あとで説明する.setTypeも使えないので、どれが呼ばれたか知るには、演算子部分を別のruleまたはTOKENに吐き出して(でも選択あるからruleじゃ無いとダメだと勘違いして)getText()で*か/か%が取得すればいいなと思ったという経緯です。