资源描述：
《编译原理期末范围.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、编译原理期末范围试卷一一、填空题（每空3分，共36分）1.设X={ad,c}、Y={b,a}，则XY={adb,ada,cb,ca}。2.上下文无关文法G[B]=S→0
2、1
3、S0
4、S1生成所有无符号二进制整数。3.设αβδ是文法G[S]的一个句型，如果且A=>β，则称β是句型αβδ相对于A→β的直接短语（简单短语）。4.设正规式x和y所表示的正规集分别为{ab}、{b,c}，则正规式(x
5、y)y所表示的正规集为{abb,abc,bb,bc,cb,cc}。5.正规式a{a
6、b}*定义与正规文法G[S]={S→aA
7、a,A→aA
8、bA
9、a
10、b}相同的语
11、言。6.如果规范句型aAAbBccD的句柄为bB，则该句型的可归前缀为aAAbB。7.表达式a*(b+c*(d+e))的逆波兰记号为abcde+*+*。8.LR(0)文法G的产生式A→cA对应的归约项目为A->cA.，待约项目为a->c.A。9.如果算符优先文法G中存在产生式A→…Bb…且a∈LASTVT(B)，则有a>b。10.设∑={a,b}，则正规式a{a
12、b}*所表示的正规集为∑上所有以a为首的串的集合。二、简答题（1）写一上下文无关文法，使得该文法生成的语言是所有能被5整除的整数。（12分）（2）已知文法G[E]={E→T
13、E+T
14、E-T
15、,T→F
16、T*F
17、T/F,F→(E)
18、i}，写出句子(i+i)/(i*i-i)的规范推导过程（12分）。三、把图二表示的DFA最小化（20分）。四、根据以下文法G’[S’]及其LR(0)分析表完成对输入串acccd#的LR(0)分析过程。要求具体写出状态栈、符号栈、输入串的变化过程及每一步的Action和Goto值（20分）。LR(0)分析表文法G’[S’]：状态ActionGotoabcd#EAB0S2S311acc2S4S1063S5S1174S4S1085S5S1196r1r1r1r1r17r2r2r2r2r28r3r3r3r3r39r5r5
19、r5r5r510r4r4r4r4r411r6r6r6r6r6(0)S’→E(1)E→aA(2)E→bB(3)A→cA(4)A→d(5)B→cB(6)B→d答案：一、简答题（1）S→aA(4分)A→aA
20、a(3分)B→bB
21、b(3分)或S→AB(4分)A→aA
22、a(3分)B→bB
23、b(3分)（2）所有以a为首的串的正规式为a(a
24、b)*（4分）改写的正规文法为：G=({S,A},{a,b},{S→aA,A→ε,A→aA,A→bA},S)（6分）二、共20分画出转换过程表（每行2分，共10分）DFSA图（6分）化简后：三、各非终结符的FIRST集合如下
25、：(10分，每个2分)FIRST(E)=｛(,i｝FIRST(E′)=｛+,ε｝FIRST(T)=｛(,i｝FIRST(T′)=｛*,ε｝FIRST(F)=｛(,i｝各非终结符的FOLLOW集合为：(10分，每个2分)FOLLOW(E)=｛),$｝FOLLOW(E′)=｛)，$｝FOLLOW(T)=｛＋，)，$｝FOLLOW(T′)=｛＋,)，$}FOLLOW(F)=｛*,＋，),$}四、共20分(1)语法树：(6分)直接短语：P和T*F(3分)句柄：P(2分)首先对非终结符求FIRSTVT集与LASTVT集过程（3分，每个0.5分），确定关系（6
26、分，每个2分）试卷二一、填空题（每空2分，共22分）1.词法分析的任务是扫描源程序，根据语言的词法规则，分解和识别出单词，构造符号表、常数表以及将源程序转换成中间语言程序。2.语言学家乔姆斯基(Chomsky)把文法分成以下四种类型，其中正规文法能够被有限自动机识别。3.令Σ={a,b}，表示{Σ上所有以a为首的串}的正规式为a(a
27、b)*。4.LL(1)文法的是自上而下的分析方法，其中第二个L表示最左推导。5.最右推导的逆过程最左规约。6.算符优先分析法只考虑终结符之间的优先关系。7.若U是文法的识别符号，则FOLLOW(U)一定包含$。8.若要
28、消除U→Ux
29、y的左递归，则应将文法改写为U→yU’和U’→xU’
30、ε两个产生式。9.将正规文法A→xA
31、y改写成的正规式为A=x*y。 简单优先分析方法中可归约串必须为句柄二、简答题（10分）1．构造生成{anbm
32、n,m>=1}语言的文法。（5分）S→aA(1分)A→aA
33、B(2分)B→bB
34、b(2分)2．描述文法G[S]:S®abS
35、bS
36、ε表示的语言（5分）三、综合题1.(16分)文法G[E]:E→E+T
37、TT→T*F
38、FF→(E)
39、i(1)写出句子i1*i2+i3的语法树的最左推导、最右推导(2)画出该句型的语法树(3)写出该句子的短语、
40、直接短语、句柄答：最左推导：E→E+T→T+T→T*F+T→F*F+T→i1*F+T→i1*i2+T→i1*i2+F→i1
