Анализ рекурсивного спуска — от LL(1) вверх
-
02-07-2019 - |
Вопрос
Следующая простая грамматика «выражения калькулятора» (BNF) может быть легко разобрана с помощью тривиального синтаксического анализатора рекурсивного спуска, который является прогнозирующим LL(1):
<expr> := <term> + <term>
| <term> - <term>
| <term>
<term> := <factor> * <factor>
<factor> / <factor>
<factor>
<factor> := <number>
| <id>
| ( <expr> )
<number> := \d+
<id> := [a-zA-Z_]\w+
Потому что всегда достаточно увидеть следующий токен, чтобы знать, какое правило выбрать.Однако предположим, что я добавляю следующее правило:
<command> := <expr>
| <id> = <expr>
Для взаимодействия с калькулятором в командной строке, с переменными, вот так:
calc> 5+5
=> 10
calc> x = 8
calc> 6 * x + 1
=> 49
Правда ли, что я не могу использовать простой предсказательный анализатор LL(1) для анализа <command>
правила ?Я пытался написать для него парсер, но, похоже, мне нужно знать больше токенов вперед.Является ли решением использование обратного отслеживания, или я могу просто реализовать LL (2) и всегда смотреть на два токена вперед?
Как генераторы парсеров RD решают эту проблему (например, ANTLR)?
Решение
Проблема с
<command> := <expr>
| <id> = <expr>
это когда ты "видишь" <id>
вы не можете сказать, начало ли это задания (второе правило) или это "<factor>
".Вы узнаете об этом только тогда, когда прочитаете следующий токен.
AFAIK ANTLR - это LL(*) (и, если я не ошибаюсь, он также может генерировать анализаторы крысиных пакетов), поэтому он, вероятно, обработает эту грамматику, рассматривая два токена одновременно.
Если вы можете поиграть с грамматикой, я бы посоветовал либо добавить ключевое слово для задания (например, let x = 8
) :
<command> := <expr>
| "let" <id> "=" <expr>
или используйте =
для обозначения оценки:
<command> := "=" <expr>
| <id> "=" <expr>
Другие советы
Я думаю, что есть два способа решить эту проблему с помощью парсера рекурсивного спуска:либо с помощью (большего) просмотра вперед, либо путем возврата.
Смотреть вперед
command() {
if (currentToken() == id && lookaheadToken() == '=') {
return assignment();
} else {
return expr();
}
}
Возврат
command() {
savedLocation = scanLocation();
if (accept( id )) {
identifier = acceptedTokenValue();
if (!accept( '=' )) {
setScanLocation( savedLocation );
return expr();
}
return new assignment( identifier, expr() );
} else {
return expr();
}
}
Проблема в том, что грамматика:
<command> := <expr>
| <id> = <expr>
не является взаимно-рекурсивной процедурой.Для достойного рекурсивного парсера вам необходимо определить нерекурсивный эквивалент.
В посте rdentato показано, как это исправить, при условии, что вы умеете играть с грамматикой.В этом Powerpoint проблема описана более подробно и показано, как ее исправить:http://www.google.com/url?sa=t&source=web&ct=res&cd=7&url=http%3A%2F%2Fxml.cs.nccu.edu.tw%2Fcourses%2Fcompiler%2Fcp2006%2Fslides%2Flec3-Parsing% 26TopDownParsing.ppt&ei=-YLaSPrWGaPwhAK5ydCqBQ&usg=AFQjCNGAFrODJxoxkgJEwDMQ8A8594vn0Q&sig2=nlYKQVfakmqy_57137XzrQ
АНТЛР 3 использует парсер «LL(*)» в отличие от парсера LL(k), поэтому он будет смотреть вперед, пока не достигнет конца ввода, если это необходимо, без возврата назад, используя специально оптимизированный детерминированный конечный автомат (DFA). .