编译原理复习课.pptx

《编译原理复习课.pptx》由会员分享，可在线阅读，更多相关《编译原理复习课.pptx（120页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章第一章 引引 论论第1页/共120页源语言程序源语言程序目标语言程序目标语言程序翻译翻译程序程序翻译翻译一.什么是编译程序q翻译程序翻译程序 把某一种语言程序把某一种语言程序(称为称为源语言程序源语言程序)等价地转等价地转换成另一种语言程序换成另一种语言程序(称为称为目标语言程序目标语言程序)的程序的程序第2页/共120页高级语言程高级语言程序序机器语言机器语言程序程序结果结果编译编译程序程序翻译翻译运行运行一.什么是编译程序q编译程序编译程序(compiler)(compiler)把某一种把某一种高级语言程序高级语言程序等价地转换成另一种等价地转换成另一种低级语低级语言程序言程序(如汇

2、编语言或机器语言程序如汇编语言或机器语言程序)的程序的程序诊断编译程序诊断编译程序优化编译程序优化编译程序交叉编译程序交叉编译程序可变目标编译程序可变目标编译程序第3页/共120页一.什么是编译程序q解释程序解释程序 把源语言写的源程序作为输入，但不产生目标程序，把源语言写的源程序作为输入，但不产生目标程序，而是边解释边执行源程序本身而是边解释边执行源程序本身源程序源程序结果结果解释解释程序程序解释执行解释执行第4页/共120页二.编译过程编译程序的工作一般分为五个阶段:词法分析语法分析中间代码产生优化目标代码产生第5页/共120页1.1.词法分析任务:输入源程序，对构成源程序的字符串进行扫描

3、和分解，识别出一个个单词符号。依循的原则：构词规则描述工具：有限自动机FOR I :=1 TO 100 DOFOR I :=1 TO 100 DO 保留字 标识符 等符 整常数 保留字 整常数 保留字第6页/共120页2.2.语法分析任务:在词法分析的基础上，根据语言的语法规则把单词符号串分解成各类语法单位。依循的原则：语法规则描述工具：上下文无关文法Z:=X+0.618*Y Z:=X+0.618*Y 算术表达式，赋值语句第7页/共120页3.3.中间代码产生任务:对各类不同语法范畴按语言的语义进行初步翻译。依循的原则：语义规则中间代码:三元式，四元式，树形结构等Z:=X+0.618*Y Z:

4、=X+0.618*Y 翻译成四元式为(1)*0.618 Y T1(1)*0.618 Y T1(2)+X T1 T2(2)+X T1 T2(3):=T2 _ Z(3):=T2 _ Z第8页/共120页4.4.优化任务：对于前阶段产生的中间代码进行加工变换，以期在最后阶段产生更高效的目标代码。依循的原则：程序的等价变换规则第9页/共120页5.5.目标代码产生任务:把中间代码变换成特定机器上的目标代码。依赖于硬件系统结构和机器指令的含义目标代码三种形式:绝对指令代码:可直接运行 可重新定位指令代码:需要连接装配汇编指令代码:需要进行汇编第10页/共120页三.编译程序结构编译程序总框第11页/共1

5、20页四元式单词符号语法单位四元式目标代码词法分析器语法分析器语义分析与中间代码生成器优化段源程序表格管理出错处理目标代码生成器第12页/共120页2.2.表格和表格管理常见的表格:符号名表，常数表，标号表，入口名表，过程引用表。格式:名字信息第13页/共120页3.3.出错处理出错处理程序：出错处理程序：发现源程序中的错误，把有关错误信息报告给用户语法错误语义错误 第14页/共120页4.4.遍(pass)(pass)所谓 遍，就是对源程序或源程序的中间表示从头到尾扫描一次。阶段与遍是不同的概念。一遍可以由若干段组成，一个阶段也可以分若干遍来完成。第15页/共120页5.编译前端与后端编译前

6、端：与源语言有关，如词法分析，语法分析，语义分析与中间代码产生，与机器无关的优化编译后端：与目标机有关，与目标机有关的优化，目标代码产生优点：减少对内存容量的要求，程序逻辑结构清晰;优化更充分，有利于移植。不足:编译程序运行的效率低源语言中间语言目标语言前端后端第16页/共120页第二章 高级语言及其语法描述 第17页/共120页一.语法程序本质上是一定字符集（称为字母表）上的字符串（有限序列）。语法：一组规则，用它可以形成和产生一个合式(well-formed)的程序。规则的一部分称为词法规则，另一部分称为语法规则（或产生式规则）。第18页/共120页语 法词法规则：单词符号的形成规则。单词

7、符号是语言中具有独立意义的最基本结构。一般包括：常数、标识符、基本字、算符、界符等。描述工具：有限自动机语法规则：语法单位的形成规则。语法单位通常包括：表达式、语句、分程序、过程、函数、程序等;描述工具：上下文无关文法第19页/共120页语义语义：一组规则，用它可以定义一个程序的意义。描述方法：自然语言描述：隐藏错误、二义性和不完整性形式描述：F 操作语义(PL/1)(PL/1)F 指称语义(ADA)(ADA)F 代数语义(PASCAL)(PASCAL)第20页/共120页2.32.3 程序语言的语法描述 几个概念:考虑一个有穷 字母表 字符集其中每一个元素称为一个字符上的字(也叫字符串)是指

8、由中的字符所构成的一个有穷序列不包含任何字符的序列称为空字，记为用*表示上的所有字的全体,包含空字例如:设=a，b，则*=,a,b,aa,ab,ba,bb,aaa,.即 是空集，表示一个不含任何元素的集合。第21页/共120页*的子集U和V的连接（积）定义为UV|U&V 设：U a,aa V b,bb 那么：UV=ab,abb,aab,aabb 第22页/共120页V自身的 n次积记为Vn=VVV规定V0=，令 V*=V0V1V2V3 称V*是V的闭包;记 VVV*，称V+是V的正规闭包。闭包V*中每个符号串都是由V中的符号串经有限次连接而成的。第23页/共120页上下文无关文法上下文无关文法

9、文法：描述语言的语法结构的形式规则第24页/共120页上下文无关文法的定义：一个上下文无关文法G G是一个四元式 G=(VG=(VT T，V VN N，S S，P)P)，其中V VT T：终结符集合(非空)V VN N：非终结符集合(非空)，且V VT T V VN N=S S：文法的开始符号，S S V VN NP P：产生式集合(有限)，每个产生式形式为P P，P P V VN N，(V VT T V VN N)*开始符S S至少必须在某个产生式的左部出现一次。第25页/共120页定义：称 A 直接推出，即 A 仅当A 是一个产生式，且，(VT VN)*。如果 1 2 n，则我们称这个序列

10、是从 1到 n的一个推导。若存在一个从 1到 n的推导，则称 1可以推导出 n。对文法G(E)：E i|E+E|E*E|(E)E (E)(E+E)(i+E)(i+i)第26页/共120页n通常，用 表示：从 1 1出发，经过一步或若干步，可以推出 n n。用 表示：从 1 1出发，经过0 0步或若干步，可以推出 n n。q定义：假定G G是一个文法，S S 是它的开始符号。如果 ，则 称是一个句型。仅含终结符号的句型是一个句子。文法G G所产生的句子的全体是一个语言，将它记为 L(G)L(G)。所以 ：即 或第27页/共120页从一个句型到另一个句型的推导往往不唯一。E+Ei+Ei+i E+E

11、E+ii+i最左推导：任何一步 都是对 中的最左非终结符进行替换。最右推导：任何一步 都是对 中的最右非终结符进行替换。规范推导、规范规约第28页/共120页定义：如果一个文法存在某个句子对应两颗不同的语法树，则说这个文法是二义的。G(E)：E i|E+E|E*E|(E)是二义文法。语言的二义性：一个语言是二义性的，如果对它不存在无二义性的文法。可能存在G和G，一个为二义的，一个为无二义的。但L(G)=L(G)二义性问题是不可判定问题，即不存在一个算法，它能在有限步骤内，确切地判定一个文法是否是二义的。可以找到一组无二义文法的充分条件。第29页/共120页形式语言鸟瞰Chomsky于1956年

12、建立形式语言体系，他把文法分成四种类型：0，1，2，3型。第30页/共120页0型(短语文法，图灵机)：产生式形如：其中：(VT VN)*且至少含有一个非终结符；(VT VN)*1型(上下文有关文法，线性界限自动机)：产生式形如：其中：|，仅 S 例外。第31页/共120页2型(上下文无关文法，非确定下推自动机)：产生式形如：A 其中：A VN；(VT VN)*。3型(正规文法，有限自动机)：产生式形如：A B 或 A 其中：VT*；A，B VN 产生式形如：A B 或 A 其中：VT*；A，B VN右线性文法左线性文法第32页/共120页第三章 词法分析词法分析的任务：从左至右逐个字符地对源

13、程序进行扫描，产生一个个单词符号。词法分析器(Lexical Analyzer)又称扫描器(Scanner)：执行词法分析的程序第33页/共120页3.13.1 对于词法分析器的要求对于词法分析器的要求一、词法分析器的功能和输出形式功能:输入源程序、输出单词符号单词符号的种类：基本字(保留字)：如 beginbegin，repeatrepeat，标识符表示各种名字：如变量名、数组名和过程名常数：各种类型的常数运算符：+，-，*，/，界符：逗号、分号、括号和空白第34页/共120页输出的单词符号的表示形式:(单词种别，单词自身的值)单词种别通常用整数编码表示。若一个种别只有一个单词符号，则种别编

14、码就代表该单词符号。假定基本字、运算符和界符都是一符一种。若一个种别有多个单词符号，则对于每个单词符号，给出种别编码和自身的值(单词符号的属性信息)。标识符单列一种；标识符自身的值表示成按机器字节划分的内部码。常数按类型分种；常数的值则表示成标准的二进制形式。第35页/共120页三、状态转换图1 1 概念状态转换图是一张有限方向图。213XY结点代表状态，用圆圈表示。状态之间用箭弧连结，箭弧状态之间用箭弧连结，箭弧上的标记上的标记(字符字符)代表射出结代表射出结状态下可能出现的输入字符状态下可能出现的输入字符或字符类。或字符类。一张转换图只包含有限个状态，其中一张转换图只包含有限个状态，其中有

15、一个为初态，至少要有一个终态。有一个为初态，至少要有一个终态。第36页/共120页识别标识符的状态转换图123字母其他字母或数字*识别整常数的状态转换图123数字其他数字*一个状态转换图可用于识别(或接受)一定的字符串。第37页/共120页单词的描述工具单词的描述工具 程序设计语言中的单词是基本语法程序设计语言中的单词是基本语法成分。单词符号的语法可以用有效的工成分。单词符号的语法可以用有效的工具加以描述，并且基于这类描述工具，具加以描述，并且基于这类描述工具，实现词法分析程序的自动构造。实现词法分析程序的自动构造。正规表达式是典型的词法规则描述正规表达式是典型的词法规则描述工具。工具。第38

16、页/共120页正规式和正规集正规式和正规集正规集正规集可以用可以用正规表达式正规表达式（简称（简称正规式正规式）表示。）表示。正正规规表表达达式式是是表表示示正正规规集集一一种种方方法法。一一个个字字集集合合是是正正规规集集当当且且仅仅当当它它能能用用正正规规式式表示。表示。正规式也称正则表达式（正规式也称正则表达式（regular expression），），是说明单词的模式是说明单词的模式(pattern)的一种重要的表示法的一种重要的表示法（记号），是定义正规集的数学工具。我们用以（记号），是定义正规集的数学工具。我们用以描述单词符号。描述单词符号。第39页/共120页正规式和正规集的递

17、归定义：正规式和正规集的递归定义：对给定的字母表对给定的字母表 1)和和都是都是 上的正规式，它们所表示的正规集为上的正规式，它们所表示的正规集为 和和;2)任何任何a，a是是 上的正规式，它所表示的正规集为上的正规式，它所表示的正规集为a;第40页/共120页3)假定假定e1和和e2都是都是 上的正规式，它们所表示的正规集为上的正规式，它们所表示的正规集为L(e1)和和L(e2)，则，则i)(e1|e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为L(e1)L(e2)，ii)(e1.e2)为正规式，它所表示的正规集为为正规式，它所表示的正规集为L(e1)L(e2)，iii)(e1

18、)*为正规式，它所表示的正规集为为正规式，它所表示的正规集为(L(e1)*，仅由仅由有限次有限次使用上述三步骤而定义的表达式才是使用上述三步骤而定义的表达式才是 上的正规式，仅由这些正上的正规式，仅由这些正规式表示的字集才是规式表示的字集才是 上的正规集。上的正规集。第41页/共120页所有词法结构一般都可以用正规式描述。所有词法结构一般都可以用正规式描述。若两个正规式所表示的正规集相同，则称这两个正规式等价。如若两个正规式所表示的正规集相同，则称这两个正规式等价。如b(ab)*=(ba)*b(a*b*)*=(a|b)*L(ba)*b)=L(ba)*)L(b)=(L(ba)*L(b)=(L(b

19、)L(a)*L(b)=ba*b=,ba,baba,bababa,b=b,bab,babab,bababab,L(b(ab)*)=L(b)L(ab)*)=L(b)(L(ab)*=L(b)(L(a)L(b)*=b ab*=b ,ab,abab,ababab,=b,bab,babab,bababab,L(b(ab)*)=L(ba)*b)b(ab)*=(ba)*b第42页/共120页确定有限自动机(DFA)对状态图进行形式化，则可以下定义：自动机M是一个五元式M=(S,f,S0,F),其中：1.S:有穷状态集，2.：输入字母表(有穷)，3.f:状态转换函数，为SS的单值部分映射，f(s，a)=s表示：

20、当现行状态为s，输入字符为a时，将状态转换到下一状态s。我们把s称为s的一个后继状态。4.S0 S是唯一的一个初态；5 F S：终态集(可空)。第43页/共120页DFA可以表示为状态转换图。假定DFA M含有m个状态和n个输入字符，那么，这个图含有m个状态结点，每个结点顶多含有n条箭弧射出，且每条箭弧用上的不同的输入字符来作标记。第44页/共120页对于*中的任何字，若存在一条从初态到某一终态的道路，且这条路上所有弧上的标记符连接成的字等于，则称 为DFA M所识别(接收)DFA M所识别的字的全体记为L(M)。可以证明：上的字集V V*是正规集，当且仅当存在上的DFA M，使得VL(M)。

21、第45页/共120页非确定有限自动机(NFA)定义：一个非确定有限自动机(NFA)M是一个五元式M=(S,M=(S,f,S S0 0,F)F)，其中：1 S:有穷状态集；2 ：输入字母表(有穷)；3 f:状态转换函数，为S*2S的部分映射(非单值)；4 S S0 0 S S是非空的初态集；5 F S S：终态集(可空)。第46页/共120页从状态图中看NFA 和DFA的区别：1 弧上的标记可以是*中的一个字，而不一定是单个字符；2 同一个字可能出现在同状态射出的多条弧上。DFA是NFA的特例。第47页/共120页1.假定NFA M=，我们对M的状态转换图进行以下改造：1)引进新的初态结点X和终

22、态结点Y，X,Y S，从X到S0中任意状态结点连一条 箭弧，从F中任意状态结点连一条 箭弧到Y。2)对M的状态转换图进一步施行替换，其中k是新引入的状态。证明:加入新初态和新终态的目的是让转换图中初态和终态唯一。任意表示状态集合中的所有节点都应该与新加入节点间有 弧相连。第48页/共120页代之为ikABjijAB代之为ijA|BijBA代之为ijA*ik jA按下面的三条规则对V进行分裂:第49页/共120页逐步把这个图转变为每条弧只标记为 上的一个字符或，最后得到一个NFA M，显然L(M)=L(M)第50页/共120页2.把上述NFA确定化采用子集法.设I是的状态集的一个子集，定义I的-

23、闭包-closure(I)为:i)若s I，则s-closure(I)；ii)若s I，则从s出发经过任意条 弧而能到达的任何状态s都属于-closure(I)即 -closure(I)=I s|从某个s I出发经过任意条 弧能到达s第51页/共120页设a是 中的一个字符，定义Ia=-closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。第52页/共120页确定化的过程:不失一般性，设字母表只包含两个a a和b b，我们构造一张表:第53页/共120页首先，置第1行第1列为-closure(X)求出这一列的Ia，Ib；然后，检查这两个Ia，Ib，看它们是否已在表中的第

24、一列中出现，把未曾出现的填入后面的空行的第1列上，求出每行第2，3列上的集合.重复上述过程，知道所有第2，3列子集全部出现在第一列为止。第54页/共120页现在把这张表看成一个状态转换矩阵，把其中的每个子集看成一个状态。这张表唯一刻划了一个确定的有限自动机M，它的初态是-closure(X)，它的终态是含有原终态Y的子集。不难看出，这个DFA M与M等价。第55页/共120页正规文法与有限自动机的等价性定理：1.对每一个右线性正规文法G或左线性正规文法G，都存在一个有限自动机(FA)M，使得L(M)L(G)。2.对每一个FA M，都存在一个右线性正规文法GR和左线性正规文法GL，使得L(M)L

25、(GR)L(GL)。第56页/共120页 了解转换过程：1.1.对每一个右线性正规文法G或左线性正规文法G，都构造一个有限自动机（FA）M，使得L(M)L(G)。(1)设右线性正规文法G=。将VN中的每一非终结符号视为状态符号，并增加一个新的终结状态符号f，f VN。令M=，其中状态转换函数 由以下规则定义：第57页/共120页(a)若对某个A VN及a VT，P中有产生式Aa，则令(A,a)=f(b)对任意的A VN及a VT，设P中左端为A，右端第一符号为a的所有产生式为：AaA1|aAk （不包括Aa），则令(A,a)=A1,Ak。显然，上述M是一个NFA。第58页/共120页对于右线性

26、正规文法G，在S w的最左推导过程中:利用AaB一次就相当于在M中从状态A经过标记为a的箭弧到达状态B（包括a=的情形）;在推导的最后，利用Aa一次则相当于在M中从状态A经过标记为a的箭弧到达终结状态f（包括a=的情形）。综上，在正规文法G中，S w的充要条件是：在M中，从状态S到状态f有一条通路，其上所有箭弧的标记符号依次连接起来恰好等于w，这就是说，w L(G)当且仅当w L(M)，故L(G)L(M)。第59页/共120页(2)设左线性正规文法G=。将VN中的每一符号视为状态符号，并增加一个初始状态符号q0，q0 VN。令M=，其中状态转换函数 由以下规则定义：(a)若对某个A VN及a

27、VT，若P中有产生式Aa，则令(q0,a)=A(b)对任意的A VN及a VT，若P中所有右端第一符号为A，第二个符号为a的产生式为：A1Aa,AkAa，则令(A,a)=A1,Ak。与(1)类似，可以证明L(G)L(M)。第60页/共120页正规式与有限自动机的等价性定理：1.对任何FA M，都存在一个正规式r，使得L(r)=L(M)。2.对任何正规式r，都存在一个FA M，使得L(M)=L(r)。2对转换图概念拓广，令每条弧可用一个正规式作标记。(对一类输入符号)第61页/共120页证明：1 1 对 上任一NFA M，构造一个 上的正规式r，使得L(r)=L(M)。首先，在M的转换图上加进两

28、个状态X和Y，从X用 弧连接到M的所有初态结点，从M的所有终态结点用 弧连接到Y，从而形成一个新的NFA，记为M，它只有一个初态X和一个终态Y，显然L(M)=L(M)。然后，反复使用下面的一条规则，逐步消去的所有结点，直到只剩下X和Y为止；第62页/共120页代之为ijr1r2kikr1r2代之为ijr1|r2ijr2r1代之为ikr1r2*r3ijr1r3kr2第63页/共120页对一个DFA M最少化的基本思想:把M的状态集划分为一些不相交的子集，使得任何两个不同子集的状态是可区别的，而同一子集的任何两个状态是等价的。最后，让每个子集选出一个代表，同时消去其他状态。第64页/共120页具体

29、做法:对M的状态集进行划分首先，把S划分为终态和非终态两个子集，形成基本划分。假定到某个时候，已含m个子集，记为=I(1)，I(2)，I(m)，检查 中的每个子集看是否能进一步划分:对某个I(i)，令I(i)=s1,s2,sk，若存在一个输入字符a使得Ia(i)不会包含在现行 的某个子集I(j)中，则至少应把I(i)分为两个部分。第65页/共120页自上而下分析自上而下分析第四章第四章 语法语法分析分析第66页/共120页4.1 语法分析器的功能语法分析的任务是分析一个文法的句子结构。语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子(合式程序)。第67页/共1

30、20页4.2 自上而下分析面临的问题自上而下就是从文法的开始符号出发，向下自上而下就是从文法的开始符号出发，向下推导推导，推出句子。，推出句子。带带“回溯回溯”的的不带回溯的递归子程序不带回溯的递归子程序(递归下降递归下降)分析方法。分析方法。自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符自上而下分析的主旨：对任何输入串，试图用一切可能的办法，从文法开始符号号(根结点根结点)出发，自上而下地为输入串建立一棵出发，自上而下地为输入串建立一棵语法树语法树。或者说，为。或者说，为输入串寻找一个最左推导。输入串寻找一个最左推导。第68页/共120页当某个非终结符有多个产生式候选时

31、，可能带来如下问题:1.1.分析过程中，当一个非终结符用某一个候选匹配成功时，这种匹配可能是暂时的。出错时，不得不“回溯”。2.2.文法左递归问题。一个文法是含有左递归的，如果存在非终结符P P含有左递归的文法将使自上而下的分析陷入无限循环。第69页/共120页结论结论左递归和回溯问题的产生直接与描述语言的文法有关。左递归和回溯问题的产生直接与描述语言的文法有关。因此，要对文法进行确定的自顶向下分析应该改造文法，使其不含左递归和因此，要对文法进行确定的自顶向下分析应该改造文法，使其不含左递归和回溯。回溯。第70页/共120页左递归的消除直接消除见诸于产生式中的左递归：假定关于非终结符P的规则为

32、PP|其中 不以P开头。我们可以把P的规则等价地改写为如下的非直接左递归形式：P P P P|左递归变右递归第71页/共120页一般而言，假定P关于的全部产生式是PP 1|P 2|P m|1|2|n其中，每个 都不等于，每个 都不以P开头 那么，消除P的直接左递归性就是把这些规则改写成：P 1P|2P|nP P 1P|2P|mP|左递归变右递归第72页/共120页消除左递归的算法:1.把文法G的所有非终结符按任一种顺序排列成P1，P2，Pn；按此顺序执行；2.FOR i:=1 TO n DO BEGIN FOR j:=1 TO i-1 DO 把形如PiPj 的规则改写成 Pi 1|2|k ;(

33、其中Pj 1|2|k是关于Pj的所有规则)消除关于Pi规则的直接左递归性 END3.化简由2所得的文法。去除那些从开始符号出发永远无法到达的非终结符的产生规则。第73页/共120页消除回溯、提左因子为了消除回溯就必须保证：对文法的任何非终结符，当要它去匹配输入串时，能够根据它所面临的输入符号准确地指派它的一个候选去执行任务，并且此候选的工作结果应是确信无疑的。A 1|2|nSa.IPA.第74页/共120页令G是一个不含左递归的文法，对G的所有非终结符的每个候选 定义它的终结首符集FIRST()为：特别是，若 ，则规定FIRST()。如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同

34、候选 i和 jFIRST(i)FIRST(j)当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。第75页/共120页提取公共左因子:假定关于A的规则是 A 1|2|n|1|2|m(其中，每个 不以 开头)那么，可以把这些规则改写成A A|1|2|mA 1|2|n经过反复提取左因子，就能够把每个非终结符(包括新引进者)的所有候选首符集变成为两两不相交。第76页/共120页当当A A面临输入符面临输入符a a时时,若若a a FIRST(A)FIRST(A)且且FIRST(A),FIRST(A),则则考虑考虑自动匹配问题

35、自动匹配问题。对于上述算术表达式文法对于上述算术表达式文法,若输入串为若输入串为i/i,i/i,即使让即使让TT自动匹配自动匹配,“/”仍不仍不能与后面符号匹配能与后面符号匹配,此时没必要让此时没必要让TT自动匹配。自动匹配。结结论论:只只有有在在当当前前输输入入符符能能与与A A后后的的第第一一个个终终结结符符匹匹配配成成功功时时,才才让让A A自自动动得得到到匹匹配配。这这就就要要求求分分析析前前先先求求出出紧紧跟跟在在A A后的终结符后的终结符,即即FOLLOW(A)FOLLOW(A)。第77页/共120页假定S是文法G的开始符号，对于G的任何非终结符A，我们定义特别是，若 ，则规定 F

36、OLLOW(A)分析条件即即FOLLOW(A)是是所有句型所有句型中紧跟在中紧跟在A之后的之后的终终结符结符 或或#。第78页/共120页自动匹配条件自动匹配条件 当当 A面面 临临 输输 入入 符符 a时时,若若 a FIRST(A)且且FIRST(A),则则只只有有当当a FOLLOW(A)时时,才才使使A自动得到匹配。缺少任一条件自动得到匹配。缺少任一条件,均不自动匹配。均不自动匹配。若若输输入入符符a FIRST(A)且且a FOLLOW(A),则则当当FIRST(A)时时仍仍可可能能需需进进行行试试探探(回回溯溯)。因因此此,对对于于存存在在-生生成成式式的的非非终终结结符符A,若若

37、要要进进行行不不带带回回溯溯的的自自上上而而下下分分析析,则则FIRST(A)与与FOLLOW(A)应应互互不不相交相交。第79页/共120页n构造不带回溯的自上而下分析的文法条件1.文法不含左递归，2.对于文法中每一个非终结符A的各个产生式的候选首符集两两不相交。即，若A 1|2|n 则 FIRST(i)FIRST(j)(i j)3.对文法中的每个非终结符A，若它存在某个候选首符集包含，则FIRST(i)FOLLOW(A)=i=1,2,.,n如果一个文法G满足以上条件，则称该文法G为LL(1)LL(1)文法文法。第80页/共120页对于一个满足上述条件的文法，可以对其输入串进行有效的无回溯的

38、自上而下分析。假设要用非终结符A进行匹配，面临的输入符号为a，A的所有产生式为A 1|2|n1.若a FIRST(i)，则指派 i执行匹配任务；2.若a不属于任何一个候选首符集，则：(1)若 属于某个FIRST(i)且 a FOLLOW(A)，则让A与 自动匹配。(2)否则，a的出现是一种语法错误。第81页/共120页对每一文法符号X VTVN构造FIRST(X)连续使用下面的规则，直至每个集合FIRST不再增大为止：1.若X VT，则FIRST(X)X。2.若X VN，且有产生式Xa，则把a加入到FIRST(X)中；若X 也是一条产生式，则把 也加到FIRST(X)中。第82页/共120页3

39、.l若XY是一个产生式且Y VN，则把FIRST(Y)中的所有非-元素都加到FIRST(X)中；l若XY1Y2Yk是一个产生式，Y1，Yi-1都是非终结符，而且，对于任何j，1 j i-1，FIRST(Yj)都含有(即Y1Yi-1)，则把FIRST(Yi)中的所有非-元素都加到FIRST(X)中；特别是，若所有的FIRST(Yj)均含有，j1，2，k，则把 加到FIRST(X)中。第83页/共120页对于文法G的每个非终结符A构造FOLLOW(A)的办法是，连续使用下面的规则，直至每个FOLLOW不再增大为止：1.对于文法的开始符号S，置于FOLLOW(S)中；2.若A B 是一个产生式，则把

40、FIRST()加至FOLLOW(B)中；3.若A B是一个产生式，或AB 是一个产生式而 (即FIRST()，则把FOLLOW(A)加至FOLLOW(B)中。第84页/共120页4.4 4.4 递归下降分析程序构造递归下降分析程序构造递归下降分析法也称递归子程序法，是一种递归下降分析法也称递归子程序法，是一种直观易于构造的自顶向下分析方法。分析过直观易于构造的自顶向下分析方法。分析过程则通过自上而下一级一级地调用子程序来程则通过自上而下一级一级地调用子程序来实现，所以称为实现，所以称为递归下降分析法递归下降分析法。思想思想:对文法中的每个对文法中的每个非终结符非终结符编写一个处理编写一个处理子

41、程序，处理子程序的代码结构由相应的非子程序，处理子程序的代码结构由相应的非终结符的规则终结符的规则右部右部来决定：规则右部的终结来决定：规则右部的终结符号与输入符号相匹配，非终结符与相应的符号与输入符号相匹配，非终结符与相应的子程序调用相对应，非终结符对应的各个候子程序调用相对应，非终结符对应的各个候选式与分支结构相对应。选式与分支结构相对应。第85页/共120页构造不带回溯的自上而下分析器分析程序由一组递归过程组成，文法中每个非终结符对应一个过程；所以这样的分析程序称为递归下降分析器。(因为文法的定义通常是递归的)几个全局过程和变量：ADVANCE，把输入串指示器IP指向下一个输入符号，即读

42、入一个单字符号SYM，IP当前所指的输入符号ERROR，出错处理子程序第86页/共120页每个非终结符有对应的子程序的定义，首先在分析过程中，当需要从某个非终结符出发进行展开(推导)时，就调用这个非终结符对应的子程序。第87页/共120页4.5 预测分析程序预测分析程序或LL(1)分析法：总控程序分析表 MA，a矩阵，A VN，a VT 是终结符或，分析栈 STACK 用于存放文法符号第88页/共120页总控程序分析表X#输入串分析栈STACKa1a2.ai#预测分析程序的工作图#Sa1a2.ai#分析开始时：第89页/共120页二、分析表MA，a的构造q构造FIRST()和FOLLOW(A)

43、q构造分析表MA，a第90页/共120页在对文法G的每个非终结符A及其任意候选 都构造出FIRST()和FOLLOW(A)之后，现在可以用它们来构造G的分析表MA，a。1.对文法G的每个产生式A 执行第2步和第3步；2.对每个终结符a FIRST()，把A 加至MA，a中；3.若FIRST()，则对任何b FOLLOW(A)把A 加至MA，b中。4.把所有无定义的MA，a标上“出错标志”。第91页/共120页第五章第五章 语语法分析法分析自下而上分析第92页/共120页语法分析的方法：自下而上分析法(Bottom-up)(Bottom-up)基本思想：从输入串开始，逐步进行“归约归约”，直到文

44、法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LRLR分析法：规范归约第93页/共120页5.5.1 1.2.2 规范归约定义：令G G是一个文法，S S是文法的开始符号，假定是文法G G的一个句型，如果有 且 则 称是句型相对于非终结符A A的短语。特别是，如果有A A,则称 是句型相对于规则A A 的直接短语。一个句型的最左直接短语称为该句型的句柄。第94页/共120页把上例倒过来写，则得到：S S aAcBeaAcBe aAcde aAcde aAbcd

45、e aAbcde a abbcde bbcde 显然这是一个最右推导。规范归约规范归约是一个最右推导最右推导的逆过程最左归约最左归约 规范推导规范推导由规范推导推出的句型称为规范句型。第95页/共120页首先必须定义任何两个可能相继出现的终结符a与b(可能中间有VN),的优先关系 三种关系ab a的优先级高于b注意：与数学上的,=不同a a算符优先分析法第96页/共120页算符优先文法及优先表构造一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：QR 则我们称该文法为算符文法。约定：a、b代表任意终结符；P、Q、R代表任意非终结符；代表由终结符和非

46、终结符组成的任意序列，包括空字。第97页/共120页假定G G是一个不含-产生式的算符文法。对于任何一对终结符a a、b b，我们说：p1.a1.a b b当且仅当文法G G中含有形如PPabab或PPaQbaQb的产生式；p3.a 3.a b b 当且仅当G G中含有形如PPRbRb的产生式，而 R R a a或R R aQaQ。p2.a b当且仅当G中含有形如PaR的产生式，而R b或R Qb；n如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：a b 则称G是一个算符优先文法。第98页/共120页从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式

47、，可找出所有满足a b的终结符对。确定满足关系 的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：a b当且仅当G中含有形如PaR的产生式，而R b或R Qb；第99页/共120页从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候选式，可找出所有满足ab的终结符对。确定满足关系 的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：a b 当且仅当G中含有形如PRb的产生式，而 R a或R aQ。第100页/共120页从算符优先文法G构造优先关系表的算法。通过检查G的每个产生式的每个候

48、选式，可找出所有满足ab的终结符对。确定满足关系 的所有终结符对：首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：比较比较第101页/共120页q有了这两个集合之后，就可以通过检查每个产生式的候选式确定满足关系的所有终结符对。假定有个产生式的一个候选形为aP 那么，对任何b FIRSTVT(P)，有 a b。第102页/共120页数据结构：布尔数组FP，a，使得FP，a为真的条件是，当且仅当a FIRSTVT(P)。开始时，按上述的规则(1)对每个数组元素FP，a赋初值。栈STACK，把所有初值为真的数组元素FP，a的符号对(P，a)全都放在STACK之中。第

49、103页/共120页运算：如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如PQ 的产生式，若FP，a为假，则变其值为真且将(P，a)推进STACK栈。上述过程必须一直重复，直至栈STACK拆空为止。第104页/共120页如果把这个算法稍为形式化一点，我们可得如下所示的一个程序(包括一个过程和主程序)：PROCEDURE INSERT(P，a)；IF NOT FP，a THENBEGIN FP，a:=TRUE；把(P，a)下推进STACK栈 END；第105页/共120页主程序：BEGIN FOR 每个非终结符P和终结符a DO FP，a:=FALSE；FOR 每个形如Pa或

50、PQa的产生式 DO INSERT(P，a)；WHILE STACK 非空 DOBEGIN 把STACK的顶项，记为(Q，a)，上托出去；FOR 每条形如PQ的产生式 DOINSERT(P，a)；END OF WHILE；END第106页/共120页这个算法的工作结果得到一个二维数组F，从它可得任何非终结符P的FIRSTVT。FIRSTVT(P)a|FP，a=TRUE同理，可构造计算LASTVT的算法。第107页/共120页构造集合LASTVT(P)的算法。按其定义，可用下面两条规则来构造集合LASTVT(P)：1.若有产生式P a或P aQ，则a LASTVT(P)；2.若a LASTVT(