编译原理考试试卷.doc

一、 填空题（每空2分，共30分）1、编译程序的整个过程可以从逻辑上划分为词法分析、 语法分析 、语义分析、中间代码生成、 代码优化 和目标代码生成等几个阶段，另外还有两个重要的工 作是 表格管理 和出错处理2、规范规约中的可归约串是 句柄 ，算符优先分析中的可归约串是 最左素短语 。3、语法分析方法主要可分为 自顶向下 和 自底向上 两大类。4、LR(0）文法的项目集中不会出现 移进归约 冲突和 归约-归约 冲突。5、数据空间的动存态储分配方式可分为 栈式 和 堆式 两种.6、编译程序是指能将 源语言 程序翻译成 目标语言 程序的程序。7、确定有穷自动机DFA是 NFA 的一个特例。8、表达式 （a+b)*c 的逆波兰表示为 ab+c 。二、 选择题（每题2分,共20分）1、L R语法分析栈中存放的状态是识别 B 的DFA状态。A、前缀 B、可归前缀 C、项目 D、句柄2、 D 不可能是目标代码。A、汇编指令代码 B、可重定位指令代码 C、绝对机器指令代码 D、中间代码3、一个控制流程图就是具有 C 的有向图A、唯一入口结点 B、唯一出口结点 C、唯一首结点 D、唯一尾结点4、设有文法GS：SbbBBbS，则该文法所描述的语言是 C 。A、L（G）=bii0 B、L（G)=b2i|i0 C、L（G)=b2i+1|i0 D、L(G)=b2i+1i15、把汇编语言程序翻译成机器可执行的目标程序的工作是由 B 完成的。A、编译器 B、汇编器 C、解释器 D、预处理器6、在目标代码生成阶段,符号表用于 D 。A、目标代码生成 B、语义检查 C、语法检查 D、预处理器地址分配07、规范归约是指 B 。A、最左推导的逆过程 B、最右推导的逆过程 C、规范推导 D、最左归约逆过程8、使用 A 可以定义一个程序的意义。A、语义规则 B、词法规则 C、语法规则 D、左结合规则9、经过编译所得到的目标程序是 D 。A、三元式序列 B、四元式序列 C、间接三元式 D、机器语言程序或汇编语言程序10、在一个基本块内进行的代码优化是 B .A、全局优化 B、局部优化 C、循环优化 D、代码外提三、简答题（3小题,共30分）1、已知文法GS：SAc|aBAab Bbc证明该文法具有二义性（本题6分）证明：因为该文法的句型abc存在如下两棵语法树:所以,该文法具有二义性一、 填空题（每空1分，共20分）1编译过程一般分为 、 、中间代码生成、 和目标代码生成五个阶段。2语法分析最常用的两类方法是 和 分析法。3确定的有穷自动机是一个 ,通常表示为 。4所谓最右推导是指 。5语法分析器的任务是 。6如果一个文法的任何产生式的右部都不含有 的非终结符，则这种文法称为 文法。7进行确定的自上而下语法分析要求语言的文法是无 和 的.8LR分析法是一种 的语法分析方法。9根据优化对象所涉及的程序范围，代码优化分为 、 和 等。10常用的优化技术包括: 、 、强度削弱、复写传播、 等。二、 是非题（下列各题，你认为正确的,请在题后的括号内打“ ”，错的打“”。每题2分,共20分）1正规文法产生的语言都可以用上下文无关文法来描述。 ( )2仅考虑一个基本块,不能确定一个赋值是否真是无用的。( ）3如果一个文法是递归的，则其产生的语言的句子是无穷个。 （ ）4四元式之间的联系是通过符号表实现的.（ ）5文法的二义性和语言的二义性是两个不同的概念。 （ )6一个LL（ l）文法一定是无二义的。 （ ）7在规范规约中用最左素短语来刻划可归约串。 （ ）8目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。 ( ）9编译程序是对汇编程序的翻译。 ( ）三、 简答题（每题5分，共15分）1、简述栈式存储管理策略； 2、何谓DAG; 3、何谓文法的二义性；四、 给出下述文法对应的正规式 （7分） S 0A| 1BA1S | 1B0S | 0五、 已知文法G（E）：ET | E+T ETTF | TF T/FF（E) i证明E+T*F是该文法的一个句型，并指出该句型的所有短语、直接短语和句柄。（8分）七、 设有文法GE：E (E) 试判断该文法是否为SLR（1）文法,若不是，请说明理由;若是请构造SLR（1)分析表。(10分) 参考答案 一、填空题（1X20=20分)1 词法分析、语法分析、代码优化2 自上而下、自下而上3 五元组、DFA=（K ， M， S, Z）4 任何一步都是对中最右非终结符进行替换5 分析一个文法的句子结构6 相邻、算符7 左递归、公共左因子8 自下而上9 局部优化、循环优化、局部优化10 删除公共子表达式、代码外提、变换循环控制条件、合并已知量、删除无用赋值（任选3个） 二、是非题(2X10=20分） 1、 2、 3、 4、 5、 6、 7、 8、 9、 10、 三、简答题(见书中相应部分）(5X3=15分)四、解：首先得正规式方程组： S=0A+1B A=1S+1 B=0S+0 求解该方程组得：S=(0110）（01|10) （8分）五、解 （2分） 是文法GS的句型。 短语：E+TF， T*F （2分) 直接短语:TF （2分) 句柄：T*F (2分）六、解：、因为FOLLOW（B)=FIRST(c)FOLLOW（S)=c，#（2分)，所以构造文法GS的LL（1）分析表（5)如下： aBc#SaBcbAB AaAbb B b符号串baabbb是该文法的句子（3分)（分析过程略)。七 （2分) 所以该文法为SLR(1）文法。其分析表如下：(8分)状态ACTIONGOTO（）E0S2r2r211 acc 2S2r2r233 S4 4 r1r1 八、 目标代码为： （10分) LD R0，B SUB R0,C LD R1,A MUL R1,R0 LD R0,D ADD R0，1 ST R1,M LD R1，E SUB R0，F MUL R0,R1 LD R1，M DIV R1，R0 ST R1,W- 3 -