将语法固定到LR(0)

Question

问题：

给定以下语法，将其修正为LR(O)语法：

S -> S' $
S'-> aS'b | T
T -> cT | c

checking --我已经尝试了很久了，使用自动工具检查我的固定语法，但没有成功。我们的教授喜欢在考试中问这样的问题，而不给我们一个方法来解决这个问题(除了反复尝试)。有什么方法可以用来回答这类问题吗？有人能证明这个方法可以应用到这个例子中吗？

Answer 1

我不知道自动程序，但基本思想是推迟决定。也就是说，如果在解析中的特定状态下，可以同时执行shift和reduction操作，那么可以找到一种推迟还原的方法。

在LR(0)解析器中，您可以根据刚才移动的令牌做出决定，而不是根据将要转移的令牌作出决定。所以在某种程度上，你需要把决定移到作品的结尾。

例如，语言的LR(0)语法是：

S -> S' $.
S' -> U | a S' b.
U -> a c T.
T -> b | c T.

(非常感谢@templatetypedef检查原始答案并识别该漏洞。更正的语法稍微复杂一些，可能存在简化，但原则是相同的。)

在最初的语法中，在项目集(包括T -> c .和T -> c . T )中，shift和reduce都是可能的: shift、c和before b。通过将b转移到T的生产中，我们将决定推迟到转移之后:在转移b之后，需要减少；在c之后，减少是不可能的。