2011函授编译原理.doc

哈尔滨工业大学成人教育学院 2010年秋季学期编译原理 试题（函授） 1、填空题（30分）1）词法分析器的任务是（组织源程序输入，识别单词并表示或记号，查填符号表，删除无用符号，错误处理）。2）参数传递方式：（传值，传名，传地址，传值结果）3)存贮分配策略有：（静态，栈态，堆态）。4:).语法分析分为：（自顶向下）和（自底向上）两大类分析方法，共有（递归下降，LL(1)预测分析，算符优先，LF分析法）四种分析方法。5）从高级语言到汇编语言或机器语言的翻译程序称为（编译程序）。6）素短语满足以下三个条件：（首先是一个短语，至少含有一个终结符，除自身外不在含有其他素短语）7）编译程序由词法分析、语法分析、（语义分析，中间代码优化，目标代码生成）五个阶段组成。8）优化的主要技术为：（删除无用公式值，复写传播，删除公共子表达式，强度削弱，删除归纳变量）2设有文法（S）：1. EE+F2. EF3. F(E)4. Fa1) 该文法含有左递归吗？若有，消除它。（10分）1消除左递归EFE FIRST(E )= （ , a E+FE FIRST(E)= + ，E FIRST(F )= （ , a F（E） FOLLOW(E )= ）, # FaFOLLOW(F)= ）, # FOLLOW(F )= + , ）. # 2) 改造后的文法是LL(1)文法吗？若是，给出其预测分析表。（10分）()a+#EEFEEFEEE E+FEE FF(E)Fa 因为分析表中没有冲突，所以改造后文法是LL（1）的。3、有文法G（S）: 1、S （A）2、S a3、AA+S4、AS1）构造该文法的算符优先矩阵 (10分)FIRSTVT(S )= （ , a FIRSTVT(A )= +，（ , a LASTVT(A ) = +，) , a LASTVT(S ) = ) , a ()+a()+a2）找出句型（A+S+S）中的所有短语、直接短语、句柄和LPP（10分） 短语：A+S，A+A+S,（A+A+S）直接短语：A+S句柄：A+SLPP：A+S4文法G（S） 1.拓广文法： 0. S S 1.SAs 1.S aS 2.SbS 2.S bS 3.Sa 3.S a 1)、写出识别文法G（S）活前缀的DFA（10分）2)、写出其SLR（1）的分析表（10分）Fellow(S)=#ab#SA0S2S311ACC2S2S3R343S2S34R15R2 5写出下面语句产生的四元式序列 （ 10分）X=0;whie AB do X=x+1 ;x=100;1.(=,0, ,X)2.(j,A,B,4)3.(j , , ,6)4.(+ ,X,1,X)5.(j , , ,2)6.(=,100, ,x)第二套1.单项选择题（10分）1) ( A ) 是编译程序的组成部分A词法分析程序B.文件管理程序C.设备管理程序D.进程管理程序2）（B）不是左递归文法。A.A-Aa|AaA B.A-aABc|CDef C.A-AapA|Aa D.A-AbSa|Aa3) （A）不是含有回溯的文法。A.S-Sa|ba B.S-aS|a C.S-aSa|aS D.S-aSa|a4) ( A )是算符文法。A.S-aS|aDsR B.S-AD|bS C.S-aSPa|aSb D.S-cS|DD5) 设有文法G（S）：E-E+T|TT-T*F|FF-(E)|I对于上面的文法，句型（ET）*i+F的最左素短语是（C）A.EB.（ET）C.ETD.I2.判断对错（对者打，错打X）（10分）1） Yacc是一个词法分析生成工具。（）2） 代码优化阶段的主要任务是改正程序中的错误。（）3） 所有LR文法一定不是二义文法。（）4） 句柄就是最左直接短语。（）5） 算符优先分析法是一种自底向上的语法分析方法。（）6） 传地址是一种参数传递方式，而传名则不是。（）7） 算符优先文法一定是算符文法。（）8） 素短语一定是含有一个终结符号。（）9） 句子的最左推导称为对句子的最右分析。（）10） 如果某一产生式形如A-A.，则称该产生式是直接左递归的。（）3 填空题（10分）1）词法分析器的任务是（组织源程序输入，识别单词，查填符号表）。2）如果在句子的每步推导中，都坚持替换当前句型中的（最右准终结符），那么句子的这种推导过程称为最右推导。3）最左推导的逆过程是（最右归约）。4）存贮分配策略有：（静态，堆式，栈式）。5）编译程序前端包括：（ 词法分析 ， 语法分析 ，语义分析）。6）参数传递方式有几种：（传值 ，传地址，传名 ，传值结果）4、简答题(30分)1) 递归下降分析法的实现思想？(10分)为每一个非终结符编制一个递归下降过程，过程的名字就产生式左部的非终结符，过程体则是按产生式的右部符号顺序编写。每匹配一个终结符，则再读入一个输入符号，对于产生式右部的每个非终结符，则递归调用相应过程。2) 什么是最左素短语？(5分)1它首先是一个短语2至少含有一个终结符3除自身外，不再含有其它的素短语句型中，最左面的素短语，称作最左素短语。3) 算符优先分析法是如何识别句柄的？(5分)利用栈顶终结符和当前输入符号之间的优先关系 ，能找到可归约串的 右端；在栈内，利用关系，可找到可归 约串的左端；将之间的符号串弹出栈，并 将归约后的非终结符压入栈，完成一次归约4) 简述语法导翻译的思想(6分)语言结构的语义以属性(attribute)的形式赋予代表此结构的文法符号，而属性的计算以语义规则(semantic rules)的形式赋予由文法符号组成的产生式；在语法分析推导或归约的每一步骤中，通过语义规则实现对属性的计算，以达到对语义的处理5) 参数传递方式有几种？(4分)四种：传值、传地址、传值结果、传名5文法G（S）1.SvI:T2.II,i3.Ii4.Treal1)、写出识别文法G（S）活前缀的DFA（5分）2)、写出其SLR（1）的分析表（5分）拓广文法0、SS 1.SvI:T2.II,i3.Ii4.Treal有效项目集： I0:S .S S.vI:TI1:S S. I2:Sv.I:T I.I,I I.iI3:SvI.:T II.,iI4:Ii.I5:SvI:.T T.realI6:II,.iI7:II,i.I8:SvI:T.I9:Treal.识别活前缀的DFA：2)FOLLOW(s)=$Follow(T)=: ,Follow(T)=$ vi,:r$SIA0S211ACC2S433S5S64R3R35S986S77R28R19R46、有文法G（E） 1、S （A）2、S a3、AA+S4、AS1）构造其算符优先矩阵（5分）2）找出句型( A+S+S) 中的所有短语、直接短语、句柄、LPP（5分）1) FIRSTVT（S）=a,( FIRSTVT（A）=+,a,( LASTVT(S)=a,) LASTVT(A)=+,a,)a + ( ) a + ( 2) 语法树 短语： A+S，A+S+S ，(A+S+S) S 直接短语： A+S 句柄：A+S ( A ) LLP：A+S A + SA + S7、设有文法G(E)： 1.EE+T2. ET 3.TT*F4.TF 5. F(E)6. F id1) 该文法含有左递归吗？若有，消除它。（5分）2) 改造后的文法是LL(1)文法吗？若是，给出其预测分析表。（5分）1) 消除E和T的直接左递归，得到： ETE E +TE|T FTT*FT| F(E)|id解：FIRST(F)=(,idFIRST(T)=*, FIRST(T )= (,id FIRST(E)=+, FIRST(E)=(,idFOLLOW(E)=), FOLLOW(T)=FOLLOW(T)=+,), FOLLOW(F)=+,),*, $8、写出下面语句产生的四元式序列 (10分)IF A B and C D THEN X=0 ELSE X=11. (j , a , b , 3 )2. (j , , , 7 )3. (j , c , d , 5 )4. (j , , , 7 )5. (= , 0 , , x )6. (j , , , )7. (= , 1 , , x )哈尔滨工业大学成人教育学院夜大 2010年秋季学期编译原理 试题 1、填空题（30分）1）编译程序的组成是（词法分析，语法分析，语义分析，中间代码优化，目标代码生成）。2）优化的主要技术：（删除无用公式值，复写传播，删除共公子表达式，强度削弱，删除归纳变量）。3）从高级语言到汇编语言或机器语言的翻译程序称为（编译程序）。4）参数传递方式：（传值，传名，传地址，传值结果）2设有文法G（S）：1、S （A）2、S a3、AA+S4、AS1) 该文法含有左递归吗？若有，消除它。（10分）解：1消除左递归1.SA FIRST(S )= （ , a 2.Sa FIRST(A )= （ , a 3.ASA FIRST(A)= + , 4.A+SA FOLLOW(A )= FOLLOW(A) = ） 5.A FOLLOW(S )= + , ） ， # 2) 改造后的文法是LL(1)文法吗？若是，给出其预测分析表。（10分）（）a+#SSASaAASAASAAA A+SA3、 有文法G（S）:1Sa2S(T)3TT,y4Ty 1）构造该文法的算符优先矩阵 (10分)解：FIRSTVT(S)=C,aFIRSTVT(S)= ,yLASTVT(S)=),aLASTVT(T)=y2）找出句型（T，y）中的所有短语、直接短语、句柄和LPP（10分） 短语：T