考虑下面上下文无关文法： S→SS*|SS＋|a 为串aa＋a*构造语法树。

在如下上下文无关文法G中：stmt-sequence→stmt;stmt-sequence|stmtstmt→s哪些是终结符号？()

Astmt-sequence

Bstmt

Cs

D;

设有文法G(S)：S→SS*｜SS＋｜a (1)G(S)的语言L(G(S))是什么？ (2)下列字符串哪些是该文法的句子？ $1：aa＋aa*＋a $2：aa＋aaa*＋＋ $3：aS＋a* (3)对属于该文法的句子$i，画出其分析树。

A.S→abS｜ε

B.S→aSbS｜bSaS｜ε

C.S→aSb｜ab｜ε

D.S→SS｜aSb｜bSa｜ε

给出下面语言的上下文无关文法描述。 (1)L1＝{anbnci｜n≥1，i≥0} (2)L2＝{abna｜n≥0} (3)L3＝{aibncn｜n≥1，i≥0} (4)L4＝{aibj｜j≥i≥1} (5)L5＝{a2nb3n｜n≥0} (6)L6＝{anbnambm｜n，m≥0} (7)L7＝{a2n+1b2ma2p+1｜n≥0，P≥0，m≥1} (8)L8＝{1n0m1m0n｜n，m≥0} (9)L9＝{ωaωr｜属于{0，a)*，ωr表示ω的逆序，如ω＝00aa0，则ωr＝0aa00} (10)L10＝{anbm｜2n＞m≥n≥1}

2型文法也称为()。

A短语文法

B上下文无关文法

C右线性文法

D左性性文法

若文法G定义的语言是无限集，则文法必然是()。

A上下文无关文法

B正规文法

C二义性文法

D递归文法

有文法G(S)： S→Aχ｜By A→y｜Ay B→χy 下面与文法G(S)表示相同语言的正规式是_______。

A．y*χ｜χy｜y

B．y*χ｜χ｜χy

C．yyχ*χ｜χy｜y

D．yy*χ｜χy｜yy

描述词法分析的有效工具是()。

A正规式

B上下文无关文法

C语言的语义规则

D有限自动机

设有文法G(S)： S→AB｜AS A→aA｜a B→b 文法G(S)与下面正规式等价的是_______。

A．aa*bb*

B．aa*b

C．(ab)*

D．a(ab)*b

有文法G(S)： S→dA A→a｜aB B→aB｜a｜b｜bC C→bC｜b 下面与文法G(S)表示相同语言的正规式是_______。

A．daa*bb*

B．daa*b*

C．daa*

D．daa*b

设有文法G(E)＝({E)，{i}，{E→E＋E｜E*E｜(E)｜i)，E)，该文法是________。 ①算符文法 ②上下文无关文法 ③3型文法 ④二义性文法可选项有：

A．①②

B．①②④

C．②④

D．①②③④