compiler-construction - 如何留下上下文无关语法？

Question

据我了解，在以下情况下，构建自上而下的解析器需要左分解。但是很难理解如何做到这一点？有人可以在这里帮助我吗？谢谢。

s = a | b
b = c d
c = (e | f) g
e = a | h

Answer 1

每个非终结符在这里只被引用一次，所以我们可以将整个语法放在一个表达式中：

s = a | ((a | h | f) g d)

所以我们有两个基本的变体，终端 a 可选地后跟 g 然后 d，或者 h 或 f 之一总是后跟 g 然后 d。

所以我们有

s =  b' | c'
b' = a | a g d
c' = (h | f) g d

或者，将通用 gd 序列拉入自己的生产中

s =  b' | c'
b' = a | a e'
c' = (h | f) e'
e' = g d

然后，我们可以通过引入 E（空）选项将 a 作为 b' 中的公共起始符号：

s =  b'' | c'
b'' = a (e' | E)
c' = (h | f) e'
e' = g d

语法现在是明确的。