делая грамматику ll (1) и однозначно

Question

У меня есть CFG в форме

PB := PB | R | R
R := s

Я попытался сделать это ll (1), удалив левую рекурсию, в результате чего

 PB := R PB' | R PB'
 PB' := PB'| ϵ
 R := s

Однако, я считаю,удаление левой рекурсии делает грамматику двусмысленной.

Как это можно исправить?

Answer 1

Оригинальная грамматика неоднозначна.Устранение левой рекурсии не создает и не устраняет неоднозначность.

Неопределенности:

PB := PB

Это произведение ничего не делает, но его можно применять любое количество раз

PB := R
PB := R

Эти два произведения идентичны, поэтому везде, где можно применить одно, вместо этого можно использовать другое.

Когда вы удаляете бессмысленные произведения, у вас остается

PB := R
R := s

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