编译原理复习题集

1、编译原理复习题集1名词解释短语句柄文法上下文无关文法LL(1)文法LR(1)文法语法分析无环路有向图(DAG)后缀式语法制导翻译遍局部优化词法分析语法分析语义分析源语言源程序目标语言中间语言(中间表示)2简答题编译程序和高级语言有什么区别?编译程序的工作分为那几个阶段?简述自下而上的分析方法。目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？何谓优化？按所涉及的程序范围可分为哪几级优化？简述代码优化的目的和意义。3.叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图。(1|01)*0*语言无符号数的正规定义如下:numdigit+(d.igit+)?E(+|-d)ig

2、i?t其中表示数字，用状态转换图表示接受无符号数的确定有限自动机。.画出中实数不带正负号，可带指数部分的状态转换图。.用状态转换图表示接收*的确定的有限自动机。.处于和之间的串构成注解，注解中间没有。画出接受这种注解的的状态转换图。某操作系统下合法的文件名为device:name.extension其中第一部分()和第三部分()可缺省，和都是字母串，长度不限，但至少为1画出识别这种文件名的确定有限自动机。9.构造一个DFA，它接受=0,1上0和1的个数都是偶数的字符串。，6，6，其中：6。请画出状态转换A6(距阵和状态转换图。11.设La,b,c*是满足下述条件的符号串构成的语言：若出现a，则

3、其后至少紧跟两个c；若出现b，其后至少紧跟一个c。试构造识别L的最小化的DFA，并给出描述L的正规表达式。2写出字母表工上语言2写出字母表工上语言并画出接受该语言的最简。的最后两个字母是或的正规式,3有穷自动机接受字母表工=上所有满足下述条件的串：串中至少包含两个连续的或两个连续的。请写出与等价的正规式。14.有正规式b*abb*(abb*)*，构造该正规式所对应的NFA(画出状态转换图)。将所求的NFA确定化(画出确定化的状态转换图)。将所求的NFA最小化.(画出最小化后的状态转换图)。求出下列文法所产生语言对应的正规式.STbSlaAATaAIbBBTaAIbClbCTbSlaA给出与下图

4、的NFA等价的正规式。17.把下面的NFA确定化。下面两个文法中哪一个不是（）文法？对非移进一归约冲突的规范的（）项目集。SaAcAbbA|b下面两个文法中哪一个不是（）文法？对非移进一归约冲突的规范的（）项目集。SaAcAbbA|bR）的那个文法。给出那个有SaAcAbAb|b9将下面的a,b0为语言L=wIwe（aIb）*并且在w的任何前缀中，a的个数不少于b的个数,写一个（）文法，不准超过个产生式。1写一个文法，使其语言是奇数集，且每个奇数不以0开头。2考查文法（1消）除文法的左递归；（2提）取公共左因子；（3对）每个非终结符，写出不带回朔的递归子程序.设文法：（消1除）左递归和回溯；计

5、算每个非终结符的和（3）构造预测分析表。24.消除下列文法的左递归.STSaPISflPPTQbPIQQTcSdle25已知文法G：ATaABelaBTBbld给出与上述文法等价的LL(1)文法G。已知文法GA：AfaABlaBfBbld构造与GA等价的LL(1)文法；构造GA的预测分析表。程序的文法如下：PDDD;Dlid:Tlprocid;D;S写一个语法制导定义，打印该程序一共声明了多少个id。写一个翻译方案，打印该程序每个变量id的嵌套深度。构造下面文法的LL(1)分析表。DTLTint|realLidRR,idR|s考虑下文法：DTTVTTintIfloatVTid,Vlid在该文法

6、中提取左公因子。为所得文法的非终结符构造First和Follow集合。说明所得的文法是LL(1)文法。为所得文法构造LL(1)分析表。假设有输入串intx,y,z写出相应LL(1)分析程序的动作。.说明如下文法是否是()文法，若不是，将其转换为()文法。最后给出该文法的()分析表。ATBeBTBbla31.设有文法：PfbeginXYendXXd;Xd;YY;sYs(1)该文法含有左递归吗？若有，消除它。改造后的文法是LL(1)文法吗？若是，给出其预测分析表。写出句子begind；send的分析过程。32已给文法GS：SSaP|Sf|PPqbP|q将GS改造成LL(1)文法，并给出LL(1)分

7、析表33设文法G(S)：S(L)|aS|aLL，S|S(1)消除左递归和回溯；计算每个非终结符的FIRST和FOLLOW；构造预测分析表。34给定文法GS：SAa|dAb|Bb|dBaAcBc构造文法GS的LR(1)分析表。5已知文法AT写出句子()的规范归约过程及每一步的句柄。6已知文法ET|ET给出句型+的最右推导及画出语法树；37.说明下面的文法不是SLR(1)文法，并重写一个等价的SLR(1)文法。S-MaIbMcIdcIbdaMTdSSSMaIbMcIdcIbdaMd因为a是M的后继符号之一，因此在上面最右边一个项目集中有移进-归约冲突。等价的SLR文法是STdaIbdcIdcIbd

8、a38.在PASCAL语言中，简单类型的变量的声明例举如下：m,n:integerp,q,r:real为这样的声明写一个LR(1)文法(为简单起见，变量标识符都用id表示)，并根据你的文法写一个语法制导定义(或叫做为你的文法加上语义动作)，它将变量的类型填入符号表。.一个非()的文法如下：LtMLbIaMT,请给出所有有移进一归约冲突的LR(1)项目集，以说明该文法确实不是LR(1)的。若有文法G(S)的产生式如下：STL=RSTRLT*RLTiRTL,构造识别所有项目集规范族的DFA.,判断该文法是否是SLR(1)文法，说明理由。现有句型Ybl和产生式Atb，分别指出LL(1)方法和LR(1

9、)方法在扫描到此句型的什么位置决定用此产生式？为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号(即值大于零还是小于零)记录在属性E.sign中(属性值分别用POS或NEG表示)。你可以假定所有的整数都不为零，这样就不用担心零的符号。ETEE丨+E丨-E丨unsigned_integer一个文法如下：ST(S)STa请给出该文法中对活前缀(有效的LR(1)项目。为下面文法添加语义规则(或叫动作子程序)，输出S，产生的二进制数的值，如输入是101时，输出5。T5写出表达式a+-的逆波兰表示及三元式序列。46.把表达式-(a+b)*(c+d)+(a+b+c)翻译成三地址码序列

10、。7设布尔表达式的文法为f1fAEfi假定它们将用于条件控制语句中，请(1改)写文法，使之适合进行语法制导翻译；(2写)出改写后的每个产生式的语义动作。48将语句f(AvX,B0)while(C0)C=C+D;翻译成三地址码序列。设有基本块如下：T1=S+RT2=3T3=12/T2T4=S/RA=T1-T4T5=S+RB=T5T6=T5*T3B=T6画出中间代码的流图；设A、B是出基本块后的活跃变量，请给出优化后的三地址码序列。设已构造出文法G(S)：STBBB-TaB(3)BTb的LR分析表如下状态ACTIONGOTOab#SB0s3s4121acc2s6s753s3s484r3r35r16

11、s6s797r38r2r29r2假定输入串为abab,请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。51给出活动记录空间结构。并给出各部分的存储对象。52将下面程序段翻译成四元式序列。while(AvCABvD)if(A=1)C=C+1;elsewhile(Ab)x=a+b*c;elsex=b-a;57考虑下面的三地址语句序列b:=1b:=2ifw=xgotoL2e:=bgotoL2L1:gotoL3L2:c:=3b:=4c:=6L3:ify=zgotoL4gotoL5L4:g:=g+1h:=8gotoL1L5:h:=9在该代码中用水平的横线将代码分成基本块，并给每个基本块

12、一个序号画出该代码的控制流图，每个基本块就用(1)的序号表示。若有循环的话，列出构成每个循环的结点。TOC o 1-5 h z1）（2）b:=1b:=2讦w=xgotoL2（1）e:=bgotoL2（2）L1:gotoL3（3）L2:c:=3b:=4c:=6（4）L3:讦y=zgotoL4（5）gotoL5（6）L4:g:=g+1h:=8gotoLI（7）L5:h:=9（8）3)结点5、7和3构成一个循环，其中5是入口结点。8一个语言程序如下:该程序在工作站上的运行结果如下:从上面的结果可以看出，函数的个形式参数的地址依次升高，而个局部变量的地址依次降低。试说明为什么会有这个区别。由于实参表达

13、式是反序进入活动记录，而局部变量是顺序在活动记录中分配。9一个语言程序如下：该程序在机器上的用命令编译时，报告的错误信息如下:请问，报告最后一行的错误的原因是什么？如何修改程序，使得编译时不再出现这个错误信息。0一个语言程序如下:该程序在机操作系统上的运行结果如下：试分析为什么会出现这样的运行错误。1一个语言函数如下：该函数在机操作系统上编译生成的汇编代码如下:试画出该函数的一个活动记录的内容，包括活动记录的每个单元存放什么东西、执行指令时栈顶指针所指的的位置、与活动记录有关的另一个指针所指的位置和地址增长方向。.一个C语言的函数如下：func(c,l)charc;longl;func(c,l

14、);在X86/Linux机器上编译生成的汇编代码如下：.fileparameter.c.version01.01gcc2_compiled.:.text.align4.globlfunc.typefunc,functionfunc:pushl%ebp将老的基地址指针压栈movl%esp,%ebp将当前栈顶指针作为基地址指针subl$4,%esp分配空间movl8(%ebp),%eaxmovb%al,-1(%ebp)movl12(%ebp),%eaxpushl%eaxmovsbl-1(%ebp),%eaxpushl%eaxcallfuncaddl$8,%esp.L1:leave和下一条指令一起完

15、成恢复老的基地址指针，将栈顶ret指针恢复到调用前参数压栈后的位置，并返回调用者.Lfe1:.sizefunc,.Lfe1-func.identGCC:(GNU)egcs-2.91.6619990314/Linux(egcs-1.1.2release)请指出对应源程序第5行的函数调用func(c,l)的汇编指令是哪几条。请说明字符型参数和长整型参数在参数传递和存储分配方面有什么区别。(小于长整型size的整型参数的处理方式和字符型参数的处理方式是一样的。)3一个语言程序及其在某种机器操作系统上的编译结果如下。根据所生成的汇编程序来解释程序中四个变量的作用域、生存期和置初值方式等方面的区别。编译

16、生成的汇编代码如下：是静态外部变量，而是外部变量，它们都分配在静态数据区（由伪指令开始），但是由伪指令指明为全局的，用来解决其它文件中对的外部引用，而只能由本文件引用。是静态局部变量，同和一样，它的生存期是整个程序并分配在静态数据区。由于在源程序中的作用域是函数的体，而在目标文件中，它的作用域至少已是整个文件了，为避免同源文件中外部变量和其它函数的静态局部变量的名字冲突，所以要对它进行改名，成了.由于不是全局的，因此前面没有伪指令。是自动变量，其作用域是函数的体，其生存期是该函数激活期间，因此它分配在栈区，并且置初值是用运行时的赋值来实现。4语言是一种类型语言，但它不是强类型语言，因为编译时的

17、类型检查不能保证所接受的程序没有运行时的类型错误。例如，编译时的类型检查一般不能保证运行时没有数组越界。请你再举一个这样的例子说明语言不是强类型语言。例如联合体的类型检查一般也不可能在编译时完成，虽然下面例子是可静态判断类型错误的。unionUintu1;int*u2;u;intp;u.u1=10;p=u.u2;p=0;5下面程序在工作站上运行时陷入死循环，试说明原因。如果将第行的改成t并且将第行改成后，中的循环体执行一次便停止了。试说明原因。main()addr();loop();long*p;loop()longi,j;j=0;for(i=0;i10;i+)(*p)-;j+;addr()longk;k=0;p=&k;面程序的结果是12面程序的结果是12。0但是如果把第10行的改(成1)1的话，则程序结果是，试分析为什么会有这不同的结果。intfact()staticinti=5;if(i=0)return(1);elsei=i-1;return(i+abs(1)*fact();ma