编译原理自测题.pdf

1 第一章一填空题1编译程序的工作过程一般可以划分为词法分析、语法分析、语义分析与中间代码产生、优化 和生成目标程序 等几个基本阶段，同时还伴有符号表管理 和出错处理2若源程序是用高级语言编写的，目标程序是汇编 或机器语言，则其翻译程序称为编译程序3编译方式与解释方式的根本区别在于运行目标程序时的控制权在解释器而不是目标程序4 翻译程序 是这样一种程序，它能将用甲种语言书写的程序转换成与其等价的乙种语言书写的程序5对编译程序而言，输入数据是高级语言（源）程序，输出结果是 低级语言（目标）程序6运行编译程序的计算机称宿主机，运行编译程序所产生目标代码的计算机称目标机7当把编译程序划分成编译前端和编译后端时，前端 主要由与源语言有关但与目标机无关的部分组成，编译后端包括编译程序中与目标机有关的部分，编译后端不依赖于源语言而仅仅依赖于中间语言8 描述词法规则的有效工具是词法分析器，通常使用 语法分析器 来描述语法规则，使用 语义分析（与中间代码产生）器描述语义规则二综合题（该答案仅供参考）1、给出 C语言编译程序对下面语句进行编译时从词法分析到目标代码生成5个分析阶段的分析过程c=a+b*30;（1）给出每个阶段的输入和输出代码或其它数据形式。

2）给出符号表，说明在哪些阶段会对符号表进行填写或查找3）编译过程是否进行了代码优化？若有，请指出优化之处，并给出属于哪种优化？答：词法分析：出入源程序；输出识别出的记号流c=a+b*30 id1=id2+id3*30 语法分析器：输入记号流，构造句子结构；输出语法树id1 +id2 *id3 30 语义分析与中间代码生成：出入语法树，输出中间代码变量地址数值注：赋值阶段会对符号表进行填写或查找 1.id1 0 c （itr，30，t1）2.id2 4 x （*，id3，t1，t2）3.id3 8 y （+，id2，t2，t3）4.t1 12 30 （=，t3，id1）优化：1.（*，id3，30.0，t1）2.（+，id2，t1，id1）精简掉多余的复写传播目标代码：mov id3，r2 mulf#30.0，r2 mov id2，r1 名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 12 页 -2 sub r1，r2 mov r2，id1 第二章一填空题1上下文无关文法包括以下四个组成部分：一组终结 符号，一组 非终结 符号，一个 开始 符号，以及一组 产生式2如果一个文法存在某个句子对应两棵不同的语法树，则这个文法是二义 文法。

3消除文法的二义性的方法主要有：改写 二义文法为非二义文法；为文法符号规定优先顺序 和结合规则二 简答题1有文法G：EE+EE*E(E)id（1）给出(id*id)+id的最左推导；E （E）（E+E）（E*E+E）（id*E+E）（id*id+E）（id*id+id）（2）并给出该推导过程中的所有句型；见（1）,把箭头去掉即可（3）给出该文法的2 个句子1*1+1 2*2+2 第三章一 综合题1给出书中P48 图 3.5 中所示有限自动机的状态转换矩阵和五元式，并说明该有限自动机可识别哪一类字符串状态 a b a 0 1 2 空空 a a 空 a 空 1 3 2 2 1 3 b b b 3 3 3 b (5,3,1,2,6,y）(5,4,1,2,6,y)可识别相继两个a 或相继两个b 的字2构造与正规式（ab）*a(a b)或(0|1)*0(0|1)等价的状态最少的确定有限自动机1）构造转换系统如下图所示A Z a S B C b a a b x 5 4 1 3 2 y 6 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 12 页 -3 正则式（ab）*a(ab)的转换系统（2）NFA 确定化为DFA 的过程如下表所示：I Ia Ib S,A,BA,B,CA,BA,B,CA,B,C,ZA,B,ZA,BA,B,CA,BA,B,C,ZA,B,C,ZA,B,ZA,B,ZA,B,CA,B相应 DFA 的状态图如下所示正则式（a b）*a(ab)的 DFA 将 DFA最小化：首先得到两个子集K1=1,2,3 和 K2=4，5 由于状态1 和状态 3 输入 a 都到达状态2，输入 b 都到达状态3，而状态 2 输入 a 到达状态4，输入b 到达状态5，所以将 K1 分割成K11=1,3 和 K12=2 又由于状态4 输入 b 到达 K2，而状态5 输入 b 到达 K11,所以状态4、5 是可分的。

这样，将原状态集合分割成以下子集：1，3，2，4，5 所以最小化DFA的状态图如下所示，正则式（a b）*a(a b)的最小化DFA2 5 a 1 3 b aa a b a 4 b b b 4 a 2 a a b 1 5 b b a b 名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 12 页 -4 3构造与正规式(a|ba)*等价的状态最少的确定有限自动机i a b b (x,1)(1,y)(1,2)空 a (1,y)-a a (1,2)(1,y)-b a 4、P64:习题 8（1）以 01 结尾的二进制数串（2）能被 5 整除的十进制整数第四章一填空题1 自上而下语法分析中存在的主要问题是由左递归引起的无限循环 问题和左公共因子引起的无法确定产生式后选项问题2自上而下语法分析的基本思想是，对任何输入串，从文法的开始 符号，即根结点出发，自上而下地为输入串建立一颗语法树递归下降分析器采用的是递归下降 语法分析方法3预测分析器模型是由总控程序（表驱动程序），预测分析表和先进后出的语法分析栈组成，预测分析器是一种下推自动机二、综合题一完成分析以下文法G 的 LL（1）预测分析器（词法分析器）的构造。

1）L E;L|（2）E TE（3）E+TE|-TE|（4）T FT（5）T *FT|/FT|mod FT|（6）F(E)|id|num 1给出或画出预测分析器的组成；2构造预测分析表，FIRST（A）和 FOLLOW（A）如下：FIRST(F)=(id num FIRST(T)=*/mod FIRST(T)=(id num FIRST(E)=+-FIRST(E)=(id num FIRST(L)=(id num FOLLOW(L)=#FOLL0W(E)=);FOLLOW(E)=);FOLLOW(T)=+-;)1 x 1 2 y 3 2 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 12 页 -5 FOLLOW(T)=+-;)FOLLOW(F)=+-*/mod);3给出驱动器算法的伪代码，令ip 指向#中的第一个终结符，top 指向文法开始符号S;4填表给出用此分析器分析句子id+id*id;的过程名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 12 页 -6 名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 12 页 -7 第五章&第七章1自下而上语法分析的基本思想是，从输入串 开始，逐步进行归约，直至规约到文法的开始符号，即从语法树的 末端 开始，步步向上规约，直到叶结点为输入符号串。

二、综合题一 P81:习题 1（1）消去文法中的左递归二画出下面表达式的DAG P168（1）f=a*(b-c)+(b-c)*d（2）a=b*(-c)+b*(-c)四 P217 习题 3 表达式的三元式、四元式代码序列，将最前面的负号去掉，改为(a+b)*(c+d)-(a+b+c)名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 12 页 -8 三请根据以下语义规则写出id1*id2+id3的中间代码用有二义的文法）产生式语义规则（1）A id:=E A.code:=newtemp;emit(:=,entry(id.name),E.code,A.code)（2）E E1+E2 E.code:=newtemp;emit(+,E1.code,E2.code,E.code)（3）E E1*E2 E.code:=newtemp,emit(*,E1.code,E2.code,E.code)（4）E id E.code:=entry(id.name)一 P81:习题 1（1）消去文法中的左递归名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 12 页 -9 二画出下面表达式的DAG（1）a+a*(b-c)+(b-c)*d +*d a -b c（2）a=b*(-c)+b*(-c)Assign A +*B uminus c 三有文法G：（1）EE+T （2）ET （3）TT*F （4）TF （5）F(E)（6）Fi 书中 P101图 5.5 是 LR分析表，以下程序是驱动器算法，loop s:=top;a:=ip;case actions，a is shift s:push(a);push(s);next(ip);reduce by A:pop(2*|);s:=top;push(A);push(goto(s，A);accept:return;others:error;end case;end loop 1完成表2 中 LR分析器利用LR分析表和驱动器对输入串i1*i2+i3进行分析的过程：写出栈中的内容和动作类型（移进或归约，若为移进请指出转向状态，若为归约请指出归约采用的产生式）；2若在语法分析同时进行语义分析，请在有语义翻译动作的步骤中标出。

ACTION GOTO 状态i+*()#E T F 0 s5 s4 1 2 3 1 s6 acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8 2 3 5 r6 r6 r6 r6 6 s5 s4 9 3 7 s5 s4 10 8 s6 s11 9 r1 s7 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 12 页 -10 表 1 文法 G的 LR分析表表 2 步骤栈内容当前输入移进-规约动作翻译动作1#i*i+i#移进#2#i*i+i#移进 i 3#F*i+i#规约 F F i Valtop=lexval 4#T*i+i#规约 T T F Valtop=lexval 5#T*i+i#移进*6#T*i+i#移进 i 7#T*F+i#规约 F F i Valtop=lexval 8#T+i#规约 T T F 9#E+i#规约 E E T 10#E+i#移进+11#E+i i#移进 i 12#E+F#规约 F F i Valtop=lexval 13#E+T#规约 T T F Valtop=Valtop+Valtop+2 14#E#规约 E E T,第六章一填空题1、属性文法是在上下文无关文法的基础上，为每个文法符号配备若干相关的“值”，称为属性，属性与变量一样可以进行计算和传递，属性加工的过程即是语义处理的过程，对文法的每个产生式配备的一组属性的计算规则，叫语义规则，语义分析和中间代码的产生就是根据该规则进行的，在自上而下或自下而上语法分析过程中，在适当的时候进行属性的计算或其它语义动作（如查填符号表、产生中间代码、发布出错信息）就可进行语法制导翻译得到中间代码，这就是语法制导翻译的基本思想。

2、属性分为两类，综合 属性用于“自下而上”传递信息，_继承 _属性用于“自上而下”传递信息名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 12 页 -11 二 简答题1、语法制导翻译所谓语法制导翻译，是指在语法规则的制导下，通过计算语义规则，完成对输入符号串的翻译由于使用属性文法时把语法规则和语义规则分开，但在使用语法规则进行推导或规约的同时又使用这些语义规则来知道翻译与最终产生目标代码，所以称为语法制导翻译第八章一填空题1、线性查找 是构造符号表最简单和最容易的办法，但查找效率很低，为了提高查找速度可以采用对折查找和 杂凑查找 查找2、线性表是构造符号表最简单和最容易的。