编译原理课件总复习

1编译原理总复习2考试范围、题型•第一章1.1---1.3第三章全部第四章全部第五章全部第六章6.1---6.3.4第七章7.1---7.3第八章8.3•试卷共八大题，四类考试题型（是非题、填空题、应用题、问答题）3绪论•编译原理：编译原理指的是编译程序的构造原理和技术。•源语言程序是诸如PASCAL、C这样的高级语言，而目标语言是诸如汇编语言或机器语言之类的低级语言，这样的一个翻译程序称为编译程序。词法分析程序语法分析程序语义分析程序中间代码生成代码优化程序目标代码生成信息表管理程序错误检查程序源程序单词符号中间代码中间代码中间代码语法单位目标代码编译程序的逻辑结构4文法和语言语言:由句子组成的集合。文法：以有穷的集合刻画无穷的集合的一个工具。•字母表：元素的非空有穷集合。(符号集)•符号：字母表中的元素。•符号串：中的符号组成的任何有穷序列。(含空符号串ε，排列是有顺序的，可用字母表示如：x=aaca）5★符号串的运算符号串的长度：符号串中符号的个数。符号串s的长度记为|s|。ε的长度为0。连接:符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy方幂:符号串x自身连接n次得到的符号串xx…xx(n个x)表示为xn6•符号串集合：若集合A中一切元素都是某字母表上的符号串，则称A为字母表上的符号串集合。•两个符号串集合A和B的乘积：定义为AB=xy|xA且yB{ε}A=A{ε}=A•闭包：使用*表示上的所有有穷长的串（包括ε）的集合。•正闭包：从*中除去ε得到的集合记为+。7•文法和语言的形式定义1.产生式（规则或生成式）：是形如α→β或α∷=β的（α，β）有序对，其中α是某字母表V的正闭包V+中的一个符号串，β是V*中的一个符号串。（α∈V+，β∈V*)•α称为产生式的左部(或规则的左部)。•β称为产生式的右部(或规则的右部)。2.文法G：四元组（VN，VT，P，S），其中VN、VT和P是非空有穷集。S至少在一条规则中作为左部出现。VN∩VT=φ，S∈VN，V=VN∪VT，称为文法G的字母表。8•文法在习惯上只将产生式写出。并有如下约定：–第一条产生式的左部是开始符号–用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符–G可写成G[S]，其中S是开始符号9★推导的定义•直接推导“”α→β，v=γαδ,w=γβδ,则：w是v的直接推导，或说：w直接归约到v，记作vw若存在v=w0w1...wn=w,(n0)，则称v推导出（产生）w（推导长度为n），或称w归约v.记作vw。若有vw，或v=w，则记为vw+++**和注：包含0步推导；而不包含0步推导。*+•推导10•句型–设G[S]是一文法，如果符号串x是从开始符号推导出来的，即Sx，则称x是文法G[S]的句型。•句子–x仅由终结符号组成（即Sx，且x∈VT*），则称x是G[S]的句子。句型、句子、语言**•文法的语言记为L(G)：是文法G的全部句子的集合:L(G)={x|Sx，且x∈VT*}文法描述的语言是该文法一切句子的集合。*•若L(G1)=L(G2)，则称文法G1和G2是等价的。•语言和文法的对应关系是一对多（1：n）的关系。11文法的类型0型文法：对任一产生式α→β，都有α∈(VN∪VT)+，且至少包含一非终结符，β∈(VN∪VT)*1型文法：对任一α→β，都有|β|≥|α|，仅仅S→ε除外2型文法：对任一产生式α→β，都有α∈VN，β∈(VN∪VT)*3型文法：任一产生式α→β的形式都为(1)A→aB或A→a，其中A∈VN，B∈VN，a∈VT*(右线性文法)或(2)A→Ba或A→a，其中A∈VN，B∈VN，a∈VT*(左线性文法)12•0型文法也叫短语文法•1型文法（上下文有关文法）：α1Aα2→α1βα2(A在VN中，其他在V*中，β≠ε)•2型文法（上下文无关文法）：A→β(A在VN中，β在V*中，)•3型文法也叫正规文法13四种文法之间的关系是将产生式做进一步限制而定义的，他们之间的逐级“包含”关系。0型文法描述语言的能力最强，3型文法描述语言的能力最弱。2型文法1型文法0型文法3型文法14★上下文无关文法及其语法树语法树：用于描述上下文无关文法的句型推导的直观方法。（每个结点都有一个标记，此标记是V的一个符号，根的标记是S）叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。•最右（最左）推导：任一步推导αβ，都是对α中的最右（左）非终结符进行替换。•最右推导被称为规范推导，所得的句型称为规范句型推导过程中施用产生式的顺序•上下文无关文法有足够的能力描述现今程序设计语言的语法结构15二义文法若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者说，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是二义的。文法的二义性和语言的二义性是两个不同的概念。因为可能有两个不同的文法G和G′，其中G是二义的，但是却有L(G)=L(G′)，也就是说，这两个文法所产生的语言是相同的。产生某上下文无关语言的每一个文法都是二义的，则称此语言是先天二义的。16•句型的分析句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法，即总是从左到右地识别输入符号串。分析算法可分为：自上而下分析法（推导）：从文法的开始符号出发，反复使用各种产生式，寻找与输入符号匹配的推导。自下而上分析法（归约）：从输入符号串开始，逐步进行归约，直至归约到文法的开始符号。两种方法反映了两种不同的语法树的构造过程17★短语、直接短语、句柄αβδ是文法G[S]的一个句型，如果：SαAδ且Aβ则称β是句型αβδ相对于非终结符A的短语。若有Aβ则称β是句型αβδ相对于规则A→β的直接短语（或简单短语）。一个句型的最左直接短语称为该句型的句柄。*+(1)每一句型都有一棵语法树，每个语法树的叶组成一句型。(2)每棵子树的叶组成短语，每棵直接子树的叶组成直接短语，最左直接子树的叶组成句柄。(★查找方法)18•有关文法的实用限制文法中不得含有有害规则和多余规则–有害规则：形如U→U的产生式。会引起文法的二义性。–多余规则：指文法中任何句子的推导都不会用到的规则。•1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达的。•2）文法中某些非终结符，由它不能推出终结符号串来，称为不可终止的。19•对于文法G[S]，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1）A必须在某句型中出现。2）必须能从A推出终结符号串t来。即1）文法G[S]，对某两个符号串α和β：SαAβ2）At,t∈VT**+化简文法：去除有害和多余规则20词法分析正规文法（3型文法）、正规式与有穷自动机（FA）正规文法G[S](左线性、右线性)正规式R有穷自动机FA正规语言正规集正规语言（正规文法产生的句子的集合）（由正规式所描述的集合）（FA所能接受的语义，即所能接受的符号串的全体L(M)）N:1N:1N:1用来描述单词的三种方式：G[S]、R、FA21单词的描述工具一、正规文法：文法G=（VN，VT，P，S），P中每一产生式的形式都为：①A→aB或A→a，（右线型文法）或②A→Ba或A→a，（左线型文法）其中：A∈VN，B∈VN，a∈VT*22设字母表为，辅助字母表’={，，，，，，}。1、和是上的R正规集：{}和；2、任何a，a是上的R正规集：{a}；二、正规式R：是说明单词的模式(pattern)的一种重要的表示法（符号法）。3、e1、e2是上的R正规集：L(e1)、L(e2)(e1)、e1e2、e1e2、e1正规集：L(e1)、L(e1)∪L(e2)、L(e1)L(e2)、(L(e1))4、仅由有限次使用上述三步骤而定义的表达式才是上的R，由R表示的字集是上的正规集。23其中•“”读为“或”（也有使用“+”代替“”的）；•“”读为“连接”；•“”读为“闭包”(即，任意有限次的自重复连接)。•在不致混淆时，括号可省去。•规定算符的优先顺序为“”、“”、“”。•连接符“”一般可省略不写。•“”、“”和“”都是左结合的。24•例={d，.，e，+，-},则上的正规式d(.dd)(e(+-)dd)表示的是无符号数的集合。其中d为0~9的数字。12.3.6e读正规式（分段）a(ab)正规集{以a开头的由a、b组成的串}(ab)(ab)正规集{由a、b组成的串，不包含}25正规式的等价•若两个正规式e1和e2所表示的正规集相同,则说e1和e2等价,写作e1=e2。•例如：e1=(ab)，e2=bab(ab)=(ba)b(ab)=(ab)证明方法：1.e1=？e2→L(e1)=?L(e2)2.使用正规运算律/性质来推导e1=…=L(e1)=…=L(e2)=…=e226正规式的运算律•设r,s,t为正规式，正规式服从的代数规律有：1、rs=sr“或”服从交换律2、r(st)=(rs)t“或”的可结合律3、(rs)t=r(st)“连接”的可结合律4、r(st)=rsrt(st)r=srtr分配律5、r=r,r=r是“连接”的恒等元素6、rr=rr=rrr…“或”的抽取律27三、正规文法和正规式的转换一个正规语言可以由正规文法定义，也可以由正规式定义。对上的正规式r,存在一个G=(VN,VT,P,S)使得L(G)=L(r)，反之亦然。对任意一个正规文法，存在一个定义同一个语言的正规式；对每个正规式，存在一个生成同一语言的正规文法。281.正规式R正规文法G[S]将上的一个正规式R转换成文法G=(VN,VT,P,S)。令VT=,选择一SVN，生成正规产生式Sr，并将S定为G的识别符号。若x和y都是正规式，那么(1)AxyAxBBy（BVN）(2)AxyAxAAy(3)AxyAxAy不断应用上述规则做变换，直到每个产生式都符合正规文法的形式（至多含一个非终结符）。292.正规文法G[S]正规式R文法产生式正规式（1）AxB,ByA=xy（2）AxAyA=xy（3）AxyA=xy30有穷自动机文法：从开始符号出发=句子（文法→语言）自动机：给出任意符号串，用FA判断其是否是符合语言的句子。（一种算法）文法0型1型2型3型抽象计算模型图灵机Turing------有穷状态自动机强能力最强（数学模型）语言描述产生（自上而下）识别（自下而上）31•例：标识符（以字母开头，由字母数字组成的串）①G[S]:S→lA|lA→lA|dA|l|d②NFA:③识别aa3b是否是标识符文法的串→从左到右扫描S→A→A→A→ASAll，dlalad3lb32DFAM五元组：M=（K，Σ，f，S，Z）K：有穷集状态集；Σ：有穷输入字母表；f：转换函数，是在K×Σ→K上的映射f（ki，a）=kjS∈K是唯一的一个初态；ZK是一个终态集，终态也称可接受状态或结束状态。NFAM=(K，，f，S，Z)•f：映射函数，K*→2K，其中2K表示K的幂集•SK是初始状态集表示方法：矩阵、状态图33•∑*上的符号串t(=t1tx)在FA上运行f（Q，t1tx）=f（f（Q，t1），tx）其中Q∈K–扩充转换函数f，是K×Σ*→K上的映射，f（Q，）=Qt为DFAM所接受（识别）：若t∑*，f(S，t)=P，其中S为DFAM的初始状态，PZ，Z为终态集。•FA接受的语言：M=（K，Σ，f，S，Z）所能接受的符号串的全体记为L(M)L(M)={x|f(S,x)Z,x}34★NFA的确定化