parsing - 对将模棱两可的语法转换为明确的语法感到困惑

Question

给出了一个模棱两可的语法，我被要求重写语法以使其明确。事实上，我不知道为什么给定的语法是模棱两可的，更不用说将它重写为一个明确的语法了。

给定的语法是 S -> SS | 一个 | b ，我有四个选择：

A: S -> Sa | Sb | epsilon  

B: S -> SS’
   S’-> a | b  

C: S -> S | S’
   S’-> a | b 

D: S -> Sa | Sb. 

对于每个选择，我已经知道 D 不正确，因为它根本不生成字符串，C 不正确，因为它只匹配字符串 'a' 和 'b'。

但是，我认为答案是 A 而正确答案是 BI 认为 B 是错误的，因为它只是一遍又一遍地生成 S，而 B 无法处理空字符串。

1. 为什么给定的语法不明确？</p>

2. 为什么A不正确而B正确？

Answer 1

原始语法是模棱两可的，因为对于任何至少三个字母的字符串都可能有多个最右边（或最左边）的推导。例如：

S -> SS -> SSS -> SSa -> Saa -> aaa
S -> SS -> Sa  -> SSa -> Saa -> aaa

粗略地说，第一个对应于 parsea(aa)而第二个对应于 parse (aa)a。

没有一个替代方案是正确的。A错误地匹配 εB而不匹配任何东西（如D）。B例如，如果是，

S  -> SS' | S'
S' -> a | b

这将是正确的。（这个语法是左结合的。）