ANTLR: Разница между возвратом и просмотром вперед?

Я относительный новичок в ANTLR. У меня очень простая грамматика:

start   :
('A' 'B' 'C' '1'
|'A' 'B' 'C' '2' 
|'A' 'B' 'C' '3'
)
;

Я думаю, что уже понял основы концепции просмотра вперед и возврата (которая работает с синтаксическими предикатами). Так что эта грамматика работает с k=4 или с backtrack=true. Но в чем точная разница и главный вопрос, когда что использовать? Я пытался найти ответ в Интернете, но не удалось.


antlr grammar ll backtracking lookahead
person Veilchen4ever    schedule 16.11.2012    source источник

Ответы (2)


arrow_upward
3
arrow_downward

Ваша грамматика работает в ANTLR v3 без каких-либо опций.

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

start: recursive_rule ';'
     | recursive_rule ':'
     ;

recursive_rule : (ID)* '%'
               ;

Эта грамматика ниже такая же, но выражена через рекурсию. ANTLR не может построить для него DFA (правда, не знаю почему), поэтому нужно включить откат:

start options {backtrack=true;} : recursive_rule ';'
                                | recursive_rule ':'
                                ;

recursive_rule : ID recursive_rule
               |'%'
               ;

Параметр k используется для повышения производительности парсера. Я не знаю другой причины для ограничения LL(*) только LL(k).

person Andy    schedule 16.11.2012
comment
Спасибо. Я попробую это с рекурсивным правилом, чтобы лучше понять его. Но теперь у меня есть идея. Спасибо. - person Veilchen4ever; 16.11.2012
comment
Не могли бы вы объяснить второй рекурсивный пример? Потому что я думаю, что это не правило левой рекурсии, и ANTLR должен с этим справиться? - person xi.lin; 10.02.2014

arrow_upward
3
arrow_downward

Я нашел теоретическое описание своего вопроса в книге «The definitve Antlr Reference», что также было важно для моего понимания. Может быть, кто-то из тех, кто задает себе подобный вопрос, тоже поможет этому фрагменту книги.

Отрывок из книги Полное руководство по Antlr

Страница 262

person Veilchen4ever    schedule 19.11.2012