《编译原理》课后复习题集

《编译原理》复习题集1．名词解释短语句柄文法上下文无关文法LL（1）文法LR（1）文法语法分析无环路有向图(DAG)后缀式语法制导翻译遍局部优化词法分析语法分析语义分析源语言源程序目标语言中间语言（中间表示）2．简答题(1)编译程序和高级语言有什么区别?(2)编译程序的工作分为那几个阶段?(3)简述自下而上的分析方法。(4)目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？(5)何谓优化？按所涉及的程序范围可分为哪几级优化？(6)简述代码优化的目的和意义。3．叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图。(1|01)*0*4．Pascal语言无符号数的正规定义如下：numdigit+(.digit+)?(E(+|-)?digit+)?其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。5．画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。6．用状态转换图表示接收(a|b)aa的确定的有限自动机。7．处于/*和*/之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。8．某操作系统下合法的文件名为device:name.extension其中第一部分（device:）和第三部分（.extension）可缺省，device,name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。9．构造一个DFA，它接受0,1上0和1的个数都是偶数的字符串。10．设有非确定的有自限动机NFAM=({A，B，C}，{0，1}，δ，{A}，{C})，其中：δ(A，0)={C}δ(A，1)={A，B}δ(B，1)={C}δ(C，1)={C}。请画出状态转换距阵和状态转换图。11．设L{a,b,c}*是满足下述条件的符号串构成的语言：(1)若出现a，则其后至少紧跟两个c；(2)若出现b，其后至少紧跟一个c。试构造识别L的最小化的DFA，并给出描述L的正规表达式。12．写出字母表∑={a,b}上语言L={w|w的最后两个字母是aa或bb}的正规式，并画出接受该语言的最简DFA。13．有穷自动机M接受字母表∑＝{0,1}上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。请写出与M等价的正规式。14．有正规式b*abb*(abb*)*，(1)构造该正规式所对应的NFA(画出状态转换图)。(2)将所求的NFA确定化(画出确定化的状态转换图)。(3)将所求的NFA最小化.(画出最小化后的状态转换图)。15．求出下列文法所产生语言对应的正规式.SbS|aAAaA|bBBaA|bC|bCbS|aA16．给出与下图的NFA等价的正规式。17．把下面的NFA确定化。18．下面两个文法中哪一个不是LR（1）文法？对非LR（1）的那个文法。给出那个有移进－归约冲突的规范的LR（1）项目集。SaAcSaAcAbbA|bAbAb|b19．将下面的DFA化成最简形式。20．为语言L＝{w|w(a|b)*并且在w的任何前缀中，a的个数不少于b的个数写一个LR（1）文法，不准超过6个产生式。21．写一个文法，使其语言是奇数集，且每个奇数不以0开头。22．考查文法G(s):S→(T)|a+S|aT→T,S|S(1)消除文法的左递归；(2)提取公共左因子；(3)对每个非终结符，写出不带回朔的递归子程序。23．设文法G(S)：S→(L)|aS|aL→L，S|S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。24．消除下列文法的左递归.SSaP|Sf|PPQbP|QQcSd|e25．已知文法G：AaABe|aBBb|d给出与上述文法等价的LL(1)文法G'。26．已知文法G[A]：A→aAB|aB→Bb|d（1）构造与G[A]等价的LL(1)文法；（2）构造G’[A]的预测分析表。27．程序的文法如下：PDDD;D|id:T|procid;D;S（1）写一个语法制导定义，打印该程序一共声明了多少个id。（2）写一个翻译方案，打印该程序每个变量id的嵌套深度。28．构造下面文法的LL（1）分析表。DTLTint|realLidRR,idR|29．考虑下文法：DTVTint｜floatVid,V|ida.在该文法中提取左公因子。b.为所得文法的非终结符构造First和Follow集合。c.说明所得的文法是LL(1)文法。d.为所得文法构造LL(1)分析表。e.假设有输入串intx,y,z写出相应LL(1)分析程序的动作。30．说明如下文法是否是LL（1）文法，若不是，将其转换为LL（1）文法。最后给出该文法的LL（1）分析表。ABeBBb|a31．设有文法：P→beginXYendX→Xd;X→d;Y→Y;sY→s(1)该文法含有左递归吗？若有，消除它。(2)改造后的文法是LL(1)文法吗？若是，给出其预测分析表。(3)写出句子begind；send的分析过程。32．已给文法G[S]：S→SaP|Sf|PP→qbP|q将G[S]改造成LL（1）文法，并给出LL（1）分析表。33．设文法G(S)：S→(L)|aS|aL→L，S|S(1)消除左递归和回溯；(2)计算每个非终结符的FIRST和FOLLOW；(3)构造预测分析表。34．给定文法G[S]：S→Aa|dAb|Bb|dBaA→cB→c构造文法G[S]的LR（1）分析表。35．已知文法G(S)S→a|∧|(T)T→T，S|S写出句子((a，a)，a)的规范归约过程及每一步的句柄。36．已知文法G(E)E→T|E＋TT→F|T*FF→(E)|i给出句型(T*F＋i)的最右推导及画出语法树；37．说明下面的文法不是SLR(1)文法，并重写一个等价的SLR(1)文法。SMa|bMc|dc|bdaMdS’SSMa|bMc|dc|bdaMd因为a是M的后继符号之一，因此在上面最右边一个项目集中有移进归约冲突。等价的SLR(1)文法是Sda|bdc|dc|bda38．在PASCAL语言中，简单类型的变量的声明例举如下：m,n:integerp,q,r:real为这样的声明写一个LR（1）文法（为简单起见，变量标识符都用id表示），并根据你的文法写一个语法制导定义（或叫做为你的文法加上语义动作），它将变量的类型填入符号表。39．一个非LR（1）的文法如下：LMLb|aM请给出所有有移进－归约冲突的LR（1）项目集，以说明该文法确实不是LR（1）的。40．若有文法G(S)的产生式如下：SL=RSRL*RLiRL,构造识别所有项目集规范族的DFA.，判断该文法是否是SLR(1)文法，说明理由。41．现有句型bl和产生式Ab，分别指出LL（1）方法和LR（1）方法在扫描到此句型的什么位置决定用此产生式？42．为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号（即值大于零还是小于零）记录在属性E.sign中（属性值分别用POS或NEG表示）。你可以假定所有的整数都不为零，这样就不用担心零的符号。EE*E|+E|E|unsigned_integer43．一个文法如下：S(S)Sa请给出该文法中对活前缀(((有效的LR(1)项目。44．为下面文法添加语义规则（或叫动作子程序），输出S产生的二进制数的值，如输入是101时，输出5。SSSSB|BB0|145．写出表达式(a＋b*c)/(a＋b)－d的逆波兰表示及三元式序列。46．把表达式-(a+b)*(c+d)+(a+b+c)翻译成三地址码序列。47．设布尔表达式的文法为E→E1∨E2E→E1∧E2E→i假定它们将用于条件控制语句中，请(1)改写文法，使之适合进行语法制导翻译；(2)写出改写后的每个产生式的语义动作。48．将语句if(A<XB>0)while(C>0)C=C+D;翻译成三地址码序列。49．设有基本块如下：T1=S+RT2=3T3=12/T2T4=S/RA=T1-T4T5=S+RB=T5T6=T5*T3B=T6(1)画出中间代码的流图；(2)设A、B是出基本块后的活跃变量，请给出优化后的三地址码序列。50．设已构造出文法G(S)：(1)SBB(2)BaB(3)Bb的LR分析表如下ACTIONGOTO状态ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。51．给出活动记录空间结构。并给出各部分的存储对象。52．将下面程序段翻译成四元式序列。while(A<C∧B<D){if(A==1)C=C+1;elsewhile(A<D){A=A+2;}}53．有一语法制导翻译如下所示：S→bAb{print(“1”)}A→(B{print(“2”)}A→a{print(“3”)}B→Aa){print(“4”)}若对输入序列b(((aa)a)a)b进行自底向上分析，请写出输出序列。54．画出IFa>0THENx:=x+1ELSEx:=4*(x-1)的翻译方案图。55．下面是一个C语言程序：main(){longi;longa[0][4];longj;i=4;j=8;printf(“%d,%d\n”,sizeof(a),a[0][0]);}虽然出现longa[0][4]这样的声明，在X86/Linux机器上该程序还是能通过编译并生成目标代码。请回答下面两个问题：（1）sizeof(a)的值是多少，请说明理由。（2）a[0][0]的值是多少，请说明理由。（1）按照数组size的计算公式，sizeof(a)的值一定是0。（2）a[0][0]的值是4。虽然a的size是0，但它仍然有起始地址，并且a[0][0]的地址等于a的起始地址。由于X86/Linux机器上，活动记录栈向低地址方向增长，另外由于低地址放低位字节，因此a[0][0]的地址和i的地址一致，其值和i的值一样，等于4。56．将下面的条件语句表示成三地址码序列：if(a>b)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（1）在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。（2）画出该代码的控制流图，每个基本块就用（1）的序号表示。（3）若有循环的话，列出构成每个循环的结点。（1）（2）b:=1b:=2ifw<=xgotoL2（1）e:=bgotoL2（2）L1:gotoL3（3）L2:c:=3b:=4c:=6（4）L3:ify<=zgotoL4（5）gotoL5（6）L4:g:=g+1h:=8gotoL1（7）L5:h:=9（8）（3）结点5、7和3构成一个循环，其中5是入口结点。58．一个C语言程序如下：func(i1,i2,i3)longi1,i2,i3;{longj1,j2,j3;printf("Addressesofi1,i2,i3=%o,%o,%o\n",&i1,&i2,&i3);printf("Addressesofj1,j2,j3=%o,%o,%o\n",&j1,&j2,&j3);}main(){longi1,i2,i3;func(i1,i2,i3);}该程序在SUN工作站上的运行结果如下：Addressesofi1,i2,i3=35777773634,35777773640,35777773644Addressesofj1,j2,j3=35777773524,35777773520,35777773514从上面的结果可以看出，func函数的3个形式参数的地址依次升高，而3个局部变量的地址依次降低。试说明为什么会有这个区别。由于实参表达式是反序进入活动记录，而局部变量是顺序在活动记录中分配。59．一个C语言程序如下：voidfun(struct{intx;doubler;}val){}main(){struct{intx;doubler;}val;fun(val);}该程序在X86/Linux机器上的用cc命令编译时，报告的错误信息如下：1:warning:structuredefinedinsideparms1:warning:anonymousstructdeclaredinsideparameterlist1:warning:itsscopeisonlythisdefinitionordeclaration,1:warning:whichisprobablynotwhatyouwant.7:incompatibletypeforargument1of‘fun’请问，报告最后一行的错误的原因是什么？如何修改程序，使得编译时不再出现这个错误信息。60．一个C语言程序如下：main(){func();printf("Returnfromfunc\n");}func(){chars[4];strcpy(s,"12345678");printf("%s\n",s);}该程序在PC机linux操作系统上的运行结果如下：12345678Segmentationfault(coredumped)试分析为什么会出现这样的运行错误。61．一个C语言函数如下：func(i)longi;{longj;j=i-1;func(j);}该函数在PC机linux操作系统上编译生成的汇编代码如下：.file"stack.c"gcc2_compiled.:__gnu_compiled_c:.text.align2.globl_func.type_func,@function_func:pushl%ebpmovl%esp,%ebpsubl$4,%espmovl8(%ebp),%edxdecl%edxmovl%edx,-4(%ebp)movl-4(%ebp),%eaxpushl%eaxcall_funcaddl$4,%espL1:leaveretLfe1:.size_func,Lfe1-_func试画出该函数的一个活动记录的内容，包括活动记录的每个单元存放什么东西、执行movl8(%ebp),%edx指令时栈顶指针所指的的位置、与活动记录有关的另一个指针所指的位置和地址增长方向。62．一个C语言的函数如下：func(c,l)charc;longl;{func(c,l);}在X86/Linux机器上编译生成的汇编代码如下：.file"parameter.c".version"01.01"gcc2_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——和下一条指令一起完成恢复老的基地址指针，将栈顶ret——指针恢复到调用前参数压栈后的位置，并返回调用者.Lfe1:.sizefunc,.Lfe1-func.ident"GCC:(GNU)egcs-2.91.6619990314/Linux(egcs-1.1.2release)"(a)请指出对应源程序第5行的函数调用func(c,l)的汇编指令是哪几条。(b)请说明字符型参数和长整型参数在参数传递和存储分配方面有什么区别。（小于长整型size的整型参数的处理方式和字符型参数的处理方式是一样的。）63．一个C语言程序及其在某种机器linux操作系统上的编译结果如下。根据所生成的汇编程序来解释程序中四个变量的作用域、生存期和置初值方式等方面的区别。staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}编译生成的汇编代码如下：.file"static.c".version"01.01"gcc2_compiled.:.data.align4.typeaa,@object.sizeaa,4aa:.long10.globlbb.align2.typebb,@object.sizebb,2bb:.value20.align4.typecc.2,@object.sizecc.2,4cc.2:.long30.text.align4.globlfunc.typefunc,@functionfunc:pushl%ebpmovl%esp,%ebpsubl$4,%espmovw$40,-2(%ebp).L1:leaveret.Lfe1:.sizefunc,.Lfe1-func.ident"GCC:(GNU)egcs-2.91.6619990314/Linux(egcs-1.1.2release)"aa是静态外部变量，而bb是外部变量，它们都分配在静态数据区（由.data伪指令开始），但是bb由伪指令.globl指明为全局的，用来解决其它文件中对bb的外部引用，而aa只能由本文件引用。cc是静态局部变量，同aa和bb一样，它的生存期是整个程序并分配在静态数据区。由于cc在源程序中的作用域是函数func的体，而在目标文件中，它的作用域至少已是整个文件了，为避免同源文件中外部变量和其它函数的静态局部变量的名字冲突，所以要对它进行改名，成了cc.2。由于cc不是全局的，因此cc.2前面没有伪指令.globl。dd是自动变量，其作用域是函数func的体，其生存期是该函数激活期间，因此它分配在栈区，并且置初值是用运行时的赋值来实现。64．C语言是一种类型语言，但它不是强类型语言，因为编译时的类型检查不能保证所接受的程序没有运行时的类型错误。例如，编译时的类型检查一般不能保证运行时没有数组越界。请你再举一个这样的例子说明C语言不是强类型语言。例如联合体的类型检查一般也不可能在编译时完成，虽然下面例子是可静态判断类型错误的。unionU{intu1;int*u2;}u;intp;u.u1=10;p=u.u2;p=0;65．下面程序在SUN工作站上运行时陷入死循环，试说明原因。如果将第8行的long