编译原理期末考试.doc
《编译原理期末考试.doc》由会员分享,可在线阅读,更多相关《编译原理期末考试.doc(25页珍藏版)》请在沃文网上搜索。
1、一、填空(每题2分,共20分)1从功能上说,程序语言的语句大体可分为( 执行性 )语句和( 说明性 )语句两大类。2扫描器的任务是从( 源程序 )中识别出一个个( 单词符号 )。3所谓最左派生是指( 任何一歩都是对中最左非终结符进行替换的 )。4语法分析最常用的两类方法是( 自顶向下 )和( 自底向上 )分析法。5一个上下文无关文法所含的四个组成部分是(一组终结符号,一组非终结符号、一个开始符号、一组产生式 )。6所谓语法制导翻译方法是( 为每个产生式配上一个翻译子程序,并在语法分析的同时执行这些子程序 )。7LR分析法中的两种冲突是( 移入归约 )和( 归约归约 )。8产生式是用于定义( 语
2、法范畴 )的一种书写规则。9属性定义中有两种性质的属性,分别是( 继承属性 )和( 综合属性 )。10常用的两种动态存储分配方法是( 栈式动态分配 )和( 堆式动态分配 )。11. 所谓最右推导是指:任何一步都是对中最右非终结符进行替换的。12. 一个过程相应的DISPLAY表的内容为 (现行活动记录地址和所有外层最新活动记录的地址。)13. 符号表中的信息栏中登记了每个名字的有关的性质,如( 类型、种属、所占单元大小、地址 )等等。14运行时的DISPLAY表的内容是什么?它的作用是什么?答:DISPLAY表是嵌套层次显示表。每当进入一个过程后,在建立它的活动记录区的同时建立一张嵌套层次显示
3、表diaplay.假定现在进入的过程层次为i,则它的diaplay表含有i+1个单元,自顶向下每个单元依次存放着现行层、直接外层、直至最外层(主程序,0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。二、名词解释(每题3分,共15分)1 编译器预处理:对于一个编译器,如果要处理的输入是对原编译器的输入的扩充,就把输入中的扩充部分转换成原输入的形式,然后把其结果交给原编译器处理,也就是把扩展的部分转换成标准形式,这就是编译器预处理2 LL(K)文法(P89)3 歧义文法(p71)正则表达式(P47) :每个正则表达式定义一个正则集。若用RE表示上的正则表达式
4、,并用L(RE)所表示的正则集,则RE的语法定义和相应正则集如下面所述,其中A和B表示正则表达式,并且表示字母表中的任一符号。 4 属性文法(P260)三、简答题(每题5分,共15分)1 设有L(G)a2n+1b2m+1c2p | n=1, m1, p=11) 给出它的正则表达式。2) 构造识别该语言的DFA。2 生成语言L(G)apbmcpanbn | p=0, m=1, n=2的文法G是什么?它是chomsky的哪型文法。解:G(3)文法为S-ACA-aAc|BB-bB|bC-aCb|ab它是乔姆斯基2型文法3 已知文法G(S): Sa|b|(T) TT,S|S 写出句子(a,b),b)的
5、规范规约过程及每一步的句柄。解:句型 规约 句柄(a,b),b) (S,b),b) S-a a(T,b),b)T-S S(T,S),b)S-bb(T),b)T-T,ST,S(S,b)S-(T)(T)(T,b)T-SS(T,S)S-bb(T)T-T,ST,SS S-(T) (T)四、计算题(每题10分,共20分)1 已知文法G(E)ET|E+TTF|T*FF(E)|i给出句型(T*F+i)的最右派生及画出语法树。解:1. (4分)ETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i) 2. (4分) 短语:(T*F+i), T*F+i, T*F, i直接短语:T*F, i句
6、柄:T*F素短语:T*F, i 2说明下面的文法不是SLR(1)文法,并重写一个等价的SLR(1)文法。S M a | b M c | d c | b d aM d解:S S S M a | b M c | d c | b d aM dS .SS .M aS .b M cS . d cS . b d aM .dS b .M cS b .d aM .dS b d .aM d .bd因为a是M的后继符号之一,因此在上面最右边一个项目集中有移进-归约冲突。等价的SLR(1)文法是S d a | b d c | d c | b d a五、设计题(每题15分,共30分)1下面的文法定义语言L = anb
7、ncm | m, n 1。写一个语法制导定义,其语义规则的作用是:对不属于语言L的子集L1= anbncn | n 1的句子,打印出错信息。S D CD a D b | a bC C c | c解:语法制导的定义如下:S D Cif D.length C.length then print (“error”)D a bD.length := 1D a D1 bD.length := D1.length + 1C cC.length := 1C C1 cC.length := C1.length + 12. 给出文法G(L)的翻译模式,它分别计算字符串中0与1的个数。(要求ANTLR代码)SL.
8、L| LLBLLB0|1Grammer L01members int n0; int n1;Start: n0=0; n1=0; jsystem.out.println(n0);system.out.println(n1);j: 0jn0 +=1; |1 jn1 +=1; | a;ws:( | t| n| r)+skip();名词解释1遍指编译程序对源程序或中间代码程序从头到尾扫描一次。 2无环路有向图(DAG)如果有向图中任一通路都不是环路,则称庐有向图为无环路有向图,简称DAG。 3语法分析按文法的产生式识别输入的符号串是否为一个句子的分析过程。 4短语令G是一个文法。S划文法的开始符号,
9、假定是文法G的一个句型,如果有SA且AB,则称是句型相对非终结符A的短语。 5后缀式一种把运算量写在前面,把算符写在后面的表示表达式的方法。简述题 1、写出表达式(ab*c)/(ab)d的逆波兰表示及三元式序列。2、已知文法G(S)Sa|(T)TT,S|S 写出句子(a,a),a)的规范归约过程及每一步的句柄。3、何谓优化?按所涉及的程序范围可分为哪几级优化?4、目标代码有哪几种形式?生成目标代码时通常应考虑哪几个问题?答案: 1、逆波兰表示: abc*ab/d 三元式序列: (*,b,c) (,a,) (,a,b) (/,) (,d)3、优化:对程序进行各种等价变换,使得从变换后的程序出发,
10、能产生更有效的目标代码。 三种级别:局部优化、循环优化、全局优化。4、目标代码通常采用三种形式:机器语言,汇编语言,待装配机器语言模块。 应着重考虑的问题: (1)如何使生成的目标代码较短; (2)如何充分利用寄存器,以减少访问内存次数; (3)如何充分利用指仅系统的的特点。计算题: 1、写一个文法,使其语言是奇数集,且每个奇数不以0开头。(5分) 解:文法G(N): NAB|B AAC|D B1|3|5|7|9 DB|2|4|6|8 C0|D(5分) 2、设文法G(S): S(L)|a S|a LL,S|S (1) 消除左递归和回溯; (2) 计算每个非终结符的FIRST和FOLLOW; (
11、3) 构造预测分析表。 解: (1) S(L)|aS SS| LSL LSL| 评分细则:消除左递归2分,提公共因子2分。 (2) FIRST)S)(,aFOLLOW(S)#,) FIRST(S),a,FOLLOW(S)#,) FIRST(L)(,aFOLLOW(L) ) FIRST(L),FOLLOW(L ) 3、Whilea0 b0do Begin X:X1; if a0 then a:a1 else b:b1 End; 翻译成四元式序列。(7分) 解: (1) (j,a,0,5) (2) (j,3) (3) (j,b,0,5) (4) (j,15) (5) (,1,T1) (6) (:,
12、T1,) (7) (j,a,0,9) (8) (j,12) (9) (,a,1,T2) (10) (:,T2,a) (11) (j,1) (12) (,b,1, T3) (13) (:,T3,b) (14) (j,1) (15) 评分细则:控制结构4分,其它3分。 4、已知文法G(E) ET|ET TF|T * F F(E)|i (1) 给出句型(T * Fi)的最右推导及画出语法树; (2) 给出句型(T * Fi)的短语、素短语。(7分) 解:(1) 最右推导: ETF(E)(ET)(EF)(Ei) (Ti)(T*Fi) (2) 短语:(T*Fi),T*Fi,T*F,i(2分) 素短语:T
13、*F,i (1分) 5、设布尔表达式的文法为 E E(1)E(2) E E(1) E(2) E i 假定它们将用于条件控制语句中,请 (1) 改写文法,使之适合进行语法制导翻译和实现回填; (2) 写出改写后的短个产生式的语义动作。(6分) 解:(1) E0E(1) EE0E(2) EAE(1) EEAE(2) Ei(3分) (2) EE(1) BACKPATCH(E(1)FC,NXQ); E0TC:E(1)TC EE0E(2) EFC:E(2)FC; ETC:MERG(E0TC,E(2)TC) EAE(1) BACKPATCH(E(1)TC,NXQ); E0FC:E(1)FC EEAE(2)
14、 ETC:E(2)TC; EFC:MERG(EAFC,E(2)FC Ei ETC:NXQ;EFC:NXQ1; GEN(jn2,entry(i),0); GEN(j,0)(3分) 6、设有基本块 T1:2 T2:10/T T3:SR T4:SR A:T2 * T4 B:A T5:SR T6:T3 * T5 B:T6 (1) 画出DAG图; (2) 假设基本块出口时只有A,B还被引用,请写出优化后的四元序列。(6分) 解:(1)DAG: (2) 优化后的四元式 T3:SR T4:SR A:5*T4 B:T3T4(3分)例题3若正规表达式r=(a|b|c)(0|1)*,则L(r)中有_D_个元素。(
15、12)A12 B18C6D无穷解析:本题考察的是程序的语言的组成句子与文法之间的关系;正规表达式r=(a|b|c)(0|1)*表示的是a,b,c中的任意一个与0、1串的连接,由于0、1串的长度和组成是不固定的,所以整个句子的数据就是不固定的,也就是说语言L(r)的组成元素是无穷的。试题4:编译器和解释器是两种高级语言处理程序,与编译器相比, B 。编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等几个阶段:其中,代码优化和 C 并不是每种编译器都必需的。词法分析的作用是识别源程序中的 B ;语法分析中的预测分析法是 B 的一种语法分析
16、方法;编译器在 C 阶段进行表达式的类型检查及类型转换。(13) A、解释器不参与运行控制,程序执行的速度慢 B、解释器参与运行控制,程序执行的速度慢 C、解释器参与运行控制,程序执行的速度快 D、解释器不参与运行控制,程序执行的速度快(14)A、词法分析 B、语法分析 C、中间代码生成 D、语义分析(15) A、字符串 B、单词 C、标识符 D、语句(16) A、自左至右 B、自顶向下 C、自底向上 D、自右至左(17) A、词法分析 B、语法分析 C、语义分析 D、目标代码生成例题5:假设某程序语言的文法如下:Sa | b | (T)TTdS | S其中,VT=a,b,d,(,),VN=S
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
10 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 期末考试