编译原理复习整理(重点含答案)

1、给出下面语言的相应文法。L1={anbnci|n≥1,i≥0}从n，i的不同取值来把L1分成两部分：前半部分是anbn：A→aAb|ab后半部分是ci：B→Bc|ε所以整个文法G1[S]可以写为：G1(S):S→AB；A→aAb|ab；B→cB|ε3、构造一个DFA，它接受={a，b}上所有包含ab的字符串。（要求：先将正规式转化为NFA，再将NFA确定化，最小化）4、对下面的文法G:E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧（1）证明这个文法是LL(1)的。（2）构造它的预测分析表。(1)FIRST(E)={(,a,b,^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε}FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#}FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#}(2)考虑下列产生式:EETTFFPEab||*|()|^||FIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,该文法式LL(1)文法.(3)+*()ab^#EETE'ETE'ETE'ETE'E'EEEETTFTTFTTFTTFTT'TTTTTTTTTTTFFPFFPFFPFFPFF'FFF*FFFFFFPPE()PaPbP^5、考虑文法:S→AS|bA→SA|a（1）列出这个文法的所有LR(0)项目。0.SS1.SS2.SAS3.SAS4.SAS5.Sb6.Sb7.ASA8.ASA9.ASA10.Aa11.Aa(2)给出识别文法所有活前缀的DFA。SASaASb确定化：SAab{0,2,5,7,10}{1,2,5,7,8,10}{2,3,5,7,10}{11}{6}{1,2,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{2,3,5,7,10}{2,4,5,7,8,10}{2,3,5,7,10}{11}{6}{2,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{2,3,5,7,9,10}{2,4,5,7,8,10}{2,3,5,7,10}{11}{6}{2,4,5,7,8,10}{2,5,7,8,10}{2,3,5,7,9,10}{11}{6}{11}φφφφ{6}φφφφ01057611123489ASSAabSaASbSAbaAASbaabbaDFA6、设有文法：P→P+Q|QQ→Q*R|RR→(P)|i（1）证明Q*R+Q+Q是它的一个句型。（3分)P=P+Q=P+Q+Q=Q+Q+Q=Q*R+Q+Q（2）给出Q*R+Q+Q的所有短语，直接短语和句柄。(4分)短语:Q*R,Q*R+Q,Q*R+Q+Q直接短语:Q*R句柄:Q*R（3）给出句子ｉ+ｉ*ｉ的最右推导。(4分)（4）给出句子ｉ+ｉ*ｉ的最左推导。(4分)7、设有文法：E→E+T|TT→T*F|FF→(E)|i（1）证明E+T*F是它的一个句型。（3分)EETETF*（2）给出E+T*F的所有短语，直接短语和句柄。(4分)短语:E+T*F,T*F,直接短语:T*F句柄:T*F（3）给出句子ｉ+ｉ*ｉ的最右推导。(4分)0:4:3:2:1:5:6:7:11、构造下面正规式相应的DFA1(0|1)*10114、对下面的文法G:Expr→-ExprExpr→(Expr)|VarExprTailExprTail→-Expr|εVar→idVarTailVarTail→(Expr)|ε（1）构造LL(1)分析表。（12分）（2）给出对句子id—id((id))的分析过程。（8分）16、已知文法G[S]为：S-a|^|(T)T-T,S|S①消除文法G[S]中的左递归，得文法G´[S]。|,)(||^)(TSTTSTTaSSG②文法G´[S]是否为LL(1)的？若是，给出它的预测分析表。FIRST(S)={a,^,(}FIRST(T)={a,^,(}FIRST()={,,}FOLLOW(S)={),,,#}FOLLOW(T)={)}FOLLOW()={)}预测分析表a^(),#ST是LL(1)文法17、对下面的文法G:SSaT|aT|aTTaT|a(1)消除该文法的左递归和提取左公因子；构造各非终结符的FIRST和FOLLOW集合；TTSaS^ST()TSTTSTTSTTTTST,18、文法G(S)及其LR分析表如下，请给出串baba#的分析过程。(1)S→DbB(2)D→d(3)D→ε(4)B→a(5)B→Bba(6)B→εLR分析表2、写出表达式a=b*c+b*d对应的逆波兰式、四元式序列和三元式序列。答：逆波兰式：abc*bd*+:=四元式序列：三元式序列:OPARG1ARG2(1)(*，b，c，t1)(1)(*b，c)(2)(*，b，d，t2)(2)(*b，d)(3)(+，t1，t2，t3)(3)(+(1)，(2))(4)(:=，t3，/，a)(4)(:=(3)，a)八、语义分析题1、将语句if((A0)(B0))thenwhile(C0)doC:=C-D翻译成四元式答案：100(j，A，0，104)101(j，-，-，102)102(j，B，0，104)103(j，-，-，109)104(j，C，0，106)105(j，-，-，109)106(-，C，D，T1)107(:=，T1，-，C)108(j，-，-，104)1092、写出下面语句经语法制导翻译后所生成的四元式代码序列。ifxythenwhileecdoc:=c+1elsex:=x+5答案：假设初始为100，则四元式代码序列为100ifxygoto102101goto107102ifecgoto104103goto109104M:=C+1105C:=M106goto102107N:=X+5108X:=N1098、写出表达式a+b*(c-d)对应的逆波兰式和三元式序列。答案：逆波兰式：(abcd-*+)三元式序列:OPARG1ARG2(1)-cd(2)*b(1)(3)+a(2)1．编译程序是对高级语言程序的解释执行。(×)2．一个有限状态自动机中，有且仅有一个唯一的终态。(×)3．一个算符优先文法可能不存在算符优先函数与之对应。(√)4．语法分析时必须先消除文法中的左递归。(×)5．LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。(√)6．逆波兰表示法表示表达式时无须使用括号。(√)7．静态数组的存储空间可以在编译时确定。(×)8．进行代码优化时应着重考虑循环的代码优化，这对提高目标代码的效率将起更大作用。(×)9．两个正规集相等的必要条件是他们对应的正规式等价。(×)10．一个语义子程序描述了一个文法所对应的翻译工作。(×)1.一个上下文无关文法的开始符，可以是终结符或非终结符。(×)2.一个句型的直接短语是唯一的。（×）3.已经证明文法的二义性是可判定的。（×）4.每个基本块可用一个DAG表示。（√）5.每个过程的活动记录的体积在编译时可静态确定。（√）6.2型文法一定是3型文法。（×）7.一个句型一定句子。(×)8.算符优先分析法每次都是对句柄进行归约。(×)9.采用三元式实现三地址代码时，不利于对中间代码进行优化。（√）10.编译过程中，语法分析器的任务是分析单词是怎样构成的。(×)11.一个优先表一定存在相应的优先函数。(√)12.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。(√)13.递归下降分析法是一种自下而上分析法。(×)14.并不是每个文法都能改写成LL(1)文法。(√)15.每个基本块只有一个入口和一个出口。(√)16.一个LL(1)文法一定是无二义的。(√)17.逆波兰法表示的表达试亦称前缀式。(×)18.目标代码生成时，应考虑如何充分利用计算机的寄存器的问题。(√)19.正规文法产生的语言都可以用上下文无关文法来描述。(√)20.一个优先表一定存在相应的优先函数。(√)21.3型文法一定是2型文法。(√)22.如果一个文法存在某个句子对应两棵不同的语法树，则文法是二义性的。(√)1、简述编译程序的工作过程：编译程序的工作过程，是指从输入源程序开始到输出目标程序为止的整个过程，是非常复杂的，就其过程而言，一般可以划分为五个工作阶段：①词法分析，对构成源程序的字符串进行扫描和分解，识别出一个个的单词；②语法分析，根据语言的语法规则，把单词符号串分解成各类语法单位；③语义分析与中间代码产生，即对各类语法单位，分析其汉一并进行初步翻译；④代码优化，以期产生更高效的代码；⑤目标代码生成，把中间代码变换成特定机器上的低级语言指令形式。2．简述代码优化的目的和意义：代码优化是尽量生成“好”的代码的编译阶段。也就是要对程序代码进行一种等价变换，在保证变换前后代码执行结果相同的前提下，尽量使目标程序运行时所需要的时间短，同时所占用的存储空间少。3、简要说明语义分析的基本功能：确定类型、类型检查、语义处理和某些静态语义检查。1．词法分析：词法分析的主要任务是从左向右扫描每行源程序的符号，按照词法规则从构成源程序的字符串中识别出一个个具有独立意义的最小语法单位，并转换成统一的内部表示(token)，送给语法分析程序。3．简述自下而上的分析方法。：所谓自下而上分析法就是从输入串开始，逐步进行“归约”，直至归约到文法的开始符号；或者说从语法树的末端开始，步步向上“归约”，直到根节点。2．LL(1)文法：若文法的任何两个产生式A|都满足下面两个条件：（1）FIRST()FIRST()=；（2）若*，那么FIRST()FOLLOW(A)=。我们把满足这两个条件的文法叫做LL(1)文法，其中的第一个L代表从左向右扫描输入，第二个L表示产生最左推导，1代表在决定分析器的每步动作时向前看一个输入符号。除了没有公共左因子外，LL(1)文法还有一些明显的性质，它不是二义的，也不含左递归。3．语法树：句子的树结构表示法称为语法树(语法分析树或语法推导树)。给定文法G=(VN，VT，P，S)，对于G的任何句型都能构造与之关联的语法树。这棵树具有下列特征：(1)根节点的标记是开始符号S。(2)每个节点的标记都是V中的一个符号。(3)若一棵子树的根节点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2…AR，那么AA1A2…AR一定是P中的一条产生式。(4)若一标记为A的节点至少有一个除它以外的子孙，则AVN。(5)若树的所有叶节点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。4．LR(0)分析器：所谓LR(0)分析，是指从左至右扫描和自底向上的语法分析，且在分析的每一步，只须