ANTLR，表达式语法有问题

Question

我最近开始使用 ANTLR。我目前正试图编码与表达语法+，-，*并array[index]和几个结构。

这是所需的语法：

Exp -> Exp (+ | - | * | < | &&) Exp
     | Exp [ Exp ]
     | -Exp
     | ( Exp )
     | Exp.length
     | true
     | false
     | Id
     | this
     | ! Exp

我首先将其重构为AndExp, SumExp,ProdExp等以解决优先级问题。大致是这样的：

Exp        -> AndExp
AndExp     -> CmpExp (&& CmpExp)*
CmpExp     -> SumExp (< SumExp)*
SumExp     -> ProdExp ((+|-) ProdExp)*
ProdExp    -> UnaryExp (Times UnaryExp)*
UnaryExp   -> Minus* PrimaryExp
PrimaryExp -> Exp.length
            | Exp [ Exp ]
            | ! Exp
            | true
            | false
            | Id
            | this

然后我意识到这使用了左递归，而 ANTLR 不喜欢那样。我继续消除左递归，最终得到了这个语法：

grammar test;

options {
    language=Java;
    output=AST;
    backtrack=true;
}

start      : expression;

expression : andExp;
andExp     : cmpExp (And^ cmpExp)*;
cmpExp     : sumExp (LessThan^ sumExp)*;
sumExp     : prodExp ((Plus | Minus)^ prodExp)*;
prodExp    : unaryExp (Times^ unaryExp)*;
unaryExp   : Minus* primaryExp;

primaryExp : INT                   primaryPrime
           | 'true'                primaryPrime
           | 'false'               primaryPrime
           | 'this'                primaryPrime
           | ID                    primaryPrime
           | '!' expression        primaryPrime
           | '('! expression ')'!  primaryPrime
           ;


primaryPrime
           : '[' expression ']'             primaryPrime
           | '.' ID '(' exprList ')'        primaryPrime
           | '.length'                      primaryPrime
           | 'new' 'int' '[' expression ']' primaryPrime
           | 'new' ID '(' ')'               primaryPrime
           |
           ;


exprList   :
           | expression (',' expression)*;

LessThan   : '<';
Plus       : '+';
Minus      : '-';
Times      : '*';
And        : '&&';
Not        : '!';
INT        :    '0' | ('1'..'9')('0'..'9')*;
ID         :    ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*;
WS         : ('\t' | ' ' | '\r' | '\n'| '\u000C') { $channel=HIDDEN; } ;

• Q1：这种类型的语法是否“需要”回溯（除非我激活它，否则我无法通过 ANTLR 获得它）还是我遗漏了一些简单的东西？

• Q2：当添加一些^and-> ^(TOKEN ...)构造来刷树时，我遇到了以下烦人的情况（因为primaryPrime这是由于左因子分解）：

  primaryPrime
      : '[' expression ']' primaryPrime -> ^(ARRAY_EXPR expression)
  //...
  

  这将打开一个array[index]成

  array
  ARRAY_EXPR
      index
  

  虽然我真的想要

  ARRAY_EXPR
      array
      index
  

  解决这个问题的最佳方法是什么？我在这里是在正确的轨道上，还是应该一起采用其他方法？

Answer 1

A1

不，（还）不需要回溯。但是，如果您确实需要一些回溯，建议不要立即使用backtrack=true，而是在确实需要回溯的规则之前使用谓词。通过使用backtrack=true，您可以对所有规则启用回溯，而可能只有一两个规则需要回溯。但是，如果您的语言相对较小，backtrack=true则比手动混合谓词更容易，并且可能不会对性能产生很大影响。但是，如果您可以避免它们，请这样做。

您有几个匹配空字符串的解析器规则，这会导致问题。您通常最好让规则匹配某些内容，并使规则可选。所以而不是：

foo : bar baz ;
bar : 'bar' ;
baz : 'baz' | /* epsilon */ ;

做

foo : bar baz? ;
bar : 'bar' ;
baz : 'baz' ;

反而。

此外，在像保留关键字的情况下true，false等，不要在你的语法规则将它们混合：在你的词法规则的顶部总是明确定义它们。词法分析器规则从上到下匹配，因此最安全的做法是（至少）在这样的规则ID也可能匹配它们之前定义它们。我通常把它们作为第一个词法分析器规则。

A2

您可以通过将参数传递给解析器规则来做到这一点，尽管这会降低您的语法（有点）可读性。

你的语法和我的评论：

grammar test;

options {
  output=AST;
}

tokens {
  ARRAY_EXPR;
}

start      : expression;

expression : andExp;
andExp     : cmpExp (And^ cmpExp)*;
cmpExp     : sumExp (LessThan^ sumExp)*;
sumExp     : prodExp ((Plus | Minus)^ prodExp)*;
prodExp    : unaryExp (Times^ unaryExp)*;
unaryExp   :  '-' primaryExp
           |  '!' primaryExp // negation is really a `unaryExp`
           |  primaryExp
           ;

primaryExp : INT                  primaryPrime[null]?
           | 'true'               primaryPrime[null]?
           | 'false'              primaryPrime[null]?
           | 'this'               primaryPrime[null]?
           | (ID -> ID)           (primaryPrime[new CommonTree($ID)] -> primaryPrime)?
           | '('! expression ')'! primaryPrime[null]?
           ;

// removed the matching of 'epsilon'
primaryPrime [CommonTree parent]
           : '[' expression ']'             primaryPrime[null]? -> ^(ARRAY_EXPR {parent} expression primaryPrime?)
           | '.' ID '(' exprList? ')'       primaryPrime[null]?
           | '.length'                      primaryPrime[null]?
           | 'new' 'int' '[' expression ']' primaryPrime[null]?
           | 'new' ID '(' ')'               primaryPrime[null]?
           ;

// removed the matching of 'epsilon' 
exprList   : expression (',' expression)*;

// be sure to create explicit tokens for keywords!
True       : 'true';
False      : 'false';
This       : 'this';
LessThan   : '<';
Plus       : '+';
Minus      : '-';
Times      : '*';
And        : '&&';
Not        : '!';
INT        : '0' | ('1'..'9')('0'..'9')*;
ID         : ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*;
WS         : ('\t' | ' ' | '\r' | '\n'| '\u000C') { $channel=HIDDEN; } ;

将输入解析"array[2*3]"为以下 AST：

正如您可以通过运行以下测试类看到的：

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 source = "array[2*3]";
    testLexer lexer = new testLexer(new ANTLRStringStream(source));
    CommonTokenStream tokens = new CommonTokenStream(lexer);
    testParser parser = new testParser(tokens);
    testParser.start_return returnValue = parser.start();
    CommonTree tree = (CommonTree)returnValue.getTree();
    DOTTreeGenerator gen = new DOTTreeGenerator();
    StringTemplate st = gen.toDOT(tree);
    System.out.println(st);
  }
}