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