华东理工大学编译原理与技术（本）期末复习题及参考答案.docx
编译原理与技术（本）期末考试复习题1第一题 问答题（4x1。分）超越高度.中间代码生成程序、中间代码优化程序、表格管理程序、错误处理程序的主要功 能是什么？1 .根据以下EBNF写出语法描述图。V写语句 :=write，（'V表达式 , V表达式'）'.设有文法GS:S: = dABA : = aA|aB : =Bb|eGS能否改写为等价的正那么文法？2 .设有文法GE:E:=T|ET+T: 二 F|TF*F: = P|FP tP : = i | E求句型TET+*i t的规范推导。二 .构造以下正规式相应的DFA （20分）给文法GS：S 一 aA|bQA-aA|bB|bB 一 bD|aQQaQ|bD|bDbB|aAE-aB|bFF 一 bD|aE|b构造相应的最小的DFAo三 .文法GS:S 一 Aa|bA 一 SBB 一 ab,试对GS进行改写，并判断改写后的文法是否为LL （1）文法？2.对于一个文法假设消除左递归，提取了左公共因子后是否一定为LL（1）文法？（20 分） 四.文法GS为:Sa|A|(T)T->S,T|S给出句子(a,a),A）# 的分析过程。（20 分）编译原理与技术（本）期末考试复习题1答案第一题问答题（4x10分）L中间代码生成程序、中间代码优化程序、表格管理程序、错误处理程序的主要功 能是什么？【答案】中间代码生成程序：按照语义规那么，将语法分析程序分析出的语法单位转换成 一定形式 的中间语言代码，如三元式或四元式。中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处 理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录 源程序的各类信息和编译各阶段的进展情况,编译的每个阶段所需信息多数都从 表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是 造表、查表的工作过程。需要指出的是，这里的，表格管理程序”并不意味着它就是 一个独立的表格管理模块，而是指编译程序具有的表格管理功能。错误处理程序：处理和校正源程序中存在的词法、语法和语义错误。当编译程序发现 源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发 现的错误进行适当的校正（修复）目的是使编译程序能够继续向下进行分析和处理。2 .根据以下EBNF写出语法描述图。V写语句 =write，表达式 , 表达式 '） 5 答案:3 .设有文法GS: S: = dAB A = aA|a B : =Bb|sGS能否改写为等价的正那么文法？ 【答案工能改写为如下等价的正那么文法GZ:Z-dAA>aA|aB|aB-bB|b4 .设有文法GE:E:=T|ET+ T:二F|TF* F: = P|FP f P: 二 i|E求句型TET+*i t的规范推导。【答案最右推导：E=>T=> F=> FP t=> Fi t=> Pi f=> Ei t=>Ti t=> TF*i t=> TP*i t=> TE*i t二TET+*i t二.构造以下正规式相应的DFA （20分） 给文法GS：S 一 aA|bQA->aA|bB|bBbD|aQQaQ|bD|bD-bB|aAE->aB|bF F-bD|aE|b 构造相应的最小的DFAo【答案工a三.文法GS:S 一 Aa|bA -> SBB > ab.试对GS进行改写，并判断改写后的文法是否为LL (1)文法？1 .对于一个文法假设消除左递归，提取了左公共因子后是否一定为LL (1)文法? (20 分)【答案】：1 .文法GS隐含有关于S的左递归所以不是LL文法，现进行改写。第1种改写：(1)用A的产生式右部替换S的产生式右部的A得：S>SBa|bB>ab消除左递归后文法变为：SbNNBaN|£B>ab由相同左部的产生式可知：FIRST(BaN)nFOLLOW (N)=aA#=0所以该文法是LL(1)文法。第2种改写：用S的产生式右部替换A的产生式右部的S得：S>Aa|bAAaB|bBB>ab(2)消除左递归后文法变为：S-Aa|bAbBNN-aBN|eB>ab由相同左部的产生式可知：FIRST(Aa)AFIRST (b) = b八b=b，0FIRST(aBN)AFOLLOW (N) = aAa= a#0所以该文法不是LL(1)文法。2 .由此题可以说明一个文法假设消除左递归，提取了左公共因子后不一定为LL (1) 文法。四.文法GS为：Sa|A|(T)T-S,T|S给出句子(a,a), A)#的分析过程。(20分)【答案】：对输入串(a,a), A)#的算符优先分析过程为步骤符号栈当前符号剩余输入串移进或归约(1)#(a,a), A)#移进(2)#(a,a), A)#移进(3)#(a，A)#移进(4)#(a9a), A)#归约(5)#(N9a), A)#移进(6)#(N,aX A)#移进(7)#(N)a),A)#归约(8)#(N,N),A)#归约(9)#(N),A)#移进(10)#(N)9A)#归约(11)#(N9A)#移进(12)#(N,A)#移进(13)#(N, A)#归约(14)#(N,N)#归约(15)#(N)#移进(16)#(N)#归约(17)#N#分析成功编译原理与技术（本）期末考试复习题2第一题问答题（4x10分）1.对以下错误信息、，请指出可能是编译的哪个阶段（词法分析、语法分析、语义分 析、代码生成）报告的。（1） else没有匹配的if（2） 数组下标越界（3） 使用的函数没有定义（4） 在数中出现非数字字符.根据以下EBNF写出语法描述图。复合语句：:=BEGINV语句；语句 END.语言L=anbbn|n=l ,写出产生L的文法。2 .设有文法GE:E:二T|ET+T:二F|TF*F: = P| FPtP: 二 i|E 求句型TET+*if的最右推导。二 .考虑正规表达式r=a*b（a|b），构造可以生成语言L（r）的一个正规文法。（20 分）.文法GS：对文法 GS Sa|A|（T）TTS|S进行改写，然后对每个非终结符写出不带回溯的递归子程序。给出它的预测分析表。 （20 分）.文法GS为：S-a|A|（T）T 一工 S|S构造GS的算符优先关系表。（20分）编译原理与技术(本)期末考试复习题2答案第一题问答题(4x10分)1.对以下错误信息，请指出可能是编译的哪个阶段(词法分析、语法分析、语义分 析、代码生成)报告的。(1) else没有匹配的if(2) 数组下标越界(3) 使用的函数没有定义(4) 在数中出现非数字字符【答案工(1) 语法分析(2) 语义分析(3) 语法分析(4) 词法分析2.根据以下EBNF写出语法描述图。复合语句：尸BEGINV语句；语句 END【答案工3,语言L=anbb，n=l ,写出产生L的文法。【答案工文法GZ为：Z>aAbA 一 aAbAb4.设有文法GE:E:二T|ET+ T: = F|TF* F: = P| FPf P : = i | E求句型TET+*if的最右推导。答案I最右推导：E=>E-T=> E-T* F=>E-T* (E)=>E-T* (E-T)=>T-T* (E-T)=>F-T* (E-T)=>(E)-T* (E-T)=>(E+T)-T* (E-T)=>(E+F)-T* (E-T)=>(E+i)-T* (E-T)=>(T+i)-T* (E-T)=>(F+i)-T* (E-T)二 .考虑正规表达式r = a*b(a|b)，构造可以生成语言L(r)的一个正规文法。(20 分)【答案工S 一 aA | bB, B 一 a | b , A 一 aA | bC, C 一 a | b三 .文法GS：对文法 GS S-a|A|（T）TTS|S进行改写，然后对每个非终结符写出不带回溯的递归子程序。给出它的预测分析表。（20 分）答案:预测与析表aA()#S>>一（T一SN一SN一SNN>一，SN四 .文法GS为：S-a|A|（T）T-TS|S构造GS的算符优先关系表。（20分）答案:算符优先关系表:aA()#a>>>A>>>(<<<<)>><>>#<<<
