编译原理课件 总复习 (1).ppt

《编译原理课件 总复习 (1).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理总复习考试范围、题型第一章1.1---1.3第三章全部第四章全部第五章全部第六章6.1---6.3.4第七章7.1---7.3第八章8.3试卷共八大题，四类考试题型（是非题、填空题、应用题、问答题）绪论编译原理：编译原理指的是编译程序的构造原理和技术。源语言程序是诸如PASCAL、C这样的高级语言，而目标语言是诸如汇编语言或机器语言之类的低级语言，这样的一个翻译程序称为编译程序。词法分析程序语法分析程序语义分析程序中间代码生成代码优化程序目标代码生成信息表管理程序错误检查程序源程序单词符号中间代码中间代码中间代码语法

2、单位目标代码编译程序的逻辑结构文法和语言语言:由句子组成的集合。文法：以有穷的集合刻画无穷的集合的一个工具。字母表：元素的非空有穷集合。(符号集)符号：字母表中的元素。符号串：中的符号组成的任何有穷序列。(含空符号串ε，排列是有顺序的，可用字母表示如：x=aaca）★符号串的运算符号串的长度：符号串中符号的个数。符号串s的长度记为

3、s

4、。ε的长度为0。连接:符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy方幂:符号串x自身连接n次得到的符号串xx…xx(n个x)表示为xn符号串集合：若集合A中一切元素都是某字母

5、表上的符号串，则称A为字母表上的符号串集合。两个符号串集合A和B的乘积：定义为AB=xy

6、xA且yB{ε}A=A{ε}=A闭包：使用*表示上的所有有穷长的串（包括ε）的集合。正闭包：从*中除去ε得到的集合记为+。文法和语言的形式定义产生式（规则或生成式）：是形如α→β或α∷=β的（α，β）有序对，其中α是某字母表V的正闭包V+中的一个符号串，β是V*中的一个符号串。（α∈V+，β∈V*)α称为产生式的左部(或规则的左部)。β称为产生式的右部(或规则的右部)。文法G：四元组（VN，VT，P，S），其中VN、VT和

7、P是非空有穷集。S至少在一条规则中作为左部出现。VN∩VT=φ，S∈VN，V=VN∪VT，称为文法G的字母表。文法在习惯上只将产生式写出。并有如下约定：第一条产生式的左部是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成G[S]，其中S是开始符号★推导的定义直接推导“”α→β，v=γαδ,w=γβδ,则：w是v的直接推导，或说：w直接归约到v，记作vw若存在v=w0w1...wn=w,(n>0)，则称v推导出（产生）w（推导长度为n），或称w归约v.记作vw。若有vw，

8、或v=w，则记为vw+++**和注：包含0步推导；而不包含0步推导。*+推导句型设G[S]是一文法，如果符号串x是从开始符号推导出来的，即Sx，则称x是文法G[S]的句型。句子x仅由终结符号组成（即Sx，且x∈VT*），则称x是G[S]的句子。句型、句子、语言**文法的语言记为L(G)：是文法G的全部句子的集合:L(G)={x

9、Sx，且x∈VT*}文法描述的语言是该文法一切句子的集合。*若L(G1)=L(G2)，则称文法G1和G2是等价的。语言和文法的对应关系是一对多（1：n）的关系。文法的类型0型文法：对任一

10、产生式α→β，都有α∈(VN∪VT)+，且至少包含一非终结符，β∈(VN∪VT)*1型文法：对任一α→β，都有

11、β

12、≥

13、α

14、，仅仅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*(左线性文法)0型文法也叫短语文法1型文法（上下文有关文法）：α1Aα2→α1βα2(A在VN中，其他在V*中，β≠ε)2型文法（上下文无关文法）：A→β(A在VN

15、中，β在V*中，)3型文法也叫正规文法四种文法之间的关系是将产生式做进一步限制而定义的，他们之间的逐级“包含”关系。0型文法描述语言的能力最强，3型文法描述语言的能力最弱。2型文法1型文法0型文法3型文法★上下文无关文法及其语法树语法树：用于描述上下文无关文法的句型推导的直观方法。（每个结点都有一个标记，此标记是V的一个符号，根的标记是S）叶子结点：树中没有子孙的结点。从左到右读出推导树的叶子标记，所得的句型为推导树的结果。也把该推导树称为该句型的语法树。最右（最左）推导：任一步推导αβ，都是对α中的最右（左）非终结符进行替换

16、。最右推导被称为规范推导，所得的句型称为规范句型推导过程中施用产生式的顺序上下文无关文法有足够的能力描述现今程序设计语言的语法结构二义文法若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。或者说，若一个文法存在某个句子有两个不同的最