编译原理复习重点

编译原理重点题型填空：10X2'选择：5X2'简答：4X5'计算：2X25'编译程序：翻译程序是指这样的一个程序，它能够把某一种语言程序转换成另一种语言程序。而后者与前者在逻辑上是等价的。如果源语言是“高级程序”，而目标语言是“低级程序”，这样的翻译程序就是编译程序编译过程，分别任务，处理方法词法分析：输入源程序，对构成源程序的字符串进行扫描和分解，识别出一个个单词；词法分析阶段所依循的是语言的词法规则,而描述词法规则的有效工具是正规式和有限自动机语法分析：在词法分析的基础上，根据语言的语法规则，把单词符号串分解成各类语法单位；通过语法分析,确定整个输入串是否构成语法上正确的“程序”.语法分析所依循的是语言的语法规则.语法规则通常用上下文无关文法描述.语义分析与中间代码生成：对语法分析所识别出的各类语法范畴，分析其含义，并进行初步翻译，即中间代码；这一阶段所依循的是语言的语义规则,通常使用属性文法,四元式描述语义规则.优化：对前段产生的中间代码进行加工变换，以期在最后阶段能产出更为高效的目标代码；优化的主要方面有:公共子表达式的提取、循环优化、删除无用代码等等.有时,为了便于“并行运算”,还可以对代码进行并行化处理.优化所依循的原则是程序的等价变换原则目标代码生成：把中间代码变换成特定机器上的低级语言代码；这阶段实现了最后的翻译,它的工作有赖于硬件系统结构和机器指令含义.这阶段工作非常复杂,涉及到硬件系统功能部件的运用,机器指令的选择,各种数据类型变量的存储空间分配,以及寄存器和后援寄存器的调度等.如何产生出足以充分发挥硬件效率的目标代码是一件非常不容易的事情.编译程序的结构编译前端和后端编译程序可以被划分为编译前端和编译后端.前端主要由与源语言有关但与目标机无关的那些部分组成,通常包括:词法分析、语法分析、语义分析与中间代码产生,有的代码优化工作也可包括在前端.后端是由编译程序中与目标机有关的那些部分组成,如与目标机有关的代码优化和目标代码生成等.通常,后端不依赖于源语言而仅仅依赖于中间语言上下文无关文法(概念，推导方法)文法：是描述语言的语法结构的形式规则上下文无关文法：一种文法，他所定义的语法范畴完全独立于这种范畴可能出现的环境包括四个组成部分：一组终结符号，一组非终结符号，一个开始符号，一直产生式1，2，3判断属于哪种类型Gl： S-〉bAA-〉aA|a L(Gl)={ba"n|n〉=l}G2： S->ABA->Aa|a|£ B-〉bB|b L(G2)={a"mb"n|m,n〉=1}G3： S-〉aSb|ab L(G3)={a"nb"n|n〉=1}语法分析树(语法树如何生成的，句柄，短语)与二义性(概念，判断方法)P30二义性：一个文法存在某个句子对应两棵不同的语法树形式语言鸟瞰语法分析器的输出形式二元组(单词种别，单词符号的属性值)正规式与正规集(概念，描述一个语言)£和0都是工上的正规式，它们所表示的正规集分别为{£}和0;任何ae£，a是工上的一个正规式，它所表示的正规集为{a}；假定U和V都是工上的正规式,它们所表示的正规集分别为L(U)和L(V)，那么，(U|V),(U.V)和(U)*也都是正规式，它们所表示的正规集分别为L(U)UL(V)、L(U)L(V)(连接积)和(L(U))*(闭包)仅由有限次使用上述三步骤而得到的表达式才是工上的正规式。仅由这些正规式所表示的字集才是工上的正规集。(A|B|0|1)*多个A,B,0,1(结合题目)确定有限自动机(概念，画出DFA，化简)非确定有限自动机(概念)确定与非确定的主要区别是初态是否为一个集合对正规式确定化，最小化自上而下分析面临的问题文法的左递归问题由于回溯，就碰到一大堆麻烦分析过程中，当一个非终结符用某一候选匹配成功时，这种成功可能是暂时的。当最终报告分析不成功时，我们难于知道输入串中出错的确切位置由于带回溯的自上而下分析实际上采用了一种穷尽一切可能的试探法，因此，效率很低，代价极高左递归的消除(直接，间接)P69E-〉E+T|T E-〉TE' E'-〉+TE'|£LL(1)文法定义，如何对LL(1)文法分析定义：文法不含左递归。对于文法中的每一个非终结符A的各个产生式的候选首两两不相交。对文法中的每A个终结符A,若它存在某个候选首符集包含£，则First(A)GFollow(A)=0分析：对于一个LL(1)文法，可以A对其输入串进行有效的无回溯的自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a,A的所有产生式为：A-〉a1|a2|„|an若aUFIRST(ai)，则指派ai去执行匹配任务若a不属于任何一个候选首符集，则：若£属于某个FIRST©i)且a^FOLLOW(A),则让A与£自动匹配否则，a的出现是一种语法错误递归下降分析程序构造(写出程序段)预测分析程序工作过程(三种动作)若X=a=‘#'则宣布分析成功，停止分析过程若X=aM'#'则把X从STACK栈顶逐出，让a指向下一个输入符号。若X是一个非终结符，则查看分析表。若M[A,a]中存放着关于X的一个产生式，那么，首先把X逐出STACK栈顶，然后，把产生式的右部符号串按反序一一推进STACK栈(若右部符号为£，则意味不推进什么东西进栈)。把产生式的右部符号推进栈的同时应做这个产生式相应的语义动作。若M[A,a]中存放着“出错标志”，则调用出错诊断程序ERROR。P774.4伪代码预测分析表的构造(first,follow,预测分析表)1)用xuvUV构造FIRST(X):TN若XUV，则FIRST(X)={X}T若XUV，且有产生式X-a…，则把a加入到FIRST(X)中；N若X-S也是一条产生式，则把£也加到FIRST(X)中若X-Y…是一个产生式且YUV，则把FIRST(Y)中的所有非£-元素都加到FIRST(X)N中；若X-Y：Y2„Yk是一个产生式…，丫卜都是非终结符，且对于任何j(lWjWi-l),FIRST(Y)都含有£,则把FIRST(Y)中的所有非£-元素都加到FIRST(X)中；特别ji是，若所有的FIRST(Y.)均含有£(j=1,2,„,k),则把£加到FIRST(X)中2)对于文法G的每个非终结符A构造FOLLOW(A)的方法：对于文法的开始符号5,置#于FOLLOW(S)中；若A-aBP即是一个产生式，则把FIRST©)\{£}加至FOLLOW(B)中；若A-aB是一个产生式，或A-aBP且P=>£,则把FOLLOW(A)加至FOLLOW(B)中P784.6规范规约简述：短语，直接短语，句柄，树短语(结合题目)令G是一个文法，S是文法的开始符号，假定aP6是文法G的一个句型，如果有S=>aA6且A=>p则称P是句型ap6相对于非终结符A的短语。特别是，如果有A=>p则称P是句型ap6相对于规则A->p的直接短语，一个句型的最左直接短语称为改句型的句柄。P86概念，规范规约，规范推导算符优先文法及优先表构造(概念，算符优先文法，关系判断)算符文法：一个文法，如果它的任意一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：„QR…，则我们称该文法为算符文法。如果一个算符文法G中的任何终结符对(a,b)至多只满足下述三关系之一:a=b,a〈b,a〉b则称G是一个算符优先文法。算符优先分析算法FirstVt,lastVt,树短语，最左树短语FIRSTVT(P)：若有产生式P—a…或P—Qa„，则a^FIRSTVT(P)；若aUFIRSTVT(Q)，且有产生式P-Q„,则a^FIRSTVT(P)同样我们用下面两条规则来构造LASTVT(P):若有产生式P—„a或P—„aQ，贝I」a^LASTVT(P)；若aeLASTVT(Q)，且有产生式P-„Q，则aeLASTVT(P)属性文法(概念)P136-P139属性通常分为两类：综合属性和继承属性。中间语言(后缀式，图表示法，三地址代码：四元式)说明语句(分析)赋值语句的翻译初态与终态如何确定？与正规式等价的有限自动机自上而下推测、自下而上规约

题目：36-7.G(S)Ot113151719Nt21416181ODt0|NDt0|NStO|AOAtAD|NP64-2.(a)a给状态编号确定化:给状态编号ab{0}{0,1}{1}{0,1}{0,1}{1}{1}{0}伞伞伞最小化:{0,1},{2,3}{0,1}={1}{0,1}={2}{2,3}a={0,3}{2,3}={3}{0,1},a{2},{3} b(b)已经确定化了,进行最小化最小化：{{0,1},{2,3,4,5}}{0,1}={1}a{0，1}b = {2,4}{2,3,4,5}={1,3,0,5} {2,3,4,5}={2,3,4,5}a{2,4}={1,0}a{3,5}={3,5}ab{2,4}={3,5}b{3,5}={2,4}b{{0,1},{2,4},{3,5}}{0,1}={1}a{2,4}={1,0}a{3,5}={3,5}a{0,1}={2,4}b{2,4}={3,5}b{3,5}={2,4}bP81-1(1)按照T,S的顺序消除左递归G'(S)STalAl(T)TTST'Tt,ST'Is递归子程序：procedureS;beginifsym=aorsym=thenabvanceelseifsym='('thenbeginadvance;T;ifsym=')'thenadvance;elseerror;endelseerrorend;procedureT;beginS;Tend;procedureT;beginifsym=','thenbeginadvance;S;TTendend;其中:sym:是输入串指针IP所指的符号advance:是把IP调至下一个输入符号error:是出错诊察程序(2)FIRST(S)={a「，(}FIRST(T)={a「，(}FIRST(T)={,,£}FOLLOW(S)={)，，，#}FOLLOW(T)={)}FOLLOW(TT)={)}预测分析表a()#SS-TaStaST(T)TTTSTTTTSTtTTSTTTTT'T£TTT,STT是LL(1)文法P81-2文法：ETTETE'T+EI£TTFTTTTTT|£FTPFTFTT*FT|£PT(E)1aIbI人(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')={+,),#}F0LL0W(F)={(,a,b「，+,),#}F0LL0W(F')={(,a,b「，+,),#}F0LL0W(P)={*,(,a,b「，+,),#}(2)考虑下列产生式:E'T+EI£T'tTI£F'T*F'I£PT(E)IAIalbFIRST(+E)GFIRST(£)={+}G{£}=QFIRST(+E)HFOLLOW(E')={+}G{#,)}=©FIRST(T)GFIRSTS)={(,a,b「}H{£}=QFIRST(T)HFOLLOW(T')={(,a,b「}H{+,),#}=©FIRST(*F')HFIRST(s)={*}H{s}=QFIRST(*F')HFOLLOW(F')={*}H{(,a,b「，+,),#}=QFIRST((E))HFIRST(a)HFIRST(b)HFIRST「)=Q所以，该文法式LL(1)文法.(3)+*()ab#EETTE'ETTE'ETTE'ETTE'E'E'T+EE'T£E'T£TTTFT'TTFT'TTFT'TTFT'T'T'T£TTTTT£T'TTT'TTT'TTT'T£FFtPF'FtPF'FtPF'FtPF'F'F'T£F't*F'F'T£F'T£F'T£F'T£F'T£F'T£PPT(E)PTaPTbPTA(4)procedureE;beginifsym=(orsym=aorsym=borsym=thenbeginT;E'endelseerrorendprocedureE';beginifsym='+'thenbeginadvance;Eendelseifsym<>')'andsym<>'#'thenerrorendprocedureT;beginifsym=(orsym=aorsym=borsym=thenbeginF;T'endelseerrorendprocedureT';beginifsym=(orsym=aorsym=borsym=thenTelseifsym='*'thenerrorendprocedureF;beginifsym=(orsym=aorsym=borsym=thenbeginP;F'endelseerrorendprocedureF';beginifsym='*'thenbeginadvance;F'endendprocedureP;beginifsym=aorsym=borsym=thenadvanceelseifsym='('thenbeginadvance;E;ifsym=')'thenadvanceelseerrorendelseerrorend;P81-3(1)是，满足三个条件。(2)不是，对于A不满足条件3。不是，A、B均不满足条件3。是，满足三个条件。P133-1EnE+TnE+T*F短语:E+T*F,T*F,直接短语:T*F句柄:T*FP133-2文法：STalAl(T)TTT,SIS(1)最左推导:Sn(T)n(T,S)n(S,S)n(a,S)n(a,(T))n(a,(T,S))n(a,(S,S))n(a,(a,S))n(a,(a,a))Sn(T,S)n(S,S)n((T),S)n((T,S),S)n((T,S,S),S)n((S,S,S),S)n(((T),S,S),S)n(((T,S),S,S)),S)n(((S,S),S,S),S)n(((a,S),S,S),S)n(((a,a),S,S),S)n(((a,a),A,S),S)n(((a,a),A,(T)),S)n(((a,a),A,(S)),S)n(((a,a),A,(a)),S)n(((a,a),A,(a)),a)最右推导:Sn(T)n(T,S)n(T,(T))n(T,(T,S))n(T,(T,a))n(T,(S,a))n(T,(a,a))n(S,(a,a))n(a,(a,a))Sn(T,S)n(T,a)n(S,a)n((T),a)n((T,S),a)n((T,(T)),a)n((T,(S)),a)n((T,(a)),a)n((T,S,(a)),a)n((T,A,(a)),a)n((S,A,(a)),a)n(((T),A,(a)),a)n(((T,S),A,(a)),a)n(((T,a),A,(a)),a)n(((S,a),A,(a)),a)n(((a,a),A,(a)),a)(2)((Q,a)「，(a)),a)(((S,a),",(a)),a)(((T,a)「，(a)),a)(((U)「，(a)),a)((!Tl,",(a)),a)((S,",(a)),a)((T,",(a)),a)((T,S,(a)),a)((T,(a)),a)((T,(S)),a)((T,(T)),a)((T,S),a)(IH,a)(S,a)(T,S)S0#(((a,a),,(a)),a)#1#(((a,a),",(a)),a)#2#(((a,a),",(a)),a)#3#(((a,a),",(a)),a)#4#(((a,a),",(a)),a)#5 #(((S,a),",(a)),a)#6 #(((T,a),",(a)),a)#7 #(((T,a),",(a)),a)#8#(((T,a),",(a)),a)#9 #(((T,S),",(a)),a)#10#(((T),",(a)),a)#11#(((T)",(a)),a)#12#((S",(a)),a)#13#((T",(a)),a)#14#((T,",(a)),a)#15#((T「,(a)),a)#16#((T,S,(a)),a)#17#((T,(a)),a)#18#((T,(a)),a)#19#((T,(a)),a)#20#((T,(a)),a)#21#((T,(S)),a)#22#((T,(T)),a)#23#((T,(T)),a)#24#((T,S),a)#25#((T),a)#26#((T),a)#27#(S,a)#28#(T,a)#29#(T,a)#30#(T,a)#31#(T,S)#32#(T)#33#(T)#34#S#“移进-归约”过程：步骤栈输入串预备进进进进归归进进归归进归归进进归归进进进归归进归归进归归进进归归进归动作

P133-3(1)g输入字符串(a,(a,a))#a,(a,a))#,(a,a))#,(a,a))#动作预备FIRSTVT(S)={a「，(}FIRSTVT(T)={,,a「，(}LASTVT(S)={a「，)}LASTVT(T)={,,a「，)}g输入字符串(a,(a,a))#a,(a,a))#,(a,a))#,(a,a))#动作预备a()a>>>>(<<<=<)>><<<>>G6是算符文法，并且是算符优先文法（3）优先函数a()f44244g55523(4)栈##(#(a#(t#(t,(a,a))##(t,（a,a））##(t,（a,a））##(t,（t,a））##(t,(t,a））##(t,(t,a））##(t,(t,s））##(t,（t））##(t,（t））##(t,s）##（t）##（t）##s#success解释程序：它已该语言写的源程序作为输入。但不产生目标程序，而是边解释边执行原程序本身。诊断编译程序：专门用于帮助程序开发和调试的编译程序优化编译程序：着重于提高目标代码效率的编译程序目标机：运行编译程序的计算机叫宿主机，运行编译程序产生目标代码的计算机成为目标机交叉编译程序：一个编译程序产生不同于宿主机的机器代码可变目标编译程序：如果不需重写编译程序中与机器无关的部分就能改变目标机，则称该编译程序为可变目标编译程序上下文无关文法的限制：（1）文法中不含任何下面形式的产生式P-P（2）每个非终结符P必须都有用处S=》aPp语法分析器的基本任务：在词法分析识别出的单词符号串的记住上，分析并判断程序的语法结构是否符合语法规