《编译原理 总复习》由会员分享，可在线阅读，更多相关《编译原理 总复习（142页珍藏版）》请在金锄头文库上搜索。
1、1,编译程序是将一种语言（源语言,通常是高级语言）翻译为另一种语言（目标语言，通常用汇编语言或机器语言表示）的计算机程序。,目标程序,翻译,源程序,一个编译程序涉及到三个方面的语言，即源语言、目标语言和编译程序的书写语言。为了描述方便通常用T型图来表示这三个方面的语言。T型图的左上角表示源语言，右上角表示目标语言，底部表示书写语言(实现语言),第一章,2,词 法 分 析,源 程 序,目 标 程 序,语 法 分 析,语 义 分 析,目 标 代 码 生 成,中 间 代 码 优 化,中 间 代 码 生 成,1.2编译过程和编译程序的基本结构,3,第二章,2.2.1 字母表和符号串 字母表 是元素的非
2、空有穷集合。例如：=a，b，c 字母表中至少包含一个元素。字母表中的元素可以是字母、数字或其他符号。 符号（字符） 字母表中的元素称为符号，或称为字符。,4,3. 字符串（字） 符号的有穷序列称为符号串。 例如有字母表 =a，b，c，则有字符串a,b,ab,ba, 符号串总是建立在某个特定字母表上的，且只能由字母表上的有穷多个符号组成。 符号串中符号的顺序很重要，例如ab和ba就是两个 不同的符号串。不包含任何符号的符号串，称为空符 号串，用表示。空符号串由0个符号组成，其长度 |0,5,注意： 是符号串，而不是集合 表示由空符号串所组成的集合，但这样的集合不是空集合 ,6,符号串的长度：符号
3、串中所包含的符号的个数 例s=string, |s|=6, |0 符号串的连接：设、是两个符号串，则称为与的连接 例=some, =thing, =something = 符号串的乘积：设A、B是两个符号串的集合，AB表示A与B的乘积。,2.2.2 符号串的运算,7,例：A=ab,cd,B=ef,gh AB=abef, abgh, cdef, cdgh 特别地， A=A =A 符号串集合的正则闭包A+ A+A A2 A3 An，即A+为集合A上所有符号串的集合 符号串集合的闭包记为A* 定义 A*= A+= A+ 显然，A+=AA*=A*A,8,符号串的幂运算 设x是符号串，则x的幂运算定义为
4、 x0 = x1 = x x2 = xx xn = xxx = xxn-1 (n0) 例如，设x=abc,9,集合的幂运算 设A是符号串的集合，则集合A的幂运算定义为 A0 = A1 = A A2 = AA An = AAA = AAn-1 (n0) 例如，设A=a , b ,则A2=? A+? A*?,10,2. 文法 文法是产生式的非空有穷集合，通常表示成四元组G=(VN,VT,P,S)。其中: VN是产生式中非终结符的集合。 VT是产生式中终结符的集合。 VN VT P是文法规则的集合。 S是一个非终结符，称为文法的开始符号，它至少要在一条规则的左部出现。由它开始，识别出我们所定义的语言
5、。,11,复杂的产生式往往用一些基本的产生式组合而成。 基本式：A，这里是终结符组成的串，这个语法所定义的语言只有一个符号串。 例： A0 嵌套式:AB，、是终结符串，B是一个非终结符串，A所定义的终结符串是每个B定义的语句（可推出的终结符串）前边加串并且后边加 串。 例： AiBchina Blove,一些基本的产生式,重点掌握给定的文法，能够写出文法所表示的语言。,12,递归式：有两个常用的产生式都能表示递归式。 AA |, A A | 它们定义的串集合为：， ， 可写成n，所以L(A)=n|n1 例： (i) D bD| (ii) AaA|d 成对符号递归：可用下述产生式表示成对符号递归
6、： AA| A定义的语言可记为L(A)=nn|n1 例：AabAcd|abcd,一些基本的产生式,13,推导从开始符号开始，经过有限次的推导后得到一个终结符串（句子）。从开始符到句子间，每步推导所得到的含有非终结符的符号串是一个句型，一个文法G经过推导所能获得的全部句子的集合就是这个文法语言L(G). =*表示经过0步或若干步推导 =+表示经过1步或若干步推导,14, 语言的形式定义,4、句型和句子,G = (VT, VN, P, S)，S=* a ，a (VTVN)* 称a为句型。 a VT* ，称a为句子。,句型与句子区别：句型由终结符和非终结符构成，句子只由终结符构成。 联系：仅含终结符
7、的句型是一个句子。 即：句子必定是句型，但句型不一定是句子。,例：设有文法GS: S01 | 0S1 请分别判断：01，000S111，0SS0，0011，0S1是该文法的句子还是句型？,15, 句型与句子举例,例： 设有文法GE: EE+E | E*E| (E) | i 试证明符号串 i+i*i (i*i+i) 是文法GE的句子。,16,例2.5 设有文法GS: S01 | 0S1 有 S=* 01 S=* 0S1 S=* 00S11 S=* 000111 问: 哪些字符串是文法G的句子?哪些是文法的句型?,17,由此可见，从已知文法确定语言的中心思想是： 从文法的开始符号出发，反复连续地使
8、用规则（产生式），对非终结符施行替换和展开，找出句子的规律，用式子或自然语言描述出来。 注意： （1）给定一个文法，就能唯一地确定其语言，即 GL(G) （2）给定一种语言，能确定其文法，但这个文法 不一定是唯一的。,文法和语言的关系, 规范推导和规范归约,最左（右）推导：指对于一个推导序列中的每一步直接推导=,都是对中的最左(右)非终结符进行替换,规范推导: 指最右推导 规范句型: 用规范推导推导出的句型称为规范句型 规范归约(最左归约): 规范推导的逆过程,例：设有文法GS: SAB AA0 | 1B B0 | S1 请给出句子1000 的最左、最右推导。,练习：给出句子101001的最左
9、推导。,19,例2.12 考虑文法GN1： N1N NND | D D0 | 1| 2 该文法是左递归的，它所描述的语言是无穷集合。 当一个语言是无穷集合时，则定义该语言的 文法一定是递归的。,0,1,2+,20,2.5.1 推导和语法树 对句型的推导 过程给出一种图形表示，这种表示称为语法树，也称推导树。,2.5 语法树与文法的二义性,与推导相对应的语法树是一个作了标记的树，其中内部的节点由非终结符标出，树叶节点由终结符标出，每个内部节点都表示推导的一个步骤中的相关非终结符的替换。树根结点是文法的开始符号。,21,语法树的特点： 如果句子中有括号的话，括号在文法中表示了操作的优先次序，这个次
10、序在语法树中已经被树的层次体现出来了。靠近根结点的计算总是较迟处理，靠近叶子的结点被优先处理。,22,短语、简单短语,G = (T, N, P, S)，w = xuy (TN)* 为文法的句型, 若S = xUy ,且 U =+ u, 则u是句型w相对于U 的短语； 若S = xUy, 且 U =u, 则u是句型w相对于U 的简单短语; 其中UN，u (TN)+ , x, y (TN)*,句柄,任一句型的最左简单短语称为该句型的句柄。,短语、简单短语是相对于句型而言， 一个句型可能有多个短语、简单短语，句柄只能有一个。,Note,23,子树：由某一结点连同所有分支组成的部分。 简单子树：指只有
11、单层分支的子树。 短语/直接短语/句柄在语法树中的直观解释： 短语-子树的末端结点形成的符号串是相对于 子树根的短语 直接短语-简单子树的末端结点形成的符号串 是相对于简单子树根的短语 句柄-最左简单子树的末端结点形成的符号串 是句柄,24,解：E=*(E+T)*i+F (E+T)*i+F是G的一句型,25,26,例2.13.设有文法GS=(S,A,B , a，b , P, S) 其中，P为 SAB AAa | bB Ba | Sb 请判断baSb是G的一句型吗？ 如果是，请画出它的推导的分析树，并写出该树的短语、简单短语、句柄。, 文法的二义性,引例：已知简单整型算术表达式文法： exp e
12、xp op exp|( exp ) | i op + | - | * 请画出串 i - i * i 的语法树!,解： 1) 推导 2) 根据推导画语法树,同一个句子若可生成两棵不同的语法树，则定义该句子的文法叫二义性文法。 注意理解：若一个文法中存在某个句子，它有两个不同的最左（最右）推导，这个文法是二义性文法。, 文法二义性的消除, 不修改文法，指定正确的语法树； 修改文法(考虑优先级、结合性等),注意：文法的二义性和语言的二义性是两个不同的概念。 只要某文法定义的语言中，有一个句子有2棵以上的语法树，该文法就是二义性的； 而二义性语言是指，对它不存在无二义性的文法，这样的语言称为先天二义性
13、的语言。,文法GE： ET|E+T|E-T TF|T*F|T/F F(E)|i,文法GE: EE+E | E*E| (E) | i,29,注意： 文法的二义性和语言的二义性是两个不同的概念。通常我们只说文法的二义性，而不说语言的二义性，这是因为可能有两个不同的文法G和G，一个是二义性的，一个不是二义性的，但他们所描述的语言却是一样的，即L(G) = L(G). 将一个语言说是二义性的，是指对它不存在无二义性的文法，这样的语言称为先天二义性的语言。 人们已经证明，不存在一个算法，它能在有限步骤内确切地判定任给的一个上下文无关文法是否是二义性文法。,30,文法和语言分类：0型、1型、2型、3型（乔
14、姆斯基层次）,0型文法称为短语结构文法（非限制）。产生式的左部和右部都可以是符号串，一个短语可以产生另一个短语。,0型：P：u v 其中u (TN)+ ，v (TN)*, 乔姆斯基层次,2.6 文法和语言的分类,31,1型文法称为上下文敏感或上下文有关文法。也即只有在x,y这样的上下文中才能把U改写为u,1型：P：xUyxuy 其中 UN， x,y,u (TN)*,例：1型（上下文有关）文法 文法GS： SCD CaCA C CbCB D ADaD BDbD AabD,32,2型文法称为上下文无关文法。也即把U 推导为v 时，不必考虑上下文。,2型：P：Uv 其中U N ，v (TN)*,文法
15、GS： SAB ABS|0 BSA|1,2型文法即上下文无关文法及相应的语言是我们主要研究的对象。,33,例： GS： S0A|1B|0 A0A|1B|0S B1B|1|0,3型文法称为正则文法，它是对2型文法进行进一步限制 3型文法不能把非终结符嵌在终结符串里。如：S aSb|ab不是3型文法，3型文法不能描述anbn这样的符号串。,3型： (左线性) P：Ut 或 UWt 其中 U、WN tT (右线性) P：Ut 或 UtW 其中 U、WN tT,34, 0型、1型、2型、3型比较, 3型：P：U t 或 U Wt 其中 U、WN tT, 2型： P：U v 其中U N ，v (TN)*, 0型：P：u v 其中u (TN)+ ，v (TN)*, 1型：P：xUy xuy 其中 UN， x,y,u (TN)*,L3 L2 L1 L0,35,3.1 词法分析程序的功能,所谓词法，即构成词的
