2022年完整word版,编译原理试卷及答案.docx
精选学习资料 - - - - - - - - - 学 号东 北 大 学 秦 皇 岛 分 校C、肯定机器指令代码D、中间代码3、一个掌握流程图就是具有C 的有向图班 级装课程名称：编译原理二试卷： B 答案月考试形式：闭卷A 、唯独入口结点B、唯独出口结点C、唯独首结点D、唯独尾结点0 授课专业：运算机科学与技术考试日期：年日试卷：共 2 页4、设有文法GS ：S b|bB BbS ,就该文法所描述的语言是 C ；题号一三四总分A 、L （G）=bi|i 0 B、 L（G）=b2i|i0 C、L（G）=b2i+1|i0 D、L （G）=b2i+1|i1 姓 名得分5、把汇编语言程序翻译成机器可执行的目标程序的工作是由B 完成的；A 、编译器B、汇编器C、说明器D、预处理器阅卷人6、在目标代码生成阶段,符号表用于D ；A 、目标代码生成B、语义检查C、语法检查D、预处理器地址安排一、 填空题 （每空 2 分,共 30 分）装订1、编译程序的整个过程可以从规律上划分为词法分析、语法分析、语义分析、7、规范归约是指B ；中间代码生成、代码优化和目标代码生成等几个阶段,另外仍有两个重要的工A 、最左推导的逆过程B、最右推导的逆过程C、规范推导D、最左归约逆过程线作是理和出错处理；表格管8、使用A 可以定义一个程序的意义；2、规范规约中的可归约串是句柄,算符优先分析中的可归约串是最左素短语；订A 、语义规章B、词法规章C、语法规章D、左结合规章3、语法分析方法主要可分为自顶向下和自底向上两大类；9、经过编译所得到的目标程序是D ；线4、LR（0）文法的项目集中不会显现移进 -归约冲突和归约 -归约冲突；A 、三元式序列B、四元式序列C、间接三元式D、机器语言程序或汇编语言程序内5、数据空间的动态储备安排方式可分为栈式和堆式两种；10、在一个基本块内进行的代码优化是B ；不6、编译程序是指能将源语言程序翻译成目标语言程序的程序；A 、全局优化B、局部优化C、循环优化D、代码外提要7、确定有穷自动机DFA 是NFA 的一个特例；三、简答题 （3 小题,共 30 分）8、表达式a+b*c 的逆波兰表示为ab+c* ；答1、已知 文法 GS ：SAc|aB 二、 挑选题 （每题 2 分,共 20 分）A ab题1、LR 语法分析栈中存放的状态是识别B 的 DFA 状态；Bbc 证明该文法具有二义性（此题 6 分）A、前缀B、可归前缀C、项目D、句柄证明：由于该文法的句型abc 存在如下两棵语法树：2、D 不行能是目标代码；A、汇编指令代码B、可重定位指令代码- 1 - 名师归纳总结 - - - - - - -第 1 页,共 5 页精选学习资料 - - - - - - - - - 所以,该文法具有二义性学 号3、如有文法 GS ：SbAb A（ B|a BAa）；构造该文法的简洁优先关系矩阵；四、综合题 （20 分）BaA|bS|c 设有文法 GS：SBA A BS|d （10 分）（1）证明文法 G 是 LL （1）文法；班 级解：（2）构造 LL （1）分析表；（3）写出句子 adccd 的分析过程；解：（1）可见,文法G 是是 LL （1）文法；姓 名装4、构造正规表达式（a|b）* b 的 DFA 并化简；（14 分）（2）装订解：先构造其NFA 如下：（3）线确定化为 DFA：订 线 内 不 要答将其最小化如下：题备注 : 同学不得在试题纸上答题含填空题、挑选题等客观题- 2 - 名师归纳总结 - - - - - - -第 2 页,共 5 页精选学习资料 - - - - - - - - - 6一个 LL l文法肯定是无二义的； 一、填空题（每空1分,共 20分）、中间代码生成、文法；7在规范规约中用最左素短语来刻划可归约串； ）1编译过程一般分为、8目标代码生成时,应考虑如何充分利用运算机的寄存器的问题； 和目标代码生成五个阶段；和分析法；9编译程序是对汇编程序的翻译； （2语法分析最常用的两类方法是10逆波兰法表示的表达式亦称前缀式； 3确定的有穷自动机是一个,通常表示为；三、简答题（每题5分,共 15分）4所谓最右推导是指；5语法分析器的任务是；1 、简述栈式储备治理策略；2 、何谓 DAG ；3 、何谓文法的二义性；6假如一个文法的任何产生式的右部都不含有的非终结符, 就这种文法称为四、给出下述文法对应的正规式（ 7分）7进行确定的自上而下语法分析要求语言的文法是无和和S 0A| 1B的；A 1S | 1的语法分析方法；8LR 分析法是一种B 0S | 09依据优化对象所涉及的程序范畴,代码优化分为、强度减弱、复写传播、五、已知文法 GE ：等；10常用的优化技术包括：、E T | E+T | E -T等；T F | T*F | T/FF E | i二、是非题 （以下各题, 你认为正确的,请在题后的括号内打“ ” , 错的打“ × ” ；证明 E+T*F 是该文法的一个句型,并指出该句型的全部短语、直接短语和句柄；（8 分）每题 2分,共 20分）1正规文法产生的语言都可以用上下文无关文法来描述； ）六、设有文法GS ：baabbb 是否是该文法的句子. 10 分 SaBc|bAB2仅考虑一个基本块,不能确定一个赋值是否真是无用的； （AaAb|b3假如一个文法是递归的,就其产生的语言的句子是无穷个； （）Bb|4四元式之间的联系是通过符号表实现的； （）构造其 LL1 分析表,并分析符号串）5文法的二义性和语言的二义性是两个不同的概念； （- 3 - 名师归纳总结 - - - - - - -第 3 页,共 5 页精选学习资料 - - - - - - - - - 七、设有文法GE:1、×2、 3、 4、×5、 6、 7、 ×8、 9、×10、×E E |SLR1 文法,如不是,请说明理由；如是请构造SLR1 分析表； 10三、简答题（见书中相应部分）（5X3=15 分）试判定该文法是否为四、解：第一得正规式方程组：分 S=0A+1B A=1S+1 B=0S+0八、假设可用寄存器为R0和 R1,试写出以下四元式序列对应的目标代码；（ 10五、解求解该方程组得：（8分）分）S=01|1001|10* T1=B-C（ 2分）T2=A*T1T3=D+1 T4=E-FT5=T3*T4是文法 GS 的句型；短语： E+T*F, T*F （2分）直接短语： T*F （2分）句柄： T*F （2分）六、解：参考答案、由于 FOLLOWB=FIRSTcFOLLOWS=c,#2分,所以构造文法GS 的 LL （ 1）分析表（ 5）如下：一、填空题 1X20=20 分aBc#1词法分析、语法分析、代码优化SaBcbABAaAbb2自上而下、自下而上Bb3五元组、 DFA=K , , M, S, Z4任何一步都是对中最右非终结符进行替换符号串 baabbb是该文法的句子3 分（分析过程略） ；GOTO5分析一个文法的句子结构6相邻、算符七2 分7左递归、公共左因子8自下而上所以该文法为SLR1 文法；其分析表如下：8 分 9局部优化、循环优化、局部优化状态ACTION10删除公共子表达式、代码外提、变换循环掌握条件、合并已知量、删除无用赋值（任选3 个）#E0S2r2r21二、是非题（2X10=20 分）1acc- 4 - 名师归纳总结 - - - - - - -第 4 页,共 5 页精选学习资料 - - - - - - - - - 2S2r2r233目标代码为：10 分S4r14r1八、 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- 5 - 名师归纳总结 - - - - - - -第 5 页,共 5 页
