编译原理中文法二义性问题

Question

G: S→SS | (S) | ()
上面文法的二义性怎么证明
为什么改成下面的就没有二义性了
G: S→TS | T
T→(S) | ()

Answer 1

二义性文法

【定义】 若文法中存在这样的句型，它具有两棵不同的语法树，则称该文法是二义性文法。

二义性文法会引起歧义，应尽量避免之！

E E

E + E E * E

i E * E E + E i

i i i i

都可以表示i+i*i

所以G(E)：E -> E+E | E*E | (E) | i ;文法具有二义性。

文法二义性的消除：

【方法1】不改变文法的原有规则,加进一些非形式规定。

加进运算符的优先顺序和结合规则对G(E)，规定*优于+，*和+服从左结合

【方法2】构造一个等价的无二义性文法，将排除 二义性的规则合并到文法中

G(E) -> G´(E) : E -> E+T | T T -> T*F | F F -> (E) | i ;