Получение построения дерева с помощью ANTLR - PullRequest
Новая
       6

Получение построения дерева с помощью ANTLR

0 голосов
/ 11 июня 2010

Как спросили и ответили в Удаление левой рекурсии в ANTLR , я могу удалить левую рекурсию 

E -> E + T|T
T -> T * F|F
F -> INT | ( E )

После удаления левой рекурсии я получаю следующий 

E -> TE'
E' -> null | + TE'
T -> FT'
T' -> null | * FT'

Тогда как сделать конструкцию дерева с измененной грамматикой? При вводе 1 + 2 я хочу иметь дерево 

^('+' ^(INT 1) ^(INT 2))
. Или похожий. 
grammar T;

options {
    output=AST;
    language=Python;
    ASTLabelType=CommonTree;
}

start : e -> e
   ;
e  : t ep -> ???
   ;
ep : 
   | '+' t ep -> ???
   ;
t : f tp -> ???
  ;
tp : 
  | '*' f tp -> ???
  ;
f : INT 
  | '(' e ')' -> e
  ;

INT :   '0'..'9'+ ;
WS: (' '|'\n'|'\r')+ {$channel=HIDDEN;} ;

1 Ответ

2 голосов
/ 12 июня 2010

Немного мнения: хотя иногда можно перейти от грамматики LR к грамматике LL, как вы уже сделали, результат не так идиоматичен и может показаться странным способом определения вашей грамматики для кого-то, знакомого сLL грамматики.

Например, рассмотрим следующую выдержку из приведенного выше: 

tp : 
  | '*' f tp -> ???

В приведенном выше тексте принимается *, за которым следует f, в ПЕРВОМ наборе которого будет INT(, начало само по себе как правильное рекурсивное.Таким образом, вы никогда не увидите начало искомого выражения с корнем в *, что значительно усложнит построение дерева, которое вам нужно.

создайте этот AST в ANTLR, вы хотите иметь как операнды, так и оператор. 

add:
   INT '+'^ INT;

Символ каретки ^ делает + корнем дерева, а два INT становятсяего дети.

Пример Барта K , связанный с , является замечательным примером того, как я ожидал бы увидеть, как это делается с грамматикой LL ... и этомасштабируется для поддержки операторов различного приоритета.

...