文法G[S]：S→AB，B→BB|B不是LR（0)文法。（)

有文法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

1. 文法G＝({A,B,S},{a,b,c},P,S), 其中P 为： S→Ac|aB A→ab B→bc 写出L(G[S])的全部元素。 2. 文法G[S]为： S→Ac|aB A→ab B→bc 该文法是否为二义的？为什么？ 3. 考虑下面上下文无关文法： S→SS*|SS+|a (1)表明通过此文法如何生成串aa+a*，并为该串构造语法树。 (2)G[S]的语言是什么？ 4. 给出生成下述语言的二型文法： (1) {anbn | n ＞=0 } (2) { ambn | m≥n ≥0 } (3) {uawb | u,w ∈{a,b}*∧|u|=|w| } (4) { anbm | n≥2m ≥0 } (5) { anbm | n ≥ 0, m ≥ 0,3n≥m≥2n } (6) {wwR|w∈{a,b}*，wR 表示w的逆} (7) {uvwvR|u,v,w∈{a,b}+=1 } 5. 给出生成下述语言的三型文法： (1) {an | n ＞=0 } (2) { anbm | n,m＞=1 } (3) {anbmck | n,m,k＞=0 }

A.2

B.3

C.4

D.5

指出下列文法所属的文法类，并给出所表示的语言。 (1)S→aA｜bB A→A0｜ε B→B00｜ε (2)S→aSb｜c (3)S→a｜aE E→AS (4)S→ASPQ｜abQ QP→PQ bP→bb bQ→bc cQ→cc

设有下列文法Gi： (1)G1：A→AaB｜bB B→Dc D→Ad (2)G2：S→aABbcd｜ε A→ASd｜ε B→PC｜SAh｜ε C→Sf｜Cg｜ε ①计算上述文法中的每个非终结符的FIRST和FOLLOW集合。 ②证明上述文法是否为LL(1)文法？说明为什么？ ③若不是LL(1)文法能否改写？构造LL(1)分析表。

判断下列文法是否是LL(1)文法。若是LL(1)文法为其构造LL(1)分析表。 (1)S→aABC｜ε A→a｜bbD B→a｜ε C→b ｜ε D→c｜s (2)A→BCc｜eDB B→ε｜bCD C→DaB｜ca D→｜dD (3)S→(X｜E]｜F) X→E)｜F] E→A F→A A→e

A.LL(1)文法

B.二义性文法

C.算符优先文法

D.SLR(1)文法

已知文法G(S)为：

S→aAcBd

A→B|A+B

B→S*|(

(1)求出文法的FIRSTVT集和LASTVT集；

(2)该文法是算符优先文法吗？如果是则构造该文法的算符优先表。

给定文法G(S)： S→0S｜1A｜0 A→1｜1S｜0B B→1A｜0B 下列符号串是L(G)中的元素的是_______。

A．10100010011011

B．0101001110010010

C．1101010011110111

D．1010011101101010