资源描述:
《编译原理考试题2009编译》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、一第一章1.编译程序绝大多数时间花在(B)上。A出错处理B词法分析C目标代码生成D表格管理2.编译方式与解释方式的根本区别在于_是否有目标代码生成______.3.编译程序是对_____A____A汇编语言的翻译B高级语言程序的解释执行C机器语言的执行D高级语言的翻译第二章1.令S={a,b},S上的正规式和相应的正规集的例子有:正规式正规集a{a}a½b{a,b}ab{ab}(a½b)(a½b){aa,ab,ba,bb}a*{e,a,a,……任意个a的串}(a½b)*{e,a,b,aa,ab……所有由a和b组成的串}(a½b)*(aa½bb)(a½b)*{S*上所有含有两个相继的a或两个相继
2、的b组成的串}2.设S={a,b,c},则aa*bb*cc*是S上的…..正规式,它所表示的正规集为L={ambncl
3、m,n,l>=1}1.DFAM接受的字集为_______。A以0开头的二进制数组成的集合B以0结尾的二进制数组成的集合C含奇数个0的二进制数组成的集合D含偶数个0的二进制数组成的集合构造下列正规式相应的NFA(1)(a
4、b)*abb14(1)(a
5、b)*a(a
6、b)(2)(a
7、b)*(aa
8、bb)(a
9、b)*随堂练习已知一状态转换图如图所示,且假定I=ε_{0}={0},试求从状态0出发经过一条有向边b而能到达的状态集J和ε_CLOSURE(J)。例2.8正规表达式(a∣b)
10、*(aa∣bb)(a∣b)*的NFAM如图2–14所示,试将其确定化为DFAM'。图2–14例2.8的NFAM表2.4例2.8的转换表表2.5例2.8的状态转换矩阵14图2–15例2.8未化简的DFAM′第三章随堂练习(一)设字母表å={a,b},试设计一个文法,描述语言L={a2n,b2n
11、n≥1}分析:n=1L={aa,bb}n=2L={aaaa,bbbb}n=3L={aaaaaa,bbbbbb}L={aa,bb,aaaa,bbbb,aaaaaa,bbbbbb,…}文法G=(VT,VN,S,ξ)VT={a,b}VN={S,A,B}方法一:ξ:Sàaa
12、aaA
13、bb
14、bbBAàaa
15、aaAB
16、àbb
17、bbB方法二:ξ:SàA
18、BAàaa
19、aAaBàbb
20、bBb注意:ξ:Sàaa
21、bb
22、Saa
23、Sbb是否可行?随堂练习(二)给出下面语言相应的文法(1)L1={ambn
24、m,n≥1}G(S):SàABAàa
25、AaBàb
26、bB14(1)L2={anbnci
27、n≥1,i≥0}G(S):SàABAàab
28、aAbBàξ
29、cB(2)L3={anbncmdm
30、n≥1,m≥1}G(S):SàABAàab
31、aAbBàcd
32、cBd(3)L4={a2n+1
33、n≥0}Sàa
34、aAAàaS或者Sàa
35、aSa随堂练习1.文法G:SàxSx
36、y所识别的语言是______.AxyxB(xyx)*Cxnyxn(n≥0
37、)Dx*yx*2.文法G[N]=({b},{N,B},N,{N→b│bB,B→bN}),该文法所描述的语言是__________。A.L(G[N])={bi│i≥0}B.L(G[N])={b2i│i≥0}C.L(G[N])={b2i+1│i≥0}D.L(G[N])={b2i+1│i≥1}随堂练习1.设有文法G[T]:TàT*F
38、FFàF↑P
39、PPà(T)
40、i直接短语:P,T*F短语:T*P↑(T*F),P↑(T*F),P,(T*F),T*F句柄:P求T*P(T*F)句型中的所有短语、直接短语、句柄。2.设有文法G[S]:Sà(AS)
41、(b)Aà(SaA)
42、(a)求出符号串(A((SaA)(b)
43、))的短语、直接短语、句柄。1.设有文法G[A]:AàAc
44、Aad
45、bd
46、e,消除直接左递归后文法G[A]改写为?2.下述文法G[S]是否含有左递归?G[S]:SàQc
47、cQàRb
48、bRàSa
49、a例3.71.设有文法G[E]:EàTE’E’à+TE’
50、εTàFT’T’à*FT’
51、εFà(E)
52、iFIRST(T’)=__________,FOLLOW(F)=___________.A{(,i}B{*,ε}C{*,+,),#}D{+,),#}2.对下面文法G[S]计算每个非终结符的FIRST集和FOLLOW集。14Sàa
53、!
54、(T)TàST’T’à,ST’
55、ε文法G[S] S
56、→uBDz B→Bv
57、w D→EF E→y
58、ε F→x
59、ε(1)计算文法的FIRST集合和FOLLOW集合 (2)构造这个文法的LL(1)分析表。例1将文法G[S]:SàaAbAàde
60、d改写为LL(1)文法。该文法没有左递归,利用提取公共左因子的方法对其进行改写:G[S]:SàaAbAàdA’A’àe
61、ε判断下