困惑于将有歧义的语法转换为无歧义的语法

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，而正确答案是B.I认为B是错误的，因为它只是一遍又一遍地生成S，而B不能处理空字符串。

Answer 1

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

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

粗略地说，第一个对应于解析 a(aa)，而第二个对应于解析 (aa)a.

None 的选项是正确的。 A 错误地匹配了 ε 而 B 不匹配任何东西（比如 D）。例如，如果 B 是

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

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

Confused at transferring an ambiguous grammar to an unambiguous one