解决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 ^次聚会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)                |
+----------------------+--------------------------------------------------------+