《编译原理与技术》课程习题集
西南科技大学成人、网络教育学院 版权所有
习题
【说明】：本课程《编译原理与技术》（编号为03002）共有简答题,计算题1,计算题2,问答与作图题,计算题3,计算题4,计算题5等多种试题类型，其中，本习题集中有[简答题]等试题类型未进入。
一、计算题1 1. 已知NFA M
1、将NFA M确定化为DFA M； 2、求DFA M的正规式； 2. 已知正规式：a+b(b|ab)*
1、求等价的NFA； 2、求等价的DFA； 3. 已知正规式((ε｜a)b*)*
1、求等价的NFA； 2、将NFA确定化
3、若所求DFA可最小化，则求其最小化DFA；若无，说明原因。 4. 写出字母表? = {a, b}上语言L = {w | w中a的个数是偶数}的正规式，并画出
接受该语言的最简DFA。
5. 有文法 G[S] ：
第 1 页 共 26 页
S → aC | aA A → aC C → bC |b
1、求等价的NFA； 2、求等价的DFA；
二、计算题2 6. 将文法G[S]：
S→aA A→AS|Bc B→Bi|i
1、消除左递归；
2、证明该文法消除左递归后是LL（1）文法？ 3、给出相应的LL(1)分析表。
7. 已知文法G（S）：
E→aTb|iE|i T→TE|E
1、提公因子和消除左递归；
2、计算每个非终结符的FIRST和FOLLOW； 3、证明该文法是否为LL（1）文法？
8. 已知文法G（S）为：
E → E or T | T T → T and F | F
F → not F | ( E ) | true | false 1、对文法消除左递归；
第 2 页 共 26 页
2、计算消除左递归后的文法的每个非终结符的FIRST和FOLLOW； 3、判断消除左递归后的文法是否是LL(1) 文法。
9. 已知文法G（D）为：
D→int L| real L L→L,id | id
1、提公因子和消除左递归；
2、计算每个非终结符的FIRST和FOLLOW； 3、证明该文法是否为LL（1）文法？
10. 已给文法 G[S]：
S → SaP | Sf | P P → qbP | q
1、对文法提公因子和消除左递归，得到其LL(１)文法； 2、对LL(１)文法计算每个非终结符的FIRST和FOLLOW； 3、给出LL(１)文法的 LL(１)分析表。
三、问答与作图题 11. 已知文法G(S)为: S?S+D︱D*S︱D D?D，H︱H H?a︱(S)
1、给出句型“(D，H＋a)”最左推导和最右推导； 2、给出句型“D*D+D”的语法树；
3、给出句型“(D，H＋a)”的短语和素短语； 12. 已知文法G(S)为:
E→T︱E＋T T→F︱T * F
第 3 页 共 26 页
F→(E) ︱i
1、给出该文法的类型及名称；
2、给出句型“(F * F＋i)”最左推导和最右推导； 3、给出句型“(F* F＋i)”的短语和句柄、素短语； 4、给出句型“i * i＋i”的语法树； 13. 已知文法G[S]：
S ? aSbS︱bSaS︱ε
1、给出句型“abbaS”的最左推导和最右推导。 2、给出句型“abbaS”的短语和素短语和句柄。 3、判断此文法是否具有二义性，并证明。
14. 已知文法G[E]：
E ?E+E︱E*E︱(E)︱F F?i
1、给出该文法的类型及名称；
2、给出句型“F+(F*F)”的短语和素短语和句柄。 3、判断此文法是否具有二义性，并证明。
15. 已知文法G[S]：
S?if B S else S︱if B S︱ａ B?b
1、给出该文法的类型及名称；
2、证明句型“if b a else if b a”是该文法的句型，并求其短语、素短语和句柄；
3、给出句型”if B if B S else S”的语法树。
四、计算题3
第 4 页 共 26 页
16. 已知文法G(S)：
S?aAcBd A?bA|e B?f
1、求出该文法的FIRSTVT集和LASTVT集；
2、求出该文法的算符优先表。
17. 已知文法G(S)：
S → var D : T D → D , i | i T → real | char
1、求出该文法的FIRSTVT集和LASTVT集； 2、求出该文法的算符优先表。
18. 已知文法G(S)：
S → a | ∧ |(T) T → T , S | S
1、求出该文法的FIRSTVT集和LASTVT集； 2、求出该文法的算符优先表。
19. 已知文法G(E)：
E → E+T|T T → T*F|F F →i
1、 求出该文法的FIRSTVT集和LASTVT集； 2、求出该文法的算符优先表。
20. 对文法G(S)：
S → a | b | (T) T → T，S | S
1、构造各非终结符的FIRSTVT和LASTVT集合；
第 5 页 共 26 页