编译原理题库

Tiange'sreference1第一章什么是编译器？编译程序的结构分为几个阶段，各阶段的任务是什么？遍、编译前端及编译后端的含义？编译程序的生成方式有哪些？第二章1.写一文法，使其语言是偶正整数的集合。要求：（1）允许0打头（2）不允许0打头解：（1）允许0开头的偶正整数集合的文法E→NT|DT→NT|DN→D|1|3|5|7|9D→0|2|4|6|8（2）不允许0开头的偶正整数集合的文法E→NT|DT→FT|GN→D|1|3|5|7|9D→2|4|6|8F→N|0G→D|02.证明下述文法G［〈表达式〉］是二义的。〈表达式〉∷=a|(〈表达式〉)|〈表达式〉〈运算符〉〈表达式〉〈运算符〉∷=+|-|*|/解：可为句子a+a*a构造两个不同的最右推导:最右推导1〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉a〈表达式〉*a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a最右推导2〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉〈表达式〉〈表达式〉〈运算符〉〈表达式〉〈运算符〉a〈表达式〉〈运算符〉〈表达式〉*a〈表达式〉〈运算符〉a*a〈表达式〉+a*aa+a*a3.给出生成下述语言的上下文无关文法：（1）{anbnambm|n，m=0}（2）{1n0m1m0n|n，m=0}解：（1）{anbnambm|n，m=0}S→AAA→aAb|εTiange'sreference2(2){1n0m1m0n|n，m=0}S→1S0|AA→0A1|ε第三章1、构造一个DFA，它接收∑={a,b}上所有满足下述条件的字符串：字符串中的每个a都有至少一个b直接跟在其右边。解：已知∑={a,b}，根据题意得出相应的的正规式为：(b*abb*)*根据正规式画出相应的DFAM，如下图所示用子集法将其确定化IIaIb{X,1,2,3,Y}{4}{2,3}{4}—{5,6,1,2,3,Y}{2,3}{4}{2,3}{5,6,1,2,3,Y}{4}{6,1,2,3,Y}{6,1,2,3,Y}{4}{6,1,2,3,Y}由DFA得状态图用最小化方法化简得：{0}，{1}，{2}，{3,4}，按顺序重新命名DFAM’第四章练习1：文法G[V]：V→N|N[E]E→V|V+EN→i是否为LL(1)文法，如不是，如何将其改造成LL(1)文法。解：LL(1)文法的基本条件是不含左递归和回溯（公共左因子），而G[V]中含有回溯，所以先消IIaIb0121—3212314414XY(b*abb*)*XYb*abb*1XYb123456bba10243aaaabbbbb0312aaabbbTiange'sreference3除回溯得到文法G’[V]：G’[V]：V→NV’V’→ε|[E]E→VE’E’→ε|+EN→i由LL(1)文法的充要条件可证G’[V]是LL(1)文法练习2：有文法G[s]:S→BAA→BS|dB→aA|bS|c(1)证明文法G是LL(1)文法。(2)构造LL(1)分析表。(3)写出句子adccd的分析过程解：(1)一个LL(1)文法的充要条件是：对每一个非终结符A的任何两个不同产生式A→α|β，有下面的条件成立：①FIRST(α)∩FIRST(β)=Φ;②若β*ε,则有FIRST(α)∩FOLLOW(A)=Φ对于文法G[s]:S→BAA→BS|dB→aA|bS|c其FIRST集如下：FIRST(B)={a,b,c};FIRST(A)={a,b,c,d};FIRST(S)={a,b,c}。其FOLLOW集如下：首先，FOLLOW(S)={#};对S→BA有：FIRST(A)\{ε}加入FOLLOW(B),即FOLLOW(B)={a,b,c,d};对A→BS有：FIRST(S)\{ε}加入FOLLOW(B),即FOLLOW(B)={a,b,c,d};对B→aA有：FOLLOW(B)加入FOLLOW(A),即FOLLOW(A)={a,b,c,d};对B→bS有：FOLLOW(B)加入FOLLOW(S),即FOLLOW(S)={#,a,b,c,d};由A→BS|d得：FIRST(BS)∩FIRST(d)={a,b,c}∩{d}=Φ;由B→aA|bS|c得：FIRST(aA)∩FIRST(bS)∩FIRST(c)={a}∩{b}∩{c}=Φ。由于文法G[s]不存在形如β→ε的产生式，故无需求解形如FIRST(α)∩FOLLOW(A)的值。也即，文法G[S]是一个LL(1)文法。(2)由G[s]:S→BAA→BS|dB→aA|bS|c的FIRST(B)={a,b,c};FOLLOW(B)={a,b,c,d};FIRST(A)={a,b,c,d};FOLLOW(A)={a,b,c,d};FIRST(S)={a,b,c}。FOLLOW(S)={#,a,b,c,d}可构造LL(1)预测分析表如下：abcd#SS→BAS→BAS→BAAA→BSA→BSA→BSA→dBB→aAB→bSB→cSS→BAS→BAS→BAAA→BSA→BSA→BSA→dBB→aAB→bSB→cTiange'sreference4(3)在分析表的控制下，句子adccd的分析过程如下：第五章1已知文法G[S]为：S→a|∧|(T)T→T,S|S(1)计算G[S]的FIRSTVT和LASTVT。(2)构造G[S]的算符优先关系表并说明G[S]是否为算符优先文法。(3)给出输入串(a,(a,a))#的算符优先分析过程。解：文法：S→a|∧|(T)T→T,S|S展开为：S→aS→∧S→(T)T→T,ST→S(1)FIRSTVT--LASTVT表非终结符FIRSTVT集LASTVT集S{a∧(}{a∧)}T{a∧(,}{a∧),}(2)算符优先关系表如下:表中无多重入口所以是算符优先（OPG）文法。a∧(),#a∧(),#≮≮≮≮≮≮≮≮≮≯≯≒≯≯≯≯≮≯≯≯≯≯≒栈当前输入符号输入串说明#Sadccd#S→BA#ABadccd#B→aA#AAaadccd##AAdccd#A→d#Addccd##Accd#A→BS#SBccd#B→c#Scccd##Scd#S→BA#ABcd#B→c#Accd##Ad#A→d#dd###分析成功Tiange'sreference5(3)输入串（a,(a,a)）#的算符优先分析过程为：栈当前字符剩余输入串动作##(#(a#(N#(N,#(N,(#(N,(a#(N,(N#(N,(N,#(N,(N,a#(N,(N,N#(N,(N#(N,(N)#(N,N#(N#(N)#N(a,,(a,,a))))))##a,(a,a))#,(a,a))#(a,a))#(a,a))#a,a))#,a))#a))#a))#))#)#)#)####MoveinMoveinReduce:S→aMoveinMoveinMoveinReduce:S→aMoveinMoveinReduce:S→aReduce:T→T,SMoveinReduce:S→(T)Reduce:T→T,SMoveinReduce:S→(T)第六章例1：有文法：S→(L)|aL→L,S|S给此文法配上语义动作子程序(或者说为此文法写一个语法制导定义)，它输出配对括号的个数。如对于句子(a,(a,a))，输出是2。解：加入新开始符号S'和产生式S'→S，设num为综合属性，代表值属性，则语法制导定义如下：产生式语义规则S'→Sprint(S.num)S→(L)S.num:=L.num+1S→aS.num:=0L→L1,SL.num:=L1.num+S.numL→SL.num:=S.num例2：构造属性文法，能对下面的文法，只利用综合属性获得类型信息。D→L,id|LL→TidT→int|real解：属性文法（语法制导）定义：产生式语义规则D→L,idD.type:=L.typeaddtype(id.entry,L.type)D→LD.type:=L.typeL→TidL.type:=T.typeaddtype(id.entry,T.type)T→intT.type:=integerT→realT.type:=realTiange'sreference6第七章例1：给出下面表达式的逆波兰表示(后缀式)：(1)a*(-b+c)(2)if(x+y)*z=0thens:=(a+b)*celses:=a*b*c解：(1)ab-c+*(2)xy+z*0=sab+c*:=sab*c*:=￥（注：￥表示if-then-else运算）例2：请将表达式-(a+b)*(c+d)-(a+b)分别表示成三元式、间接三元式和四元式序列。解：三元式间接三元式(1)(+a,b)间接三元式序列间接码表(2)(+c,d)(1)(+a,b)(1)(3)(*(1),(2))(2)(+c,d)(2)(4)(-(3),/)(3)(*(1),(2))(3)(5)(+a,b)(4)(-(3),/)(4)(6)(-(4),(5))(5)(-(4),(1))(1)(5)四元式(1)(+,a,b,t1)(2)(+,c,d,t2)(3)(*,t1,t2,t3)(4)(-,t3,/,t4)(5)(+,a,b,t5)(6)(-,t4,t5,t6)例3：请将下列语句while(AB)doif(CD)thenX:=Y+Z翻译成四元式解：假定翻译的四元式序列从（100）开始：（100）ifABgoto（102）（101）goto（107）（102）ifCDgoto（104）（103）goto（100）（104）T∶=Y+Z（105）X∶=T（106）goto（100）（107）例4：写出for语句的翻译方案解：产生式动作S→forEdoS1S.begin:=newlabelS.first:=newtempS.last:=newtempS.curr:=newtempS.code:=gen(S.first“:=”E.init)||gen(S.last“:=”E.final)Tiange'sreference7||gen(“if”S.first“”S.last“goto”S.next)||gen(S.curr“:=”S.first)||gen(S.begin“:”)||gen(“if”S.curr“”S.Last“goto”S.next)||S1.code||gen(S.curr:=succ(S.curr))||gen(“goto”S.begin)E→v:=initialtofinalE.init:=initial.placeE.final:=final.place第八章例1：C语言中规定变量标识符的定义可分为extern,externstatic,auto,localstatic和register五种存储类：(1)对五种存储类所定义的每种变量，分别说明其作用域。(2)试给出适合上述存储类变量的内存分配方式。(3)符号表中登记的存储类属性，在编译过程中支持什么样的语义检查。解：(1)extern定义的变量，其作用域是整个C语言程序。externstatic定义的变量，其作用域是该定义所在的C程序文件。auto定义的变量，其作用域是该定义所在的例程。localstatic定义的变量，其作用域是该定义所在的例程。且在退出该例程时，该变量的值仍保留。register定义的变量，其作用域与auto定义的变量一样。这种变量的值，在寄存器有条件时，可存放在寄存器中，以提高运行效率。(2)对extern变量，设置一个全局的静态公共区进行分配。对externstatic变量，为每个C程序文件，分别设置一个局部静态公共区进行分配。对auto和register变量，设定它们在该例程的动态区中的相对区头的位移量。而例程动态区在运行时再做动态分配。对localstatic变量，为每个具有这类定义的例程，分别设置一个内部静态区进行分配。(3)实施标