ANTLR, проблема с грамматикой выражения - PullRequest
Новая
       6

ANTLR, проблема с грамматикой выражения

3 голосов
/ 11 марта 2011

Я недавно начал использовать 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: При добавлении нескольких конструкций ^ и -> ^(TOKEN ...) для чистки дерева я столкнулся со следующей раздражающей ситуацией (из-за primaryPrime, который связан с левый факторинг): 

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

    Это превращает array[index] в 

    array
ARRAY_EXPR
    index

    пока я очень хочу 

    ARRAY_EXPR
    array
    index

    Как лучше всего это решить? Я на правильном пути, или я должен пойти другим путем?

1 Ответ

4 голосов
/ 11 марта 2011

A1

Нет, возврат не требуется (пока). Но если вам нужен некоторый возврат, рекомендуется не использовать backtrack=true сразу, а использовать предикат до правил, которые действительно требуют возврата. Используя backtrack=true, вы включаете возврат по всем вашим правилам, в то время как, вероятно, только один или два требуют возврата. Но если ваш язык будет относительно небольшим, backtrack=true проще, чем смешивать предикаты вручную, и, вероятно, не окажет большого влияния на производительность. Но если вы можете избежать их, сделайте это.

У вас есть пара правил синтаксического анализа, которые соответствуют пустым строкам, которые вызывают проблемы. Обычно лучше позволить правилам соответствовать чему-либо и сделать правило необязательным. Так что вместо: 

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

сделать 

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

вместо.

Кроме того, в случае зарезервированных ключевых слов, таких как true, false и т. Д., Не смешивайте их в правилах вашего синтаксического анализатора: всегда явно определяйте их в начале ваших правил лексера. Правила Lexer сопоставляются, начиная сверху вниз, поэтому их безопаснее всего определить (по крайней мере) перед правилами, подобными 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:

enter image description here

Как вы можете видеть, запустив следующий тестовый класс: 

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);
  }
}
...