如何将因子留给无上下文语法？

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(空)选项将其作为b'中的公共起始符号:

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

语法现在是明确的.