文法G=({E),{＋,*,(,),a},P,E),其中P由下列产生式组成E－>E＋E|E*E|(E)|a。它生成由a,＋,*,(,)组成的

Question

文法G＝({E),{+,*,(,),a},P,E)，其中P由下列产生式组成E-＞E+E|E*E|(E)|a。它生成由a,+,*,(,)组成的算术表达式，该文法在乔姆斯基分层中属于(16)型文法，其对应的自动机是(17)，如产生句子a*a+a，它的派生树是(18)，且最左派生由(19)种，该文法是(20)。

A．0

B．1

C．2

D．3

Answer 1

正确答案：C
解析：乔姆斯基定义了4种文法类型，他们之间的差别是按文法G=(V(下标)v,V(下标)T,P,S)中P所允许的产生式的形式加以区分的。如果P中的每个产生式形式如A-＞P，其中A为非终结符，P为9，则称此文法为2型文法或上下文无关文法。对应的语言称为上下文无关语言，对用的自动机称为下推自动机。题中的文法属于1型对应的下推自动机。产生句子a*a+a的派生树有两棵，如下：这是三叉树，最左派生有两种，他们是E=＞E+E=＞E*E+E＝＞a*E+E=＞a*a+E=＞a*a+aE＝＞E*E＝＞a*E=＞a*E+E=＞a*a+E＝＞a*a+a因此，该文法是二义的。