文档介绍：该【《编译原理》00本科班A卷(答案) 】是由【莫比乌斯】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【《编译原理》00本科班A卷(答案) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。——————————————装————————————————订————————————————线————————————————————————————————2003-2004学年第二学期韶关学院计算机系《编译原理》期末考试试卷(A卷答案)年级:00专业:计算机科学技术班级:学号:姓名:题号一二三四五总分签名得分注:1、共120分钟,总分100分。2、此试卷适用专业:计算机本科一得分阅卷教师判断题:(每小题1分,共5分)*每个文法都能改写为LL(1)文。(×)2、符号表是上下文语义的合法性检查的依据之一。(√)3、函数backpatch(p,t)的功能是指将字符p后退t格。(×)4、算符优先关系表不一定存在对应的优先函。(√)5、“把所有语言中的符号都组织在一张符号表中”是用得最多的一种对符号表的总体组织方法中。(×)二得分阅卷教师填空题(每空1分,共20分)1、编译过程一般分为:词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成六个阶段。2、词法分析的任务是:从左到右一个字符一个字符地读入源程序,对构成源程序的字符流进行扫描,从而识别出一个个单词。3、语法分析最常用的两类方法是自顶向下分析法和自底向上分析法。4、一个上下文无关文法包含非终结符集、终结符集、产生式集和开始符号四个组成部分是。5、在有穷自动机中,两类状态s和t等价的条件是:一致性条件和蔓延性条件。6、程序设计语言的语义分为:静态语义和动态语义两类。7、乔姆斯把文法分成 0型文法(短语文法)、1型文法(上下文有关文法)、2型文法(上下文无关文法)和3型文法(正规文法)四种类型。三得分阅卷教师三、名词解释(每题2分,共10分)1、句柄:令S是文法G的开始符,如果有STaAd且ATb则称b是句型abd相对于非终结符A的直接短语,其中最左直接短语为句柄。2、规范推导:如果在推导的任何一步aTb,其中a,b是句型,都是对a中的最右非终结符进行替换,则称这种推导为最右推导,也称为规范推导。*3、语法分析:是编译程序的第二个阶段,其任务是在词法分析的基础上将单词序列分解成各类语法短语,如“程序”、“语句”、“表达式”等。4、素短语:至少包含一个终结符,且不包含其它短语的短语。5、句型:设G[S]是一文法,如果符号串x是从识别号推导出来的,即有STx,则称x是文法G[S]的句型。四得分阅卷教师*四、简述题(每题5分,共25分)1、已知文法G:E→T|E+T|E-T,T→F|T*F|T/F,F→(E)|i试给出下述表达式的推导及语法树。①i+i*i②i*(i+i)解:①推导过程如下:ETE+TTE+T*FTE+T*iTE+F*iTE+i*ITT+i*ITF+i*iTi+i*i②推导过程如下:ETTTT*FTT*(E)TT*(E+T)TT*(E+F)TT*(E+i)TT*(T+i)TT*(F+i)TT*(i+i)TF*(i+i)Ti*(i+i)①和②的语法树如下:EE+TT*FTFFiii①的语法树FTFTETET*F(E)Fiii②的语法树+——————————————装————————————————订————————————————线————————————————————————————————2、给出语言{anbnambm|n,m≥0}的上下无关文法。解:上下无关文法如下:G[S]:S?AB,A?aAb|ab|e,B?aBb|ab|e3、写出表达式(a+b*c)/(a+b)-d的逆波兰表示及三元式序列。解:逆波兰:abc*+ab+/d-三元式:①(*b,c)②(+a,①)③(+a,b)④(/②,③)⑤(-④,d)4、文法G[N]为:N→D|NDD→0|1|2|3|4|5|6|7|8|9G[N]的语言是什么?解:G[N]的语言是:{(0|1|2|3|4|5|6|7|8|9)n|n≥1}即为非负整数。5、构造正规式b((ab)*|bb)*ab的NFA。解:a,beebbebae4235106a五得分阅卷教师五、综合题(每题10分,共40分)1、已知文法G[S]:S→MH|aH→LSo|eK→dML|eL→eHfM→K|bLM判断G是否是LL(1)文法,如果是,构造LL(1)分析表。解:(1)求出能推出e的非结符为:S、H、K、M(2)计算FIRST集FIRST(S)=FIRST(MH)U{a}={a,b,d,e,e}FIRST(H)=FIRST(L)U{e}={e,e}FIRST(K)={d,e}FIRST(L)={e}FIRST(M)=FIRST(K)U{b}={b,d,e}(3)计算FOLLOW集FOLLOW(S)={o,#}FOLLOW(H)=FOLLOW(S)U{f}={f,o,#}FOLLOW(K)=FOLLOW(M)={e,o,#}FOLLOW(L)=FIRST(S)U{o}UFOLLOW(K)UFIRST(M)UFOLLOW(M)={a,b,d,e,o,#}FOLLOW(M)=FIRST(H)UFOLLOW(S)UFIRST(L)={e,o,#}(4)计算SELECT集SELECT(S?MH)=FIRST(MH)UFOLLOW(S)={b,d,e,o,e,#}SELECT(S?a)={a}SELECT(H?LSo)=FIRST(L)={e}SELECT(H?e)=FOLLOW(H)U{e}={f,o,#,e}SELECT(K?dML)={d}SELECT(K?e)=FOLLOW(K)U{e}={e,o,#,e}SELECT(L?eHf)={e}SELECT(M?K)=FIRST(K)UFOLLOW(M)={d,e,o,#,e}SELECT(M?bLM)={b}(5)判断G是否是LL(1)文法由于相同左部的产生式的SELECT集合的集为空,所以是LL(1)文法。——————————————装————————————————订————————————————线————————————————————————————————(6)构造LL(1)分析表abdefo#S?a?MH?MH?MH?MH?MHH?LSo?e?e?eK?dML?e?e?eL?eHfM?bLM?K?K?K?K2、采用语法制导翻译思想,表达式E的“值”的描述如下:产生式语义动作(0)S′→E{}(1)E→E1+E2{:=+}(2)E→E1*E2{:=*}(3)E→(E1){:=}(4)E→n{:=}如采用LR分析方法,给出表达式(5*4+8)*2的语法树并在各结点注明语义值VAL。解:表达式(5*4+8)*2的语法树如下:E(val=56)(E(val=28)+)(val=20)E+E(val=8)254S′(val=28)E*E(val=2)T(val=5)E*E(val=4)83、已知文法G[S]为:S→a|ù|(T)T→T,S|S(1)计算G[S]的FIRSTVT和LASTVT。(2)构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。(3)给出输入串(a,a)#的算符优先分析过程。解:(1)给G[S]加入规则S'→#S#,并求得FIRSTVT和LASTVT如下: FIRSTVT(S)={a,ù,(}FIRSTVT(T)={,,a,ù,(}LASTVT(S)={a,ù,)}LASTVT(T)={,,a,ù,)}(2)G[S]的算符优先关系如下:(=)、#=#、(<FIRSTVT(T)、,<FIRSTVT(S)、#<FIRSTVT(S)、LASTVT(T)>)、LASTVT(T)>,、LASTVT(T)>#从而构造优先关系表如下:——————————————装————————————————订————————————————线————————————————————————————————aù(),#a>>>ù>>>(<<<=<)>>>,<<<>>#<<<=由于该文法G[S]中任何句型不包含两个相邻的非终结符,且任意两个终结符对a,b之间至多只有<、>、=三种关系的一种成立,所以该文法是为算符优先文法。(3)输入串(a,a)#的归约过程如下:步骤栈S当前输入符剩余输入串动作①②③##(#(a(a,a,a)#,a)#a)#移进移进归约④⑤⑥⑦⑧⑨⑩#(S#(S,#(S,a#(S,S#(T#(T)#S,a)))##a)#)####移进移进归约归约移进归约接受4、若有定义二进制数的文法如下:S→|LL→LB|BB→0|1(1)试为该文法构造LR分析表,并说明属哪类LR分析表。(2)。解:(1)首先对语言文法G[S]的产生式编号如下:①S→②S→L③L→LB④L→B⑤B→0⑥B→1画出识别活前辍的有限自动机DFA如下::S?·?·LL?·LBL?·BB?·0B?·11:S?L·.LS?L·L?L·BB?·0B?·12:S?L.·LL?·LBL?·BB?·0B?·13:S?·L?L·BB?·0B?·14:L?B·5:B?0·6:B?1·7:L?LB·构造LR分析表如下:状态ACTIONGOTO·01#LB——————————————装————————————————订————————————————线————————————————————————————————0S5S6141S2S5S6acc72S5S6343S5S6acc74r4r4r4r45r5r5r5r56r6r6r6r67r3r3r3r3(2):步骤状态栈符号栈输入串ACTIONGOTO10##S6206##r64304##r41401##S55015##r576017##r31701##S68016##r679017##r311001##S211012#L·110#S6120126#L·110#r64130124#L·B10#r43140123#L·L10#S61501236#L·L10#r671601237#L·LB0#r33170123#L·L0#S51801235#L·L0#r571901237#L·LB#r33200123#L·L#acc