编译原理考条

单选题:1.(设备管理程序)不是编译程序的组成部分.2.(S-aS|a)是左递归文法.3.(S-aS|a)是含有回溯的文法.4.(S-a|bS)是LL(1)文法.5.设有文法G(S):E-E+T|TT-T*F|FF-(E)|I对于上面的文法,句型(E+T)*i+F的句柄是(E+T).1.(词法分析程序)是编译程序的组成部分2.(A-aABc|CDef)不是左递归文法3.(S-Sa|ba)不是含有回溯的文法4.(S-aS|aDsR)是算符文法1.(代码生成程序)不是编译程序的前端2.(S-aSSa|a)是不算符文法3.(S-Sa|a)不是含有回溯的文法4.(S-a|bS)是LL(1)文法5.设有文法G(S)E-E+T|TT-T*F|FF-(E)|I对于上面的文法,下面的(E+E)不是句型判断题:1.LEX是一个词法分析生成工具.(Y)2.代码优先阶段的主要任务是对中间代码进行优化处理.(Y)3.LR文法可以具有二义性.(N)4.句柄就是最右直接短语.(N)5.算符优先分析法是一种自上而下的语法分析方法.(N)6.传地址是一种参数传递方法,是将实参的值传给形参.(N)7.算符优先文法不一定是算符文法.(N)8.素短语除自身之外,可以含有其他短语.(N)9.句子的最左推导称为对句子的最左分析.(Y)10.如果某一产生式形如:A-A,则称该产生式是直接左递归的.(N)1.Yacc是一个词法分析生成工具(N)2.代码优先阶段的主要任务是改正程序中的错误(N)3.所有LR文法一定不是二义文法(Y)4.句柄就是最左直接短语(Y)5.算符优先分析法是一种自底向上的语法分析方法(Y)6.传地址是一种参数传递方法,而传名则不是(N)7.算符优先文法一定是算符文法(Y)8.素短语一定是含有一个终结符号(Y)9.句子的最左推导称为对句子的最右分析(N)10.如果某一生产式形如A-A,则称该产生式是直接左递归的(Y)1.词法分析阶段的主要任务是识别单词,表示成记号形式(Y)2.所有的标识符都必须填写到符号表中(Y)3.算符优先分析法中的归约的是真正的句柄(N)4.LR分析法是一种自底向上的语法分析方法(Y)5.传名是一种参数传递方式,和传地址一样,都是把实参地址传给形参(N)6.算符文法允许两个终结符相邻(Y)7.素短语一定是一个短语(Y)8.当句柄中含有终结符时,句柄和最左素短语就是同一个符号串(Y)9.并不是所有的左递归都能消除(N)填空题:1.词法分析器的任务是(识别单词),(表示成记号形式).2.如果在句子的每步推导中,都坚持替换当前句型中的(最左非终结符),那么句子的这种推导过程称为最左推导.3.最右推导的逆过程是(最左归约).4.存贮分配策略有:(静态存贮分配),(栈式存贮分配),(堆式存贮分配).5.从高级语言到汇编语言或机器语言的翻译程序称为(编译程序).1.语法分析器的任务是(为源程序),(建立语法树)2.如果在句子的每步推导中,都坚持替换当前句型中的(最右非终结符),那么句子的这种推导过程称为最右推导.3.最左推导的逆过程是(最右归约)4.编译程序前端包括:(词法分析器),(语法分析器),(语义分析程序)1.如果产生式具有(A-A)的形式,我们就称这个文法是左递归的2.推导就是用(产生式的的右部替换左部的操作)3.最右推导指的是(每一步都坚持替换当前句型中最右非终结符的推导,也称为规范推导)4.优化的目的为(节约时间)和(节约空间)5.语义分析阶段的主要任务是:对(源程序的语义进行分析,生成中间代码)简答:1.编译过程分为哪几个阶段?简述每个阶段完成的主要任务.答:词法分析,语法分析,语义分析,代码优化,目标代码生成五个阶段组成2.优化的主要技术有几种:答:删除公共子表达式,复制传播,删除无用表达式,强度削弱,删除归纳变量1.递归下降分析法的实现思想?答:为每一个非终结符编制一个递归下降过程,过程的名字就产生左部的非终结符,过程体则是按产生式的右部符号顺序编写.每匹配一个终结符,则再读入一个输入符号;对于产生式右部的每个非终结符,则递归调用相应过程.2.什么是最左素短语?答:素短语:1)它首先是一个短语2)至少含有一个终结符3)除自身外,不在含有其他的素短语句型中,最左面的素短语,称为最左素短语3.算符优先分析法是如何识别句柄的?答:利用栈顶终结符和当前输入符号之间的优先关系-,能找到可归约串的右端;在栈内,利用-关系,可找到可归约串的左端;将之间的符号串弹出栈,并将归约后的非终结符压入栈,完成一次归约.4.简述语法制导翻译的思想?答:将语言结构的语义以属性(attribute)的形式赋予代表此结构的文法符号,而属性的计算以语义规则(semantic rules)的形式赋予由文法符号组成的产生式;在语法分析推倒或归约的每一步骤中,通过语义规则实现对语义的计算,以达到对语义的处理5.参数传递方式有几种?答:四种:传值,传地址,传值结果,传名.1.自低向上的实现思想?答:自左向右逐个扫描输入串,一边把输入符号移入分析栈,一边检查对于栈顶的一串符号是否与某个产生式的右部相同,如果相同,就把栈顶的这串符号归约为左部的非终结符;不同,则继续移入输入符号,进行判断.上述过程一直重复到输入串结束,栈内恰好为S.2.什么是句柄?答: 如果S=aAw=w,则称为相对于A的,句型w的短语.若A-为一产生式,则称为相对与A的,句型w的直接短语.最左直接短语是句炳.3.为什么算符优先分析法中,识别的不是真正的句柄?答:因为算符优先分析没对非终结符定义优先关系,所以无法发现由单一终结符组成的”可归约串”,有时候归约的不是真正的句柄4.什么是素短语?答:素短语:1)它首先是一个短语2)至少含有一个终结符3)除自身外,不在含有其他的素短语5.优先的目的是什么?答:优先目的:节省时间,节省空间*文法G(S)1.S-vI:T2.I-I,i3.I-i4.T-real1)写出识别文法G(S)活前缀的DFA2)写出SLR(1)的分析表答:1)拓广文法0.S-S1.S-vI:T2.I-I,i3.I-i4.T-real有效项目集:I0:S-SI1:S-S.I2:S-v.I:TI-.I,II-.iI3:S-vI.:TI-I.,iI4:I-i.I5:S-vI:.T T-.realI6:I-I,.iI7:I-I,i.I8:S-vI:T.I9:T-real.识别活前缀的DFA:2)FOLLOW(s)=SFollow(T)=:,Follow(T)=S*有文法G(E)1.S-(A)2.S-a3.A-A+S4.A-S1)构造其算符优先矩阵2)找出句型(A+S+S)中的所有短语,直接短语,句柄,LPP答:1)FIRSTVT(S)=a,(FIRSTVT(A)=+,a,(LASTVT(A)=+,a, )2)短语:A+S,A+S+S,(A+S+S)直接短语:A+S句柄:A+SLLP:A+S*设有文法G(E):E-E+TE-TT-T*FT-FF-(E)F-id1)该文法含有左递归吗?若有,消除它2) 改造后的文法是LL(1)文法吗?若是,给出其预测分析表答:1)消除E和T的直接左递归,得到:E-TEE-+TE|.T-FTT-*FT|F-(E)|id解:FIRST(F)=(,idFIRST(T)=*, FIRST(T)=(,idFIRST(E)=+, FIRST(E)= (,idFOLLOW(E)= ),$FOLLOW(T)=FOLLOW(T)=+, ),$FOLLOW(F)=+, ),*,$2)*写出下面语句产生的四元式序列IF AB and CD THENX=0ELSEX=1答:1.(j,a,b,3)2.(j,7)3.(j,c,d,5)4. (j,7)5.(=,0,x)6.(j,)7.(=,1,x)*设有文法G(S):S-BAA-BS|dB-aA|bS|c1)证明该文法是LL(1)文法2)构造LL(1)预测分析表3)写出句子adccd的分析过程答:1)FIRST(S)=a,b,cFIRST(A)=a,b,c,dFIRST(B)=a,b,cFOLLOW(S)=a,b,c,dFOLLOW(A)=a,b,c,dFOLLOW(B)=a,b,c,dFIRST集两两不相交,原文法是LL(1)文法2)LL(1)分析表3)拓广文法:0.S-A1.A-iA2.A-dA3.A-i*已知文法G(B)B-aBB-bBB-a1)构造识别该文法所产生的活前缀的DFA2)构造其SLR分析表:答:1)2)构造其SLR分析表:follow(A)=$*有文法G(R) R-A|A(C) C-R|R*C A-a1)构造其算符优先矩阵2)找出句型A(a*C)中的所有短语,直接短语,句柄,最左素短语答:1)FIRSTVT(R)=(,aFIRSTVT(C)=*,(,aFIRSTVT(A)=aLASTVT(R)=a, )LASTVT(C)=*,a, )LASTVT(A)=a2)短语:a,a*C,A(a*C)直接短语:a句柄:aLLP:a*写出下面语句产生的四元式序列 If A0 then While AC and BD do A=A+1;Else A=A+2;D=0;答:1.(j,a,0,3) 2.(j, , ,10)3.(j,a,c,5)4.(j, , ,11)5.(jB and CD do X=x+1;答：(j , a , b , 3 )(j , , , )(j , c , d , 5 )(j , , , 27 )(+ , X , 1 , x )(j , , , 1 )