编译原理期末考试.doc可修改原格式下载

资源描述

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表示上的正则表达式

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

17、,T，S是开始符号。考查该文法，称句型(Sd(T)db)是S的一个A 。其中B是句柄；C是素短语；D是该句型的直接短语；E是短语。A：最左推导最右推导规范推导推导B： S b (T) Sd(T)C： S b (T) Sd(T)D： S S,(T),bS,(T),TdS,b(Sd(T)db)E： (Sd(T)db)d(T)Td Sd(T)d此句型的语法树如下所示：S (T) （T d S）（T d S b）（S （T）从语法树我们可以看出，短语就是位于同一个非终端结点的所有叶子结点，比如S、Sd(T)、Sd(T)db就是是相对于T的短语，b、(T)、(Sd(T)db)是相对于S的短语。

18、而直接短语则进一步要求这些叶子结点的非终端结点是它们的直接父结点。因此可以S、(T)、b都是该句型的直接短语。语法树上最左的直接短语就是句柄，本题中是S。所谓素短语是指这样一个短语，它至少含有一个终结符，并且除它自身之外不再含任何更小的素短语。最左素短语则指处于句型最左边的那个素短语。最左推导是指任何一步推导过程，都是对中的最左非终结符进行替换。因此，在语法树中也很容易看出，如果语法树中的只有最左的非终结符结点（包括各级结点）具有其子树，则它就是最左推导。最右推导与之类似，最右推导也称规范推导。本题从语法推导树可以看出，既不是最左推导也不是最右推导，就是一般的推导。A： B： C： D： E：

19、1、算符优先关系表不一定存在对应的优先函数。正确2、数组元素的地址计算与数组的存储方式有关。正确3、仅考虑一个基本块，不能确定一个赋值是否真是无用的。正确4、每个文法都能改写为LL(1)文法。不正确5、对于数据空间的存贮分配，FORTRAN采用动态贮存分配策略。不正确一、回答下列问题：(30分)1什么是S-属性文法？什么是L-属性文法？它们之间有什么关系？解答：S-属性文法是只含有综合属性的属性文法。（2分）L-属性文法要求对于每个产生式AX1X2Xn，其每个语义规则中的每个属性或者是综合属性，或者是Xj的一个继承属性，且该属性仅依赖于：（1）产生式Xj的左边符号X1,X2Xj-

20、1的属性；（2） A的继承属性。（2分）S-属性文法是L-属性文法的特例。（2分）2什么是句柄？什么是素短语？一个句型的最左直接短语称为该句型的句柄。（3分）素短语是这样的一个短语，它至少包含一个终结符并且不包含更小的素短语。（3分）3划分程序的基本块时，确定基本块的入口语句的条件是什么？解答：（1）程序第一个语句，或（2）能由条件转移语句或无条件转移语句转移到的语句，或（3）紧跟在条件转移语句后面的语句。4(6分)运行时的DISPLAY表的内容是什么？它的作用是什么？答：DISPLAY表是嵌套层次显示表。每当进入一个过程后，在建立它的活动记录区的同时建立一张嵌套层次显示表diaplay.

21、假定现在进入的过程层次为i，则它的diaplay表含有i+1个单元，自顶向下每个单元依次存放着现行层、直接外层、直至最外层(主程序，0层)等每层过程的最新活动记录的起始地址。通过DISPLAY表可以访问其外层过程的变量。5(6分)对下列四元式序列生成目标代码： A:=B*CD:=E+FG:=A+DH:=G*2其中，H是基本块出口的活跃变量， R0和R1是可用寄存器答：LD R0， BMUL R0， CLD R1， EADD R1， FADD R0， R1MUL R0， 2ST R0， H二、设S=0，1上的正规集S由倒数第二个字符为1的所有字符串组成，请给出该字集对应的正规式，并构造一个识别该

23、(T*F+i)的最右推导并画出语法树。2. 写出上述句型的短语，直接短语、句柄和素短语。答：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句柄：T*F 素短语：T*F, i五、设文法G(S)：(12分)1 构造各非终结符的FIRSTVT和LASTVT集合；2 构造优先关系表和优先函数。(12分)答：(6分)FIRSTVT(S)= i，+，)，( FIRSTVT(A)= +，)，( FIRSTVT(B)= )，( LASTVT(S)= i，+，*，( LASTVT

24、(A)= +，*，( LASTVT(B)= *，( 优先关系表: (3分)i+()*i()优先函数: (3分)i+()*f26616g14661六、设某语言的do-while语句的语法形式为 (9分) S do S(1) While E其语义解释为：真假S(1)的代码E的代码针对自下而上的语法分析器，按如下要求构造该语句的翻译模式：(1) 写出适合语法制导翻译的产生式；(2) 写出每个产生式对应的语义动作。答：(1). 适合语法制导翻译的文法(3分) G(S): R do UR S(1) While SU E (2). (6分) R do R.QUAD:=NXQ UR S(1) While U

25、.QUAD:=R.QUAD; BACKPATCH(S.CHAIN, NXQ) SU E BACKPATCH(E.TC, U.QUAD); S.CHAIN:=E.FC 答案二：(1) S do M1 S(1) While M2 E M (3分)(2) M M.QUAD := NXQ (6分)S do M1 S(1) While M2 EBACKPATCH(S(1).CHAIN, M2.QUAD);BACKPATCH(E.TC, M1.QUAD); S.CHAIN:=E. FC七、(8分)将语句 if (A0) then while C0 do C:=C+D翻译成四元式。答：100 (j， B，

26、0， 104)103 (j， -， -， 109)104 (j， C， 0， 106)105 (j， -， -， 109)106 (+， C， D， T1)107 (:=， T1， -， C)108 (j， -， -， 104)109八、(10分) 设有基本块如下：T1:=S+RT2:= 3T3:= 12/T2T4:=S/RA:=T1-T4T5:=S+RB:=T5T6:=T5*T3B:=T6(1)画出DAG图；T1,T5, B3T24SR+/*_T3T4AT6,Bn4n5n1n2n3n6n8n7(2)设A,B是出基本块后的活跃变量，请给出优化后的四元式序列。答：(1) DAG如右图：(6分)(

27、2) 四元式序列：(4分)T1:=S+RT4:=S/RA:=T1-T4B:=T1*4九、(9分) 设已构造出文法G(S)：(1) S BB(2) B aB(3) B b的LR分析表如下ACTIONGOTO状态ab#SB0s3s4121acc2s6s753s3s484r3r35r16s6s797r38r2r29r2假定输入串为abab，请给出LR分析过程(即按照步骤给出状态，符号，输入串的变化过程)。答：步骤状态符号输入串00#abab#103#abab#2034#abab#3038#aBab#402#Bab#5026#Bab#60267#Bab#70269#BaB#8025#BB#901#S#

28、acc二、（10分）设有文法GA: A iB*e B SB|e S eC|.i C eC|e 判定该文法是否为LL(1)文法？若是则给出它的LL(1)分析表，否则说明理由。解：先计算各个产生式的Predict集： Predict (A- iB*e)= i ; Predict (B- SB) = , . Predict (B-e ) = * Predict (S-eC) = Predict (S-. i) = . Predict (C- eC) = e Predict (C-e ) = 因为Predict集没有冲突，所以是LL(1)文法。 LL(1)分析表如下： i * e . A - iB*e

29、 - e B -S B -S B S -e C -. i C -eC - e 三、（15分）设有文法GS: S LaR|R L bR|c R L判断该文法是否为LR(1)文法。若是则给出它的LR(1)状态机以及LR分析表。5已知文法GS： S S；GG G G(T) H H a (S) T T+S S 找出句型：a(T+S)；H；(S)的短语、简单短语和句柄。解：短语共有7个：a(T + S) ; H ; (S)a(T + S) ; Ha(T + S)T + S(S)Ha简单短语个：a , T + S , H , (S)句柄：a。6已知文法GS为： SAB | bC Ab | BaD | CA

30、D | b DaS | c 对其每一个非终级符求First集和Follow集。解： First (S)= b , a , First (A) = b , First (B) = a , First (C) = b , a , c First (D) = a , c Follow (S)= # Follow (A) = a , c , # Follow (B) = # Follow (C) = # Follow (D) = # 1 编译程序在逻辑上由哪几部分组成？答：六个阶段: 词法分析,语法分析,语义分析,中间代码生成,中间代码优化和目标代码生成。2. 文法G的产生式为：a|b|()c|1）构

31、造句型（bcc）的推导树，并指出该句型的所有短语、简单短语、句柄。2）若句柄存在，求下述符号串的句柄。a)(c(b) b)() c)(a) d)c e) f)b分析：符号串的某一部分符号要成为句柄，必须满足：a）该符号串必须是该文法的句型（句子）。b）是最左简单短语，所以文法的开始符号不是句柄。因此只要给出句型(句子)对应的推导树就容易求出短语、简单短语和句柄。解答：1）句型（bcc）的推导树如图2.1所示：图2.1 句型（bcc）的推导树短语：b;bcc;c;(bcc)简单短语：b;c句柄：b2) a）句型(c(b)的推导树如图2.2所示：图2.2 句型(c(b)的推导树句柄为b。b) 句

32、型()的推导树如图2.3所示：图2.3 句型()的推导树句柄为。c) 句子(a)的推导树如图2.4所示：图2.4 句子(a)的推导树句柄为a。d）c不是文法G的句型，句柄不存在。e）是开始符号，句柄不存在。f）句子b的推导树如图2.5所示：图2.5 句子b的推导树句柄为b。3. 试证具有直接左递归产生式的文法不是LL(k)文法。证明：考察文法G：ab即= a=a b=b，考虑最左推导iai aai与最左推导iai bai，i0表示i次直接推导，当ik时 FIRSTk(aai)FIRSTk(bai)=bak-1 ，G不是LL(k)文法。由于文法G是有直接左递归产生式的文法，所以命题得证。4. 考察如下文法G：abadefga) 试证文法G是LL(1)文法。解答：a)G各个产生式的选择集合为：Select(a)=FIRST(a)=a,f,gSelect(b)=FIRST(b)=d,e,bSelect(a)=FIRST(a)=aSelect()=FIRST()=f,gSelect(d)=FIRST()=dSelect(e)=FIRST()=eSelect()

展开阅读全文