Почему бизон не конвертирует грамматику автоматически?

Question

Я изучаю лексер и парсер, поэтому я читаю эту классическую книгу: flex & bison (Джон Левайн, издатель: O'Reilly Media). Приведен пример, который не может быть проанализирован бизоном:

phrase : cart_animal AND CART | work_animal AND PLOW
cart_animal-> HORSE | GOAT
work_animal -> HORSE | OX

Я очень хорошо понимаю, почему не смог. Действительно, для этого требуется ДВА символов предвкушения.

Но, с простой модификацией, он может быть проанализирован:

phrase : cart_animal CART | work_animal PLOW
cart_animal-> HORSE AND | GOAT AND
work_animal -> HORSE AND | OX AND

Интересно, почему бизон не может автоматически переводить грамматику в таких простых случаях, как это?

Answer 1

Поскольку такие простые случаи довольно искусственны, а в случае реальных примеров это трудно или невозможно.

Для ясности, если у вас есть LR(k) грамматика с k>1 и вы знаете значение k, существует механическое преобразование, с помощью которого вы можете сделать эквивалент LR(1) грамматика, и, кроме того, вы можете с помощью некоторого жонглирования исправить действия сокращения так, чтобы они имели одинаковый эффект (по крайней мере, до тех пор, пока они не содержат побочных эффектов). Я не знаю ни одного генератора синтаксического анализатора, который бы это делал, отчасти потому, что правильно преобразовать действия сокращения будет непросто, а отчасти потому, что результирующая грамматика LR (1) обычно довольно велика, даже для небольших значений k.

Но, как я упоминал выше, вам нужно знать значение k, чтобы выполнить это преобразование, и оказывается, что не существует алгоритма, который может взять грамматику и сказать вам, является ли она LR(k). Поэтому все, что вы можете сделать, это попробовать последовательно увеличивать значения k до тех пор, пока не найдете подходящее, или не решите отказаться.