ANTLR：由于可从 alts 1,2 访问递归规则调用，因此规则令牌具有非 LL(*) 决策

Question

grammar AdifyMapReducePredicate;

PREDICATE 
    :   PREDICATE_BRANCH
    |   EXPRESSION
    ;

PREDICATE_BRANCH
    :   '(' PREDICATE (('&&' PREDICATE)+ | ('||' PREDICATE)+) ')'
    ;

EXPRESSION 
    :   ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*
    ;

尝试在 ANTLRWorks 1.4 中解释这一点并收到以下错误：

[12:18:21] error(211): <notsaved>:1:8: [fatal] rule Tokens has non-LL(*) decision due to recursive rule invocations reachable from alts 1,2.  Resolve by left-factoring or using syntactic predicates or using backtrack=true option.
[12:18:21] Interpreting...

当我解释时，我试图解释 PREDICATE 并且我的测试用例是 (A||B)

我缺少什么？

Answer 1

根据 ANTLR 的约定，解析器规则名称以小写字母开头，而词法分析器规则以大写字母开头。因此，正如您所写的那样，语法具有三个词法分析器规则，用于定义标记。这可能不是您想要的。

错误消息的原因显然是这些标记之间的歧义：您的输入模式与 PREDICATE 和 PREDICATE_BRANCH 的定义匹配。

只需使用以小写字母开头的名称，而不是 PREDICATE 和 PREDICATE_BRANCH。您可能还需要为目标符号添加一条不直接参与递归的额外规则。

顺便说一句，这个语法是递归的，但不是左递归的，并且当使用解析器规则时，它肯定是LL(1)。

Answer 2

您没有解析器规则（解析器规则以小写字母开头），尽管我不确定在解释 ANTLRWorks 中的某些测试用例时最后一部分是否必要。

无论如何，尝试这样的事情：

grammar AdifyMapReducePredicate;

parse
  :  (p=predicate {System.out.println("parsed :: "+$p.text);})+ EOF
  ;

predicate 
  :  expression
  ;

expression
  :  booleanExpression
  ;

booleanExpression
  :  atom ((AND | OR) atom)*
  ;

atom
  :  ID
  |  '(' predicate ')'
  ;

AND
  :  '&&'
  ;

OR
  :  '||'
  ;

ID 
  :  ('a'..'z'|'A'..'Z'|'_') ('a'..'z'|'A'..'Z'|'0'..'9'|'_')*
  ;

SPACE
  :  (' ' | '\t' | '\r' | '\n') {skip();}
  ;

使用以下测试类：

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

public class Main {
    public static void main(String[] args) throws Exception {
        ANTLRStringStream in = new ANTLRStringStream("(A || B) (C && (D || F || G))");
        AdifyMapReducePredicateLexer lexer = new AdifyMapReducePredicateLexer(in);
        CommonTokenStream tokens = new CommonTokenStream(lexer);
        AdifyMapReducePredicateParser parser = new AdifyMapReducePredicateParser(tokens);
        parser.parse();
    }
}

在生成词法分析器和之后；解析器 (a)，编译所有 .java 文件 (b) 并运行测试类 (c)，产生以下输出：

parsed :: (A||B)
parsed :: (C&&(D||F||G))

a

java -cp antlr-3.2.jar org.antlr.Tool AdifyMapReducePredicate.g 

b

javac -cp antlr-3.2.jar *.java

c (*nix/MacOS)

java -cp .:antlr-3.2.jar Main

c (Windows)

java -cp .;antlr-3.2.jar Main

HTH