LL (1) конфликт анализа

Question

Я пишу парсер LL (1) для очень простой грамматики.И все же я обнаружил конфликты при попытке создать таблицу синтаксического анализа.

Я удивлен, поскольку грамматика кажется простой.Я не знаю, есть ли у меня проблема с анализатором или с моим пониманием синтаксического анализа LL (1).Возможно, в конце грамматика не LL (1).

Грамматика:

1: S         -> begin list
2: list      -> id    listPrime
3: listPrime -> id    listPrime
4:            | ε

Мой код сталкивается с двумя конфликтами, оба для получения listPrime, один с терминаломсимвол id и один с EOF.В обоих случаях правило 3 вступает в противоречие с правилом 4.

Мои вычисленные наборы FIRST и FOLLOW:

first:
   { S: Set { 'begin' },
     list: Set { 'id' },
     listPrime: Set { 'id', 'eps' } },

follow:
   { S: Set { 'EOF' },
     list: Set { 'EOF', 'id' },
     listPrime: Set { 'EOF', 'id' } } }

Answer 1

Грамматика - LL (1). Ваши наборы FOLLOW вычислены неправильно, что легко проверить: нет деривации, в которой за list или listPrime следовал бы токен, отличный от EOF.