资源描述：
《编译原理题库.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第一章§什么是编译器？§编译程序的结构分为几个阶段，各阶段的任务是什么？§遍、编译前端及编译后端的含义？§编译程序的生成方式有哪些？第二章§1.写一文法，使其语言是偶正整数的集合。§要求：（1）允许0打头（2） 不允许0打头解：（1）允许0开头的偶正整数集合的文法E→NT
2、DT→NT
3、DN→D
4、1
5、3
6、5
7、7
8、9D→0
9、2
10、4
11、6
12、8（2）不允许0开头的偶正整数集合的文法E→NT
13、DT→FT
14、GN→D
15、1
16、3
17、5
18、7
19、9D→2
20、4
21、6
22、8F→N
23、0G→D
24、02.证明下述文法G［〈表达式〉］是二义的。〈表达式〉∷=a
25、(〈表达
26、式〉)
27、〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+
28、-
29、*
30、/解：可为句子a+a*a构造两个不同的最右推导:最右推导1〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉aÞ〈表达式〉*aÞ〈表达式〉〈运算符〉〈表达式〉*aÞ〈表达式〉〈运算符〉a*aÞ〈表达式〉+a*aÞa+a*a最右推导2〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉Þ〈表达式〉〈运算符〉〈表达式〉〈运算符〉aÞ〈表达式〉〈运算符〉〈表达式〉*aÞ〈表达式〉〈运算符〉a*aÞ〈表达式〉+a*
31、aÞa+a*a3.给出生成下述语言的上下文无关文法：（1）{anbnambm
32、n，m>=0}（2）{1n0m1m0n
33、n，m>=0}解：（1）{anbnambm
34、n，m>=0}S→AAA→aAb
35、ε(2){1n0m1m0n
36、n，m>=0}S→1S0
37、AA→0A1
38、ε第三章1、构造一个DFA，它接收∑={a,b}上所有满足下述条件的字符串：字符串中的每个a都有至少一个b直接跟在其右边。解：已知∑={a,b}，根据题意得出相应的的正规式为：(b*abb*)*根据正规式画出相应的DFAM，如下图所示用子集法将其确定化XY(b*ab
39、b*)*XYb*abb*1eeXYb123456bbaeeeeeeIIaIb{X,1,2,3,Y}{4}{2,3}{4}—{5,6,1,2,3,Y}{2,3}{4}{2,3}{5,6,1,2,3,Y}{4}{6,1,2,3,Y}{6,1,2,3,Y}{4}{6,1,2,3,Y}IIaIb0121—3212314414由DFA得状态图用最小化方法化简得：{0}，{1}，{2}，{3,4}，按顺序重新命名DFAM’10243aaaabbbbb0312aaabbb第四章练习1：文法G[V]：V→N
40、N[E]E→V
41、V+EN→i是否
42、为LL(1)文法，如不是，如何将其改造成LL(1)文法。解：LL(1)文法的基本条件是不含左递归和回溯（公共左因子），而G[V]中含有回溯，所以先消除回溯得到文法G’[V]：G’[V]：V→NV’V’→ε
43、[E]E→VE’E’→ε
44、+EN→i由LL(1)文法的充要条件可证G’[V]是LL(1)文法练习2：有文法G[s]:S→BAA→BS
45、dB→aA
46、bS
47、c(1)证明文法G是LL(1)文法。(2)构造LL(1)分析表。(3)写出句子adccd的分析过程解：(1)一个LL(1)文法的充要条件是：对每一个非终结符A的任何两个不同
48、产生式A→α
49、β，有下面的条件成立：①FIRST(α)∩FIRST(β)=Φ;②若β*Þε,则有FIRST(α)∩FOLLOW(A)=Φ对于文法G[s]:S→BAA→BS
50、dB→aA
51、bS
52、c其FIRST集如下：FIRST(B)={a,b,c};FIRST(A)={a,b,c,d};FIRST(S)={a,b,c}。其FOLLOW集如下：首先，FOLLOW(S)={#};对S→BA有：FIRST(A){ε}加入FOLLOW(B),即FOLLOW(B)={a,b,c,d};对A→BS有：FIRST(S){ε}加入FOLLO
53、W(B),即FOLLOW(B)={a,b,c,d};对B→aA有：FOLLOW(B)加入FOLLOW(A),即FOLLOW(A)={a,b,c,d};对B→bS有：FOLLOW(B)加入FOLLOW(S),即FOLLOW(S)={#,a,b,c,d};由A→BS
54、d得：FIRST(BS)∩FIRST(d)={a,b,c}∩{d}=Φ;由B→aA
55、bS
56、c得：FIRST(aA)∩FIRST(bS)∩FIRST(c)={a}∩{b}∩{c}=Φ。由于文法G[s]不存在形如β→ε的产生式，故无需求解形如FIRST(α)∩FOLLO
57、W(A)的值。也即，文法G[S]是一个LL(1)文法。(2)由G[s]:S→BAA→BS
58、dB→aA
59、bS
60、c的FIRST(B)={a,b,c};FOLLOW(B)={a,b,c,d};FIRST(A)={a,b,c,d};FOLLOW(A)={a,b,c,d};FIRST(S)={a,b
