《编译原理复习题及参考标准答案.doc》由会员分享，可在线阅读，更多相关《编译原理复习题及参考标准答案.doc（13页珍藏版）》请在金锄头文库上搜索。
1、编译原理课程复习资料一、判断题：1.一个上下文无关文法的开始符，可以是终结符或非终结符。 2.一个句型的直接短语是唯一的。 3.已经证明文法的二义性是可判定的。 4.每个基本块可用一个DAG表示。 5.每个过程的活动记录的体积在编译时可静态确定。 6.2型文法一定是3 型文法。 7.一个句型一定句子。 8.算符优先分析法每次都是对句柄进行归约。 9.采用三元式实现三地址代码时，不利于对中间代码进行优化。 10.编译过程中，语法分析器的任务是分析单词是怎样构成的。 11.一个优先表一定存在相应的优先函数。 12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 13.递归下降分析法是一种
2、自下而上分析法。 14.并不是每个文法都能改写成 LL(1)文法。 15.每个基本块只有一个入口和一个出口。 16.一个 LL(1)文法一定是无二义的。 17.逆波兰法表示的表达试亦称前缀式。 18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 19.正规文法产生的语言都可以用上下文无关文法来描述。 20.一个优先表一定存在相应的优先函数。 21.3型文法一定是2 型文法。 22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。 二、填空题：1. 称为规范推导。2.编译过程可分为 ， ， ， 和 五个阶段。3.如果一个文法存在某个句子对应两棵不同的语法树，则称这个文
3、法是 。4.从功能上说，程序语言的语句大体可分为 语句和 语句两大类。5.语法分析器的输入是 ，其输出是 。6.扫描器的任务是从 中识别出一个个 。7.符号表中的信息栏中登记了每个名字的有关的性质，如 等等。8.一个过程相应的DISPLAY表的内容为 。9.一个句型的最左直接短语称为句型的 。10.常用的两种动态存贮分配办法是 动态分配和 动态分配。11.一个名字的属性包括 和 。12.常用的参数传递方式有 ， 和 。13.根据优化所涉及的程序范围，可将优化分成为 ， 和 三个级别。14.语法分析的方法大致可分为两类，一类是 分析法，另一类是 分析法。15.预测分析程序是使用一张 和一个 进行
4、联合控制的。16.常用的参数传递方式有 ， 和 。17.一张转换图只包含有限个状态，其中有一个被认为是 态；而且实际上至少要有一个 态。18.根据优化所涉及的程序范围，可将优化分成为 ， 和 三个级别。19.语法分析是依据语言的 规则进行。中间代码产生是依据语言的 规则进行的。20.一个句型的最左直接短语称为句型的 。21.一个文法G，若它的预测分析表M不含多重定义，则该文法是 文法。22.对于数据空间的存贮分配， FORTRAN采用 策略， PASCAL采用 策略。23.如果一个文法存在某个句子对应两棵不同的语法树， 则称这个文法是 。24.最右推导亦称为 ，由此得到的句型称为 句型。25.
5、语法分析的方法大致可分为两类，一类是 分析法，另一类是 分析法。26.对于文法G，仅含终结符号的句型称为 。27.所谓自上而下分析法是指 。28.语法分析器的输入是 ，其输出是 。29.局限于基本块范围的优化称 。30.预测分析程序是使用一张 和一个 进行联合控制的。31.2型文法又称为 文法；3型文法又称为 文法。32.每条指令的执行代价定义为 。33.算符优先分析法每次都是对 进行归约。三、名词解释：1.局部优化2.二义性文法3.DISPLAY表4.词法分析器5.最左推导6.语法7.文法8.基本块9.语法制导翻译10.短语11.待用信息12.规范句型13.扫描器14.超前搜索15.句柄16
6、.语法制导翻译17.规范句型18.素短语19.语法20.待用信息21.语义四、简答题：1.写一个文法G,使其语言为不以0开头的偶数集。2.已知文法G(S)及相应翻译方案 SaAb print “1”Sa print “2”AAS print “3”Ac print “4”输入acab,输出是什么？3.已知文法G(S)SbAaA(B | aBAa)写出句子b(aa)b的规范归约过程。4.考虑下面的程序： Procedure p(x, y, z)； beginy:=x+y;z:=z*z; end beginA:=2;B:=A*2;P(A, A, B);Print A, B end.试问，若参数传递
7、的方式分别采用传地址和传值时，程序执行后输出A,B的值是什么？5.文法GSSdABAaA| a BBb| 描述的语言是什么？6.证明文法GS SSaS| 是二义性的。7.已知文法GS SBA ABS| d BaA| bS | c 的预测分析表如下 a b c d # SSBASBASBA AABSABSABSAd BBaA BbS Bc给出句子 adccd 的分析过程。8.写一个文法G, 使其语言为 L(G)=albmclanbn| l=0, m=1, n=2 9.已知文法G(S):Sa| (T)TT,S|S的优先关系表如下：关系a(),a.(.=.,.请计算出该优先关系表所对应的优先函数表。
8、10.何谓优化？按所涉及的程序范围可分为哪几级优化？11.目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？12.一字母表=a, b，试写出上所有以a为首的字组成的正规集相对应的正规式。13.基本的优化方法有哪几种？14.写一个文法G, 使其语言为 L(G)=abncn| n015.考虑下面的程序： procedure p(x, y, z);begin y:=y+z; z:=y*z+xend;begin a:=2; b:=3; p(a+b, b, a); print aend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么? 16.写出表达式ab*(c-d)/e的逆波兰式和三元序列。17.证明文法GA AAA | (A)| 是二义性的。18.令=a,b，则正规式a*b|b*a 表示的正规集是什么？19.何谓DISPLAY表？其作用是什么？20.考虑下面的程序：procedure p(x, y, z)； beginy:=y+2;z:=z+x; end begina:=5;b:=2;p(a+b, a-b, a);print a end.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么? 21.写一个文法G, 使其语言为 L(G)=anbncm| n0为奇数， m0
