V→0Z|0
（1） 请写出此文法描述的只含有４个符号的全部句子。 （2） G[Z]产生的语言是什么？
（3） 该文法在Chomsky文法分类中属于几型文法？
2. 已知文法G[S]: S→TB
T→Ba|? B→Db|eT|? D→d|?
解答：
计算文法的FIRST和FOLLOW集合：(4分)
FIRST(M) = { a，b，e，d， } FIRST(T) = { a，b，e，d， } FIRST(B) = {b，e，d， } FIRST(D) = {d，}
FOLLOW (M) = {#} FOLLOW (T) = { a，b，e，d，#} FOLLOW (B) = {a，# } FOLLOW (D) = { b} 3. 已知文法G(E)： E→T|E＋T|E-T
T→F|T *F|T/F F→(E)|i
求符号串T*i+(F-i)的短语、素短语、直接短语和句柄。 句型T+T*F+I的短语为i、T*F、第一个T、T+T*F+i; 简单短语为i、T*F、第一个T;句柄为第一个T。 4. 考虑简单赋值语句的文法G[S]： S ? id:= E
E ? E + E E ? E * E E ? id
(1) 试构造识别该文法所有规范句型活前缀的有穷自动机。 (2) 判断该文法是否为LR(0)文法（必须说明理由）。
请求出G[S]每个非终结符的FIRST和FOLLOW集合，并判断该文法是否是LL(1)的，请说明理由。
解: (1)
I0: S’ ? .S S ? .id = E I1: S’ ? S. I2: S ? id. = E I3: S ? id = .E E ? .E + E E ? .E * E E ? .id
I1SI0idI2=I3idEI5idI7id+EI9+E+*I4I6I8I7 I4: S ? id = E. E ? E. + E E ? E. * E I5: E ? id. I6: E ? E + .E （2）由于I4、 I8、 I9均有移进—归约冲突， E ? .E + E
E ? .E * E 故该文法不是LR(0)文法。 E ? .id I7: E ? E * E E ? .E + E E ? .E * E E ? .id I8: E ? E + E E ? E.+ E E ? E. * E I9: E ? E * E. E ? E .+ E
E ? E .* E
5. 构造正规式 ba(b︱a)*
bab相应的DFA。
6. 已知文法G[E]: E→Tc|aF T→ab F→bc 证明该文法是二义性文法。
7. 写一个文法，使其语言是偶数的集合，且每个偶数不以0开头。
8. 已知文法G[S]: S→1A
A→0A|1B|1 请求出G[S]所对应的正规式。
B→1A
9. 已知文法G[S]： S?（L|a
L?S,L|)
（1） 构造文法G[S]的预测分析表。
（2） 若输入串为“（ａ，）”，请给出语法分析过程。
10. 已知文法G[Z]: Z→HZ|a
H→ZH|b
判断该文法是否为LR(0)、SLR(1)、LR(1)、LALR(1)文法？并说明理由。
11. 给出表达式-a+b*(-c+d)的三元式和四元式两种中间代码表示形式。
12. 已知文法G[S]: S→1S0|10 求该文法G[S]所描述的语言L。
13. 已知文法G[E]: E→Tc|aF T→ab F→bc 证明该文法是二义性文法。
14. 已知表达式为-a+b*(c+d/e)，求该表达式的三元式、四元式和树形表示式。
请按要求完成以下内容。 15. 已知文法G[A]: A→AaB|B
（1）改写文法以消除左递归；（2分） B→BbC|C
,
（2）并求改写后的文法G[A]每个非终结符的C→eD|D
FIRST集和FOLLOW集；（4分） D→(A)|i
,
（3）判断G[A]是否是LL(1)的。(4分)
16. 已知文法G[S]: S→aA|bB
A→cA|d
B→cB|d
求该文法的LR(0)项目及分析表。
17. 已知文法G[S]：S→a︱*︱(T) T →T ，S︱S
判断该文法消除左递归即改写后的G[S]是否为LL（1）文法。
18. 8. 文法G[S]： S ?#G#
G ? R|aPbR
R ? d=P|aPbRcR
P ?d|P+d
请按要求完成以下内容。
(1)求文法G[S]每个非终结符的FIRSTVT集 和LASTVT集；（4分）
(2)构造该文法的算符优先关系表。(6分)
,
19. 已知文法G[S]：S→L=R|R 构造该文法的算符优先关系表
L→*R|i R→L
20. 写一个正规文法，使其语言是奇数的集合，且每个奇数不以0开头。
21. 判断文法S→S(S)S |ε是二义性的吗?说明理由。
22. 构造正规式(a|b)*(ab|ba)(a|b)*相应的最小的DFA。
23. 已知文法G[S]：S→aAbDe|d, A→BSD|e, B→SAc|cD|?,D→Se|?求:1、每个VN的FIRST
集和FOLLOW集；2、判定该文法是否为LL(1)文法。( 15分)
24. 已知文法G[S]：S→bASB|bA, A→dSa|1, B→cAd|c判断该文法是否为LR(0)、SLR(1)、
LR(1)、LALR(1)文法？(10分)