ANTLR: токены правила имеют не-LL (*) решение из-за рекурсивных вызовов правил, достижимых из alts 1,2 - PullRequest
Новая
       3

ANTLR: токены правила имеют не-LL (*) решение из-за рекурсивных вызовов правил, достижимых из alts 1,2

2 голосов
/ 14 июля 2010 
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...

Когда я интерпретирую, я пытаюсь интерпретировать ПРЕДИКАТ, и мой тестовый пример (A || B)

Чего мне не хватает?

Ответы [ 2 ]

5 голосов
/ 16 июля 2010

В соответствии с соглашениями ANTLR имена правил синтаксического анализатора начинаются со строчной буквы, а правила лексера начинаются с заглавных букв. Таким образом, грамматика, как вы ее написали, имеет три правила лексера, определяющих токены. Это может быть не то, что вы хотите.

Причина сообщения об ошибке, очевидно, заключается в неоднозначности между этими токенами: ваш входной шаблон соответствует определениям PREDICATE и PREDICATE_BRANCH.

Просто используйте имена, начинающиеся с строчных букв вместо PREDICATE и PREDICATE_BRANCH. Возможно, вам также понадобится добавить дополнительное правило для целевого символа, которое напрямую не участвует в рекурсии.

Кстати, эта грамматика является рекурсивной, но не леворекурсивной, и при использовании правил синтаксического анализа она определенно является LL (1).

1 голос
/ 14 июля 2010

У вас нет правила синтаксического анализа (правила синтаксического анализа начинаются со строчной буквы), хотя я не уверен, что последняя часть необходима при интерпретации некоторых тестовых примеров в 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

...