使语法 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

这是明确且非递归的。由于不是递归的，所以没有左递归可以去掉。