编译原理期末考试试卷及答案.doc

得分一 填空题（每空2分,共20分)1. 不同的编译程序关于数据空间的存储分配策略可能不同，但大部分编译中采用的方案有两种：静态存储分配方案和动态存储分配方案,而后者又分为（1） 和 (2） 。2。 规范规约是最（3）规约.3。 编译程序的工作过程一般划分为5个阶段:词法分析、（4） 、语义分析与中间代码生成,代码优化及(5） 。另外还有（6)和出错处理。4表达式x+y*z/（a+b）的后缀式为 （7) 。5文法符号的属性有综合属性和 （8）。6假设二位数组按行存放，而且每个元素占用一个存储单元,则数组a1。15，1.20某个元素ai，j的地址计算公式为（9）.7局部优化是局限于一个（10）范围内的一种优化.得分二 选择题（1-6为单选题,7-8为多选题，每问2分，共20分）1。 一个上下文无关文法G包括四个组成部分：一组终结符，一组非终结符,一个（ ），以及一组（ ）。A 字符串 B 产生式 C 开始符号 D 文法2。程序的基本块是指( )。A 一个子程序 B 一个仅有一个入口和一个出口的语句C 一个没有嵌套的程序段 D 一组顺序执行的程序段，仅有一个入口和一个出口3。 高级语言编译程序常用的语法分析方法中,递归下降分析法属于( ）分析方法。A 自左向右 B 自顶向下 C 自底向上 D 自右向左4在通常的语法分析方法中，（ )特别适用于表达式的分析。A 算符优先分析法 B LR分析法C 递归下降分析法 D LL(1）分析法5经过编译所得到的目标程序是（ )。A 四元式序列 B 间接三元式序列C 二元式序列 D 机器语言程序或汇编语言程序6 一个文法所描述的语言是( )；描述一个语言的文法是（ ）.A 唯一的 B 不唯一的 C 可能唯一，也可能不唯一7 如果在文法G中存在一个句子,当其满足下列条件( ）之一时，则称该文法是二义文法。A 其最左推导和最右推导相同 B 该句子有两个不同的最左推导C 该句子有两个不同的最右推导 D 该句子有两棵不同的语法树E 该句子对应的语法树唯一8 下面（ ）语法制导翻译中,采用拉链回填技术。A。 赋值语句 B. 布尔表达式的计算 C。 条件语句 D。 循环语句得分三 解答题（共60分）1 （共15分）已知文法GE: EETE|(E）i T+（1） 将文法G改造成LL（1）文法；（5分）（2） 构造文法G中每个非终结符的FIRST集合及FOLLOW集合；（5分）（3） 构造LL（1）分析表。（5分）2 (共12分）给定文法GS：SS(S)|（1） 给出句子()()）（）(）的规范推导过程;（4分）(2） 指出每步推导所得句型的句柄；(4分)（3） 画出该句子的语法推导树。（4分）3 （共8分）在一个移入规约分析过程中采用以下的语法制导翻译模式，在按一个产生式规约时,立即执行括号中的动作. AaB print “0； Ac print “1”; BAb print “2”；（1） 当分析器的输入为aacbb时，打印的字符串是什么？(3分）（2） 写出分析过程。（5分）5 （共15分）设有表格构造文法GS： Sa|(T) TT,SS(1) 计算文法GS的FIRSTVT集和LASTVT集。（5分)(2) 构造GS的优先关系表,并判断GS是否为算符优先文法。（5分）(3) 计算GS的优先函数。(5分）得分二 单项选择题（每题2分,共10分）1. 设有文法GI： II1|I0|Ia|Ic|a|b|c下列符号串中是该文法句子的有（ ). ab0 a0c01 aaa bc10可选项有：A B C D2。程序的基本块是指（ ）。A 一个子程序 B 一个仅有一个入口和一个出口的语句C 一个没有嵌套的程序段 D 一组顺序执行的程序段，仅有一个入口和一个出口3. 高级语言编译程序常用的语法分析方法中,递归下降分析法属于（ ）分析方法。A 自左向右 B 自顶向下 C 自底向上 D 自右向左4经过编译所得到的目标程序是（ ）。A 四元式序列 B 间接三元式序列C 二元式序列 D 机器语言程序或汇编语言程序5 运行阶段的存储组织与管理的目的是( ）。 提高编译程序的运行速度 节省编译程序的存储空间 提高目标程序的运行速度 为运行阶段的存储分配做准备可选项有:A。 B. C. D。 得分2. （10分) 已知文法GS： SaBc|bABAaAb|bBb（4） 构造其LL（1）分析表；（5） 判断符号串baabbb是否为该文法的句子（写出含有符号栈、输入串和规则的分析过程）。答案:：(1) 栈式动态存储分配(2) 堆式动态存储分配(3) 左(4) 语法分析(5) 目标代码生成(6) 表格管理(7) xyzab+/+(8) 继承属性(9) a+（i-1）20+j-1(10) 基本块一、 选择题（每问2分，共20分）1。C B 2.D 3.B 4。A 5。D 6.A,C7。BCD，选对一个得1分且不超过满分，选错一个扣一分,扣完为止。8。BCD，选对一个得1分且不超过满分，选错一个扣一分，扣完为止。二、 解答题1(1）文法存在左递归，消除左递归后的文法为：E(E)E|i E（2分）ETEE| （2分）T+ (1分）(2）（5分）没考虑#扣0。5分，其它错或少写一个扣0.5分FIRST(E)=（，i FIRST（E)=，+, FIRST（T)=，+ FOLLOW(E)=）,+, FOWLLOW(E)= ）,*,+，# FOLLOW(T)=（,i（3)每错一个扣0.5分，全错或不写不得分，扣完为止，共5分（）i+#EE(E)EEiEEE ETEEE ETEEE E TT*T+2(1)规范推导过程如下。写错推导符号扣0.5分,错写或少写一步推导扣0。5分，扣完为止,最左推导扣2分，共4分。（2)(1）中加下划线的部分是句柄，标识如（1）。每少写一个句柄扣0。5分,扣完为止，共4分。（3）每少写步扣0。5分，扣完为止，共4分。SS ( S )S ( S ) ) )S ( S ) )S ( S ) ) S ( S ) )3(1）打印的字符串是：12020（错一个扣0。5分，共3分）（2）归约过程中错一步扣0.5分，扣完为止。（共5分）5（1）少写一个扣1分，全错或不写不得分，共5分。FIRSTVT（S）=a，（FIRSTVT(T）=， a，（LASTVT（S)= a,)LASTVT（T)= a,）， ,三、 单项选择题（每题2分，共10分）1。B 2.D 3.B 4.D 5。C四、 解答题(共70分）1（1) L(G)=0m1mM1 共2分，写成扣1分（2） S=0S1=00S11=000111,共3分， =写成-扣1分（3） 共3分，错处扣0。5分,扣完为止一、判断题:1.一个上下文无关文法的开始符，可以是终结符或非终结符。 ( )2。一个句型的直接短语是唯一的. （ ）3.已经证明文法的二义性是可判定的。 ( )4。每个基本块可用一个DAG表示。 （ )5.每个过程的活动记录的体积在编译时可静态确定. （ ）6.2型文法一定是3型文法。 ( ）7。一个句型一定句子。 ( )8.算符优先分析法每次都是对句柄进行归约。 （ ）9。采用三元式实现三地址代码时，不利于对中间代码进行优化。 （ ）10。编译过程中，语法分析器的任务是分析单词是怎样构成的。 ( )11.一个优先表一定存在相应的优先函数。 ( ）12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 （ )13。递归下降分析法是一种自下而上分析法。 （ ）14。并不是每个文法都能改写成LL(1)文法。 ( )15.每个基本块只有一个入口和一个出口。 （ ）16.一个LL(1)文法一定是无二义的。 ( )17.逆波兰法表示的表达试亦称前缀式。 （ ）18。目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 （ )19。正规文法产生的语言都可以用上下文无关文法来描述。 （ )20.一个优先表一定存在相应的优先函数。 （ ）21.3型文法一定是2型文法。 ( ）22。如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的. （ )二、填空题：1。( )称为规范推导。2。编译过程可分为 （ ） ,（ )，（ ），（ )和( ）五个阶段。3。如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是( ). 4.从功能上说，程序语言的语句大体可分为（ ）语句和（ )语句两大类。5。语法分析器的输入是（ ），其输出是（ ）。6。扫描器的任务是从（ ）中识别出一个个（ ）.7.符号表中的信息栏中登记了每个名字的有关的性质，如（ ）等等。8。一个过程相应的DISPLAY表的内容为( ）。9.一个句型的最左直接短语称为句型的( ）.10.常用的两种动态存贮分配办法是（ ）动态分配和( ）动态分配.11。一个名字的属性包括（ ）和（ ）。12.常用的参数传递方式有（ ),（ ）和（ ）.13.根据优化所涉及的程序范围，可将优化分成为( ），（ ）和（ )三个级别.14。语法分析的方法大致可分为两类，一类是（ ）分析法，另一类是（ ）分析法.15。预测分析程序是使用一张（ ）和一个( )进行联合控制的。16.常用的参数传递方式有( ），（ ）和( )。17.一张转换图只包含有限个状态，其中有一个被认为是( )态；而且实际上至少要有一个（ ）态.18.根据优化所涉及的程序范围，可将优化分成为（ )，( ）和( ）三个级别。19.语法分析是依据语言的( ）规则进行。中间代码产生是依据语言的（ ）规则进行的.20。一个句型的最左直接短语称为句型的（ ）。21.一个文法G,若它的预测分析表M不含多重定义，则该文法是（ ）文法。22。对于数据空间的存贮分配， FORTRAN采用( )策略， PASCAL采用( ）策略。23。如果一个文法存在某个句子对应两棵不同的语法树， 则称这个文法是( ）。24。最右推导亦称为（ ），由此得到的句型称为（ ）句型。25。语法分析的方法大致可分为两类，一类是( )分析法,另一类是（ ）分析法。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.语法制导翻译17.规范句型18.素短语19.语法20.待用信息21.语义四、简答题:1。写一个文法G， 使其语言为 不以0开头的偶数集。2.已知文法G(S)及相应翻译方案SaAb print “1Sa 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:=zz； end beginA：=2；B:=A*2;P（A， A， B)；Print A, B end。试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 A, B的值是什么？ 5。文法G（S)SdABAaA aBBb| 描述的语言是什么？6.证明文法G(S) SSaS| 是二义性的。7.已知文法G(S) SBAABS| dBaA| 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,SS的优先关系表如下：关系a(),a。(。.,。请计算出该优先关系表所对应的优先函数表。10。何谓优化？按所涉及的程序范围可分为哪几级优化？11.目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题?12.一字母表=a， b，试写出上所有以a为首的字组成的正规集相对应的正规式。13.基本的优化方法有哪几种？14。写一个文法G, 使其语言为 L（G）=abncn| n015。考虑下面的程序:procedure p(x， y， z)；begin y:=y+z; z:=yz+xend；begin a：=2； b：=3; p（a+b, b， a）； print aend。试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么？ 16.写出表达式ab(c-d）/e的逆波兰式和三元序列。17.证明文法G(A） AAA （A）| 是二义性的。25.符号表的作用是什么?符号表查找和整理技术有哪几种？五、计算题：1.设文法G（S）: S | a | (T) TT，S S 消除左递归； 构造相应的FIRST和FOLLOW集合； 构造预测分析表 3.设文法G(S）：S(T) | aTT+S S（1）计算FIRSTVT 和LASTVT; (2)构造优先关系表。 7.已知文法G（S）Sa (T）TT,S | S(1） 给出句子（a,（a，a）的最左推导；（2） 给出句型（(T,S），a)的短语, 直接短语，句柄.9。已知文法G（S） SaAcBe AAb b Bd（1)给出句子abbcde的最左推导及画出语法树；(2）给出句型aAbcde的短语、素短语. 10。设文法G（S): S(T） aS a TT,S S 消除左递归和提公共左因子； 构造相应的FIRST和FOLLOW集合； 构造预测分析表。参考答案一、是非题：1。 2。 3. 4。 5. 6。 7。 8. 9. 10. 11。12。 13。 14. 15。 16。 17. 18. 19。 20。 21。 22.二、填空题:1。（最右推导）2.(词法分析）,（语法分析),（中间代码生成）,（代码优化），(目标代码生成）3。(二义性的）4.(执行性），(说明性)5.（单词符号)，（语法单位）。6.（源程序），（单词符号）7。（类型、种属、所占单元大小、地址）8。(现行活动记录地址和所有外层最新活动记录的地址)9.(句柄）10。（栈式）,(堆式)11。（类型)，(作用域）12.(传地址），（传值）,(传名）13。（局部优化），(循环优化)，（全局优化）14.（自上而下），（自下而上)15.(分析表），（符号栈）16.（传地址），(传值），（传名）17.（初），（终)18。（局部优化）,（循环优化），(全局优化）19.(语法），（语义）20。(句柄）21。(LL(1) 文法)22。(静态），（动态）23。(二义性文法）24。（规范推导），（规范）25.(自上而下)，（自下而上)26.（句子）27。（从开始符号出发，向下推导,推出句子）28。(单词符号），(语法单位)29。(局部优化）30。(分析表），（符号栈）31.（上下文无关文法），（正规)32。(指令访问主存次数加1）33。（最左素短语）三、名词解释题： 1。局部优化-局限于基本块范围的优化称。2。二义性文法-如果一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义性文法。3.DISPLAY表-过程的嵌套层次显示表,记录该过程的各外层过程的最新活动记录的起始地址。4.词法分析器-执行词法分析的程序。5。最左推导-任何一步=都是对中的最右非终结符替换.6。语法-一组规则,用它可形成和产生一组合式的程序。7。文法-描述语言的语法结构的形式规则。8。基本块-指程序中一顺序执行的语句序列,其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。9。语法制导翻译-在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。10.短语-令G是一个文法,S划文法的开始符号，假定是文法G的一个句型,如果有SA且A，则称是句型相对非终结符A的短语.11。待用信息-如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值，则称j是四元式i的变量A的待用信息。12。规范句型-由规范推导所得到的句型。13.扫描器-执行词法分析的程序。14。超前搜索-在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。15。句柄-一个句型的最左直接短语。16.语法制导翻译-在语法分析过程中,根据每个产生式所对应的语义程序进行翻译的方法 叫做语法制导翻译.17.规范句型-由规范推导所得到的句型.18.素短语-素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。19.语法-是组规则，用它可形成和产生一个合式的程序。 20。待用信息-如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值,则称j是四元式i的变量A的待用信息。21。语义-定义程序的意义的一组规则。四、简答题: 1。所求文法是GS:SAB |B A0AAD CB2 4 |6 8C1 3 |5 |7 9 BD0 C2。输出是42313.句子b（aa)b的规范归约过程：步骤符号栈输入串动作0#b(aa）b预备1b(aa）b#移进2b（aa）b#移进3 b（a a)b 移进4b（Aa）b归约5 b（Ma）b#移进6b(Ma)b#移进7b（B b 归约8bAb#归约9bAb移进10#S接受4.传地址 A=6, B=16传值 A=2, B=45.L(G)=danbm n0， m06.证明： 因为文法GS存在句子aa有两个不同的最左推导，所以文法GS是是二义性的.S=SaS=SaSaS=aSaS=aaS=aa S=SaS=aS=aSaS=aaS=aa7。句子 adccd 的分析过程:步骤符号栈输入串产生式0Sadccd1#ABadccdSBA2#AAaadccdBaA3AAdccd#4#Addccd#Ad5#Accd#6#SBccd#ABS7#Scccd Bc8#S cd# 9#ABcd#Bc10Acd11#A d#12ddAd13# 8.所求文法是GS: SAB AaAc D DbD | bBaBb | aabb9.函数a（)，f4244g552310.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化11。目标代码通常采用三种形式：机器语言，汇编语言,待装配机器语言模块.应着重考虑的问题: （1）如何使生成的目标代码较短；(2）如何充分利用寄存器,以减少访问内存次数；(3)如何充分利用指令系统的特点.12.正规式 a ( a b ）.13。删除多余运算，代码外提,强度削弱，变换循环控制条件，合并已知量,复写传播和删除无用赋值。14。文法GS：SaB | a Bbc bBc15.传值 a=2 传地址 a=1516.逆波兰式： abcd-*e/+三元序列： op arg1 arg2 (1) c d （2） b （1） （3) / （2） e (4) + a (3)17.证明：因为文法GS存在句子 () 有两个不同的最左推导,所以文法GS是是二义性的。A=AA=（A）A=()A=() A=AA=A=(A)=()25.作用：登记源程序中出现的各种名字及其信息,以及了解各阶段的进展状况。主要技术：线性表，对折查找，杂奏技术。五、计算题:1。（1)消除左递，文法变为GS：S a (T）TST ST,ST 此文法无左公共左因子。(2)构造相应的FIRST和FOLLOW集合： FIRST(S）=a, , (， FOLLOW（S）=#, ,， ）FIRST（T）=a, , ( ，FOLLOW（T）=FIRST(T)=，, ,FOLLOW(F)=)（3）构造预测分析表:a（）,#SSaSS(T)TTSTTSTTSTTTT，ST2. （1）Cif E thenSCS(1） （2） Cif E then BACK（E。TC, NXQ)； C。chain：=E.FC SCS(1) S。chain：=MERG(C.Chain, S(1）。 Chain)3. （1） FIRSTVT(S）=a， ( FIRSTVT(T)=+， aa, ( LASTVT（S)=a, ） LASTVT(T)=+, a， ） (2) a + （ ) a . 。+ . 。 。 .( 。 。4. (1) Ffor i：=E(1) to E（2） do SFS(1）(2) Ffor i:=E（1) to E(2） doGEN(:=, E(1）。place， _, entry(i)）;F。place:=entry(i);LIMIT:=Newtemp;GEN（:=, E(2).place, _， LIMIT);Q:=NXQ；F。QUAD:=q;GEN（j， entry(i）， LIMIT, q+2)F.chain:=NXQ;GEN(j, _， _， 0）SFS(1）BACKPATCH（S（1）.chain, NXQ）； GEN(+, F。place, 1, F。place)； GEN（j, _， _, F。QUAD）; S。chain：=F。chain5. (1） （j， c， 0, (5）(4) （j， _， _， (8）)(5) （+， a, 1, T1）(6) (：=, T1, _， a）(7) （j， _, _, （1)(8) (*, a， 13, T2）(9) （-, T2, 1， T3）(10) (:=, T3， _, a)(11) (j, _, _, (1）6。优化后的四元序列D：=ACE：=ACF:=DEM：=F+207. 最左推导S=（T)=(T，S)=（S,S)=（a，S)=（a，（T）=（a,(T，S)）=（a,（S,S)=(a,(a，S)）=（a，(a，a)短语 （T，S),a） （T,S),a （T,S） T，S a直接短语 T,S a句柄 T，S8.(1）Sdo M1 S1 while M2 EM （2）M M.quad=nestquad；Sdo M1 S1 while M2 E backpatch（s1.nextlist, M2.quad）; backpatch（E。truelist, M1。quad); S。nextlist=E。falelist; 9.（1) S=aAcBe=AAbcBe=abbcBe=abbcde(2） 短语: aAbcde, Ab, d 素短语： Ab, d10.(1） S （L） | aS SS LSL L，SL （2) FIRST(S）=a, （ FIRST(S)=a, （， FIRST(L）=a, ( FIRST(L)=, FOLLOW(S）=， ）, FOLLOW(S)=,， ）, #FOLLOW（L）= ) FOLLOW（L）= ）（3） ( ) a , SS （L)S aSSSSSSSSSLLSLLSLL,SL LL第 12 页 共 13 页