资源描述：
《编译原理套卷11》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、一、单项选择题。（10分）1.一般程序设计语言的定义都涉及B三个方面。①语法②语义③语用④程序基本符号的确定A、①②③B、①②④C、②③④D、①③④2.下面说法正确的是B。A、一个正规式只能对应一个确定的有限状态自动机；B、一个正规语言可能对应多个正规文法；3.程序基本块是指D。A、一个子程序B、一个仅有一个入口和一个出口的语句C、一个没有嵌套的程序段D、一组顺序执行的程序段，仅有一个入口和一个出口。4.词法分析的常用方法有A。A、有穷自动机理论B、图灵机C、图论D、无穷自动机理论5.编译方法中自顶向下的语法分
2、析算法有D。①简单优先分析方法②算符优先分析方法③递归子程序法④LL(K)分析法⑤SLR分析法⑥LR(K)方法⑦LALR(K)方法⑧预测分析方法A、①②③⑧B、④⑤⑥⑦C、①②⑤⑥⑦D、③④⑧E、①②③⑤⑥二、填空题（15分）1.编译程序的工作过程一般可以划分为词法分析_、_语法分析_、_语义分析、_中间代码生成、_代码优化_等几个基本阶段，同时还会伴有表格处理和出错处理（6分）。2.在目标代码生成阶段，符号表是地址分配的依据。（2分）。3.符号表的数据结构可以是无序符号表、有序符号表、栈式符号表。4.词法分析
3、阶段的错误主要是单词拼写错误，可通过最小距离匹配的办法纠正错误。5.在大部分现有编译中采用的方案主要有两种：动态分配方案和静态分配方案。三、简答题。（30分）1、什么是规范推导？每个句型都有规范推导吗？规范推导就是最右推导每一个句子都有一个规范推导，而每一个句型则不一定都有规范推导，比如说采用非规范推导得到的句型。2、已知文法G[E]:E→ET+
4、TT→TF*
5、FF→F^
6、a试证：FF^^*是文法的句型，指出该句型的短语、简单短语和句柄。该句型对应的语法树如下：该句型相对于E的短语有FF^^*；相对于T的短语有
7、FF^^*,F;相对于F的短语有F^;F^^;简单短语有F;F^;句柄为F.3、写出表达式w+(a+b)*(c+d/(e-10)+8)的逆波兰表示及三元式序列。(1)（+,a,b）(2)(-,e,10)(3)(/,d,(2))(4)(+,c,(3))(5)(+,(4),8)(6)(*,(1),(5))(7)(+,w,(6))4、何谓优化？按所涉及的程序范围可分为哪几级优化？所谓优化，一般是指为提高目标程序的质量而进行的各项工作，即对程序或中间代码进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。
8、在源程序级在语义动作的设计上在中间代码级在目标代码级5、简述自顶向下分析法。从识别符号出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。从语法树角度看，自顶向下分析过程是以识别符号为根结点，试图向下构造一棵语法树，使其末端结点符号串正好与输入符号串相同。四、已知：（15分）正规式（1）（（a
9、b）*
10、aa）*b正规式（2）（a
11、b）*b试用有限自动机的等价性证明正规式（1）和（2）是等价的。两者化简后的DFA都为：abba五、设文法G(S)：（15分） SàAAàBA
12、εB
13、àaB
14、b(1)证明它是LR(1)文法；(2)构造它的LR(1)分析表；(3)给出输入符号串abab的分析过程。1)拓广文法G’:(0)S'àS(1)SàA(2)AàBA(3)Aàε(4)BàaB(5)BàbFIRST(A)={ε,a,b}FIRST(B)={a,b}构造的DFA如下: 由项目集规范族看出，不存在冲突动作。∴该文法是LR(1)文法。(2)LR(1)分析表状态ActionGotoaB#SAB0S4S5r31231 acc 2 r1 3S4S5r3 634S4S5 75r5r5r5
15、 6 r2 7r4r4r4 (3)输入串abab的分析过程为： 步骤状态栈符号栈当前字符剩余字符串动作(1)0#abab#移进(2)04#abab#移进(3)045#abab#归约Bàb(4)047#aBab#归约BàaB(5)03#Bab#移进(6)034#Bab#移进(7)0345#Bab# 归约Bàb(8)0347#BaB# 归约BàaB(9)033#BB# 归约Aàε(10)0336#BBA# 归约AàBA(11)036#BA# 归约AàBA(12)02#A# 归约SàA(13)01#S#
16、acc六、把语句While a＞0∨b＜0 do Begin X：＝X＋1； ifa＞0thena：＝a－1 elseb：＝b＋1 End；翻译成四元式序列。（15分）100(j>,a,0,104)101(j,_,_,102)102(j<,b,0,104)103(j,_,_,111)104(+,x,1,x)105(j>,a,0,107)106(j,_,_,
