Делая грамматику 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

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