编译原理套卷11.doc

一、单项选择题。（10分）1. 一般程序设计语言的定义都涉及 B 三个方面。语法 语义 语用 程序基本符号的确定A、 B、 C、 D、 2. 下面说法正确的是 B 。 A、一个正规式只能对应一个确定的有限状态自动机； B、一个正规语言可能对应多个正规文法；3. 程序基本块是指 D 。 A、一个子程序 B、一个仅有一个入口和一个出口的语句 C、一个没有嵌套的程序段 D、一组顺序执行的程序段，仅有一个入口和一个出口。4. 词法分析的常用方法有 A 。 A、有穷自动机理论 B、图灵机 C、图论 D、无穷自动机理论5. 编译方法中自顶向下的语法分析算法有 D 。简单优先分析方法算符优先分析方法 递归子程序法 LL(K)分析法 SLR分析法 LR(K)方法LALR(K)方法 预测分析方法A、 B、 C、 D、 E、二、填空题 （15分）1. 编译程序的工作过程一般可以划分为词法分析_、_语法分析_、_语义分析、_中间代码生成、_代码优化_等几个基本阶段，同时还会伴有表格处理 和 出错处理（6分）。 2. 在目标代码生成阶段，符号表是 地址分配 的依据。（2分）。3. 符号表的数据结构可以是无序符号表、有序符号表 、栈式符号表 。4. 词法分析阶段的错误主要是 单词拼写错误 ，可通过最小距离匹配的办法纠正错误。5. 在大部分现有编译中采用的方案主要有两种： 动态 分配方案和 静态 分配方案。三、简答题。（30分） 1、什么是规范推导？每个句型都有规范推导吗？规范推导就是最右推导每一个句子都有一个规范推导，而每一个句型则不一定都有规范推导，比如说采用非规范推导得到的句型。2、已知文法GE: EET+|T TTF* | F FF | a 试证：FF*是文法的句型，指出该句型的短语、简单短语和句柄。该句型对应的语法树如下：该句型相对于E的短语有FF*；相对于T的短语有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、何谓优化？按所涉及的程序范围可分为哪几级优化？所谓优化，一般是指为提高目标程序的质量而进行的各项工作，即对程序或中间代码进行各种等价变换，使得从变换后的程序出发，能生成更有效的目标代码。 在源程序级 在语义动作的设计上 在中间代码级 在目标代码级5、简述自顶向下分析法。从识别符号出发，不断建立直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。从语法树角度看，自顶向下分析过程是以识别符号为根结点，试图向下构造一棵语法树，使其末端结点符号串正好与输入符号串相同。四、已知： （15分）正规式（1）（a|b）* |aa）*b正规式（2）（a|b）*b试用有限自动机的等价性证明正规式（1）和（2）是等价的。两者化简后的DFA都为：a b b a五、设文法G(S)：（15分） S A A BA | B aB | 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 b FIRST(A) = , a, b FIRST(B) = a, b 构造的DFA如下:由项目集规范族看出，不存在冲突动作。 该文法是LR(1)文法。 (2) LR(1)分析表 状态 ActionGoto a B # S A B 0 S4 S5 r3 1 2 3 1 acc 2 r1 3 S4 S5 r3 6 3 4 S4 S5 7 5 r5 r5 r5 6 r2 7 r4 r4 r4 (3)输入串abab的分析过程为： 步骤 状态栈 符号栈 当前字符 剩余字符串 动作 (1) 0 # a bab# 移进 (2) 04 #a b ab# 移进 (3) 045 #ab a b# 归约 Bb (4) 047 #aB a b# 归约 BaB (5) 03 #B a b# 移进 (6) 034 #Ba b # 移进 (7) 0345 #Bab # 归约 Bb (8) 0347 #BaB # 归约 BaB (9) 033 #BB # 归约 A (10) 0336 #BBA # 归约 ABA (11) 036 #BA # 归约 ABA (12) 02 # A # 归约 SA (13) 01 #S # acc 六、把语句Whilea0 b0do Begin X：X1； if a0 then a：a1 else b：b1 End； 翻译成四元式序列。（15分）100(j,a,0,104)1