编译原理复习题集

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

2、号数的正规定义如下：num ® digit+ (.digit+)? (E(+|-)? digit+)?其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。5画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。 6用状态转换图表示接收(a|b)*aa的确定的有限自动机。7处于/* 和 */之间的串构成注解，注解中间没有*/。画出接受这种注解的DFA的状态转换图。8某操作系统下合法的文件名为device:name.extension其中第一部分（device:）和第三部分（.extension）可缺省，device, name和extension都是字母串，

3、长度不限，但至少为1，画出识别这种文件名的确定有限自动机。9构造一个DFA，它接受å=0, 1上0和1的个数都是偶数的字符串。10设有非确定的有自限动机 NFA M=(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

4、| w的最后两个字母是aa或bb的正规式，并画出接受该语言的最简DFA。13有穷自动机M接受字母表0,1上所有满足下述条件的串：串中至少包含两个连续的0或两个连续的1。请写出与M等价的正规式。14有正规式 b*abb*(abb*)* ，(1) 构造该正规式所对应的 NFA(画出状态转换图) 。(2) 将所求的 NFA 确定化(画出确定化的状态转换图)。 (3) 将所求的 NFA 最小化. (画出最小化后的状态转换图)。15求出下列文法所产生语言对应的正规式. SàbS|aA AàaA|bB BàaA|bC|b CàbS|aA 16给出与下图的NFA等价的

5、正规式。S0S1S3S217把下面的NFA确定化。123456101110118下面两个文法中哪一个不是LR（1）文法？对非LR（1）的那个文法。给出那个有移进归约冲突的规范的LR（1）项目集。S ® aAcS ® aAcA ® bbA | bA ® bAb | b0123aababba,b19将下面的DFA化成最简形式。20为语言L w | w Î (a | b)*并且在w的任何前缀中，a的个数不少于b的个数写一个LR（1）文法，不准超过6个产生式。21写一个文法，使其语言是奇数集，且每个奇数不以0开头。 22考查文法G(s): S( T )

6、 | a + S | aTT, S | S(1) 消除文法的左递归；(2) 提取公共左因子；(3) 对每个非终结符，写出不带回朔的递归子程序。23设文法G(S)： S(L)|a S|a LL，S|S (1)消除左递归和回溯； (2)计算每个非终结符的FIRST和FOLLOW； (3)构造预测分析表。 24消除下列文法的左递归. SàSaP|Sf|P PàQbP|Q QàcSd|e 25已知文法 G ：AàaABe|a BàBb|d 给出与上述文法等价的 LL(1)文法 G'。26已知文法GA：A aAB | a B Bb | d（1）构

7、造与GA等价的LL(1)文法；（2）构造GA的预测分析表。27程序的文法如下：P ® DD ® D ; D | id : T | proc id ; D ; S（1）写一个语法制导定义，打印该程序一共声明了多少个id。（2）写一个翻译方案，打印该程序每个变量id的嵌套深度。28构造下面文法的LL（1）分析表。D ® TLT ® int | realL ® id RR ® , id R | e29考虑下文法：D à TVT à int floatV à id , V | ida. 在该文法中提取左公因子。b

8、. 为所得文法的非终结符构造First和Follow集合。c. 说明所得的文法是LL(1)文法。d. 为所得文法构造LL(1)分析表。e. 假设有输入串int x , y , z 写出相应LL(1)分析程序的动作。 30说明如下文法是否是LL（1）文法，若不是，将其转换为LL（1）文法。最后给出该文法的LL（1）分析表。 A à B e B à B b | a 31设有文法：Pbegin XYendXXd;Xd;YY;sYs(1) 该文法含有左递归吗？若有，消除它。(2) 改造后的文法是LL(1)文法吗？若是，给出其预测分析表。(3) 写出句子 begin d；s end的

9、分析过程。32已给文法 GS ： S SaP | Sf | P P qbP | q 将 GS 改造成 LL （ 1 ）文法，并给出 LL （ 1 ）分析表。 33设文法G(S)： S(L)|a S|a LL，S|S (1) 消除左递归和回溯； (2) 计算每个非终结符的FIRST和FOLLOW； (3) 构造预测分析表。 34给定文法 GS ： S Aa|dAb|Bb|dBa A c B c 构造文法 GS 的 LR （ 1 ）分析表。 35已知文法G(S) Sa|(T) TT，S|S 写出句子(a，a)，a)的规范归约过程及每一步的句柄。 36已知文法G(E) ET|ET TF|T *F F

10、(E)|i 给出句型(T *Fi)的最右推导及画出语法树； 37说明下面的文法不是SLR(1)文法，并重写一个等价的SLR(1)文法。S à M a | b M c | d c | b d aM à dS ® S S ® M a | b M c | d c | b d aM ® dS ® .SS ® .M aS ® .b M cS ® . d cS ® . b d aM ® .dS ® b .M cS ® b .d aM ® .dS ® b d

11、.aM ® d .bd因为a是M的后继符号之一，因此在上面最右边一个项目集中有移进-归约冲突。等价的SLR(1)文法是S ® d a | b d c | d c | b d a38在PASCAL语言中，简单类型的变量的声明例举如下：m, n : integerp, q, r : real为这样的声明写一个LR（1）文法（为简单起见，变量标识符都用id表示），并根据你的文法写一个语法制导定义（或叫做为你的文法加上语义动作），它将变量的类型填入符号表。39一个非LR（1）的文法如下：L ® MLb | aM ® e请给出所有有移进归约冲突的LR（1）项目集，

12、以说明该文法确实不是LR（1）的。40若有文法 G(S)的产生式如下：SàL=R SàR Là*R Lài RàL,构造识别所有项目集规范族的 DFA.，判断该文法是否是 SLR(1)文法，说明理由。 41现有句型g ba lb 和产生式A® ba，分别指出LL（1）方法和LR（1）方法在扫描到此句型的什么位置决定用此产生式？42为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式E的符号（即值大于零还是小于零）记录在属性E.sign中（属性值分别用POS或NEG表示）。你可以假定所有的整数都不为零，这样就不用担心零的符号

13、。E ® E *E | +E | -E | unsigned_integer43一个文法如下： S ® ( S ) S ® a 请给出该文法中对活前缀(有效的LR (1)项目。44为下面文法添加语义规则（或叫动作子程序），输出S¢产生的二进制数的值，如输入是101时，输出5。S¢ ® SS ® S B | BB ® 0 | 145写出表达式(ab*c)/(ab)d的逆波兰表示及三元式序列。 46把表达式- (a+b)*(c+d)+(a+b+c)翻译成三地址码序列。47设布尔表达式的文法为 E E1E2 E E1E2

14、 E i 假定它们将用于条件控制语句中，请 (1)改写文法，使之适合进行语法制导翻译； (2)写出改写后的每个产生式的语义动作。 48将语句 if (A<X Ù B>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) S ® BB (2) B ® aB (3) B®

15、; b的LR分析表如下ACTIONGOTO状态ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。51给出活动记录空间结构。并给出各部分的存储对象。52将下面程序段翻译成四元式序列。while( A<CB<D )if ( A=1) C=C+1 ; else while ( A<D ) A=A+2; 53有一语法制导翻译如下所示：S bAb print(“1”) A (B print(“2”) A a print(“3”) B Aa) p

16、rint(“4”) 若对输入序列b(aa)a)a)b 进行自底向上分析，请写出输出序列。54画出IF a>0 THEN x:=x+1 ELSE x:=4*( x- 1)的翻译方案图。55下面是一个C语言程序：main()long i;long a04;long j;i = 4; j = 8;printf(“%d, %dn”, sizeof(a), a00);虽然出现long a04这样的声明，在X86/Linux机器上该程序还是能通过编译并生成目标代码。请回答下面两个问题：（1）sizeof(a)的值是多少，请说明理由。（2）a00的值是多少，请说明理由。（1）按照数组size的计算公式

17、，sizeof(a)的值一定是0。（2）a00的值是4。虽然a的size是0，但它仍然有起始地址，并且a00的地址等于a的起始地址。由于X86/Linux机器上，活动记录栈向低地址方向增长，另外由于低地址放低位字节，因此a00的地址和i的地址一致，其值和i的值一样，等于4。56将下面的条件语句表示成三地址码序列： if ( a>b ) x=a+b*c ; else x=b-a; 57考虑下面的三地址语句序列：b := 1b := 2if w <= x goto L2e := bgoto L2L1:goto L3L2:c := 3b := 4c := 6L3:if y <= z

18、 goto L4goto L5L4:g := g + 1h := 8goto L1L5:h := 9（1）在该代码中用水平的横线将代码分成基本块，并给每个基本块一个序号。（2）画出该代码的控制流图，每个基本块就用（1）的序号表示。（3）若有循环的话，列出构成每个循环的结点。（1） （2）14237865b := 1b := 2if w <= x goto L2（1）e := bgoto L2（2）L1:goto L3（3）L2:c := 3b := 4c := 6（4）L3:if y <= z goto L4（5）goto L5（6）L4:g := g + 1h := 8goto

19、L1（7）L5:h := 9（8）（3）结点5、7和3构成一个循环，其中5是入口结点。58一个C语言程序如下：func(i1,i2,i3)long i1,i2,i3;long j1,j2,j3; printf("Addresses of i1,i2,i3 = %o,%o,%on",&i1,&i2,&i3);printf("Addresses of j1,j2,j3 = %o,%o,%on",&j1,&j2,&j3);main()long i1,i2,i3;func(i1,i2,i3);该程序在SUN工作站上

20、的运行结果如下：Addresses of i1,i2,i3 = 35777773634,35777773640,35777773644Addresses of j1,j2,j3 = 35777773524,35777773520,35777773514从上面的结果可以看出，func 函数的3个形式参数的地址依次升高，而3个局部变量的地址依次降低。试说明为什么会有这个区别。由于实参表达式是反序进入活动记录，而局部变量是顺序在活动记录中分配。59一个C语言程序如下：void fun(struct int x; double r; val) main()struct int x; double r;

21、 val;fun(val);该程序在X86/Linux机器上的用cc命令编译时，报告的错误信息如下：1: warning: structure defined inside parms1: warning: anonymous struct declared inside parameter list1: warning: its scope is only this definition or declaration,1: warning: which is probably not what you want.7: incompatible type for argument 1 of f

22、un 请问，报告最后一行的错误的原因是什么？如何修改程序，使得编译时不再出现这个错误信息。60一个C语言程序如下：main()func();printf("Return from funcn");func()char s4;strcpy(s,"12345678");printf("%sn",s);该程序在PC机linux操作系统上的运行结果如下：12345678Segmentation fault (core dumped)试分析为什么会出现这样的运行错误。61一个C语言函数如下：func(i)long i;long j;j=i-1;

23、func(j);该函数在PC机linux操作系统上编译生成的汇编代码如下：.file"stack.c"gcc2_compiled.:_gnu_compiled_c:.text.align 2.globl _func.type_func,function_func:pushl %ebpmovl %esp,%ebpsubl $4,%espmovl 8(%ebp),%edxdecl %edxmovl %edx, -4(%ebp)movl -4(%ebp),%eaxpushl %eaxcall _funcaddl $4,%espL1:leaveretLfe1:.size_func,

24、Lfe1-_func试画出该函数的一个活动记录的内容，包括活动记录的每个单元存放什么东西、执行movl 8(%ebp),%edx指令时栈顶指针所指的的位置、与活动记录有关的另一个指针所指的位置和地址增长方向。62一个C语言的函数如下：func(c,l)char c;long l; func(c,l);在X86/Linux机器上编译生成的汇编代码如下：.file"parameter.c".version"01.01"gcc2_compiled.:.text.align 4.globl func.type func,functionfunc:pushl %e

25、bp 将老的基地址指针压栈movl %esp,%ebp 将当前栈顶指针作为基地址指针subl $4,%esp 分配空间movl 8(%ebp),%eaxmovb %al,-1(%ebp)movl 12(%ebp),%eaxpushl %eaxmovsbl -1(%ebp),%eaxpushl %eaxcall funcaddl $8,%esp.L1:leave 和下一条指令一起完成恢复老的基地址指针，将栈顶ret 指针恢复到调用前参数压栈后的位置，并返回调用者.Lfe1:.size func,.Lfe1-func.ident"GCC: (GNU) egcs-2.91.66 19990

26、314/Linux (egcs-1.1.2 release)"(a) 请指出对应源程序第5行的函数调用func(c,l)的汇编指令是哪几条。(b) 请说明字符型参数和长整型参数在参数传递和存储分配方面有什么区别。（小于长整型size的整型参数的处理方式和字符型参数的处理方式是一样的。）63一个C语言程序及其在某种机器linux操作系统上的编译结果如下。根据所生成的汇编程序来解释程序中四个变量的作用域、生存期和置初值方式等方面的区别。static long aa = 10;short bb = 20;func() static long cc = 30; short dd = 40;编

27、译生成的汇编代码如下：.file"static.c".version"01.01"gcc2_compiled.:.data.align 4.type aa,object.size aa,4aa:.long 10.globl bb.align 2.type bb,object.size bb,2bb:.value 20.align 4.type cc.2,object.size cc.2,4cc.2:.long 30.text.align 4.globl func.type func,functionfunc:pushl %ebpmovl %esp,%eb

28、psubl $4,%espmovw $40,-2(%ebp).L1:leaveret.Lfe1:.size func,.Lfe1-func.ident"GCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)"aa是静态外部变量，而bb是外部变量，它们都分配在静态数据区（由.data伪指令开始），但是bb由伪指令.globl指明为全局的，用来解决其它文件中对bb的外部引用，而aa只能由本文件引用。cc是静态局部变量，同aa和bb一样，它的生存期是整个程序并分配在静态数据区。由于cc在源程序中的作用域是函数func

29、的体，而在目标文件中，它的作用域至少已是整个文件了，为避免同源文件中外部变量和其它函数的静态局部变量的名字冲突，所以要对它进行改名，成了cc.2。由于cc不是全局的，因此cc.2前面没有伪指令.globl。dd是自动变量，其作用域是函数func的体，其生存期是该函数激活期间，因此它分配在栈区，并且置初值是用运行时的赋值来实现。64 C语言是一种类型语言，但它不是强类型语言，因为编译时的类型检查不能保证所接受的程序没有运行时的类型错误。例如，编译时的类型检查一般不能保证运行时没有数组越界。请你再举一个这样的例子说明C语言不是强类型语言。例如联合体的类型检查一般也不可能在编译时完成，虽然下面例子是可静态判断类型错误的。union U int u1; int *u2; u;int *p;u.u1 = 10;p = u.u2;*p = 0;65下面程序在SU