Может ли последующий конфликт существовать в грамматике?

Question

Я знаю, что конфликты First / First и First / Follow существуют в грамматике, которая делает грамматику "не LL (1)".Мне просто интересно, существует ли в грамматике конфликт «следуй / следуй».

Answer 1

Это, возможно, более простой пример

S → A a 
A → B | C
B → ε
C → ε

Здесь, поскольку a находится в FOLLOW из B и C, в (A, a) будет конфликт междуA → B и A → C.Обратите внимание, что других конфликтов нет.

Answer 2

Да, это возможно, но для этого требуется необычная конфигурация.Рассмотрим следующую грамматику, которая была дополнена новым начальным символом:

S '→ S $

S → tT

T → A |B

A → ε

B → ε

Теперь давайте представим, что мы пытаемся заполнить нашу таблицу анализа LL (1), которая показана здесь:

          $          t
     +----------+----------+
 S'  |          | S' -> S$ |
     +----------+----------+
 S   |          | S -> tT  |
     +----------+----------+
 T   | T -> A   |          |
     | T -> B   |          |
     +----------+----------+
 A   | A -> e   |          |
     +----------+----------+
 B   | B -> e   |          |
     +----------+----------+

Обратите внимание, что в записи есть два элемента для (T, $).И это имеет смысл: если у нас есть активный нетерминал T и мы видим $, мы знаем, что нам нужно выбрать производство, которое будет расширяться до пустой строки.И у нас есть два разных способа сделать это: мы могли бы использовать T → A или T → B, с конечной целью расширения каждого из этих нетерминалов до пустой строки.Это проблема - мы не можем предсказать, какой путь выбрать.

Теперь, что это за конфликт?Это не может быть конфликт FIRST / FIRST, потому что FIRST (A) = {ε} и FIRST (B) = {ε}, поэтому ни A, ни B не имеют терминалов в своем первом наборе.Это не может быть конфликт FIRST / FOLLOW по той же причине.

Это означает, что это редкий конфликт FOLLOW / FOLLOW - мы знаем, что выберем производство на основе того, что находится в наборах FOLLOW Aи B, и все же они абсолютно идентичны друг другу, и поэтому анализатор не может однозначно выбрать, что делать дальше.