编译原理整理资料

1名词解释编译：编译程序的翻译过程。词法分析,语法分析,语义分析,中间代码生成,代码优化,目标代码生成.语言：由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)={x|S=*x，其中S为文法的开始符号，且x∈VT*}二义文法：若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。二义语言：如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。属性文法：属性文法(attributegrammar)是一个三元组：A=(G,V,F),其中G:是一个上下文无关文法,V:有穷的属性集,F:关于属性的属性断言或一组属性的计算规则(称为语义规则)。活动记录：一个过程的一次执行所需要的信息，使用一个连续的存储区来管理这个区（块），叫做一个活动记录AR。词法：规定什么是正确的单词，boy不能写成byo等等。语法（文法）：是指一组规则，用它可以形成和产生一个合适的程序。（定义什么样的符号序列是合法的）语义：自然语言中词语的意义，逻辑形式系统中符号的解释。（定义什么样的符号序列是有含义的）句子：有文法G[s]，若S=*x，且x∈VT*，则称x是文法G的句子。句型：有文法G[s]，若S=*x，则称x是文法G的句型。语法树：设G=(VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树。最左/最右推导符进行替换。自上而下分析：从文法的开始符号出发，反复使用文法的产生式，寻找与输入符号串匹配的推导，或者说，为输入串寻找一个最左推导。自下而上分析：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。短语：存在文法G[s],S=*αAδ且A=+β，则称β是句型αβδ相对于非终结符A的短语。句柄：一个句型的最左直接短语称为该句型的句柄项目：在右端某一位置有圆点的G的产生式语法制导翻译：在语法分析的同时，执行语义规则描述的动作：2回填：一旦真假出口确定下来之后,用顺着真链和假链把真假出口补上.拉链：为了记录需回填地址的四元式,把需要回填的真出口的四元式拉成链,把需要回填家出口的四元式拉成一链,分别称作真链假链.目标程序运行时存储区划分图：简答题：一．给出一个句子的最左，最右推导，语法树。例:G[S]:S→aASA→SbAA→SSS→aA→ba最右推导：SaASaAaaSbAaaSbbaaaabbaa最左推导：SaASaSbASaabASaabbaSaabbaa任意推导：SaASaSbASaSbAaaabAaaabbaa语法树：二.判定文法的类型（0，1，2，3型）：运用知识：文法的类型：通过对产生式施加不同的限制，Chomsky将文法分为四种类型：0型文法：对任一产生式α→β，都有α∈(VN∪VT)+，β∈(VN∪VT)*1型文法：对任一产生式α→β，都有|β|≥|α|，仅仅S→ε除外32型文法：对任一产生式α→β，都有α∈VN3型文法：任一产生式α→β的形式都为A→aB或A→a，其中A∈VN，B∈VN，a∈VT*1型文法例：1型（上下文有关）文法文法G[S]：S→CDAb→bAC→aCABa→aBC→bCBBb→bBAD→aDC→aBD→bDD→bAa→bD2型文法例：2型（上下文无关）文法文法G[S]：S→ABA→BS|0B→SA|13型文法例子G[S]：S→0A|1B|0A→0A|1B|0SB→1B|1|0三．正规式，正规文法，自动机之间的转换正规式到正规文法的转换运用知识：对上的正规式r,存在一个RG=(VN,VT,P,S)：L(G)=L(r)(R.0)VT=,SVN,生成正规产生式：Sr(R.1)对形如Ar1r2的正规产生式：Ar1BBr2BVN(R.2)对形如Arr1的正规产生式：ArAAr1(R.3)对形如Ar1r2的正规产生式:Ar1Ar2不断应用(R.x)做变换，直到每个产生式右端至多有一个VN例子r=a(ad)解：(1)Sa(ad)(Sr)(2)SaAA(ad)(Ar1B,Br2)(3)A(ad)A(ArA,Ar1)AG[s]:SaAAVT={a,d}AaBVN={S,A}AdB4正规文法到正规式的转换运用知识：对G=(VN,VT,P,S),存在一个=VT上的正规式r:L(r)=L(G)AxB,By形成正规式A=xyAxAy形成正规式A=xyAxy形成正规式A=xy例子：由NFAM构造正规式r运用知识：从Σ上的一个NFAM，构造Σ上的,一个正规式r，使得L(M)=L(r)的方法。由NAM构造正规式r步骤如下：(1)在NFAM的状态图中增加2个新节点：X和Y。从X节点到NFAM的所有初态引标记的弧，从NFAM的所有终态到Y节点引标记的弧，形成一个新的NFAM’，这个M’只有一个初态X和一个终态Y。显然M与M’等价。(2)逐步消去M’的节，直至剩下X和Y节，消节的过程中，根据消节规则，逐步用正规式标记弧。消结规则：5NFA到正规式的例子：由正规式r构造NFAM从Σ上的一个正规式r，构造Σ上的一个NFAM，使得L(M)=L(r)的方法。“语法制导”的方法，即按正规式的语法结构指引构造过程，构造规则具体描述如下：(1)R=,构造任一具有空终态集的NFAM(2)R=，构造的NFAM=({k0},∑,f,k0,{k0});f(k0,a)对于所有a∑都没定义。(3)R=a,构造的NFAM=({k0,,k1},∑,f,k0,{k1}):f(k0,a)=k1(4)R=R1|R2,将步骤（1）（2）（3）分别应用到R1,R2；产生M1=(K1,∑,f1,k1,F1),M2=(K2,∑,f2,k2,F2),其中K1,K2不相交.构造的NFAM=(K1K2{k},∑,f,k,F):k是新增加的状态符号，f包含f1和f2,且f(k,a)=f1(k1,a)f2(k2,a).6若k1F1且k2F2，则F=F1F2；否则F=F1F2{k}(5)R=R1.R2将步骤（1）（2）（3）分别应用到R1,R2；产生M1==(K1,∑,f1,k1,F1),M2=(K2,∑,f2,k2,F2),其中K1,K2不相交.构造的NFAM=(K1K2,∑,f,k1,F2):f包含f1和f2,且f(k,a)=f1(k,a),当kF1时;f(k,a)=f2(k,a),当k∈K2时;f(k1,)=k2,(6)R=R1*将步骤（1）（2）（3）分别应用到R1,产生M1==(K1,∑,f1,k1,F1),构造的NFAM=(K1{k0,F0},∑,f,k0,F0),其中k0,F0是新增加的两个状态,f(k,a)=f1(k,a),当kF1时;f(k0,)=f(F1,)={k1,F0},从正规表达式构造等价的–NFA由正规文法G构造NFAM定理：设G=(VN,VT,P,S)为一个正规文法，则存在一个有穷自动机NFAM=(K,∑,f,S,Z)，使得L(M)=L(G)。M的构造方法：•∑=VT;S=S•为G中每一个非终结符生成M的一个状态（不妨取成相同的名字），G的开始符号M的开始状态S；•增加一个新状态Z，作为NFA的终态；K=VN+{Z}•若G中有形如A-tB的产生式，则令f(A,t)=B;7•若G中有形如A-t的产生式，则令f(A,t)=Z;求与文法G[S]等价的NFA由NFAM构造正规文法G定理：已知一个有穷自动机NFAM=(K,∑,f,S,Z)，则存在一个正规文法G=(VN,VT,P,S)，使得L(M)=L(G)。G的构造方法：•VN=K;VT=∑;S=S•P:若f(A,t)=B,则A-tB在P中；•对于可接受状态Z，增加产生式Z-ε;求与NFA等价的文法G[S]四.NFA-DFA既NFA的确定化NFA的确定化例子：8等价的DFA五．DFA的最小化DFA的最小化算法DFAM=（K,∑,f,k0,kt),最小状态DFAM’1.构造状态的一初始划分；终态kt和非终态K-kt两组(group)2.对∏施用过程PP构造新划分∏new3.如∏new=∏,则令∏final:=∏并继续步骤4，否则∏:=∏new重复2.4.为∏final中的每一组选一代表，这些代表构成M’的状态。若k是一代表且f(k,a)=t,令r是t组的代表，则M’中有一转换f’(k,a)=rM’的开始状态是含有S0的那组的代表9M’的终态是含有F的那组的代表5.去掉M’中的死状态.例子：1、初始划分：(终态集和非终态集)P0={{1,2,3,4},{5,6,7}}2、观察第一个子集{1,2,3,4}，读入符号a后情形，得出{1,2}和{3,4}是可区别的重新划分：P1={{1,2},{3,4},{5,6,7}}3、在P1中寻找一个子集和一个输入符号，使得这个子集中的状态可区别重新划分：P2={{1,2},{3},{4},{5,6,7}}4、P2中的{5,6,7}可由输入符号a或b而分割重新划分：P3={{1,2},{3},{4},{5},{6,7}}5、经观察P3不能再划分了。令1代表{1,2}消去2,令6代表{6,7}消去2，得到DFAM’六.文法二义性的判定若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一组充分条件文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G′，其中G是二义的，但是却有L(G)=L(G′)，也就是说，这两个文法所产生的语言是相同的。二义文法改造为无二义文法G‘[E]:E→iG[E]：E→T|E+TE→E+ET→F|T*FE→E*EF→（E）|iE→(E)规定算符优先性和结合性如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。七.找短语，直接短语，句柄用语法树找短语，直接短语，句柄子树：语法树中的某个非叶结点连同它所有子孙所组成的树。10•短语：一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。•直接短语：仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串。•句柄：一个句型的语法树中最左那棵只有父子两代的子树的所有叶子的自左至右排列。例子八.LL(1)的判定以及预测分析表的构造，对指定符号串的分析过程1．LL(1)的判定：文法G[S]：S-aA|dA-bAS|ε是否是LL(1)文法？（文法中含有ε，比较麻烦）判断第一个非终结符SSELECT(S-aA)=First(aA)={a}；SELECT(S-d)=First(d)={d}；SELECT(S-aA)∩SELECT(S-d)=Ø满足LL(1)文法要求，判断下一个非终结符ASELECT(A-bAS)=First(bAS)={b}；SELECT(A-ε)=(First(ε)-{ε})∪Follow(A)求Follow(A)：Follow(A)=First(S)+follow(S);Follow(S)={#}+follow(A)其中First(S)={a,d};解得Follow(A)={a,d,#}SELECT(A-bAS)∩SELECT(A-ε)=Ø满足LL(1)文法要求，所有的非终结符都已经判断完毕，所以这个文法是LL(1)文法。九.LR(0)的判定以及分析表的构造，对指定符号串的分析过程LR(0)分析的完整例子例G[S]为:SaAcBeAb11AAbBd1)构造识别活前缀的DFA2)构造它的LR(0)分析表3)分别给出对输入符号串abbcde和abbce#的LR(0)分析步骤。LR(0)项目集及DFA:12