Почему Antlr заходит в бесконечный цикл при обработке моей грамматики

Я создал грамматику ANTLR для разбора математических выражений и второй для их оценки. Поскольку я думал, что создание AST с последующим повторным анализом для его фактической оценки - это слишком сложная операция, я хотел реорганизовать мою грамматику, чтобы получить иерархию объектов "Term", представляющих выражение, включая логику для выполнения этого конкретного операция. Корневой объект Term затем может быть просто оценен до конкретного результата.

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

Может ли кто-нибудь здесь помочь мне разобраться в проблеме? Я думаю, что грамматика должна быть довольно интересной для некоторых, поэтому я публикую ее. (Я должен признать, что он основан на гарммар, который я нашел в Google, но я довольно сильно изменил его, чтобы удовлетворить свои потребности).

grammar SecurityRulesNew;

options {
language = Java;
    output=AST;
    backtrack = true;
    ASTLabelType=CommonTree;
    k=2;
}

tokens {
    POS;
    NEG;
    CALL;
}

@header {package de.cware.cweb.services.evaluator.parser;}
@lexer::header{package de.cware.cweb.services.evaluator.parser;}

formula returns [Term term]
: a=expression EOF { $term = a; }
;
expression returns [Term term]
: a=boolExpr { $term = a; }
;
boolExpr returns [Term term]
: a=sumExpr { $term = a; }
| a=sumExpr AND b=boolExpr { $term = new AndTerm(a, b); }
| a=sumExpr OR b=boolExpr { $term = new OrTerm(a, b); }
| a=sumExpr LT b=boolExpr { $term = new LessThanTerm(a, b); }
| a=sumExpr LTEQ b=boolExpr { $term = new LessThanOrEqualTerm(a, b); }
| a=sumExpr GT b=boolExpr { $term = new GreaterThanTerm(a, b); }
| a=sumExpr GTEQ b=boolExpr { $term = new GreaterThanTermOrEqual(a, b); }
| a=sumExpr EQ b=boolExpr { $term = new EqualsTerm(a, b); }
| a=sumExpr NOTEQ b=boolExpr { $term = new NotEqualsTerm(a, b); }
;
sumExpr returns [Term term]
: a=productExpr { $term = a; }
| a=productExpr SUB b=sumExpr { $term = new SubTerm(a, b); }
| a=productExpr ADD b=sumExpr { $term = new AddTerm(a, b); }
;
productExpr returns [Term term]
: a=expExpr { $term = a; }
| a=expExpr DIV productExpr { $term = new DivTerm(a, b); }
| a=expExpr MULT productExpr { $term = new MultTerm(a, b); }
;
expExpr returns [Term term]
: a=unaryOperation { $term = a; }
| a=unaryOperation EXP expExpr { $term = new ExpTerm(a, b); }
;
unaryOperation returns [Term term]
: a=operand { $term = a; }
| NOT a=operand { $term = new NotTerm(a); }
| SUB a=operand { $term = new NegateTerm(a); }
;
operand returns [Term term]
: l=literal { $term = l; }
| f=functionExpr { $term = f; }
| v=VARIABLE { $term = new VariableTerm(v); }
| LPAREN e=expression RPAREN { $term = e; }
;
functionExpr returns [Term term]
: f=FUNCNAME LPAREN! RPAREN! { $term = new CallFunctionTerm(f, null); }
| f=FUNCNAME LPAREN! a=arguments RPAREN! { $term = new CallFunctionTerm(f, a); }
;
arguments returns [List<Term> terms]
: a=expression 
    { 
        $terms = new ArrayList<Term>(); 
        $terms.add(a);
    }
| a=expression COMMA b=arguments
    { 
        $terms = new ArrayList<Term>(); 
        $terms.add(a);
        $terms.addAll(b);
    }
;
literal returns [Term term]
: n=NUMBER { $term = new NumberLiteral(n); }
| s=STRING { $term = new StringLiteral(s); }
| t=TRUE { $term = new TrueLiteral(t); }
| f=FALSE { $term = new FalseLiteral(f); }
;

STRING
:
'\"'
    ( options {greedy=false;}
    : ESCAPE_SEQUENCE
    | ~'\\'
    )*
'\"'
|
'\''
    ( options {greedy=false;}
    : ESCAPE_SEQUENCE
    | ~'\\'
    )*
'\''
;
WHITESPACE
: (' ' | '\n' | '\t' | '\r')+ {skip();};
TRUE
: ('t'|'T')('r'|'R')('u'|'U')('e'|'E')
;
FALSE
: ('f'|'F')('a'|'A')('l'|'L')('s'|'S')('e'|'E')
;

NOTEQ           : '!=';
LTEQ            : '<=';
GTEQ            : '>=';
AND             : '&&';
OR              : '||';
NOT             : '!';
EQ              : '=';
LT              : '<';
GT              : '>';

EXP             : '^';
MULT            : '*';
DIV             : '/';
ADD             : '+';
SUB             : '-';

LPAREN          : '(';
RPAREN          : ')';
COMMA           : ',';
PERCENT         : '%';

VARIABLE
: '[' ~('[' | ']')+ ']'
;
FUNCNAME
: (LETTER)+
;
NUMBER
: (DIGIT)+ ('.' (DIGIT)+)?
;

fragment
LETTER 
: ('a'..'z') | ('A'..'Z')
;
fragment
DIGIT
: ('0'..'9')
;
fragment
ESCAPE_SEQUENCE
: '\\' 't'
| '\\' 'n'
| '\\' '\"'
| '\\' '\''
| '\\' '\\'
;

Помощь очень ценится.

Крис

Источник

2 ответа

Решение

Поскольку ваша грамматика невероятно неоднозначна, у ANTLR возникла проблема с созданием парсера. Очевидно ANTLR 3.3+ дросселирует его, но ANTLR 3.2 (с меньшим временем, чем 3.3+) выдает следующую ошибку:

ошибка (10): внутренняя ошибка: org.antlr.tool.Grammar.createLookaheadDFA(Grammar.java:1279): не удалось даже сделать k=1 для решения 1; причина: истекло время ожидания (>1000 мс)

Для простого парсера выражений вам действительно не следует использовать backtrack=true,

Помимо того, что ваша грамматика неоднозначна, большая часть вашего встроенного кода содержит ошибки.

Давайте посмотрим на ваш formula правило:

formula returns [Term term]
: a=expression EOF { $term = $a; }
;

Кроме того, тип возврата правила должен быть явно определен. a в { $term = a; } должен иметь $ перед ней:

formula returns [Term term]
: a=expression EOF { $term = $a; }
;

но потом $a относится ко всей "вещи" expression возвращается. Затем вы должны "сказать" ANTLR, что вы хотите Term этот expression создает. Это можно сделать так:

formula returns [Term term]
: a=expression EOF { $term = $a.term; }
;
expression returns [Term term]
: a=boolExpr { $term = $a.term; }
;

Похоже, вы преобразовали некоторую грамматику LR в грамматику ANTLR (обратите внимание, что, хотя ANTLR заканчивается LR, ANTLR 3.x является генератором синтаксического анализатора LL), и без промежуточного тестирования вы надеялись, что все это должно работать: к сожалению, это не делает. В этом слишком много неправильного, чтобы создать небольшой рабочий пример, основанный на вашей грамматике: я бы посмотрел на существующий синтаксический анализатор выражений, основанный на грамматике ANTLR, и попробовал бы снова. Посмотрите на эти вопросы и ответы:

Источник

Прежде всего, спасибо за это подробное объяснение. Это действительно помогает:-) ... Все "$a.term" и тому подобное разбираются сейчас, и генерируется код, который фактически компилируется (я просто взломал этот код, желая исправить проблемы с этим, как только что-то генерируется вообще). Я просто прокомментировал множество вариантов и продолжал генерировать, пока не пришел к одному фрагменту, который, кажется, нарушает сборку. Я включил эту функцию возврата, потому что некоторые ошибки, которые я получил, предложили включить ее.

РЕДАКТИРОВАТЬ: Ну, я на самом деле реорганизовал грамматику, чтобы избавиться от ошибок без активации возврата, и теперь мой парсер генерируется очень быстро, и, кажется, хорошо справляется со своей задачей. Вот текущая версия:

grammar SecurityRulesNew;

options {
language = Java;
    output=AST;
ASTLabelType=CommonTree;
/*  backtrack = true;*/
}

tokens {
POS;
NEG;
CALL;
}

@header {package de.cware.cweb.services.evaluator.parser;

import de.cware.cweb.services.evaluator.terms.*;}
@lexer::header{package de.cware.cweb.services.evaluator.parser;}

formula returns [Term term]
: a=expression EOF { $term = $a.term; }
;
expression returns [Term term]
: a=boolExpr { $term = $a.term; }
;
boolExpr returns [Term term]
: a=sumExpr (AND! b=boolExpr | OR! c=boolExpr | LT! d=boolExpr | LTEQ! e=boolExpr | GT! f=boolExpr | GTEQ! g=boolExpr | EQ! h=boolExpr | NOTEQ! i=boolExpr)? {
        if(b != null) {
            $term = new AndTerm($a.term, $b.term);
        } else if(c != null) {
            $term = new OrTerm($a.term, $c.term);
        } else if(d != null) {
            $term = new LessThanTerm($a.term, $d.term);
        } else if(e != null) {
            $term = new LessThanOrEqualTerm($a.term, $e.term);
        } else if(f != null) {
            $term = new GreaterThanTerm($a.term, $f.term);
        } else if(g != null) {
            $term = new GreaterThanOrEqualTerm($a.term, $g.term);
        } else if(h != null) {
            $term = new EqualsTerm($a.term, $h.term);
        } else if(i != null) {
            $term = new NotEqualsTerm($a.term, $i.term);
        } else {
            $term = $a.term;
        }
    }
;
sumExpr returns [Term term]
: a=productExpr (SUB! b=sumExpr | ADD! c=sumExpr)?
    {
        if(b != null) {
            $term = new SubTerm($a.term, $b.term);
        } else if(c != null) {
            $term = new AddTerm($a.term, $c.term);
        } else {
            $term = $a.term;
        }
    }
;
productExpr returns [Term term]
: a=expExpr (DIV! b=productExpr | MULT! c=productExpr)?
    {
        if(b != null) {
            $term = new DivTerm($a.term, $b.term);
        } else if(c != null) {
            $term = new MultTerm($a.term, $c.term);
        } else {
            $term = $a.term;
        }
    }
;
expExpr returns [Term term]
: a=unaryOperation (EXP! b=expExpr)?
    {
        if(b != null) {
            $term = new ExpTerm($a.term, $b.term);
        } else {
            $term = $a.term;
        }
    }
;
unaryOperation returns [Term term]
: a=operand { $term = $a.term; }
| NOT! a=operand { $term = new NotTerm($a.term); }
| SUB! a=operand { $term = new NegateTerm($a.term); }
| LPAREN! e=expression RPAREN! { $term = $e.term; }
;
operand returns [Term term]
: l=literal { $term = $l.term; }
| v=VARIABLE { $term = new VariableTerm($v.text); }
| f=functionExpr { $term = $f.term; }
;
functionExpr returns [Term term]
: f=FUNCNAME LPAREN! (a=arguments)? RPAREN! { $term = new CallFunctionTerm($f.text, $a.terms); }
;
arguments returns [List<Term> terms]
: a=expression (COMMA b=arguments)?
    { 
        $terms = new ArrayList<Term>(); 
        $terms.add($a.term);
        if(b != null) {
            $terms.addAll($b.terms);
        }
    }
;
literal returns [Term term]
: n=NUMBER { $term = new NumberLiteral(Double.valueOf($n.text)); }
| s=STRING { $term = new StringLiteral($s.text.substring(1, s.getText().length() - 1)); }
| TRUE! { $term = new TrueLiteral(); }
| FALSE! { $term = new FalseLiteral(); }
;

STRING
:
'\"'
    ( options {greedy=false;}
    : ESCAPE_SEQUENCE
    | ~'\\'
    )*
'\"'
|
'\''
    ( options {greedy=false;}
    : ESCAPE_SEQUENCE
    | ~'\\'
    )*
'\''
;
WHITESPACE
: (' ' | '\n' | '\t' | '\r')+ {skip();};
TRUE
: ('t'|'T')('r'|'R')('u'|'U')('e'|'E')
;
FALSE
: ('f'|'F')('a'|'A')('l'|'L')('s'|'S')('e'|'E')
;

NOTEQ   : '!=';
LTEQ    : '<=';
GTEQ    : '>=';
AND     : '&&';
OR      : '||';
NOT     : '!';
EQ      : '=';
LT      : '<';
GT      : '>';

EXP     : '^';
MULT    : '*';
DIV     : '/';
ADD     : '+';
SUB     : '-';

LPAREN  : '(';
RPAREN  : ')';
COMMA   : ',';
PERCENT : '%';

VARIABLE
: '[' ~('[' | ']')+ ']'
;
FUNCNAME
: (LETTER)+
;
NUMBER
: (DIGIT)+ ('.' (DIGIT)+)?
;

fragment
LETTER 
: ('a'..'z') | ('A'..'Z')
;
fragment
DIGIT
: ('0'..'9')
;
fragment
ESCAPE_SEQUENCE
: '\\' 't'
| '\\' 'n'
| '\\' '\"'
| '\\' '\''
| '\\' '\\'
;

Еще раз спасибо за ваше объяснение... это привело меня на правильный путь:-)

Крис

Источник
Другие вопросы по тегам