问题
单项选择题
文法G=(E，+，*，(，)，a，P，E)，其中P由下列产生式组成E-＞E+E|E*E| (E)|a。它生成由a，+，*，(，)组成的算术表达式，该文法在乔姆斯基分层中属于 (33) 型文法，其对应的自动机是 (34) ，如产生句子a*a+a，它的派生树是 (35) ，且最左派生由 (36) 种，该文法是 (37) 。
37（）
A．非二义性
B．二义性
C．单一性
D．多义性
答案
参考答案：B
解析：
乔姆斯基定义了4种文法类型，他们之间的差别是按文法G= (VN，VT，P，S)的P所允许的产生式的形式加以区分的。如果P中的每个产生式形式如A-＞P，其中A为非终结符，P为P*，则称此文法为2型文法或上下文无关文法。对应的语言称为上下文无关语言，对应的自动机称为下推自动机。题中的文法属于1型对应的下推自动机。
[*]
产生句子a*a+a的派生树有两棵，如图3所示：
这是三叉树，最左派生有两种，它们是
E= ＞E+E= ＞E*E+E= ＞a*E+E= ＞a*a+E= ＞a*a+a
E= ＞E*E= ＞a*E= ＞a*E+E= ＞a*a+E= ＞a*a+a
因此，该文法是二义的。