【精品】编译原理ppt课件（完整）

1,编译原理,一 什么是编译程序？,2,计算机经过几十年的发展， 在程序设计语言方面,已经从低级语言发展到高级语言;然而,计算机内部的本质只能识别 0 , 1 代码序列（机器语言）,而对高级语言甚至符号语言仍然一窍不通。 因此用高级语言编写的程序,必须先翻译为机器语言，才能被计算机理解执行。第一个完成这种翻译任务的编译程序为FORTRAN编译程序,是上世纪五十年代设计的.,第一章 引论,第一节、编译程序概述,3,定义:设源语言为L1,目标语言为L2, 翻译程序是一个程序,它能将L1转换为逻辑上等价的L2。 若 L1 为高级语言，L2 为低级语言或机器语言，称这种 翻译程序为编译程序。 若 L1 为低级语言，L2 为机器语言，称这种翻译程序为 汇编程序。 解释程序是指逐条翻译 L1的语句，并立即执行翻译出的 目标代码序列。 编译原理 就是介绍编译程序的一般规律及设计方法的一门课程。,高级语言程序,机器语言程序,翻译为,4,二 编译过程概述 编译程序从接受源程序到输出目标代码的整个过程，可逻辑的分为 5 个阶段，词 法 分 析语 法 分 析 中间代码生成 代 码 优 化 目标代码生成 1） 词法分析：把源程序作为字符串进行扫描 ，根据单词词法，识别出所有单词，过滤无用符，并检查是否为合法的单词。 单词一般分为如下几种： 基本字，标识符，常数，算符，界符,5,例如： if n 循环控制语句 while do ; for := to do ; repeat ;. until 7 子程序调用 函数调用一般出现在表达式中,形式如下: (实际参数) 过程调用一般作为语句,形式如下: (实际参数);,25,8 输入输出语句 read(); write();9 简单句和复合句 简单句是指不包含其它语句的基本语句, 复合句是指句中有句.例如: V:=E,goto L ,read(a,b) 等都是简单句; if B then S else S, while B do S 等都是复合句.,26,五 子程序参数传递 当调用一个子程序时,首先应将所需的数据传递给子程序,传递方式主要有三种: 传值,传地址,传名 设有如下函数: function distence(x1,y1,x2,y2):real; begin distence:=sqrt(x2-x1)*2+(y2-y1)*2) end; x1,y1,x2,y2 称为形式参数 设主程序调用如下: d=distence(a1,b1,a2,b2); a1,b1,a2,b2 称为实际参数.,27,1传值 调用程序把实际参数的值传递到形式参数的空间中.,这种方式,子程序一般不改变实际参数的值.,28,这种方式,子程序间接访问主程序实际参数的值,改变了实际参数的值.,29,3传名 传名是一种宏替换,直接在调用处产生一个子程序副本,并且用实际参数名替代形式参数名. 设主程序调用如下: d:=distence(a1,b1,a2,b2);相当于在此处产生一段程序: d:=sqrt(a2-a1)*2+(b2-b1)*2);,30,六 存储分配 程序运行时,必须分配相应的存储空间. 这些空间包括:变量空间,常量空间,临时空间,连接单元 等.有的空间在编译时就能确定其大小,而有的空间必须在程序运行时才能确定.根据这一特性,把空间分配分为两种: 静态存储分配 动态存储分配1 静态存储分配 若在编译时能完全确定程序所需空间大小,并能确定每个数据项的地址,就可在编译时分配所需空间,这种分配方法称为静态存储分配. 若一个语言无递归调用,无可变数据项,则可静态地确定各数据项的空间大小和地址. Fortran语言满足这种定义.,31,2 动态存储分配 是指在程序运行时才能确定存储空间和地址的一种分配方法.适用于允许递归和可变数据项的语言,如pascal 和 c 语言. 一般采用堆栈动态地分配空间, 当调用子程序时,就在堆栈中为该子程序分配所需空间;而子程序运行结束后,就释放该子程序空间.,32,第二章 词法分析,内容提要:状态转换图正规式与有限制动机词法分析器的自动生成,词法分析器,源程序,单词序列,34,第一节 状态转换图,一 单词分类及表示 编译中,把高级语言的单词分为五类: 标识符,基本字,常数,运算符,界符 基本字,运算符,界符都是有限可枚举的;而标识符,常数可认为是无限的. 简单起见,单词可表示为如下二元组: (单词分类号,单词自身值); 或者为: (单词种别码,单词自身值); 标识符,常数 各为一个种别码,而由于基本字,运算符,界符的有限性,可以设计为一字一个种别码.,35,36,二 词法分析器的设计1 源程序的预处理子程序 源程序中,存在许多编辑用的符号,它们对程序逻辑功能无任何影响. 例如:回车,换行,多余空白符,注释行等.在词法分析之前,首先要剔除掉这些符号,使得词法分析更为简单.,源程序,输入缓冲区,预处理子程序,扫描缓冲区2,扫描缓冲区1,缓冲区分为两部分,每个长度为256字节,这样单词的总长度可达到256字节.预处理子程序把处理好的字符串轮流放入两个缓冲区中,供词法分析程序使用.,37,2 词法分析程序 词法分析程序又称为词法分析器或扫描器.可以单独为一个程序;也可以作为整个编译程序的一个子程序,当需要一个单词时,就调用词法分析子程序返回一个单词.这里,作为子程序介绍. 词法分析器的结构:,源程序,输入缓冲区,预处理子程序,扫描缓冲区2,扫描缓冲区1,词法分析子程序,调用,返回一单词,数据,38,3 词法规则的表示-状态转换图定义:状态转换图是一有向图,由有限个结点及有向边连接而成; 每个结点称为状态;状态图有一个初态,多个终态;每条边上 有相应的字符. 状态转换图用于表示单词结构,从状态转换图的初态到终态间,每条路径上字符的连接,就构成了该状态图的合法单词.例如:,0,1,2,初态,终态,字母,字母,数字,其它,*,1标识符的状态图表示:,星号表示单词尾部多跟一个字符,应该去掉.,39,0,1,2,初态,终态,数字,数字,其它,*,2整数的状态图表示:,0,1,6,初态,终态,数字,数字,其它,*,3实数的状态图表示:,2,3,4,5,6,数字,数字,数字,E,+或 ,数字,E,其它,数字,40,4 单词的识别 状态图即可以表示单词规则,同时也可以用于识别单词. 设有一字符串S = s1s2.sn, 若状态图中存在一初态到终态的路径,且路径上字符的连接为: s1s2.sn, 称 S 可被状态图识别.例如: S=var1,0,1,2,初态,终态,v,ar,1,其它,*,保留字由于满足标识符定义,因此可以跟标识符用同样的状态图表示与识别,只需增加一个保留字表,当识别出一个标识符时,通过查保留字表来区别保留字及普通标识符.,因此 var1 是一个合法的标识符.,41,5 一个简单示例 构造一个简单语言所有单词的状态转换图.该语言的单词种类如下表所示:,42,0,1,2,初态,终态,字母,字母,数字,其它,*,空白,3,4,终态,数字,数字,非数字,*,5,=,6,+,7,*,9,8,*,*,非 *,*,10,11,(,12,),13,其它,43,6 状态转换图的程序实现 为便于程序实现,假设每个单词间都有界符或运算符或空格隔开,并引入下面的全局变量及子程序:1) CHAR 字符变量2) TOKEN 单词字符串3) GETCHAR 读一个字符到 CHAR 中4) GETBC 读一个非空白字符到CHAR 中5) CONCAT 把CHAR 中字符连接到TOKEN 之后6) LETTER 判断CHAR 中字符是否为字母7) DIGIT 判断CHAR 中字符是否为数字8) RESERVE 用TOKEN中的字符串查找保留字表,并返回保留 字种别码,若返回零,则非保留字9) RETRACT 把CHAR 中字符回送到缓冲区,44,下面分析状态图的结构特点.每个状态图都由三种结构构成: 分支结构 循环结构 终结点1分支结构程序设计,i,i2,i1,in,c1,c2,cn,state i:GETCHAR; CASE CHAR OF c1 :CONCAT；state i1: . c2 :CONCAT；state i2: . cn :CONCAT；state in: . ELSE ERROR END;,45,2循环结构程序设计,i,j,C,其它,state i:GETCHAR; WHILE CHAR=C DO CONCAT;GETCHAR; RETRACT；state j: .,3终结点程序设计 一般对应一条返回语句: return( c,val); c 为种别码, val 为单词值. 带 * 号的终结点,必须用RETRACT 退还多余字符 下面程序为简单示例语言的实现:,46,TYPE WORDTYPE=RECORD C：INTEGER； VAL：CHAR； END；FUNCTION RETURN_WORD( ):WORDTYPE; STATE0: TOKEN:=;GETCHAR;GETBC; CASE CHAR OF A.Z: CONCAT; STATE1:GETCHAR; WHILE (LETTER OR DIGIT) DO CONCAT;GETCHAR; RETRACT； STATE2: C:=RESERVE; IF C=0 THEN RETURN($ID,TOKEN) ELSE RETURN(C,_ ) ,47, 0. 9: CONCAT; STATE3:GETCHAR; WHILE ( DIGIT) DO CONCAT;GETCHAR; RETRACT； STATE4: RETURN($INT,TOKEN ); =: STATE5:RETURN($ASSIGN,_ ); +: STATE6:RETURN($PLUS,_ ); *: STATE7:GETCHAR; STATE9: IF CHAR=* THEN RETURN($POWER,_ ); STATE8: RETRACT; RETURN($STAR,_ ); , : STATE10:RETURN($COMMA,_ ); ( : STATE11:RETURN($LPAR,_ ); ) : STATE12:RETURN($RPAR,_ ); ELSE STATE13: ERROR,这节介绍词法规则的形式表示(正规式),从正规式向有限自动机的转化.,正规式,有限自动机,词法分析器,控制程序,自动生成器,转化,合成,第二节 正规式与有限自动机,49,一 基本概念 定义 1 字与字集 假设: 是一有穷字符集,它的每个元素称为一个字符; 字- 上的一个字,是由 中的字符所构成的一个有穷序列;空串-不包含任何元素的序列称为空串,记为;闭包*- 上所有可能的字的全体; 空字集-不含任何字的集合称为空字集;记为 = ; 例如: =a,b 则 *=,a,b,aa,ab,ba,bb. 注意: , , 三者间的关系定义 2 连接运算 设 U,V * 则 UV= | U, V 一般 UVVU Vn =VV.V 称为 V 的 n 次积,50,例如: 设 U=a,aa, V=b 则UV=ab,aab VU=ba,baa定义 3 V的闭包 设 V 为字集,且 V0= 令 V*=V0V1 V2 . V+= V* - 称V* 为V的闭包 称V+ 为V的正则闭包 注意: * 与 V* 的区别.,51,二 正规式与正规集 *是一个无穷集,在程序语言中,我们只研究满足词法规则(正规式)的单词集(正规集).定义 1 正规式与正规集的递归定义 : 1) , 是 上的正规式, 所表示的正规集为 , ; 2) 若 a ,则 a 为正规式, 所表示的正规集为 a; 3) 设U,V 为 上的正规式, 所表示的正规集为 L(U),L(V); 则 U|V为 上的正规式, 所表示的正规集为 L(U) L(V); UV为 上的正规式, 所表示的正规集为 L(U) L(V); V* 为 上的正规式, 所表示的正规集为 L(V)* ; 4) 仅当有限次使用上述三步骤而定义的表达式,才是 上的正规式 , 而这些正规式所表示的字集才是上的正规集.,52,示例: 令=A.Z,0.9 则整数的正规式为: (0|1|2.|9)(0|1|2.|9) * 所表示的正规集为所有整数; 标识符的正规式为:(A|B|.Z)(A|B|.Z| 0|1|.|9) * 所表示的正规集为所有标识符定义 2 若两个正规式 U,V 所表示的正规集相同,即 L(V)=L(U), 则称两个正规式等价,记为 U=V.正规式的运算: 设 U V W 为正规式, 则满足以下关系: 1) U|V=V|U 2) U|(V|W)=(U|V)|W 3) U(VW)=(UV)W 4) U(V|W)=UV|UW (U|V)W=UW|VW 5) U=U =U,53,三 确定有限自动机 一个确定有限自动机(DFA M)是一个五元式: DFA M=(S, , f,s0,Z) 其中 S 是一有限集,每个元素称为一个状态; 是一个有穷字母表,每个元素为一字符; f 是一个单值映射函数,f(si,a)=sj ( si , sj S, a ); 其含义为:在状态 si ,输入字符 a 时,将转换到下一状态sj. 称sj为 si的后继状态. s0 S, 是唯一的初态; Z S ,是终态集. 一个DFAM可用状态转换矩阵或状态图表示,54,例如: DFAM=( 0,1,2,3, a,b, f, 0, 3) 其中f为: f(0,a)=1 f(1,a)=3 f(2,a)=1 f(3,a)=3 f(0,b)=2 f(1,b)=2 f(2,b)=3 f(3,b)=3状态转换矩阵可表示为: 状态图可表示为:,ab012132213333,状态,字 符,0,1,3,初态,终态,2,a,b,b,a,a,a,b,b,55,四 非确定有限自动机 一个非确定有限自动机(NFA M)是一个五元式: NFA M=(S, , f,S0,Z) 其中 S 是一有限集,每个元素称为一个状态; 是一个由穷字母表,每个元素为一字符; f 是一个多值映射函数,f(si,)=s i1 , s i2 ,. s ik ( si , si1 ,. , s ik S, *); 其含义为:在状态 si ,输入字串 时,将转换到下一状态集: s i1 , s i2 ,. s ik S0 S, 是初态集; Z S ,是终态集. 一个NFAM也可用状态图表示,此时每条边用字串表示.,56,例如:,0,1,初态,终态,2,aa,bb,a,b,a,b,a,b,终态,DFAM 是 NFAM 的特例.定义: 状态图中,从初态到终态任一路径上的字串连接,称为该状态图可识别的单词,可识别单词的全体记为:L(M). 若L(M)= L(M),称M 与M等价.,57,五 正规式与有限自动机的等价性 前面,介绍了正规式,DFAM,NFAM, 下面讨论这三个概念间的关系.定理1 : 对任意正规式V,存在一个NFAM ,使得L(V)=L(NFAM);证明: (1)构造一个拓广转换图 显然,该转换图能识别的 单词集为:L(V),X,Y,V,58,(2) 进行如下等价变换,直到转换图的每条边上的标志为上的 字符.,i,j,V1V2,i,j,V1,k,V2,a,i,j,V1 | V2,i,V1,j,V2,b,i,j,V*,i,j,k,c,V,等价变换后的转换图M 符合 NFAM的定义,显然有 L(V)=L(M).该定理说明,从正规式可逐步构造一个NFAM.,59,定义:设 S 是一个状态集, _CLOSURE(S)定义如下: a) 若 s S,则 s _CLOSURE(S); b) 若 s S,则 从 s 出发经过任意条 边所能到达的状态 s 都属于 _CLOSURE(S). 状态集_CLOSURE(S)称为 S 的_ 闭包.定理2: 对任意NFAM,存在一个DFAM ,使得L(DFAM)=L(NFAM);证明: (1) 对 NFAM 进行等价变换,使得变换后的转换图NFAM中 仅含边和 上的字符边; (2) 用状态转换矩阵M 表示NFAM;,60,(3) 将M 中的状态集换名, si = Ii 得到一新的状态转换矩阵 M , M 满足 DFAM 的定义.,61,证毕.推论: 对任意正规式V,存在一个DFAM ,使得L(DFAM)= L(V).,62,示例: 设正规式为 ( a|b) *(aa|bb)(a|b) *,求与之等价的DFAM. (1) 由定理 1 的证明方法,可如下构造NFAM,X,Y,( a|b) *(aa|bb)(a|b) *,等价变换得到:,5,1,3,2,6,4,a,a,a,a,b,b,b,b,NFAM,X,Y,(2) 用状态转换矩阵M 表示NFAM;,63,Iabx,5,1 5,1,3 5,1,45,1,3 5,1,3,2,6,y 5,1,45,1,4 5,1,3 5,1,4,2,6,y5,1,3,2,6,y 5,1,3,2,6,y 5,1,4,6,y5,1,4,2,6,y 5,1,3,6,y 5,1,4,2,6,y5,1,4,6,y 5,1,3,6,y 5,1,4,2,6,y5,1,3,6,y 5,1,3,2,6,y 5,1,4,6,y,M,(3) 将M 中的状态集换名, si = Ii 得到一新的状态转换矩阵 M注意: M 与 M等价.,64,Sabs0 s1 s2s1 s3 s2s2 s1 s4 s3 s3 s5 s4 s6 s4 s5 s6 s4 s6 s3 s5,M,M满足确定有限自动机的定义,状态图表示如下:,s0,s1,s3,s5,s6,s4,a,b,b,s2,a,a,a,a,a,a,b,b,b,b,b,65,第三节 词法分析器的 自动生成原理及LEX语言,正规式,确定自动机状态转换矩阵,词法分析器,控制程序,自动生成器,转化,合成,一 自动生成原理,66,二 LEX 语言 LEX 语言用正规式描述单词的词法规则,并通过LEX编译,自动生成词法扫描器.,LEX语言源程序,LEX编译,词法分析器,67,1 辅助定义式 辅助定义式是如下形式的 LEX 语句,Ri为正规式, Di为简名. 规定Ri中只能出现上的字符及之前已定义过的D1. Di -1 .例如:,68,2 识别规则,Pi为正规式, 规定Pi中只能出现上的字符及D1. Dn ;P1. Pm 代表了某种高级语言的所有词形. Ai为一段程序代码,指出当识别出满足规则Pi的单词时,扫描器应采取的动作.,69,3 LEX编译的工作原理 LEX编译对源程序进行处理, 产生一个词法分析器.主要有三个步骤: 1 对每条识别规则Pi ,构造一个非确定有限自动机 Mi , 设一 初态X ,用边连接每个Mi的初态,构成一个总的NFAM;,M1,M2,Mm,x,P1,P2,Pm,NFAM,70,2根据定理 3 ,把 NFAM 确定化,得到一确定有限自动机 DFAM 的状态转换矩阵;3产生一个控制程序.输出如下所示的词法分析器:,状态转换矩阵,控制程序,控制程序用于扫描输入字符串,控制状态的转移;(对任何 转换矩阵,其控制程序是一样的)当识别出某词形Pi后,执行Ai. (返回种别码及值),词法分析器,71,本章习题1) 构造如下正规式相应的DFA 11(0|1)*1012) 构造一个DFA,它接受=0,1上所有满足如下 条件的字符串: 每个1后都有0直接根在后边;根 据DFA的状态图,编写一个识别程序.,72,第三章 语法分析,内容提要:上下文无关文法算符优先分析法递归下降分析法,语法分析的任务: 把单词符号作为基本单位,分析程序是否为 合法的程序.,74,第一节 上下文无关文法,上下文无关文法是这样一种文法: 它定义的语法单位,独立于该语法单位可能出现的环境,不必考虑上下文关系. 自然语言不是上下文无关文法; 程序语言是上下文无关文法;1. 上下文无关文法定义 上下文无关文法 G 是一个四元式: G =(VT,VN,S,P),75,VT : 是一个非空有限单词集,每个元素称为终结符号.VN: 是一个非空有限集,每个元素为非终结符号,代表了一 种语法单位. 且 VT VN=. 例如:表达式,短语,语句等S: 是一个非终结符号,称为开始符号,S VN. S 是文法 G 的最高层次的语法单位. 在程序语言中, S代表了程序这一语法概念.P: 是一个非空有限集,每个元素称为一条产生式;一条产 生式定义了一个非终结符.产生式形式如下: Pi i (Pi VN , i (VT VN ) * ) 称Pi定义为i .,76,b) 用英文大写字母串代表非终结符; 英文小写字母串代表终结符; 希腊字母 等代表由VT,VN组成的符号串; 即: , (VT VN) * .c) 一个文法,可以仅用开始符号及产生式代替.例如:表达式的文法可以定义如下: E E+E|E-E|E*E|E/E|(E)|i E 为文法的开始符号, + - * / ( ) 为终结符.,77,78,一个句型到另一个句型的推导有两种方式:最左推导和最右推导: 最左推导是指每次直接推导,对句型的最左非终结符实行替换; 最右推导是指每次直接推导,对句型的最右非终结符实行替换.,79,4 语法树与文法的二义性 语法树可以表示句型的推导及句型的层次结构. 语法树是一棵倒立树,根结点表示了文法的初始符号,每进行一步推导,树的叶结点构成的有序序列构成一个句型. 例如:E=E+E=E*E +E=i * E + E= i * i + E = i * i + i 可表示为: 语法树可以表示同一句型的多种推导,是多种推导的共性抽象.但未必代表了同一句型的所有推导:E=E*E=E*E +E =i * E + E = i * i + E = i * i + i,语法树,80,定义: 若文法 G 的某个句型存在两个不同的语法树表示,称该文法 是二义文法. 因此,文法 E 是二义文法. 二义性导致了i * i + i 的两种不同运算结果: (i*i)+i 以及 i*(i+i). 编译中应避免二义文法. E 文法的二义性是因为没有规定*,+ 运算符的优先顺序,改进 E 后,得到: ET|E+T TF|T*F F(E)| i,E为表达式,T 为项,F 为因子,该文法对于句子i * i + i的各种推导,对应的语法树是唯一的.,E,E,T,+,T,F,T,*,i,F,i,F,i,81,5 乔姆斯基文法分类定义:若G =(VT,VN,S,P)的每一个产生式型如:, , (VT VN) * , 且 至少含有一个非终结符, 称 G 为 0 型文法; , (VT VN) * , 至少含有一个非终结符, 且满足 | , 称 G 为 1 型文法;A A VN , (VT VN) * , 称 G 为 2 型文法(上下文无关文法);A B 或A , A,B VN , VT * , 称 G 为 3 型文法(正则文法).,82,第二节 语法分析概述,语法分析的任务: 把单词符号作为基本单位,根据文法,分析源程序 (字串)是否为合法的程序.1 语法分析方法,自下而上是指: 根据文法,对输入字串进行归约,若能正确地归约 为文法的初始符号,则表示输入字串是合法的. 典型方法是算符优先分析法.自上而下是指: 从文法的初始符号进行推导,若能推导出与输入 字串相同的句子,则表示输入字串是合法的. 典型方法是递归下降分析法.,83,2 归约栈 自下而上分析的基本技术是采用归约栈,如下图所示:,把输入符号依次移入栈内,当栈顶符号串形成某产生式的右部时,就归约为产生式左部非终结符;继续移入输入字串,直到栈中归约为文法初始符号S. 这种方法也称为移进归约法.,84,例如: G: SaAcBe分析句子 abbcde 是否 Ab|Ab 为合法的句子 Bd,经分析,判定该句子是合法的句子.,85,定义:栈顶形成的某产生式候选称为归约串. 在上例中,当栈中为 aAb 时,存在两个归约串: b 及 Ab,它们都可以归约为 A. 若使用 b 进行归约, 栈中得到 aAA, 导致最终不能归约为 S,因此,判定输入字串非法.这是一种错误归约, 原因在于栈中同时存在多个归约串,而只有一个归约串的选择是正确的,如 Ab. 把 Ab 称为可归约串,而 b 为非可归约串. 移进归约的关键问题,就是在栈中如何寻找可归约串.一旦能确定可归约串,句子分析的难点就迎刃而解.,86,3 分析树 分析树也是一棵倒立的树,用于描述归约过程.分析树是从叶结点开始建立的,每进行一次归约,就生成相应的节点.例如,上例中的归约过程可描述为如下分析树:,该归约树与句子abbcde 的语法树是一样的.,87,4 规范归约简介 规范归约是一种较常用的自下而上分析方法.该方法实质上是最右推导的逆过程.例如:最右推导: S =aAcBe = aAcde = aAbcde =abbcde规范归约: abbcde = aAbcde= aAcde= aAcBe = S 规范归约采用句柄来刻画可归约串.定义:设 S 为文法 G 的开始符号,若,则称 为句型 相对于 A 的短语;若A 则称 为句型 相对于 A 的直接短语;一个句型的最左直接短语,称为句柄.,88,例如: 设句型为 aAbcde 该句型有两个直接短语: Ab, d S=aAcBe = aAcde AAb 所以Ab为直接短语; S=aAcBe = aAbcBe Bd 所以d为直接短语; 注意:b 不是句型 aAbcde 的直接短语; 因此,该句型的句柄为 Ab,若输入串是合法的,那么栈中内容与栈外内容的连接正好为 S 的一个句型. 当栈顶出现句柄时就进行归约.,89,规范归约分析算法: (1) 在栈底放入 # ,在输入串尾附上 #; (2) 逐个移入输入符号,当栈顶形成句柄时,进行归约; (3) 重复 (2) 直到输入串已全部进栈,仅剩 #, 若栈中归约为 #S, 表示分析成功,输入串为合法的句子, 否则为非法句子. 这里,虽然指出对句柄进行归约,但并没有指出如何在栈中 确定句柄,这是第四章的内容.,90,第三节 算符优先分析法,算符优先分析法是一种简单实用的自下而上分析方法,本节将详细介绍该方法,包括 介绍 什么是算符优先文法,优先关系表构造,可归约串的刻画与寻找方法,算符优先分析算法等内容.1 算符优先文法定义1: 若一个文法 G 的任何产生式右部,都不含两个相继出现的 非终结符, 则称 G 为算符文法.,91,定义2: 设 G 是一个算符文法,任何相继出现的终结符对之间存在如下三种归约优先顺序: 1) a b 当且仅当 G 中含有型如 P .ab. 或 P .aQb.的产生式; 2) a b 当且仅当 G 中含有型如 P .aR