编译原理 第5章 语法分析――自底向上分析方法

第5章语法分析——自底向上分析方法第5章语法分析——自底向上分析方法5.1自底向上语法分析方法介绍5.2简单优先分析5.3LR(k)分析法本章重点：自底向上分析原理；简单优先文法的判别与优先关系矩阵的构造；LR(k)分析法的工作过程；LR(0)分析方法；SLR(1)分析方法；几种LR分析法之间的关系。本章难点：简单优先文法的判别；LR(0)分析法；SLR(1)分析法。本章内容：第5章语法分析——自底向上分析方法5.1自底向上语法分析方法介绍该方法基本思想：从待分析的符号串开始，自左向右进行扫描，自下而上进行分析，通过反复查找当前句型的句柄，并使用产生式规则将找到的句柄归约为相应产生式的左部非终结符。这样，一步一步进行归约，试图逐步将输入串归约为文法的开始符号。如果可归约到文法的开始符号，则表示给定的符号串是正确的句子。否则表明符号串不是文法的句子。关键是每一步寻找当前句型的句柄。第5章语法分析——自底向上分析方法例：有文法G[S]:SaAcBeAbAAbBd输入符号串为：abbcde,则自底向上归约过程为：表5-1所示。第5章语法分析——自底向上分析方法第5章语法分析——自底向上分析方法思想是依据一定原则预先确定文法的各个符号（包括终极符和非终极符）之间的优先关系，以此确定归约中的句柄并进行归约。5.2.1简单优先文法及其优先关系矩阵的构造简单优先分析技术是由Wirth和Weber于1966年提出的，曾用于开发AlogolW的分析器。该技术简单，规定任意的两个相继出现的文法符号A、B之间，可能有三种优先关系之一。分别是：。定义5.1假定G是一个文法，A、B是G中任意两个符号（终极符或非终极符），则：5.2简单优先分析第5章语法分析——自底向上分析方法若G中存在形如PAB的规则，A和B可以同时被归约，这样就说A和B有相同的优先关系，记作：AB。若G中存在形如PAX的规则，且X+B使B先于A被归约，这样就说A的优先级低于B，记作：AB。若G中存在形如PXY的规则，且X+A,Y*B,使A先于B被归约，这样就说A的优先级高于B，记作：AB。第5章语法分析——自底向上分析方法定理5.1设X1XiXi+1XjXn是一个句型，若有XiXi+1Xi+2Xj-1XjXj+1则Xi+1Xi+2Xj-1Xj一定是该句型的简单短语。定义5.2若一个文法G满足下列条件，则称G为简单优先文法：文法符号集中的任意两个符号之间至多存在一种优先关系。文法中任意两个产生式均无相同右部。一个文法的全部优先关系可用矩阵来表示，称作优先关系矩阵。如何判断一个文法是否为简单优先文法，首先要确定文法中各符号之间的优先关系。例5.2已知文法G[E],判断该文法是否是简单优先文法。EE1E1E1+T|T1T1TTT*F|FF(E)|i第5章语法分析——自底向上分析方法文法符号的全部优先关系，可写成优先关系矩阵的形式，如下图：第5章语法分析——自底向上分析方法5.2.2简单优先分析算法1）根据已知文法构造相应的优先关系矩阵。2）设立符号栈S，将输入符号串“#X1X2Xn#”从左到右依次压入符号栈S中，同时检查相邻符号Xi与Xi+1的优先关系，一旦出现关系XiXi+1时停止压栈,进入下一步。3）栈顶当前符号为Xi,再从Xi开始，从右至左逐个检查栈中符号，直到某两个相邻符号间存在Xk-1Xk为止。4）符号串XkXi即为当前的句柄，查找文法右部为XkXi的规则，若找到，则将其归约为左部，否则出错。5）重复2）—4），直到扫描完所有输入符号，归约结束后，如果S栈中仅剩开始符号，则分析成功，否则失败。第5章语法分析——自底向上分析方法以例5.2中文法，分析句子i*i,依据上述算法的语法分析过程如下：第5章语法分析——自底向上分析方法5.3LR(k)分析法LR(k)分析法是1965年由D.Knuth提出来的一种自底向上的语法分析方法。L:从左向右扫描输入串；R:最右推导的逆过程；特点：对文法限制少；适用范围广；分析速度快；准确及时地发现语法错误。5.3.1LR(k)分析法的工作过程LR(k)分析法主要是根据当前分析栈中的符号串和向前顺序查看输入串中k（k=0）个符号来唯一确定分析器的动作是移进还是归约，并确定用于归约的产生式。一个完整的LR分析器的逻辑结构图如下：第5章语法分析——自底向上分析方法第5章语法分析——自底向上分析方法从上图可看出，一个LR分析器由以下几个部分组成：输入流（Input）：一个有待分析的输入符号串；分析栈：其中包括文法符号栈和相应状态栈；分析表：其中包括action表和goto表；驱动程序：不同LR分析法，有相同驱动器。核心是分析表，其构成：a)动作表(action表)action[s,a]表示在当前状态S下，面临输入符号a所应采取的动作。b)状态转换表(goto表)goto[s，X]：规定状态s面对输入符号X（终极符或非终极符）时下一个状态是什么。第5章语法分析——自底向上分析方法动作有四种可能：移入、归约、成功、报错。移入：把(s,a)的下一状态s’=goto[S，a]和输入符号压入栈内，下一输入符号变成当前输入符号；归约：指用产生式A进行归约。若的长度为r，则弹出栈顶r项，使栈顶状态变为sm-r，然后将(sm-r,A)的下一状态s’=goto[sm-r,A]和文法符号A压入栈内，栈顶变为(s’,A)。不改变当前输入符号。成功：语法分析成功，退出总控程序。报错：发现输入串含有错误，调用相应出错处理程序第5章语法分析——自底向上分析方法如：(状态序列，已归约串，输入流)初始格局:(s0,#,a1a2an#)当前格局：(s0s1sm,#X1X2Xm,aiai+1an#)1)2)3)4)(s0s1sms,#X1X2Xmai,ai+1an#)成功错误(s0s1sm-rs,#X1X2Xm-rA,aiai+1an#)1)action(sm,ai)为移入，s=goto(sm,ai);2)action(sm,ai)={A},归约，||=r,goto(sm-r,A)=s3)action(sm,ai)为“成功”；4）action(sm,ai)为“报错”。第5章语法分析——自底向上分析方法5.3.2LR(0)分析法是LR(k)分析法中k=0的情况，在分析的每一步，只要根据当前栈顶状态，而无需向前看输入符号，即可确定分析动作。基本概念和术语：规范句型：用最右推导导出的句型；规范前缀：若有规范句型，且是终极符串或空串，则称为规范前缀；规范活前缀（活前缀）：若规范前缀不含句柄，或句柄在最右端，则称规范前缀为规范活前缀；规约规范活前缀：含有句柄的活前缀；即具有形式=‘，是句柄，则称活前缀为归约规范活前缀（简称归约活前缀或可归活前缀）。第5章语法分析——自底向上分析方法第5章语法分析——自底向上分析方法例5.3对于文法G[S]：SaAbBAc|AcBd|dB句子accbdd的规范推导是：SSaAbBaAbdBaAbddaAcbddaccbddaAbB句子accbdd的规范归约是：accbddaAcbddaAbddAcdBaAbdBaAbBS语法树：（如右图）cd第5章语法分析——自底向上分析方法由规范前缀和归约活前缀的定义：前一例中每个规范句型的规范前缀和归约活前缀分别是：规范句型规范前缀归约活前缀accbdda、acacaAcbddaA、aAcaAcaAbddaA、aAb、aAbd、aAbddaAbddaAbdBaAbdBaAbdBaAbBaAbBaAbBLR分析法的创始人Knuth证明了：一个与具体文法相联系的规范推导的所有规范活前缀能被有限自动机接受。下面介绍派生定理：第5章语法分析——自底向上分析方法即下列重要结论：开始符产生式的右部是归约活前缀；如果A是归约活前缀，且A是产生式，则也是归约活前缀；任何归约活前缀都可被上述方法派生。根据派生定理，对于一个文法G，可以构造一个有限自动机，它能识别G的所有归约活前缀，我们称这种自动机为线性正则式状态机（LRSM），它是构造LR分析表的基础。下面看几个概念：定义5.3LR(0)项目：若A是产生式，则称A.为LR(0)项目（简称项目）。第5章语法分析——自底向上分析方法定义5.4LR(0)项目集的投影集：设IS是LR(0)项目集，则称IS(x)为IS关于X的投影集。IS(x)={AX•|A•XIS,X(VTVN)}定义5.5LR(0)项目集的闭包集：设IS是LR(0)项目集，则称CLOSURE(IS)为IS的闭包集。CLOSURE(IS)={B•|A•BCLOSURE(IS),B是产生式}定义5.6设IS是LR(0)项目集，X是一个文法符号，函数GO(IS,X)定义为GO(IS,X)=CLOSURE(IS(x)),其中IS(x)为LR(0)项目集IS的投影。为了使“成功”易于识别，通常要求文法开始符号唯一，且不出现于任一产生式的右部，因此，对文法G[S]，需引入新开始符，构造新产生式：ZS即增加拓广产生式，对原文法进行拓广。第5章语法分析——自底向上分析方法下面给出构造识别LR(0)归约活前缀状态机的算法：1）构造初始项目集ISS={CLOSURE({Z•S#})};2)对于ISS中的每个项目集ISi和XVTVN{#},令ISj=GO(ISi,X),如果ISj不空且不属于ISS,则ISS=ISSISj3)重复第二步，直到ISS收敛为止。4)对于ISS中的每个项目集ISi和XVTVN{#},令ISj=GO(ISi,X)，如果Isj，则ISiXISj第5章语法分析——自底向上分析方法例5.4假设有表达式文法G[E]：SE$EE+T|TTid|(E)活前缀状态机如右图：概念：移入型项目：归约型项目：冲突项目：移入-归约冲突归约-归约冲突第5章语法分析——自底向上分析方法构造LR(0)分析表的算法：假定ISk为LR(0)项目集，则：若A•aISk,且GO(ISk,a)=ISi,aVT,则action(ISk,a)=Si,表示把状态ISi和展望符a入栈；若A•ISk,则对任意aVT{#},令action(ISk,a)=Rj,其中产生式A的编号为j，表示用此产生式进行归约；若Z•ISk,Z为拓广产生式左部，则action(ISk,#)=Accept；若GO(ISk,A)=ISi,AVN,则goto(ISk,A)=I；其它情形，则表示出错，可加标志或不填。第5章语法分析——自底向上分析方法例5.5构造下列文法的LR(0)分析表：SE$(1)EE+T(2)Tid(4)分析表如下：|T(3)|(E)(5)第5章语法分析——自底向上分析方法有了分析表，就可以分析句子了。例如，句子id+id#分析过程如下：第5章语法分析——自底向上分析方法5.3.3SLR(1)分析法LR(0)文法非常简单，即使是算术表达式也不是；它只看状态栈内容，而不看输入符，因此容易出现冲突状态。例如：一个LR(0)—LRSM0中含有状态S:S={X•b,A•,B•}其中第一个项目是移进项目，第二与第三个项目是归约项目，从而出现冲突。能否说明该文法是二义的呢？不能，因为LR(0)方法，不看展望符号，如果考虑展望信息，则可以消除该冲突。当展望符是a时，若aFollow(A),且aFollow(B),则用A归约；若aFollow(B),且aFollow(A),则用B归约；若aFollow(B),且aFollow(A),则展望符需为b，否则就出错。第5章语法分析——自底向上分析方法针对LR(0)项目集，构造SLR(1)分析表算法：假定ISk为LR(0)项目集，则若AaISk，且GO(ISk,a)=ISi，aVT，则action(ISk,a)=Si表示把状态ISi和展望符a入栈；若