编译原理复习题集.doc

《编译原理复习题集.doc》由会员分享，可在线阅读，更多相关《编译原理复习题集.doc（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date编译原理复习题集编译原理复习题集编译原理复习题集1名词解释短语句柄文法上下文无关文法LL（1）文法LR（1）文法语法分析无环路有向图(DAG)后缀式语法制导翻译遍局部优化词法分析语法分析语义分析源语言源程序目标语言中间语言（中间表示）2简答题(1) 编译程序和高级语言有什么区别? (2) 编译程序的工作分为那几个阶段? (3) 简述自下而上的分析方法。(4) 目标代码

2、有哪几种形式？生成目标代码时通常应考虑哪几个问题？(5) 何谓优化？按所涉及的程序范围可分为哪几级优化？ (6) 简述代码优化的目的和意义。3叙述下面的正规式描述的语言，并画出接受该语言的最简DFA的状态转换图。( 1 | 01 )* 0*4Pascal语言无符号数的正规定义如下：num digit+ (.digit+)? (E(+|-)? digit+)?其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。5画出Pascal中实数(不带正负号，可带指数部分)的状态转换图。 6用状态转换图表示接收(a|b)*aa的确定的有限自动机。7处于/* 和 */之间的串构成注解，注解中

3、间没有*/。画出接受这种注解的DFA的状态转换图。8某操作系统下合法的文件名为device:name.extension其中第一部分（device:）和第三部分（.extension）可缺省，device, name和extension都是字母串，长度不限，但至少为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* 是满足下述条件的符号串

4、构成的语言： (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) 将所求的 N

5、FA 最小化. (画出最小化后的状态转换图)。15求出下列文法所产生语言对应的正规式. SbS|aA AaA|bB BaA|bC|b CbS|aA 16给出与下图的NFA等价的正规式。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、6个产生式。21写一个文法，使其语言是奇数集，且每个奇数不以0开头。 22考查文法G(s): S( T ) | 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消除下列文法的左递归. SSaP|Sf|P PQbP|Q QcSd|e 25已知文法 G ：AaABe|a BBb|d 给出与上述文法等价的 LL(1)文法 G。26已知文法GA：A aA

7、B | a B Bb | d（1）构造与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. 为所得文法的非终结符构造First和Follow集合。c. 说明所得的文法是LL(1)

8、文法。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的分析过程。32已给文法 GS ： S SaP | Sf | P P qbP | q 将 GS 改造成 LL （ 1 ）

9、文法，并给出 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(E)|i 给出句型(T *Fi)的最右推导及画出语法树； 37说明下面的文法不是SLR(1)文法，并重写一个等价的S

10、LR(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 .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）文法（为简单起见，变

11、量标识符都用id表示），并根据你的文法写一个语法制导定义（或叫做为你的文法加上语义动作），它将变量的类型填入符号表。39一个非LR（1）的文法如下：L MLb | aM e请给出所有有移进归约冲突的LR（1）项目集，以说明该文法确实不是LR（1）的。40若有文法 G(S)的产生式如下：SL=R SR L*R Li RL,构造识别所有项目集规范族的 DFA.，判断该文法是否是 SLR(1)文法，说明理由。 41现有句型g ba lb 和产生式A ba，分别指出LL（1）方法和LR（1）方法在扫描到此句型的什么位置决定用此产生式？42为下面的算术表达式文法写一个语法制导的翻译方案，它将每个子表达式

12、E的符号（即值大于零还是小于零）记录在属性E.sign中（属性值分别用POS或NEG表示）。你可以假定所有的整数都不为零，这样就不用担心零的符号。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设布尔表达式

13、的文法为 E E1E2 E E1E2 E i 假定它们将用于条件控制语句中，请 (1)改写文法，使之适合进行语法制导翻译； (2)写出改写后的每个产生式的语义动作。 48将语句 if (A0) while ( C0 ) 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 b的LR分析表如下ACTIONGOTO状态a

14、b#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。51给出活动记录空间结构。并给出各部分的存储对象。52将下面程序段翻译成四元式序列。while( ACBD )if ( A=1) C=C+1 ; else while ( A0 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

15、(a), a00);虽然出现long a04这样的声明，在X86/Linux机器上该程序还是能通过编译并生成目标代码。请回答下面两个问题：（1）sizeof(a)的值是多少，请说明理由。（2）a00的值是多少，请说明理由。（1）按照数组size的计算公式，sizeof(a)的值一定是0。（2）a00的值是4。虽然a的size是0，但它仍然有起始地址，并且a00的地址等于a的起始地址。由于X86/Linux机器上，活动记录栈向低地址方向增长，另外由于低地址放低位字节，因此a00的地址和i的地址一致，其值和i的值一样，等于4。56将下面的条件语句表示成三地址码序列： if ( ab ) x=a+b

16、*c ; else x=b-a; 57考虑下面的三地址语句序列：b := 1b := 2if w = x goto L2e := bgoto L2L1:goto L3L2:c := 3b := 4c := 6L3:if y = z 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

17、:= 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 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,

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

19、(struct int x; double r; val) main()struct int x; double r; 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

20、 not what you want.7: incompatible type for argument 1 of fun 请问，报告最后一行的错误的原因是什么？如何修改程序，使得编译时不再出现这个错误信息。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

21、(i)long i;long j;j=i-1;func(j);该函数在PC机linux操作系统上编译生成的汇编代码如下：.filestack.cgcc2_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:

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

23、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.identGCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1

24、.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;编译生成的汇编代码如下：.filestatic.c.

25、version01.01gcc2_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,%ebpsubl $4,%espmovw $40,-2(%ebp).L1:leaveret.Lfe1:.

26、size func,.Lfe1-func.identGCC: (GNU) egcs-2.91.66 19990314/Linux (egcs-1.1.2 release)aa是静态外部变量，而bb是外部变量，它们都分配在静态数据区（由.data伪指令开始），但是bb由伪指令.globl指明为全局的，用来解决其它文件中对bb的外部引用，而aa只能由本文件引用。cc是静态局部变量，同aa和bb一样，它的生存期是整个程序并分配在静态数据区。由于cc在源程序中的作用域是函数func的体，而在目标文件中，它的作用域至少已是整个文件了，为避免同源文件中外部变量和其它函数的静态局部变量的名字冲突，所以要对它

27、进行改名，成了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.

28、u2;*p = 0;65下面程序在SUN工作站上运行时陷入死循环，试说明原因。如果将第8行的long *p改成short *p，并且将第23行long k 改成short k后，loop中的循环体执行一次便停止了。试说明原因。main()addr();loop();long *p;loop()long i,j;j=0;for(i=0;i10;i+)(*p)-;j+;addr()long k;k=0;p=&k;66下面程序的结果是120。但是如果把第10行的abs(1)改成1的话，则程序结果是1，试分析为什么会有这不同的结果。int fact()static int i=5;if(i=0) re

29、turn(1);else i=i-1;return(i+abs(1)*fact();main()printf(factor of 5 = %dn, fact();67一个C语言函数如下：main()int i,j,k;i=5;j=1;while(j100)k=i+1;j=j+k;经优化编译后，生成的代码如下：.file“optimize.c” gcc2_compiled.:_gnu_compiled_c:.text.align 2.globl _func.type_func,function _func:pushl %ebpmovl %esp,%ebpmovl $1,%eaxmovl $6,%

30、edx.align 2,0x90L4:addl %edx,%eaxcmpl $99,%eaxjle L4leaveretLfe1:.size_func,Lfe1-_func试说明编译器对这个程序作了哪些种类的优化（只需要说复写传播、删除公共子表达式等，不需要说怎样完成这些优化的）。68对下面的流程图，假定各基本块出口之后的活跃变量均为a、b、f，循环中可用作固定的寄存器为R0、R1，则将R0、Rl固定分配给循环中哪两个变量，可使执行代价节省得最多?写出分析过程。 69. Pascal语言的repeat -until语句的语法形式为 S repeat S1 until E其语义解释为：假真S1的代码E的代码请按如下要求构造该语句的翻译模式： (1) 写出适合语法制导翻译的产生式； (2) 写出每个产生式对应的语义动作。-