SLR(1)或LR(1)解析

Question

如果我们找到一个类型的乘积，我们会发现如下(A)

一个→α

α这里可以是ε吗？

如下面的示例所示：

P_ aPa _ bPb _ε

如果α可能是ε，则它不是LR(1)

Answer 1

是的，α可以是ε。α表示任意字符串，因为ε是字符串，所以它是可能的α。

因此，语法不是LR(1)，因此也不是SLR(1) (因为所有SLR(1)语法也都是LR(1))。

要看到这一点，我们可以构造LR(1)配置集：

(1)  P' -> .P     ($)
     P  -> .aPa   ($)
     P  -> .bPb   ($)
     P  -> .      ($)

(2)  P  -> a.Pa   ($)
     P  -> .aPa   (a)
     P  -> .bPb   (a)
     P  -> .      (a)

在这一点上，我们可以停止，因为有一个shift/reduce描述:考虑到终端a，我们无法判断是移动a还是减少P→ε。

使用一些更高级的数学，您可以证明这种语言没有LR(1)语法(所有偶数长度回文的语言)。这是因为具有LR(1)语法的语言正是确定性上下文无关语言，而所有偶数长度回文集都不是确定性上下文无关语言。

希望这能有所帮助！