《编译原理大题集合.doc》由会员分享，可在线阅读，更多相关《编译原理大题集合.doc（35页珍藏版）》请在金锄头文库上搜索。
1、1. 简要说明语义分析的基本功能。答：语义分析的基本功能包括: 确定类型、类型检查、语义处理和某些静态语义检 查。2. 考虑文法 GS: S (T) | a+S | a T T,S | S 消除文法的左递归及提取公共左因子。解：消除文法GS的左递归： S(T) | a+S | a TST T,ST| 提取公共左因子： S(T) | aS S+S | TST T,ST| 3. 试为表达式 w+(a+b)*(c+d/(e-10)+8) 写出相应的逆波兰表示。解： w a b + c d e 10 - / + 8 + * +4. 按照三种基本控制结构文法将下面的语句翻译成四元式序列：while (A
2、C BD) if (A 1) C=C+1;else while (A D)A=A+2;。解：该语句的四元式序列如下(其中E1、E2和E3分别对应ACBD、A1和AD，并且关系运算符优先级高)： 100 (j,A,C,102) 101 (j,_,_,113) 102 (jaAd|aAb| 判断该文法是否是 SLR(1) 文法，若是构造相应分析表，并对输入串 ab# 给出分析过程。解：增加一个非终结符S/后，产生原文法的增广文法有： S-A A-aAd|aAb| 下面构造它的LR(0)项目集规范族为： 从上表可看出,状态I0和I2存在移进-归约冲突，该文法不是LR(0)文法。对于I0来说有：FOL
3、LOW(A)a=b,d,#a=，所以在I0状态下面临输入符号为a时移进，为b,d,#时归约，为其他时报错。对于I2来说有也有与I0完全相同的结论。这就是说，以上的移进-归约冲突是可以解决的，因此该文法是SLR(1)文法。 其SLR(1)分析表为： 对输入串ab#给出分析过程为： 三、名词解释题：1.局部优化-局限于基本块范围的优化称。2.二义性文法-如果一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义性文法。3.DISPLAY表-过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址。5.最左推导-任何一步=都是对中的最右非终结符替换。6.语法-一组规则，用它可形成和
4、产生一组合式的程序。7.文法-描述语言的语法结构的形式规则。8.基本块-指程序中一顺序执行的语句序列，其中只有一个入口和一个出口，入口就是其中的第一个语句，出口就是其中的最后一个语句。9.语法制导翻译-在语法分析过程中，根据每个产生式所对应的语义子程序进行翻译的办法叫做语法制导翻译。10.短语-令G是一个文法，S划文法的开始符号，假定是文法G的一个句型，如果有SA且A，则称是句型相对非终结符A的短语。11.待用信息-如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值，则称j是四元式i的变量A的待用信息。12.规范句型-由规范推导所得到的句型。13.扫描器-
5、执行词法分析的程序。14.超前搜索-在词法分析过程中，有时为了确定词性，需超前扫描若干个字符。15.句柄-一个句型的最左直接短语。16.语法制导翻译-在语法分析过程中，根据每个产生式所对应的语义程序进行翻译的方法 叫做语法制导翻译。17.规范句型-由规范推导所得到的句型。18.素短语-素短语是指这样一个短语，至少含有一个终结符，并且，除它自身外不再含任何更小的素短语。19.语法-是组规则，用它可形成和产生一个合式的程序。 20.待用信息-如果在一个基本块中，四元式i对A定值，四元式j要引用A值，而从i到j之间没有A的其它定值，则称j是四元式i的变量A的待用信息。21.语义-定义程序的意义的一组
6、规则。四、简答题：1.写一个文法G, 使其语言为 不以0开头的偶数集。2.已知文法G(S)及相应翻译方案SaAb print “1”Sa print “2”AAS print “3”Ac print “4”输入acab, 输出是什么？3. 已知文法G(S)SbAaA(B | aBAa)写出句子b(aa)b的规范归约过程。4. 考虑下面的程序：procedure p(x, y, z)；beginy:=x+y;z:=z*z; end beginA:=2;B:=A*2;P(A, A, B);Print A, B end.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 A, B的值是什么
7、? 5文法G(S)SdABAaA| aBBb| 描述的语言是什么？6. 证明文法G(S) SSaS| 是二义性的。7. 已知文法G(S) SBAABS| dBaA| bS | c的预测分析表如下 a b c d # SSBASBASBA AABSABSABSAd BBaA BbS Bc给出句子 adccd 的分析过程。8. 写一个文法G, 使其语言为 L(G)=albmclanbn| l=0, m=1, n=2 9. 已知文法G(S):Sa| (T)TT,S|S的优先关系表如下：关系a(),a-.(.=.,.请计算出该优先关系表所对应的优先函数表。10. 何谓优化？按所涉及的程序范围可分为哪几
8、级优化？11. 目标代码有哪几种形式？生成目标代码时通常应考虑哪几个问题？12. 一字母表=a, b，试写出上所有以a为首的字组成的正规集相对应的正规式。13. 基本的优化方法有哪几种？14. 写一个文法G, 使其语言为 L(G)=abncn| n015. 考虑下面的程序：procedure p(x, y, z);begin y:=y+z; z:=y*z+xend;begin a:=2; b:=3; p(a+b, b, a); print aend.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么? 16.写出表达式ab*(c-d)/e的逆波兰式和三元序列。17.证明
9、文法G(A) AAA | (A)| 是二义性的。18.令=a,b，则正规式a*b|b*a 表示的正规集是什么？19.何谓DISPLAY表？其作用是什么？20.考虑下面的程序：procedure p(x, y, z)；beginy:=y+2;z:=z+x; end begina:=5;b:=2;p(a+b, a-b, a);print a end.试问，若参数传递的方式分别采用传地址和传值时，程序执行后输出 a的值是什么? 21.写一个文法G, 使其语言为 L(G)=anbncm| n0为奇数， m0为偶数22.写出表达式a:=(b+c)*e+(b+c)/f的逆波兰式和三元序列。23.一个文法G
10、别是LL(1)文法的充要条件是什么？24.已知文法GSSS*aF | aF | *aFF+aF | +a消除文法左递归和提公共左因子。25.符号表的作用是什么？符号表查找和整理技术有哪几种？答案：1.所求文法是GS:SAB |B A0AAD |CB2 |4 |6 |8C1 |3 |5 |7 |9 |BD0 |C2.输出是42313.句子b(aa)b的规范归约过程：步骤符号栈输入串动作0#b(aa)b#预备1#b(aa)b#移进2#b(aa)b#移进3 #b(a a)b# 移进4#b(Aa)b#归约5 #b(Ma)b#移进6#b(Ma)b#移进7#b(B b# 归约8#bAb#归约9#bAb#移
11、进10#S#接受4.传地址 A=6, B=16传值 A=2, B=45.L(G)=danbm |n0, m06.证明： 因为文法GS存在句子aa有两个不同的最左推导，所以文法GS是是二义性的。S=SaS=SaSaS=aSaS=aaS=aa S=SaS=aS=aSaS=aaS=aa7.句子 adccd 的分析过程：步骤符号栈输入串产生式0#Sadccd#1#ABadccd#SBA2#AAaadccd#BaA3#AAdccd#4#Addccd#Ad5#Accd#6#SBccd#ABS7#Scccd# Bc8#S cd# 9#ABcd#Bc10#Acd#11#A d#12#dd#Ad13# 8.所求文法是GS: SAB AaAc | D DbD | bBaBb | aabb9.函数a(),f4244g552310.优化：对程序进行各种等价变换，使得从变换后的程序出发，能产生更有效的目标代码。三种级别：局部优化、循环优化、全局优化11.目标代码通常采用三种形式：机器语言，汇编语言，待装配机器语言模块。应着重考虑的问题： (1)如何使生成的目标代码较短；(2)如何充分利用寄存器，以减少访问内存次数；(3)如何充分利用指
