Опция LOOKAHEAD синтаксического анализатора Javacc, Java
Я недавно начал играть вокруг с грамматическими анализаторами с помощью javacc, и одно из полей является опциями один... У меня есть код как следующее:
options
{
LOOKAHEAD=1;
}
PARSER_BEGIN(Calculator)
public class Calculator
{
...
}
PARSER_END(Calculator)
Что точно это означает опцию LOOKAHEAD? Спасибо
3 ответа
См. http://en.wikipedia.org/wiki/Lookahead#Lookahead_in_parsing
Обычно синтаксический анализатор смотрит только на следующую лексему, чтобы определить, какое правило производства применить. Однако в некоторых случаях этого недостаточно, чтобы сделать выбор. Например, если даны два правила производства:
p0: foo -> identifier "=" expr
p1: bar -> identifier "(" arglist ")"
Если следующая лексема имеет тип identifier, то синтаксический анализатор не может определить, следует ли ему использовать производство foo или bar. JavaCC выдаст ошибку, сообщив, что ему нужно использовать большее опережение. Изменение на 2 означает, что синтаксическому анализатору разрешено просматривать следующие две лексемы, что в данном случае достаточно для выбора между производствами.
Как указал Стив, это есть в документации по javacc: https://javacc.org/tutorials/lookahead
JavaCC создает парсеры с рекурсивным спуском. Этот тип синтаксического анализатора работает, просматривая следующий символ, чтобы решить, какое правило выбрать. По умолчанию он смотрит только на следующий символ (lookahead=1). Но вы можете настроить парсер так, чтобы он смотрел не только на следующий, но и на N следующих символов. Если вы установите значение lookahead равным 2, сгенерированный синтаксический анализатор будет просматривать следующие два символа, чтобы решить, какое правило выбрать. Таким образом, вы можете сделать свою грамматику более естественной, но ценой снижения производительности. Чем больше опережение, тем больше синтаксическому анализатору придется делать.
Если вы установите общее опережение на большее число, ваш синтаксический анализатор будет работать медленнее для всех входных данных (для нетривиальных грамматик). Вы можете использовать lookahead локально, если хотите, чтобы парсер по умолчанию имел lookahead=1 и использовал больший lookahead только в определенных ситуациях.
http://www.engr.mun.ca/~theo/JavaCC-FAQ/javacc-faq-moz.htm#tth_sEc4. 5
Например, парсер с lookahead=1 не может решить, какое из правил (1 или 2) взять, а с lookahead=2 может:
void rule0() : {} {
<ID> rule1()
| <ID> rule2()
}
Вы можете изменить определение грамматики, чтобы получить тот же результат, но использовать lookahead=1:
void rule0() : {} {
<ID> ( rule1() | rule2() )
}
Значение LOOKAHEAD указывает генерируемому синтаксическому анализатору, сколько необработанных (т.е. будущих) лексем использовать для решения, в какое состояние переходить. В языке с жесткими ограничениями необходим только один маркер lookahead. Чем более двусмысленным является язык, тем больше маркеров будущего необходимо для определения того, в какое состояние следует перейти.
Я думаю, это рассматривается в учебнике по javacc(1).