华东理工大学编译原理与技术（本）期末复习题及参考答案.docx

《华东理工大学编译原理与技术（本）期末复习题及参考答案.docx》由会员分享，可在线阅读，更多相关《华东理工大学编译原理与技术（本）期末复习题及参考答案.docx（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编译原理与技术（本）期末考试复习题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|

2、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中间代码生成程序、中间代码优化程序、表格管理程序、错误处理程序的主要功 能是什么？【答案】中间代码生成程序：按照语义规那么，将语法分析程序分析出的

3、语法单位转换成 一定形式 的中间语言代码，如三元式或四元式。中间代码优化程序：为了产生高质量的目标代码，对中间代码进行等价变换处 理。目标代码生成程序：将优化后的中间代码程序转换成目标代码程序。表格管理程序：负责建立、填写和查找等一系列表格工作。表格的作用是记录 源程序的各类信息和编译各阶段的进展情况,编译的每个阶段所需信息多数都从 表格中读取，产生的中间结果都记录在相应的表格中。可以说整个编译过程就是 造表、查表的工作过程。需要指出的是，这里的，表格管理程序”并不意味着它就是 一个独立的表格管理模块，而是指编译程序具有的表格管理功能。错误处理程序：处理和校正源程序中存在的词法、语法和语义错误

4、。当编译程序发现 源程序中的错误时，错误处理程序负责报告出错的位置和错误性质等信息，同时对发 现的错误进行适当的校正（修复）目的是使编译程序能够继续向下进行分析和处理。2 .根据以下EBNF写出语法描述图。V写语句 =write，表达式 , 表达式 ） 5 答案:3 .设有文法GS: S: = dAB A = aA|a B : =Bb|sGS能否改写为等价的正那么文法？ 【答案工能改写为如下等价的正那么文法GZ:Z-dAAaA|aB|aB-bB|b4 .设有文法GE:E:=T|ET+ T:二F|TF* F: = P|FP f P: 二 i|E求句型TET+*i t的规范推导。【答案最右推导：E

5、=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

6、文法，现进行改写。第1种改写：(1)用A的产生式右部替换S的产生式右部的A得：SSBa|bBab消除左递归后文法变为：SbNNBaN|Bab由相同左部的产生式可知：FIRST(BaN)nFOLLOW (N)=aA#=0所以该文法是LL(1)文法。第2种改写：用S的产生式右部替换A的产生式右部的S得：SAa|bAAaB|bBBab(2)消除左递归后文法变为：S-Aa|bAbBNN-aBN|eBab由相同左部的产生式可知：FIRST(Aa)AFIRST (b) = b八b=b，0FIRST(aBN)AFOLLOW (N) = aAa= a#0所以该文法不是LL(1)文法。2 .由此题可以说明一个文

7、法假设消除左递归，提取了左公共因子后不一定为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)#

8、移进(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: 二

9、 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) 使用的函数没有定义

10、(4) 在数中出现非数字字符【答案工(1) 语法分析(2) 语义分析(3) 语法分析(4) 词法分析2.根据以下EBNF写出语法描述图。复合语句：尸BEGINV语句；语句 END【答案工3,语言L=anbb，n=l ,写出产生L的文法。【答案工文法GZ为：ZaAbA 一 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)

11、=(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()#aA(#