antlr - 解决antlr左递归

Question

我正在尝试使用 ANTLR 解析一种语言，它可以包含以下语法：

someVariable, somVariable.someMember, functionCall(param).someMember,  foo.bar.baz(bjork).buffalo().xyzzy

这是我到目前为止提出的 ANTLR 语法，并access_operation抛出错误

The following sets of rules are mutually left-recursive [access_operation, expression]：

grammar Test;

options { 
  output=AST;
  ASTLabelType=CommonTree; 
}

tokens {
  LHS;
  RHS;
  CALL;
  PARAMS;
}

start   
  :  body? EOF
  ;

body
  : expression (',' expression)*
  ;

expression
  : function -> ^(CALL)
  | access_operation
  | atom
  ;

access_operation
  : (expression -> ^(LHS)) '.'! (expression -> ^(RHS))
  ;

function
  : (IDENT '(' body? ')') -> ^(IDENT PARAMS?) 
  ;         

atom
  : IDENT
  | NUMBER
  ;

fragment LETTER : ('a'..'z' | 'A'..'Z');
fragment DIGIT  : '0'..'9';

IDENT    : (LETTER)+ ;
NUMBER   : (DIGIT)+ ;
SPACE    : (' ' | '\t' | '\r' | '\n') { $channel=HIDDEN; };

到目前为止，我可以管理的是重构生成 AST 的access_operation规则，'.' expression其中access_operation节点仅包含操作的右侧。

我正在寻找的是这样的东西：

在这种情况下如何解决左递归问题？

Answer 1

通过“错误的 AST”，我会做出一个半有根据的猜测，对于类似 的输入"foo.bar.baz"，您会得到一个 AST，其中foo根是bar作为孩子的孩子，而孩子又baz是孩子，这是 AST 中的叶子。您可能希望将其反转。但如果我是你，我不会选择这样的 AST：我会尽可能保持 AST：

    foo
   / | \
  /  |  \
bar baz  ...

这样，评估就容易得多：您只需向上查找foo，然后从左到右遍历其子项。

快速演示：

grammar Test;

options { 
  output=AST;
  ASTLabelType=CommonTree; 
}

tokens {
  BODY;
  ACCESS;
  CALL;
  PARAMS;
}

start   
 : body EOF -> body
 ;

body
 : expression (',' expression)* -> ^(BODY expression+)
 ;

expression
 : atom
 ;         

atom
 : NUMBER
 | (IDENT -> IDENT) ( tail       -> ^(IDENT tail)
                    | call tail? -> ^(CALL IDENT call tail?)
                    )?
 ;

tail
 : (access)+
 ;

access
 : ('.' IDENT -> ^(ACCESS IDENT)) (call -> ^(CALL IDENT call))?
 ;

call
 : '(' (expression (',' expression)*)? ')' -> ^(PARAMS expression*)
 ;

IDENT  : LETTER+;
NUMBER : DIGIT+;
SPACE  : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;};

fragment LETTER : ('a'..'z' | 'A'..'Z');
fragment DIGIT  : '0'..'9';

可以通过以下方式进行测试：

import org.antlr.runtime.*;
import org.antlr.runtime.tree.*;
import org.antlr.stringtemplate.*;

public class Main {
  public static void main(String[] args) throws Exception {
    String src = "someVariable, somVariable.someMember, functionCall(param).someMember, " + 
        "foo.bar.baz(bjork).buffalo().xyzzy";
    TestLexer lexer = new TestLexer(new ANTLRStringStream(src));
    TestParser parser = new TestParser(new CommonTokenStream(lexer));
    CommonTree tree = (CommonTree)parser.start().getTree();
    DOTTreeGenerator gen = new DOTTreeGenerator();
    StringTemplate st = gen.toDOT(tree);
    System.out.println(st);
  }
}

的输出Main对应于以下 AST：

编辑

并且由于您指出您的最终目标不是评估输入，而是您需要使 AST 的结构符合某些 3 ^rd方 API，所以这里有一个语法，它将创建一个 AST，就像您在编辑的问题中指出的那样：

grammar Test;

options { 
  output=AST;
  ASTLabelType=CommonTree; 
}

tokens {
  BODY;
  ACCESS_OP;
  CALL;
  PARAMS;
  LHS;
  RHS;
}

start   
 : body EOF -> body
 ;

body
 : expression (',' expression)* -> ^(BODY expression+)
 ;

expression
 : atom
 ;         

atom
 : NUMBER
 | (ID -> ID) ( ('(' params ')' -> ^(CALL ID params)) 
                ('.' expression -> ^(ACCESS_OP ^(LHS ^(CALL ID params)) ^(RHS expression)))?
              | '.' expression  -> ^(ACCESS_OP ^(LHS ID) ^(RHS expression))
              )?
 ;

params
 : (expression (',' expression)*)? -> ^(PARAMS expression*)
 ;

ID     : LETTER+;
NUMBER : DIGIT+;
SPACE  : (' ' | '\t' | '\r' | '\n') {$channel=HIDDEN;};

fragment LETTER : ('a'..'z' | 'A'..'Z');
fragment DIGIT  : '0'..'9';

Main如果您运行该类，它将创建以下 AST ：

这条atom规则可能有点令人生畏，但你不能把它缩短太多，因为左边ID需要可供大多数替代品使用。ANTLRWorks 有助于可视化此规则可能采用的替代路径：

这意味着atom可以是以下 5 个备选方案中的任何一个（及其相应的 AST）：

+----------------------+--------------------------------------------------------+
| alternative          | generated AST                                          |
+----------------------+--------------------------------------------------------+
| NUMBER               | NUMBER                                                 |
| ID                   | ID                                                     |
| ID params            | ^(CALL ID params)                                      |
| ID params expression | ^(ACCESS_OP ^(LHS ^(CALL ID params)) ^(RHS expression))|
| ID expression        | ^(ACCESS_OP ^(LHS ID) ^(RHS expression)                |
+----------------------+--------------------------------------------------------+