文档介绍：该【编译原理 上海交通大学期末考试 】是由【小屁孩】上传分享，文档一共【15】页，该文档可以免费在线阅读，需要了解更多关于【编译原理 上海交通大学期末考试 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:....上海交通大学期末考试编译原理试题及答案一、对于文法G[S]:S→1A|0B|εA→0S|1AAB→1S|0BB⑴(3分)请写出三个关于G[S]的句子;⑵(4分)符号串11A0S是否为G[S]的句型?试证明你的结论。⑶(3分)试画出001B关于G[S]的语法树。二、请构造一个文法,使其产生这样的表达式E:表达式中只含有双目运算符+、*,且+的优先级高于*,+采用右结合,*采用左结合,运算对象只有标识符i,可以用括号改变运算符优先级。要求给出该文法的形式化描述。三、设有语言L={α|α∈{0,1}+,且α不以0开头,但以00结尾}。⑴试写出描述L的正规表达式;⑵构造识别L的DFA(要求给出详细过程,并画出构造过程中的NDFA、DFA的状态转换图,以及DFA的形式化描述)。四、给定文法G[S]:S→ABA→aB|bS|cB→AS|d⑴(6分)请给出每一个产生式右部的First集;⑵(3分)请给出每一个非终结符号的Follow集;⑶(8分)请构造该文法的LL(1)分析表;⑷(8分)什么是LL(1)文法?该文法是LL(1)文法吗?为什么?五、给定文法G[S]:S→SaA|aA→AbS|b⑴请构造该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA。⑵请构造该文法的LR(0)分析表。⑶什么是LR(0)文法?该文法是LR(0)文法吗?为什么?⑷什么是SLR(1)文法?该文法是SLR(1)文法吗?为什么?六、给定下列语句:ifa+b>cthenx:=a*(b-c)+(b*c-d)/e⑴写出其等价的逆波兰表示;⑵写出其等价的四元式序列。七、已知下列C语言程序:int*f(){inta=100;return&a;}main(){int*i=f();chara[]=“compiler”;printf(“theresultis%d”,*i);};.:....程序运行结果为:theresultis26157,请解释为什么程序运行的结果不是期望的“theresultis100”?=>1A=>11AA=>:G[E]=({+,*,(,),i},{E,F,T},P,E),其中P为:E→E*F|FF→T+F|TT→(E)|i第三题(1)正规表达式:1(0|1)*00(2)第一步:将正规表达式转换为NDFA第二步:将NDFA确定化为DFA:造表法确定化(3分)确定化后DFAM的状态转换表(2分)状态输入I0I1t01[S]—[A,D,B]q0—q1[A,D,B][D,B,C][D,B]重新命名q1q2q3[D,B,C][D,B,C,Z][D,B]q2q4q3;.:....[D,B][D,B,C][D,B]q3q2q3[D,B,C,Z][D,B,C,Z][D,B]q4q4q3DFA的状态转换图(3分)第三步:给出DFA的形式化描述DFAM=({q0,q1,q2,q3,q4},{0,1},t,q0,{q4})t的定义见M的状态转换表。第四题(1)First(AB)={a,b,c}First(aB)={a}First(bS)={b}First(c)={c}First(AS)={a,b,c}First(d)={d}(2)Follow(S)={#,a,b,c,d}Follow(A)={a,b,c,d}Follow(B)={#,a,b,c,d}(3)LL(1)分析表(8分)VTVNabcd#SS?ABS?ABS?ABAA?aBA?bSA?CBB?ASB?ASB?ASB?d;.:....(4)对于文法G的每一个非终结符U的产生式U?α1|α2|…|αn,如果SELECT(U?αi)?SELECT(U?αj)=?(i≠j,i,j=1,2,…,n),则文法G是一个LL(1)文法。该文法是LL(1)文法。因为SELECT(A?aB)?SELECT(A?bS)?SELECT(A?C)=?SELECT(B?AS)?SELECT(B?d)=?第五题⑴拓广文法1分G[S′]:S′→S⑴S→SaA⑵S→a⑶A→AbS⑷A→b⑸该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA:⑵该文法的LR(0)分析表:ACTIONGOTO状态ab#SA0S212r3r3r33S544r2r2/S6r25r5r5r56S277r4/S3r4r4⑶LR(0)文法:该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA中没有冲突状态。该文法不是LR(0)文法;.:....因为存在冲突状态:I4和I7⑷SLR(1)文法:该文法的以LR(0)项目集为状态的识别规范句型活前缀的DFA中有冲突状态,冲突可用FOLLOW集解决。该文法不是SLR(1)文法。因为FOLLOW(S)={a,b,#},所以无法解决冲突第六题(1)(1)ab+c>(23)jumpf(8)xabc-*bc*d-e/+:=(23)...(2)第七题C语言采用栈式存储分配方法作为其运行环境;f()返回的是指向其活动记录某一位置的指针;f()返回后,其活动记录被释放,并且,其对应的存储空间被数组a占用,再次引用该指针时,其结果由于对回收的活动记录所占用的内存空间的再分配,其所指的值发生了改变。释放在前,引用在后的现象称:DanglingReference。;.:....<编译原理>历年试题及答案一.(每项选择2分,共20分)“遍”是为了___。。。。。。。—。+cd+/可用表达式___来表示。+b/c+db.(a+b)/(c+d)+b/(c+d)+b+c/,称为______管理技术。。(每小题10分,共80分),简述各部分的主要功能。[E]:E→ET+|TT→TF*|FF→F^|a试证:FF^^*是文法的句型,指出该句型的短语、(a|b)*a(a|b)构造一个确定的有限自动机。(S):S→(L)|aS|aL→L,S|S(1)消除左递归和回溯;;.:....(2)计算每个非终结符的FIRST和FOLLOW;(3)构造预测分析表。->aAd|aAb|ε判断该文法是否SLR(1)文法,若是构造相应分析表,并对输入串ab#给出分析过程。[H]的算符优先关系(含#)。G[H]:H→H;M|MM→d|(S)(1)SBB(2)BaB(3)Bb1)。给出DFA图2).给出LR分析表3).假定输入串为abaab,请给出LR分析过程(即状态,符号,输入串的变化过程)。:whileA<C∧B<DdoifA=1thenC:=C+lelsewhileA≤DdoA:=A+2;,(1)求出流图中各结点N的必经结点集D(n),(2)求出流图中的回边,(3)求出流图中的循环。“遍”是为了使编译程序的结构更加清晰,故选b。2..构造编译程序应掌握源程序、目标语言及编译方法等三方面的知识,故选d。,变量既持有左值又持有右值,故选c。,因此选d。,选C。,故选C。。。,.【解答】。词法分析器:输入源程序,进行词法分析,输出单词符号。;.:....语法分析器:在词法分析的基础上,根据语言的语法规则(文法规则)把单词符号串分解成各类语法单位,并判断输入串是否构成语法上正确的“程序”。中间代码生成器:按照语义规则把语法分析器归约(或推导)出的语法单位翻译成一定形式的中间代码,比如说四元式。优化:对中间代码进行优化处理。目标代码生成器:把中间代码翻译成目标语言程序。表格管理模块保存一系列的表格,登记源程序的各类信息和编译各阶段的进展情况。编译程序各阶段所产生的中间结果都记录在表格中,所需信息多数都需从表格中获取,整个编译过程都在不断地和表格打交道。出错处理程序对出现在源程序中的错误进行处理。此外,编译的各阶段都可能出现错误,出错处理程序对发现的错误都及时进行处理。2.【解答】该句型对应的语法树如下:该句型相对于E的短语有FF^^*;相对于T的短语有FF^^*,F;相对于F的短语有F^;F^^;简单短语有F;F^;.【解答】。4.【解答】(1)S→(L)|aS’S’→S|εL→SL’L’→SL’|ε评分细则:消除左递归2分,提公共因子2分。(2)FIRST和FOLLOWFIRST)S)={(,a}FOLLOW(S)={#,,,)}FIRST(S’)={,a,ε}FOLLOW(S’)={#,,,)}FIRST(L)={(,a}FOLLOW(L)={)}FIRST(L’)={,,ε}FOLLOW(L’〕={)}5.【解答】(1)拓广文法(0)S->A(1)A->aAd(2)A->aAb(3)A->ε(2)构造识别活前缀的DFAFOLLOW(A)={d,b,#}对于状态I0:FOLLOW(A)∩{a}=Ф对于状态I1:FOLLOW(A)∩{a}=Ф因为,在DFA中无冲突的现象,所以该文法是SLR(1)文法。(3)SLR(1)分析表状态ACTIONGOTOaBd#A0S2r3r3r312S2r3r3r33;.:....3S5S44r1r1r15r2r2r2(4)串ab#的分析过程步骤状态栈符号栈当前字符剩余字符串动作10#ab#移进202#ab#归约A->ε3023#aAb#移进40235#aAb#归约A->aAb501#A#接受6.【解答】由M→d和M→a…得:FIRSTVT(M)={d,a};由H-H;…得:FIRSTVT(H)={;}由H→M得:FIRSTVT(M)cFIRSTVT(H),即FIRSTVT(H)={;,d,a}由M→d和M→…b得:LASTVT(M)={d,b};由H---,;m得:LASTVT(H)={;};由H→M得:LASTVT(M)cLASTVT(H),即LASTVT(H)={;,d,b}对文法开始符H,有#H#存在,即有#=#,#<FIRSTVT(H),LASTVT(H)>#,也即#<;,#<d.#<a,;>#,d>#,b>#。对形如P→…ab…,或P→…aQb…,有a=b,由M→a|b得:a=b;对形如P→…aR…,而b∈FIRSTVT(R),有a<b,对形如P→…Rb…,而a∈LASTVT(R).有a>b。由H→…;M得:;<FIRSTVT(M),即::<d,:<a由M→aH…得:a<FIRSTVT(H),即:a<;,a<d,a<a由H→H;’’?得:LASTVT(H)>;,即:;>;,d>;,b>;由M→…Hb得:LASTVT(H)>b,即:;>b,d>b,b>b由此得到算符优先关系表,。7.【解答】(1)LR分析表如下:(2)分析表状态ACTIONGOTOab#SB0s3s4122S3S453s3s464r3r35R1R1r16R2R2R2;.:....(3)句子abaab的分析过程表:句子abaab的分析过程步骤状态符号栈输入串所得产生式0#0#abaad#1#03#abaad#2#034#abaab#B→b3#036#aBaab#B→aB4#02#Baab#5#023#Baab#6#0233#Baab#7#02334#Baab#8#02336#BaaB#9#0236#BaBad#10#025#BBad#11#01#Sd#12##d#13识别成功8.【解答】该语句的四元式序列如下(其中E1、E2和E3分别对应:A<C∧B<D,A=1和A≤D并且关系运算符优先级高):100(j<,A,C,102)101(j,_,_,113)/*E1为F*/102(j<,B,D,104)/*El为T*/103(j,_,_,113)/*El为F*/104(j=,A,1,106)/*Ez为T*/105(j,_,_,108)/*EZ为F*/106(+,C,1,C)/*C:=C+1*/107(j,_,_,112)/*跳过else后的语句*/108(j≤,A,D,110)/*E3为T*/109(j,_,_,112)/*E3为F*/110(+,A,2,A)/*A:=A+2*/111(j,_,_,108)/*转回内层while语句开始处*/112(j,_,_,100)/*转回外层while语句开始处*/1139.【解答】(1)流图中各结点N的必经结点集D(n),D(l)={1},D(2)={1,2},D(3)={1,2,3},D(4)={1,2,3,4},D(5)={1,2,5},D(6)={1,2,5,6}(2)求出流图中的回边,5->2,4->3(3)求出流图中的循环:回边5->2对应的循环:2、5、3、4;回边4->3对应的循环:3、4;.:....参考答案一、单项选择题(共10小题,每小题2分,共20分)、、、语法分析、、?L?L??L?L?=L?L??L?L=;.:....、填空题(本大题共5小题,每小题2分,共10分)(单词),然后再分析每个(句子)并翻译其意义。(自底向上)和(自顶向下)两种。。词法、语法和语义分析是对源程序的(分析),中间代码生成、代码优化与目标代码的生成则是对源程序的(综合)。,主要分为两大类,即(静态存储分配)方案和(动态存储分配)方案。,输入数据是(源程序),输出结果是(目标程序)。三、名词解释题(共5小题,每小题4分,共20分),按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位,并转换成统一的内部表示(token),送给语法分析程序。(1)文法若文法的任何两个产生式A??|?都满足下面两个条件:(1)FIRST(?)?FIRST(?)=?;(2)若??*?,那么FIRST(?)?FOLLOW(A)=?。我们把满足这两个条件的文法叫做LL(1)文法,其中的第一个L代表从左向右扫描输入,第二个L表示产生最左推导,1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外,LL(1)文法还有一些明显的性质,它不是二义的,也不含左递归。(语法分析树或语法推导树)。给定文法G=(V,V,P,S),对于G的任何句型都能构造与之关联的NT语法树。这棵树具有下列特征:(1)根节点的标记是开始符号S。(2)每个节点的标记都是V中的一个符号。(3)若一棵子树的根节点为A,且其所有直接子孙的标记从左向右的排列次序为AA…A,那么A?AA…A一定是P中的一条产生式。12R12R(4)若一标记为A的节点至少有一个除它以外的子孙,则A?V。N(5)若树的所有叶节点上的标记从左到右排列为字符串w,则w是文法G的句型;若w中仅含终结符号,则w为文法G所产生的句子。(0)分析器;.:....所谓LR(0)分析,是指从左至右扫描和自底向上的语法分析,且在分析的每一步,只须根据分析栈当前已移进和归约出的全部文法符号,并至多再向前查看0个输入符号,就能确定相对于某一产生式左部符号的句柄是否已在分析栈的顶部形成,从而也就可以确定当前所应采取的分析动作(是移进还是按某一产生式进行归约等)。,是有穷非空的产生式集合。文法G定义为四元组的形式:G=(V,V,P,S)NT其中:V是非空有穷集合,称为非终结符号集合;V是非空有穷集合,NT称为终结符号集合;P是产生式的集合(非空);S是开始符号(或识别符号)。这里,V∩V=?,S?V。V=V∪V,称为文法G的字母表,它是出现NTNNT文法产生式中的一切符号的集合。文法G所描述的语言用L(G)表示,它由文法G所产生的全部句子组成,即L(G)={x|S?*x,其中S为文法开始符号,且x?V?}T简单的说,文法描述的语言是该文法一切句子的集合。四、简答题(共4小题,每小题5分,共20分)?用汇编语言或高级语言编写的程序,必须先送入计算机,经过转换成用机器语言表示的目标程序(这个过程即编译),才能由计算机执行。执行转换过程的程序叫编译程序。汇编程序是指没有编译过的汇编语言源文件。编译程序转换过的叫目标程序,也就是机器语言。编译程序的工作情况有三种:汇编型、解释型和编译型。汇编型编译程序用来将汇编语言编写的程序,按照一一对应的关系,转换成用机器语言表示的程序。解释型编译程序将高级语言程序的一个语句,先解释成为一组机器语言的指令,然后立即执行,执行完了,取下一组语句解释和执行,如此继续到完成一个程序止。用解释型编译程序,执行速度很慢,但可以进行人和计算机的止。用解释型编译程序,执行速度很慢,但可以进行人和计算机的对话对话,随时可以修改高级语言的程序。BASIC语言就是解释型高级语言。编译型编译程序将级语言编写的程序,一次就会部翻译成机器语言表示的程序,而且过程进行很快,在过程中,不能进行人机对话修改。FORTRAN语言就是编译型高级语言。?词法分析、语法分析和语义分析是对源程序进行的分析(称为编译程序的前端),而中间代码生成、代码优化和代码生成三个阶段合称为对源程序进行综合(称为编译程序的后端),它们从源程序的中间表示建立起和源程序等价的目标程序。。所谓自下而上分析法就是从输入串开始,逐步进行“归约”,直至归约到文法的开始符号;或者说从语法树的末端开始,步步向上“归约”,直到根节点。。;.:....代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行一种等价变换,在保证变换前后代码执行结果相同的前提下,尽量使目标程序运行时所需要的时间短,同时所占用的存储空间少。五、综合应用题(共3小题,每小题10分,共30分):S?aSbS|aS|d是二义性文法。解:一个文法,如果存在某个句子有不只一棵语法分析树与之对应,那么称这个文法是二义性文法。句子aadbd有两棵语法树。如下图:SSaSaSbSadaSbSSddd(1)(2)由此可知,S?aSbS|aS|d定义的文法是二义性文法。[S]:S?AB,A?Aa|bB,B?a|Sb求句型baSb的全部短语、直接短语和句柄?句型baSb的语法树如图五(2)所示。SABbBSba图五(2)句型baSb的的语法树解:baSb为句型baSb的相对于S的短语,ba为句型baSb的相对于A的短语,Sb为句型baSb的相对于B的短语,且为直接短语,a为句型baSb的相对于B的短语,且为直接短语和句柄。;.:....=({A,B,C},{0,1},?,{A},{C}),其中:?(A,0)={C}?(A,1)={A,B}?(B,1)={C}?(C,1)={C}。请画出状态转换距阵和状态转换图。解:状态转换距阵为:?01ACA,BB?CC?C状态转换图为:1111AB1C0;.