编译原理之词法分析

Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,Click to edit Master title style,课 程 名 称 ： 编译原理,主讲教师：徐艳群,教师教案之,编 译 原 理,主讲教师：徐艳群,第四章,教学时数,教学目的与要求,教学重点,教学难点,本章主要阅读文献资料,课 程 名 称 ： 编译原理,主讲教师：徐艳群,教学学时,14,学时,课 程 名 称 ： 编译原理,主讲教师：徐艳群,教学目的与要求,了解语法分析程序的构造，掌握自顶向下和自底向上的语法分析方法，能应用LL(1)文法和LR文法进行分析，能解决非LL(1)文法中的左递归和回溯问题,目的与要求,能利用LR（1）解决SLR（1）中出现移进归约冲突和归约归约冲突，能达到在LL(1)分析中用First集和Follow集构造分析表， 能进行LR（0），SLR（1），LR（1），LALR(1)的分析,课 程 名 称 ： 编译原理,主讲教师：徐艳群,教学难点,文法的定义段,对简单的定义，算法通过讲解来完成一个具体题目求解过程，对学生不易掌握的算法通过具体的例题来理解算法。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,本章主要阅读文献资料,Kenneth C.Louden,著：,Compiler Construction,Principle and,Pratice,，,机械工业出版社。,蒋立源著：,编译原理,（第,2,版），西北工,业大学出版社。,陈火旺著：,程序设计语言编译程序,（第,2,版），国,防工业出版社。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,第四章,语法分析,教学目的与要求： 要求学生了解语法分析程序的构造，掌握自顶向下和自底向上的语法分析方法，能应用,LL(1),文法和,LR,文法进行分析，能解决非,LL(1),文法中的左递归和回溯问题，能利用,LR,（,1,）解决,SLR,（,1,）中出现移进归约冲突和归约归约冲突，能达到在,LL(1),分析中用,First,集和,Follow,集构造分析表，能进行,LR,（,0,），,SLR,（,1,），,LR,（,1,），,LALR(1),的分析。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,教学重点,算符优先分析法,简单优先分析法,LR,分析法,LL,（,1,）文法,课 程 名 称 ： 编译原理,主讲教师：徐艳群,教学难点,通过算法分析和具体例题的讲解来理解像,FITST,集和,FOLLOW,集，,LEADVT,，,LASTVT,，,LL,（,1,）分析法，优先分析法及,LR,分析法。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,4.1,自顶向下分析,4.1.1,自顶向下分析思想,4.1.2 LL,（,1,）文法,4.1.3,递归下降分析法,课 程 名 称 ： 编译原理,主讲教师：徐艳群,4.1.1,自顶向下分析思想,给定符号串,S,，,若预测是某一语法成分， 那么可根据该语法成分的文法,设法为,S,构造一棵语法树,.,若成功,则,S,最终被识别为某一语法成分,即,S,L(GZ),其中,GZ,为某语言成分的文法,.,若不成功,则,S,L(GZ),我们可以通过一例子来说明语法分析过程,课 程 名 称 ： 编译原理,主讲教师：徐艳群,1.,自顶向下分析方法特点,1.,分析过程是带有预测的，对输入符号串要预测属于什么,语法成分，然后根据该语法成分的文法建立语法树。,2.,分析过程是一种试探过程，是尽一切办法,(,选用不同规则,),设法建立语法树的过程，由于是试探过程，故难免有失败，,所以分析过程需进行回溯，因此我们也称这种方法是带,回溯的自顶向下分析方法。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,2.,自顶向下分析存在的问题及解决方法,自顶向下分析,方法的,基本缺点,：,不能处理具有左递归性的文法,自顶向下分析为什么不能处理左递归文法？,1,） 左递归文法：,文法,G,，,存在,U,Vn,，,if U=U,则,G,为左递归文法,+,课 程 名 称 ： 编译原理,主讲教师：徐艳群,4.1.2 LL(1),分析法,此过程有三部分组成,:,分析表,执行程序,(,总控程序）,符号栈 （分析栈）,#,执行程序,分析表,#,符号栈,输入串,在实际语言中，每一种语法成分都有确定的左右,界符，为了研究问题方便，统一以,表示 。,1,、,LL,分析程序构造及分析过程,LL,自左向右扫描输入串。 分析过程表现为最左推导的性质。,每步推导只需向前查看一个符号。一种自顶向下分析方法,通常把按,LL(1),方法完成语法分析任务的程序叫,LL(1),分析程序或者,LL(1),分析器。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,2,、分析表的构造：,LL(1),分析器构造的核心,设有文法,GZ:,定义：,FIRST() = a | ,a,，,a,Vt,，,V*,若,，,则规定,FIRST(),该集合称为,的头符号集合,*,*,15,15,定义：,AVn,FOLLOW(A)=a|Z,A,且,aVt,aFIRST(),Vt,*,V,+,若,Z,A ,且,，,则,#,FOLLOW(A),该集合称为,A,的后继符号集合,或定义为：,FOLLOW(A)=a| Z,Aa,，,aVtAVn,Z,识别符号,特殊地：若,Z,.A,则,#FOLLOW(A),*,*,*,*,*,课 程 名 称 ： 编译原理,主讲教师：徐艳群,4.1.2 LL,（,1,）文法,定义：一个文法,G,，,其分析表,M,不含多重定义入口,(,即分,析表中无二条以上规则,),，则称它是一个,LL(1),文法,.,定理,：文法,G,是,LL(1),文法的,充分必要条件,是：对于,G,的,每一个非终结符,A,的任意两条规则,A:=|,下列条件成立：,2,、若,= ,则,FIRST(,),FOLLOW(,A,)= ,*,1,、,FIRST(,),FIRST(,)= ,SELECT(A,),SELECT(A,) = ,或,课 程 名 称 ： 编译原理,主讲教师：徐艳群,LL(1),文法及,LL(1),语言的性质,任何,LL(1),文法都是无二义性的；,若一文法中的非终结符含有左递归，则它必然是非,LL(1),文法；,非,LL(1),语言是存在的；,存在一种算法，它能判定任一文法是否为,LL(1),文法；,不存在这样的算法，它能判定上下文无关语言能否由,LL(1),文法产生。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,一个含有冲突的例子,设有文法,GS,：,S,if,E then S,S|a,S,else,S|,E,b,FIRST(S)=,if,a,，,FIRST(S)=else,，,，,FIRST(E)=b,FOLLOW(S)=else,，,#,，,FOLLOW(E)=then,SELECT(,S,if,E then S S)=if,SELECT(,S,a,)=a,SELECT(,S,else,S)=else,SELECT(,S,)=else,，,#,SELECT(,E,b,)=b,课 程 名 称 ： 编译原理,主讲教师：徐艳群,4.1.3,递归子程序法（递归下降分析法）,递归下降分析法也称递归子程序法，是一种直观易于构造的,自顶向下分析方法。,分析过程则通过自上而下一级一级地调用,子程序来实现，所以称为,递归下降分析法,。,思想,对文法中的每个非终结符编写一个处理子程序，处理子程序的,代码结构由相应的非终结符的规则右部来决定：规则右部的终,结符号与输入符号相匹配，非终结符与相应的子程序调用相对,应，非终结符对应的各个候选式与分支结构相对应。,限制,：,对文法要求高，必须满足,LL(1),文法；,由于递归调用多，速度慢，占用空间多。,尽管这样,它还是许多高级语言的编译系统,经常采用的语法分析方法。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,扩展的巴科斯范式,(EBNF),EBNF,是在,BNF,基础上扩展如下三组符号：,“, ,”,：,表示花括号内的语法成分可以重复；,“, ,”,：表示方括号内的成分是可选项；,“,( ),”,：表示括号内的成分优先。,用,EBNF,改写文法,对于非终结符,A,的一组形如,A,x|y|z|Aa,的规则，可表示成,A,(x|y|z)a,。例如，,对于规则,E,E+T|T,，,可以写成,E,T+T,。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,例,设有文法,GE,：,E,E+T|E-T|T,TT*F|T/F|F,FPF|P,P(E)|i,用,EBNF,表示消除左递归得到文法,G,E,：,E,T(+|-)T,T,F(*|/)F,FPP,P(E)|i,T - FT,T - *FT | /FT | ,课 程 名 称 ： 编译原理,主讲教师：徐艳群,4.2,自底向上分析,4.2.1,移进,-,归约分析,(,自底向上分析的一般过程,),4.2.2,简单优先分析法,4.2.3,算符优先分析法,4.2.4 LR,分析法,课 程 名 称 ： 编译原理,主讲教师：徐艳群,若,Z,S,则,S,L(GZ),否则,S,L(GZ),+,GZ,存在主要问题,:,左递归问题,回溯问题,主要方法,:,递归子程序法,LL,分析法,自顶向下分析算法的基本思想为,若,Z,S,则,S,L(GZ),否则,S,L(GZ),+,GZ,自底向上分析算法的基本思想为：,存在主要问题,:,句柄的识别问题,主要方法,:,算符优先分析法,LR,分析法,课 程 名 称 ： 编译原理,主讲教师：徐艳群,4.2.1,移进,归约分析（,Shift-reduce parsing),#,L.R.P,#,符号栈,输入串,要点：,建立符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是归约。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,自下而上分析一般过程,例：文法,G,：,S ,cAd,A a A ,ab,识别输入串,w=,cabd,是否该文法的句子,A A,a ! S,cAbd,?,c a b d c a b d,S,A A,c a b d c a b d,c a b d,归约过程形成的推导：,S,cAd,cabd,课 程 名 称 ： 编译原理,主讲教师：徐艳群,4.2.2,简单优先优先分析法,1,、简单优先分析法概述,基本思想,简单优先分析法的基本思想是对一个文法按一定原则求出该文法的所有符号之间的优先关系，按照这种关系确定归约过程中的句柄以进行归约。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,简单优先文法,若一个文法是简单优先文法，必须满足以下条件：,在文法符号集,V,中，任意两个符号之间最多只有一种优先关系成立；,在文法中任意两个产生式没有相同的右部。,简单优先分析法的基本思想是找到形如,Sj-1SjSj+1,SiSi+1,的句柄。,简单优先分析法的算法思想是：,在不断将输入符号移进分析栈的过程中通过比较优先级，首先发现句柄的尾，然后再反向找到句柄的头，从而找到句柄。之后寻找句柄以句柄为右部的规则，如找到则进行规约，否则出错,课 程 名 称 ： 编译原理,主讲教师：徐艳群,优先关系的定义,XY,表示,X,与,Y,的优先关系相等,XY,表示,X,优先级小于,Y,的优先级,XY,表示,X,优先级大于,Y,的优先级,注意：这里,、,与数学中的,=,、,不同。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,优先关系确定,定理,XY,当且仅当,G,中存在产生式,A,XY,XY,当且仅当,G,中存在产生式,A,XB,，,且,B,Y,XY,当且仅当,G,中存在产生式,A,BD,，,且,B,X,，,DY,课 程 名 称 ： 编译原理,主讲教师：徐艳群,4.2.3,算符优先分析法概述,定义,：如果不含空产生式的上下文无关文法,G,中没有形如,U,VW,的产生式，其中,V,，,WVN,，则称,G,为算符文法（,OG,）。,性质,1,：在算符文法中任何句型都不包含两个相邻的非终结符。,性质,2,：如,Vx,或,xV,出现在算符文法的句型,中，其中,VVN,，,xVT,，则,中任何含,x,的短语必含有,V,。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,定义：设,G,是一个算符文法，,a,和,b,是任意两个终结符，,A,、,B,、,C,是非终结符，算符优先关系,、,、,定义如下：,算符文法的优先关系,课 程 名 称 ： 编译原理,主讲教师：徐艳群,（,1,）,ab,当且仅当,G,中含有形如,A,ab,或,A,aBb,的产生式。,（,2,）,ab,当且仅当,G,中含有形如,A,aB,的产生式，且,B b,或,B C b,。,（,3,）,ab,当且仅当,G,中含有形,A,Bb,的产生式，且,B,a,或,B,aC,。,课 程 名 称 ： 编译原理,主讲教师：徐艳群, a ,b,p,p,B b ,a B, a, b,A,A,A,(,a)a,b,(,b)a,b,(,c)a,b,a,b,当且仅当,G,中含有形如,A,ab,或,A,aBb,的产生式,a,b,当且仅当,G,中含有形如,A,aB,的产生式，且,B b,或,B,Cb,a,b,当且仅当,G,中含有形如,ABb,的产生式，且,B a,或,B ,aC,算符文法的优先关系,课 程 名 称 ： 编译原理,主讲教师：徐艳群,算符优先文法,设有一不含,产生式的算符文法,G,，如果对任意两个终结符对,a,，,b,之间至多只有,、,和,三种关系的一种成立，则称,G,一个算符优先文法。（,Operator Precedence Grammar,）即,OPG,文法。,注意,：允许,bc,，,cb,，不允许,bc,，,bc,，,bc,。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,EE+E|E*,E|(E)|i,不是算符优先文法。,因为对算符,+,、*来说，由,EE+E,和,E E*E,可有,+,*,，,又可由,EE*E,和,E E+E,得,+,*,，这样,+,、*的优先关系不唯一，所以该表达式的文法仅是算符文法而不是算符优先文法。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,关于,#,的特别说明,文法开始符号,S,#S#,#=#,#,对于算符优先文法，,#,的优先级小于任何终结符；任何终结符的优先级大于,#,；,#,的优先级等于,#,。,由于仅对终结符定义优先关系，未对非终结符号定义算符优先关系，不能使用这些关系查找右单个非终结符号组成的句柄。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,4.2.4,LR,分析法,LR(K),分析法的含义,L,自左向右扫描输入串,(,源程序,),R,分析过程构成最右推导的逆序,K,每次根据当前的输入符号最多向前,(,右,),查看,K,个符号就可以唯一地确定下一步动作是移进还是归约以及用哪条规则进行归约，因而也能唯一地确定句柄,课 程 名 称 ： 编译原理,主讲教师：徐艳群,LR,分析的特点,是规范归约,适用范围广，适用于大多数上下文无关文法描述的语言,分析速度快，能准确定位错误,缺点：,LR,分析器的构造工作量大,课 程 名 称 ： 编译原理,主讲教师：徐艳群,a,1,a,i,#,X,m,#,S,m,X,m,S,m-1,X,m-1,S,1,X,1,S,O,#,总控程序,分析表,LR,分析器结构示意图,分析栈示意图,（,a,）,LR,分析器结构示意图 （,b,）,分析栈示意图,课 程 名 称 ： 编译原理,主讲教师：徐艳群,S,i,:,移进，并将状态,i,进栈。,r,i,:,用第,i,个产生式归约，同时状态栈与符号栈退出相应个符号，根据,GOTO,表将相应状态入栈。,LR,分析表,课 程 名 称 ： 编译原理,主讲教师：徐艳群,LR,分析器的逻辑结构,LR,分析器组成：,分析表,总控程序,下推分析栈,a,1,a,2,a,n,#,总控程序,S,m,x,m,S,m-1,x,m-1,S,2,x,2,S,1,x,1,S,0,#,输入串,(,源程序,),输出分,析结果,分析表,ACTION,GOTO,课 程 名 称 ： 编译原理,主讲教师：徐艳群,分析栈,符号栈,符号栈内存放分析过程中移进或归约的符号。,状态栈,状态栈存放的是状态,(,标记,),，状态,Si,概括了栈中位于,Si,下面的全部信息，也就是记录分析过程从开始的某一归约阶段的整个分析历史或预测扫描可能遇到的分析符号。分析开始时，分析栈压入初始状态,S0,和输入符号,#,，分析器处于初始状态,S0,。,S0,刻画了当前栈内仅有一个符号,#,的事实并预示将扫描的输入字符应刚好是可作为句子首符号的那些符号。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,分析表,动 作 表,(ACTION),状态转换表,(GOTO),课 程 名 称 ： 编译原理,主讲教师：徐艳群,ACTION,表,ACTION,表的结构如下：,终结符,状态,a,1,a,2,a,m,S,1,ACTIONS,1, a,1,ACTIONS,1, a,2,ACTIONS,1, a,m,S,2,ACTIONS,2, a,1,ACTIONS,2, a,2,ACTIONS,2, a,m,S,n,ACTIONS,n, a,1,ACTIONS,n, a,2,ACTIONS,n, a,m,课 程 名 称 ： 编译原理,主讲教师：徐艳群,分析动作,ACTION,表中的元素,ACTIONSm,ai,是一个动作，表示当前状态,Sm,面临输入符号,ai,时所完成的分析动作。分析动作可分四类：,移进,归约,接受,出错,课 程 名 称 ： 编译原理,主讲教师：徐艳群,移进,此时,ACTIONSm,ai,=,Sj,。,分析动作为移进时，表示句柄尚未在分析栈的栈顶形成，正期待继续移进符号，以形成句柄。,ACTIONSm,ai,=,Sj,表示当前栈顶状态为,Sm,，,输入符号为,ai,，,应将输入符号,ai,移进分析栈的符号栈栈顶，同时将,Sj,移进分析栈的状态栈栈顶。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,归 约,此时,ACTIONSm,ai,=,rj,。,其中,rj,表示按文法的第,j,条规则,(,产生式,),进行归约。设第,j,条规则为：,A,Xm-r+1Xm-r+2 ,Xm,分析动作为归约时，表明当前分析栈顶部的符号串,Xm-r+1Xm-r+2 ,Xm,已是当前句型的句柄，需要立即进行归约。具体是将分析栈自顶向下的,r,个符号,(,包括状态栈内相应的状态,),弹出，将,A,压入符号栈内，此时分析栈格局为：,课 程 名 称 ： 编译原理,主讲教师：徐艳群,接 受,此时,ACTIONSm,ai,=,acc,。,分析动作接受表示当前输入的符号串分析成功，终止分析器工作。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,出 错,此时,ACTIONSm,ai,=,error,(error,表示出错，在此用空白来表示,),。分析动作为出错，表示当前输入的符号串中有语法错误，调用相应的出错处理程序。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,GOTO,表,GOTO,表的结构如下：,非终结符,状态,X,1,X,2,X,m,S,1,GOTOS,1, X,1,GOTOS,1, X,2,GOTOS,1,X,m,S,2,GOTOS,2, X,1,GOTOS,2, X,2,GOTOS,2,X,m,S,n,GOTOS,n, X,1,GOTOS,n, X,2,GOTOS,n,X,m,课 程 名 称 ： 编译原理,主讲教师：徐艳群,状态转换,GOTO,表中的元素,GOTOSm, Xi,是一个状态，表示当前状态,Sm,面临输入符号,Xi,时需转移的下一个状态。,51,课 程 名 称 ： 编译原理,主讲教师：徐艳群,总控程序,总控程序是,LR,分析的实现算法。描述如下：,初始化，将初始状态,S0,及输入符号串的左界符,#,推入分析栈；,从输入串中读入当前的输入符号,ai,，,根据当前状态栈栈顶状态,Sm,与输入符号,ai,查,ACTION,表：,若,ACTIONSm,ai,=,Sj,，,完成移进动作；,若,ACTIONSm,ai,=,rj,，,以文法的第,j,条规则完成归约动作；,若,ACTIONSm,ai,=acc,，,分析成功，结束；,若,ACTIONSm,ai,=error,，,出错处理。,重复,2),直到出错或接受为止。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,例,设有文法,GS,：,S,S,S,(S)S,S,根据给定的分析表，对输入串,(),进行,LR,分析。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,步骤,状态栈,符号栈,输入串,ACTION,GOTO,0 0 # ()# S,2,1 02 #( )# r,3,3,2 023 #(S )# S,4,3 0234 #(S) # r,3,5,4 02345 #(S)S # r,2,1,5 01 #S # acc,课 程 名 称 ： 编译原理,主讲教师：徐艳群,例：文法,GE,(1)E:=E+T,(2)E:=T,(3)T :=T*F,(4)T:=F,(5)F:=(E),(6)F:=i,其,LR,分析表如下页，分析输入串,i*i+i,例,2,课 程 名 称 ： 编译原理,主讲教师：徐艳群,LR,分析表说明,sj,把下一个状态,j,和当前输入符号,a,进栈,rj,按第,j,个产生式归约,acc,接受,空格 出错标志，报错,课 程 名 称 ： 编译原理,主讲教师：徐艳群,由分析过程可以看到,:,(1),每次规约总是,规约,当前句型的句柄,，是规范归约，可以看到语法树,(,算符优先是规约最左素短语,),E,E,T,+,T,T,*,F,F,i,i,F,i,8,7,5,6,4,3,2,1,(2),分析的每一步栈内符号串与输入串的剩余部分构成规范句型,.,课 程 名 称 ： 编译原理,主讲教师：徐艳群,LR,文法,LR,文法,一个文法,G,若能构造一张,LR,分析表，并使它的每个入口,(,表中的元素,),都是唯一确定的，则称文法,G,为,LR,文法。,LR(K),文法,一个,LR,文法,G,，,若每步最多向前查看,K,个输入符号就能决定当前分析动作，从而按,LR,方法进行分析，则称文法,G,为,LR(K),文法。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,规范句型的活前缀,对于句型,t,，,表示句柄,如果,=u1u2,ur,那么符号串,u1u2,ui(1ir),即是句型,t,的活前缀,例：有文法,ET | E+T | E-T,Ti | (E),拓广文法,G,：,SE#,ET | E+T | E-T,Ti | (E),已知句型,E-(i) #,，,求,活前缀,?,E, E-, E-(, E-(i,是句型,E-(i+i)#,的活前缀。,S,E,#,E,T,-,(,),E,T,i,课 程 名 称 ： 编译原理,主讲教师：徐艳群,一个,LR,分析器的工作过程，实质上就是一个逐步产生所给文法的规范句型的活前缀的过程。,在分析过程中，分析栈中的符号串始终是活前缀，然后通过对余留符号串的继续扫描，逐步在分析栈中构成活前缀，当栈顶形成句柄时，立即进行归约。,分析过程中的句柄获得确定和归约是通过寻找规范句型的活前缀来实现的。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,LR(0),项目族的构造,LR(0),项目,在文法,G,每条规则的右部的任何位置上添加一个圆点，所构成的规则称为,LR(0),项目。其中规定规则,A,的,LR(0),项目为,A,。,例如，对于文法,GS,：,S,A|b,，,AaA|b,，其,LR(0),项目有：,S,A,，,S,A,，,S,b,，,S,b,，,AaA,，,AaA,，,AaA,，,Ab,，,Ab,课 程 名 称 ： 编译原理,主讲教师：徐艳群,LR(0),项目的分类,归约项目：,形如,A,，,表示当前栈顶的内容已构成所期望的句柄，应按,A,进行归约。,接受项目：,形如,S,，,其中,S,是文法唯一的开始符号。表示句柄已在栈顶形成，用,S,进行归约，整个分析成功。,移进项目：,形如,Aa(aV,T,),，,表示栈内仅是句柄的一部分，为了构成活前缀，应先把,a,移进分析栈。,待约项目：,形如,AB(BV,N,),，,表示栈内仅是句柄的一部分，为了构成活前缀，应先把当前输入符号串中相应的内容归约到,B,。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,基本思想,首先构造出识别文法活前缀的,NFA,，,再将,NFA,确定化和最小化，最终得到所需的,DFA,。,活前缀：,若分析过程能够保证栈中符号均是规范句型的前缀，则表示输入串已分析过的部分没有语法错误，所以称为规范句型的活前缀,.,在分析的过程中，只要符号栈中的符号串是一个活前缀，就可保证已被分析过的部分是该文法规范句型的正确部分。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,由文法的,LR(0),项目构造识别文法所有活前缀的,NFA,的步骤为：,令所有,LR(0),项目对应,NFA,的一个状态，归约项目对应为终态；,令含有文法开始符号的规则,(,设为,S,A,),的第一个,LR(0),项目,(S,A,),为,NFA,的初态；,若状态,i,和,j,中的,LR(0),项目出自同一条规则，只是圆点位置相差一个符号，即,i,为,X,X,1,X,2,X,i-1,X,i,X,n,j,为,X,X,1,X,2,X,i,X,i+1,X,n,则从状态,i,到状态,j,，,引一条标记为,X,i,的箭弧；,若状态,i,为待约项目,(,设为,XA,),，,则从状,i,态引箭弧到所有,A,的状态并标记为。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,例,设文法,GA,：,AaA,Ab,构造识别文法,G,的所有活前缀的,NFA,。,先对,GA,进行拓广，拓广后的文法,GS,：,S,A,AaA,Ab,课 程 名 称 ： 编译原理,主讲教师：徐艳群,GS,的,LR(0),项目,S,A,AaA,AaA,Ab,Ab,S,A,AaA,课 程 名 称 ： 编译原理,主讲教师：徐艳群,A,b,S,A,A,aA,A,b,S,A,A,aA,A,aA,a,b,A,A,识别文法,GS,的活前缀的,NFA,课 程 名 称 ： 编译原理,主讲教师：徐艳群,命名状态的识别活前缀的,NFA,7,1,b,2,3,6,4,5,a,A,A,课 程 名 称 ： 编译原理,主讲教师：徐艳群,识别文法,GS,的活前缀的,DFA,S,A,A,aA,A,b,A,b,S,A,A,aA,A,aA,A,b,A,aA,a,b,A,A,a,b,课 程 名 称 ： 编译原理,主讲教师：徐艳群,上图中每个状态都是由一组的项目组成的集合，称为项目集。,通过列出拓广文法的所有项目，进而构造识别活前缀的,NFA,，,再确定化为,DFA,的方法，工作量较大，不实用。,实用的方法是直接构造以项目集为状态的识别活前缀的,DFA,。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,LR(0),项目集规范族,识别文法,G,的活前缀的,DFA,项目集的全体称为文法的,LR(0),项目集规范族。,对于上述文法,GS,的,LR(0),项目集规范族,C,为：,C=S,A,，,A,aA,，,A,b,，,A,aA,，,A,aA,，,A,b,，,A,b,，,S,A,，,A,aA,课 程 名 称 ： 编译原理,主讲教师：徐艳群,构造文法,G,的,LR(0),项目集规范族的方法二,项目集的闭包,设,I,是文法,GS,的一个项目集，则,I,的闭包,closure(I),是按下列规则构造的项目集。,对于任何,LR(0),项目,i,I,，,都有,i,closure(I),；,若项目,AB,closure(I),且,B,是,GS,的产生式，则,B,closure(I),；,重复,2),直至,closure(I),不再增大为止,。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,GO,函数,设,I,是文法,GS,的,LR(0),项目集，,X,V,N,V,T,，,则：,GO(I, X)=closure(J),其中,J=,形如,AX,的项目,|AXI,。,是一个转换函数，通过这个函数可以从一个项目集求出另外的的项目集。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,构造算法,构造,LR(0),项目集规范族,C,的算法描述如下：,C=closure(S,S,),；,repeat,for C,中每一个项目集,I,和每一个文法符号,X do,if (GO(I, X),不空且,GO(I, X),不属于,C) then,将,GO(I, X),加入,C,中；,until(C,不再增大,),。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,例,设文法,GS,：,S,A,AaA|b,计算,GS,的,LR(0),项目集规范族。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,I,0,=closure(S,A,)=S,A,A,aA,A,b,GO(I,0, a)=,closure(A,aA,)=A,aA,A,aA,A,b,=I,1,GO(I,0, b)=,closure(A,b,)=A,b,=I,2,GO(I,0, A)=,closure(S,A,)=S,A,=I,3,GO(I,1, a)=,closure(A,aA,)=I,1,GO(I,1, b)=,closure(A,b,)=A,b,=I,2,GO(I,1, A)=,closure(A,a A,)=,A,aA,=I,4,由于,I,2,，,I,3,和,I,4,都是归约项目，则,GS,的,LR(0),项目集规范族,C=I,0,，,I,1,，,I,2,，,I,3,，,I,4,。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,识别文法,GS,的活前缀的,DFA,S,A,A,aA,A,b,A,b,S,A,A,aA,A,aA,A,b,A,aA,a,b,A,A,a,b,I,1,I,0,I,2,I,3,I,4,课 程 名 称 ： 编译原理,主讲教师：徐艳群,LR(0),分析表的构造,LR(0),文法的限制,对于一个文法,GS,的拓广文法,GS,，其,LR(0),项目集规范族中的每一个项目集的各个项目必须是相容的，即同一项目集中不能有移进项目和归约项目并存，或多个归约项目并存。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,LR(0),分析表的构造算法,设,C=I,0,，,I,1,，,，,I,n,，,每个项目集,I,k,的下标,k,作为分析表的状态。则,若,GO,(I,k, a)=,I,j,，,且项目,AaI,k,(aV,T,),，,则置,ACTIONk, a,=,S,j,；,若,GO,(I,k, A)=,I,j,(AV,N,),，,则置,GOTOk, A,=j,；,若,AI,k,，,则对所有终结符号,a,和,#,置,GOTOk, a,=,r,j,和,GOTOk, #,=,r,j,(,其中,A,是文法的第,j,条规则,),。,若,SSI,k,，,则置,ACTIONk, #,=acc,；,表中空白处置出错标志。,课 程 名 称 ： 编译原理,主讲教师：徐艳群,例,对于文法,GA,：,AaA,Ab,拓广后的文法为,GS,：,SA,AaA,Ab,课 程 名 称 ： 编译原理,主讲教师：徐艳群,GS,的,LR(0),分析表,状 态,ACTION,GOTO,a,b,#,A,0,S,1,S,2,3,1,S,1,S,2,4,2,r,2,r,2,r,2,3,acc,4,r,1,r,1,r,1,课 程 名 称 ： 编译原理,主讲教师：徐艳群,A,c.A,A,.cA,A,.d,I,4,S,a.A,A,.cA,A,.d,I,2,S,b.B,B,.cB,B,.d,I,3,B,c.B,B,.cB,B,.d,I,5,S,.S,S,.aA,S,.bB,I,0,start,S,S.,I,1,A,cA,.,I,8,S,aA,.,I,6,A,d.,I,10,A,d,d,A,c,a,b,S,S,bB,.,I,7,B,cB,.,I,9,B,d.,I,11,B,d,d,B,c,c,c,识别文法,活前缀的,DFA,课 程 名 称 ： 编译原理,主讲教师：徐艳群,LR(0),分析表,课 程 名 称 ： 编译原理,主讲教师：徐艳群,第四章 语法分析小结,自顶向下分析法,递归下降分析,预测分析,LL(1),分析表构造,自底向上分析法,简单优先分析法,算符优先分析法,LR(0),分析法,LR(0),分析表构造,课 程 名 称 ： 编译原理,主讲教师：徐艳群,语法分析方法,:,自顶向上分析法,Z,S,+,自顶向上分析法,S,Z,+,SLZ,(,一,),自顶向下分析,1,概述自顶向下分析的一般过程,存在问题,左递归问题,回溯问题,消除左递归的方法,无回溯的条件,改写文法,超前扫描,课 程 名 称 ： 编译原理,主讲教师：徐艳群,2,两种常用方法,:,(1),递归子程序法,a),改写文法,消除作递归,回溯,b),写递归子程序,(2)LL(1),分析法,LL(1),分析器的逻辑结构及工作过程,LL(1),分析表的构造方法,LL(1),文法的定义以及充分必要条件,1.,构造,First,集合的算法,2.,构造,Followselect,集合的算法,3.,构造分析表的算法,课 程 名 称 ： 编译原理,主讲教师：徐艳群,(,二,),自底向上分析,规约过程,:,(1),一般过程,:,移进,规约过程,(2),算法,:,问题,:,如何寻找句柄,i),算符优先分析法,:,1.,分析器的构造,分析过程,.,根据算符优先关系矩阵来决定,是移进还是规约,.,课 程 名 称 ： 编译原理,主讲教师：徐艳群,2.,算符优先法的进一步讨论,1.,适用的文法类,-,引出的,算符优先法,的定义,2.,优先关系矩阵地构造,3.,什么是,“句柄”,如何找,有句柄引出的,最左素短语,的概念,.,最左素短语的定理,如何找,.,ii)LR,分析法,1.,概述,-,概念、术语,(,活前缀、项目,),课 程 名 称 ： 编译原理,主讲教师：徐艳群,2.LR,分析,1),逻辑结构,2),分析过程,状态栈,分析表,控制程序,GOTO,表,分析动作表,3.,如何构造,LR(0),分析表,1),构造,DFA,2),由,DFA,构造分析表,课 程 名 称 ： 编译原理,主讲教师：徐艳群,除了递归子程序法，其他几种方法逻辑结构很象,输入串,符号栈,(,状态栈,),控制程序,分析表,(1),对于,LL(1),分析法,符号栈,i,(,自顶向下，保证最左推导,),LL(1),分析表,i,A,A:=,i,error,终结符,非终结符,首字符,课 程 名 称 ： 编译原理,主讲教师：徐艳群,(2),对于算法优先分析,:,符号栈,栈内终结符,= error,栈外终结符,(3)LR,分析,:,符号栈,S,0,S,1,S,m,#X,0,X,1,X,m,分析表,状态转移,GOTO,表,分析动作表,课 程 名 称 ： 编译原理,主讲教师：徐艳群,GOTO,表,下一状态,状态,符号,根据栈顶状态和栈,顶符号推导出下一,状态,分析动作表,移进,S,规约,(,r,j,),状态,终结符号,根据栈顶状态和输入,符号推导出下一动作,课 程 名 称 ： 编译原理,主讲教师：徐艳群,习 题,1,、文法,GS,S:=,aBc,|,bAB,A:=,aAb,| b,B:= b | ,构造其,LL(1),分析表，并分析符号串,baabbb,是否该文法的句子,2,、设文法,GS,的产生式为：,S,aA,|,bB,A,cA,| d B,cB,| d,进行,LR,分析,讨论题：,1,、,LL,（,1,）分析器与,LR,分析器有何异同,?,2,、,LR,（,0,）与,SLR,（,1,）分析表有何异同？,3,、,LALR,（,1,）文法一定是,LR,（,1,）文法，反之成立吗？,课 程 名 称 ： 编译原理,主讲教师：徐艳群,本章教学后记,LL(1),文法，包括构造,first follow select,集、预测分析表的构造及证明是,LL(1),文法及对输入串的分析、消除消除左递归,掌握算符优先算法求,FIRSTVT,和,LASTVT,及算符优先表并对输入串进行判断,LR,分析表的构造及对输入串进行分析,94,课 程 名 称 ： 编译原理,主讲教师：徐艳群,主讲教师：徐艳群,Thank You !,