Опция парсера Javacc LOOKAHEAD, Java

Question

Я недавно начал играть с грамматическими анализаторами, используя javacc, и одно из полей это опции ... У меня есть код, подобный следующему:

options
{
  LOOKAHEAD=1;
}
PARSER_BEGIN(Calculator)

public class Calculator
{
 ...
}
PARSER_END(Calculator)

Что именно означает опция LOOKAHEAD? Спасибо

Answer 1

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() )
}

Answer 2

См. 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

Answer 3

Значение LOOKAHEAD сообщает сгенерированному синтаксическому анализатору, сколько необработанных (то есть будущих) токенов использовать, чтобы решить, в какое состояние перейти. В жестко ограниченном языке необходим только один жетон предпросмотра. Чем более двусмысленен язык, тем больше лексем необходимо для определения перехода между состояниями.

Я думаю, что это описано в руководстве по javacc (1).

Answer 4

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

Эта конфигурация необходима для разрешения конфликтов выбора, поскольку javacc не поддерживает возврат.

, поэтому важно написать грамматику, которая подходит для LOOKAHED = 1, то есть, глядя на один токен, определяется поток в дереве синтаксиса. это способ написания грамматики.

Например:

Поскольку JavaCC является синтаксическим анализатором LR, левый токен производственного правила повторяется, поэтому в дереве синтаксиса это будет разветвленным. Конфликт выбора возникает, на какой ветви выбрать, как показано ниже,

void PhoneNumber() : {} {​

(LocalNumber() | CountryNumber()) <EOF> ​

}​

void LocalNumber() : {} { ​

AreaCode() "-" <FOUR_DIGITS>  ​

}​

void CountryNumber() : {} {  ​

AreaCode() "-" <THREE_DIGIT> "-" <FOUR_DIGITS>   ​

}​

void AreaCode() : {} {   ​

 <THREE_DIGIT> ​

}

обратите внимание, что CountryNumber и LocalNumber начинаются с терминала <THREE_DIGIT>, который является конфликтом выбора,

Это можно переписать с помощью подхода, называемого левым факторингом.

void PhoneNumber() : {} {​

AreaCode() "-" (LocalNumber() | CountryNumber()) <EOF> ​

}​

void LocalNumber() : {} { ​

<FOUR_DIGITS>  ​

}​

void CountryNumber() : {} {  ​

<THREE_DIGIT> "-" <FOUR_DIGITS>   ​

}​

void AreaCode() : {} {   ​

 <THREE_DIGIT> ​

}

Для случая, когда это невозможно сделать, используется Lookahead

Lookahead имеет пять типов, как,

• Несколько токенов LOOKAHEAD
• Синтаксический LOOKAHEAD
• Сочетание нескольких токенов и синтаксического LOOKAHEAD
• Семантический LOOKAHEAD
• Вложенный Lookahead

Несколько токенов LOOKAHEAD

Это можно использовать с целым числом, переданным в методе LOOKAHEAD (k). Это можно сделать с помощью

• Местный LOOKAHEAD

  void PhoneNumber (): {} { ( LOOKAHEAD (3) LocalNumber () | CountryNumber () ) }

• Global LOOKAHEAD

  Опции: {LOOKAHEAD = 3; }

Синтаксический LOOKAHEAD

Спецификация Syntactic lookahead использует синтаксическую конструкцию в качестве решателя выбора.

При указании синтаксического просмотра без использования нескольких токенов на самом деле вы указываете синтаксический просмотр с бесконечным множеством токенов.

Например: LOOKAHEAD (2147483647, LocalNumber ())

void PhoneNumber() : {} {​

(​
LOOKAHEAD(("A"|"B")+ AreaCode() "-" <FOUR_DIGITS>) LocalNumber() ​

| CountryNumber()​

) <EOF> ​

}

Сочетание нескольких токенов и синтаксического LOOKAHEAD

Таким образом, мы можем смотреть ограниченное количество токенов, если будет сделан синтаксический просмотр, удовлетворяющий заданному выбору.

void PhoneNumber() : {} {​

(​
LOOKAHEAD(10, ("A"|"B")+ AreaCode() "-" <FOUR_DIGITS>) LocalNumber() ​

| CountryNumber()​

) <EOF> ​

}

1072 *

Семантический LOOKAHEAD

Семантическое рассмотрение предполагает встраивание кода Java в грамматику в точке выбора.

Если код Java возвращает true, выбрано текущее расширение.

void PhoneNumber() : {} {​

(​
LOOKAHEAD({getToken(1).image.equals("123")}) ​
KeysvilleNumber() ​

| FarmvilleNumber()​

) <EOF> ​

}

1083 *

Вложенный Lookahead

Вложенный lookahead возникает, когда одна директива lookahead перекрывает другую. В JavaCC вложенный упреждения игнорируется, но не вложенный семантический просмотр.

void Start() : {} {​

(​
LOOKAHEAD(Fullname()) Fullname() ​

| Douglas()​

) <EOF> ​

}​

void Fullname() : {} {​

( LOOKAHEAD(Douglas() Munro()) ​

 Douglas()​

| Douglas() Albert()​

)​

Munro() ​

}​

void Douglas() : {} { "Douglas" } ​

void Albert() : {} { "Albert" }}​

void Munro() : {} { "Munro" }}

Все примеры взяты из удивительной книги Создание парсеров с помощью JavaCC Тома Коупленда

Надеюсь, это полезно, спасибо.