compiler-construction - 关于 SLR、LALR 的语法和一些挑战

Question

我知道：

如果一种语言可以由 LL(1) 语法生成，则称该语言为 LL(1)。可以证明 LL(1) 文法是

not ambiguous and
not left-recursive.

但我遇到了一个问题。

为什么语法

S-> aBDb

B -> 拉姆达

D-> dD | 拉姆达

为什么这个语法不是 LL(1) 也不是 SLR 也不是 LALR？谁能形容我？

Answer 1

这个文法确实是 LL(1)。这是解析表：

      a     b     d       $
S     aBDb
B           eps   eps
D           eps   dD

它也是单反（1）。以下是 FOLLOW 集：

S: $
B: d, b
D: b

以下是配置集：

 S' -> .S$ 
 S  -> .aBDb  ($)

 S' -> S.$

 S  -> a.BDb   ($)
 B  -> .       (b, d)

 S  -> aB.Db   ($)
 D  -> .       (b)
 D  -> .dD     (b)

 D  -> d.D     (b)
 D  -> .dD     (b)
 D  -> .       (b)

 D  -> dD.     (b)

没有移位/归约或归约/归约冲突，所以这个语法是 SLR(1)。因此，它也是 LALR(1)。

希望这可以帮助！