编译原理第5章：语法分析-自下而上分析

第五章语法分析—自下而上分析22023/12/17主要内容：

5.1自下而上分析基本问题

5.2算符优先分析

5.3LR分析概述

5.4LR(0)分析

5.5SLR(1)分析

5.6LR(1)分析

5.7LALR(1)分析

5.8二义文法的应用32023/12/175.1自下而上分析基本问题自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”,直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约42023/12/17例：G(E)：E

i|E+E|E-E|E*E|E/E|(E)

i*i+i E*i+i E*E+i E+i E+E Ei+*EiiEEEE52023/12/17一、归约采用“移进－归约”思想进行自下而上分析。基本思想：设计一个堆栈，把符号串从左至右压入栈中，判别栈顶符号是否为某一个产生式的右部，若是则把栈顶的这一部分替换成(归约为)该产生式的左部符号。可归约串在算符优先分析法中即为最左素短语，在规范归约中是句柄。最左归约是最右推导的逆过程，最左归约称为规范。62023/12/17例：设文法G(S)：(1)SaAcBe (2)Ab (3)AAb (4)Bd试对abbcde进行“移进－归约”分析。abbcdebabcdeAabcdebAacdeAacdecAadedcAaeabbcdeeBcAa

S

BcAae72023/12/1782023/12/17二、分析树语法分析过程可用一棵语法分析树表示出来。自下而上分析过程：边输入单词符号，边归约。即，在自下而上分析的每一步，都可画出一棵子树，随着归约的完成，便最终形成一棵分析树。如果文法无二义，分析树恰好等同于语法树。核心问题：识别可归约串bdbaceSABA92023/12/17三、规范归约定义：令G是一个文法，S是文法的开始符号，假定

是文法G的一个句型，如果有且则

称是句型

相对于非终结符A的短语。特别地，如果有A,则称

是句型

相对于规则A

的直接短语。一个句型的最左直接短语称为该句型的句柄。

102023/12/17例：考虑文法G(E)：E

T|E+TTF|T*FF(E)|i

和句型i1*i2+i3：E

E+T

E+FE+i3T+i3

T*F+i3T*i2+i3

F*i2+i3

i1*i2+i3短语：i1，i2，i3，i1*i2，i1*i2+i3直接短语：i1，i2，i3句柄：i1112023/12/17在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。EFFTTTi1+*EFi3i2122023/12/17可用句柄来对句子进行归约 句型归约规则 abbcde(2)Ab aAbcde(3)AAb aAcde(4)Bd

aAcBe(1)SaAcBeS132023/12/17定义：假定

是文法G的一个句子，我们称序列

n，n-1，，0是

的一个规范归约，如果此序列满足：

1、

n=

2、

0为文法的开始符号，即

0=S3、对任何i，0

i

n，

i-1是从

i经把句柄替换成为相应产生式左部符号而得到的。142023/12/17把上例倒过来写，则得到：S

aAcBe

aAcde

aAbcde

abbcde

显然这是一个最右推导。最右推导常被称为规范推导。容易看到，规范归约是关于的一个最右推导的逆过程。因些，规范归约也称最左归约。由规范推导推出的句型称为规范句型。152023/12/17bdbaceSABAdbaceSABAdaceSABaceSABS162023/12/17四、符号栈的使用栈是语法分析的一种基本数据结构。’#’作为栈底符号。初始状态：栈＃输入串ω#自左至右把输入符号一一进栈，一旦栈顶形成句柄，就把其归约，直至栈顶不再形成句柄为止。然后继续移进，重复上述过程，直至形成栈＃S,输入串＃。若达到上述状态，则表示分析成功，否则输入串不是句子。

172023/12/17步骤

符号栈

输入串

动作0 # i1*i2+i3# 预备1 #i1 *i2+i3# 进2 #F *i2+i3# 归，用F→i3#T *i2+i3# 归，用T→F4 #T* i2+i3# 进例：考虑文法G(E)：E

T|E+TTF|T*FF(E)|i输入串为i1*i2+i3，分析步骤为：182023/12/17步骤

符号栈

输入串

动作4 #T* i2+i3# 进5 #T*i2 +i3# 进6 #T*F +i3# 归，用F→i7 #T +i3# 归，用T→T*F8 #E +i3# 归，用E→T9 #E+ i3#进例：考虑文法G(E)：E

T|E+TTF|T*FF(E)|i输入串为i1*i2+i3，分析步骤为：192023/12/17步骤

符号栈

输入串

动作9#E+i3# 进10 #E+i3 # 进11 #E+F # 归，用F→i12 #E+T # 归，用T→F13 #E # 归，用E→E+T14 #E # 接受例：考虑文法G(E)：E

T|E+TTF|T*FF(E)|i输入串为i1*i2+i3，分析步骤为：202023/12/175.2算符优先分析四则运算的优先规则：先乘除后加减，同级从左到右考虑二义文法文法G(E)：G(E)：E

i|E+E|E-E|E*E|E/E|(E)

它的句子有几种不同的规范规约。归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的。212023/12/17算符优先分析过程是自下而上的归约过程，但未必是严格的最左归约。也就是说，算符优先分析法不是一种规范归约法。所谓算符优先分析法就是定义算符之间的某种优先关系，借助于这种关系寻找“可归约串”进行归约的一种方法。222023/12/17首先必须定义任何两个可能相继出现的终结符a与b的优先关系三种关系a<·b

a的优先级低于bab

a的优先级等于ba·>b

a的优先级高于b注意：与数学上的<,>,=不同a<·b并不意味着b·>a一、直观算符优先分析法232023/12/17直观算符优先分析法使用两个工作栈。OPTR--寄存操作符及＃，初值为＃，（输入串末尾也加＃）OPND--寄存操作数及结果，初值为空，最后为运算结果。242023/12/17设Q代表OPTR栈顶的当前符号，a代表新的输入符号，则直观算符优先算法为：1．Readnextsymboltoa;2．Ifa=ithenpushaintoOPND,GOTO1;3．IfQ·>

athenCallE(1)QE(2);GOTO3;(注：E(1)QE(2)指popE(1);popE(2);t:=E(1),&,E(2)进行Q运算；pusht;popQ);4．IfQathenIfQ=’(‘anda=‘)’thenpopQ;GOTO1;IfQ=a=‘＃’thensuccess;halt.5．IfQ<·athenpushaintoOPTR;GOTO1;6．If(Q,a)=Err.ThenCallERROR.

252023/12/17二、算符优先文法及优先表构造一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：…QR…

则我们称该文法为算符文法。约定：a、b代表任意终结符；P、Q、R代表任意非终结符；‘…’代表由终结符和非终结符组成的任意序列，包括空字。262023/12/17假定G是一个不含

-产生式的算符文法。对于任何一对终结符a、b，我们说：1.ab 当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；3.a·>b 当且仅当G中含有形如P→…Rb…的产生式，而R…a或R…aQ。2.a<·

b 当且仅当G中含有形如P→…aR…的产生式，而Rb…或RQb…；如果一个算符文法G中的任何终结符对(a，b)至多只满足下述三关系之一：a<·b，ab，a·>b则称G是一个算符优先文法。272023/12/17FIRSTVT构造集合FIRSTVT(P)的算法。按其定义，可用下面两条规则来构造集合FIRSTVT(P)：1.若有产生式P→a…或P→Ra…，

则a

FIRSTVT(P)；2.若a

FIRSTVT(R)，且有产生式P→R…，

则a

FIRSTVT(P)。282023/12/17构造集合LASTVT(P)的算法。按其定义，可用下面两条规则来构造集合LASTVT(P)：1.若有产生式P→…a或P→…aQ，则a

LASTVT(P)；2.若a

LASTVT(Q)，且有产生式P→…Q，则a

LASTVT(P)。LASTVT292023/12/17检查G的每个候选式，若有p→…aQb…或p→…ab…的产生式，则置ab若G中有形如…aP…的候选式，则对于所有的b∈FIRSTUT(P)，有a<·b若G中有形如…Pb…的候选式，则对于所有的a∈LASTUT(P)有a·>b优先关系表的构造302023/12/17数据结构：布尔数组F[P，a]，使得F[P，a]为真的条件是，当且仅当a

FIRSTVT(P)。开始时，按上述的规则(1)对每个数组元素F[P，a]赋初值。栈STACK，把所有初值为真的数组元素F[P，a]的符号对(P，a)全都放在STACK之中。构造优先关系表的算法312023/12/17运算：如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如P→Q…

的产生式，若F[P，a]为假，则变其值为真且将(P，a)推进STACK栈。上述过程必须一直重复，直至栈STACK拆空为止。322023/12/17如果把这个算法稍为形式化一点，我们可得如下所示的一个程序(包括一个过程和主程序)：PROCEDUREINSERT(P，a)；IFNOTF[P，a]THENBEGINF[P，a]:=TRUE；

把(P，a)下推进STACK栈END；332023/12/17主程序：BEGIN

FOR每个非终结符P和终结符aDOF[P，a]:=FALSE；

FOR每个形如P→a…或P→Qa…的产生式DO INSERT(P，a)；

WHILESTACK非空DO BEGIN

把STACK的顶项，记为(Q，a)，上托出去； FOR每条形如P→Q…的产生式DO INSERT(P，a)； ENDOFWHILE；END342023/12/17这个算法的工作结果得到一个二维数组F，从它可得任何非终结符P的FIRSTVT。FIRSTVT(P)＝{a|F[P，a]=TRUE}同理，可构造计算LASTVT的算法。352023/12/17三、算符优先分析法的设计可归约串，句型，短语，直接短语，句柄，规范归约。一个文法G的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。最左素短语是指处于句型最左边的那个素短语。362023/12/17例：考虑下面的文法G(E)：(1)E→E+T|T(2)T→T*F|F (3)F→P

F|P(4)P→(E)|iEEF+*TiFTFTP+ETP句型：T+F*P+i短语：直接短语：句柄：素短语：最左素短语：,T+F*P+iT,F,P,F*P,,iT+F*PT,F,P,iTF*P,iF*P372023/12/17算符优先文法句型(括在两个＃之间)的一般形式写成：#N1a1N2a2…NnanNn+1#

其中，每个ai都是终结符，Ni是可有可无的非终结符。定理：一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串Njaj…NiaiNi+1，

其中，aj-1<·aj ajaj+1，…，ai-1ai ai·>ai+1382023/12/17根据这个定理，下面我们讨论算符优先分析算法。为了和定理叙述的相适应，我们使用一个符号栈S，用它寄存终结符和非终结符，下面的分析算法是直接根据这个定理构造出来的，k代表符号栈S的使用深度。

392023/12/17k:=1; S[k]:=‘#’;REPEAT

把下一个输入符号读进a中； IFS[k]

VTTHENj:=kELSEj:=k-1; WHILES[j]aDO BEGIN REPEAT Q:=S[j]; IFS[j-1]

VTTHENj:=j-1ELSEj:=j-2 UNTILS[j]Q;

把S[j+1]…S[k]归约为某个N； k:=j+1; S[k]:=N ENDOFWHILE; IFS[j]aORS[j]aTHEN BEGINk:=k+1;S[k]:=aEND ELSEERROR/*调用出错诊察程序*/UNTILa=‘#’自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同。N→X1X2…Xk-j

↕↕↕S[j+1]S[j+2]…S[k]402023/12/17在算法的工作过程中，若出现j减1后的值小于等于0时，则意味着输入串有错。在正确的情况下，算法工作完毕时，符号栈S应呈现：#N#。由于非终结符对归约没有影响，因此，非终结符根本可以不进符号栈S。412023/12/17算符优先分析一般并不等价于规范归约。EE+*iTP+iPiPiPEEF+*TiFTFTP+ETiFPiPiP考虑下面的文法G(E)：(1)E→E+T|T(2)T→T*F|F (3)F→P

F|P(4)P→(E)|i的句子i+i*i+i422023/12/17算符优先分析法特点：优点:简单，快速缺点:可能错误接受非法句子，能力有限.算符优先分析法是一种广为应用、行之有效的方法。用于分析各类表达式ALGOL60432023/12/17四、优先函数把每个终结符

与两个自然数f(

)与g(

)相对应，使得若

1

2，则f(

1)<g(

2)若

1

2，则f(

1)=g(

2)若

1

2，则f(

1)>g(

2)f称为入栈优先函数，g称为比较优先函数。优点:便于比较，节省空间；缺点:原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。442023/12/17例：文法G(E)(1)E→E+T|T(2)T→T*F|F (3)F→P

F|P(4)P→(E)|i的优先函数如下表452023/12/17有许多优先关系表不存在优先函数，如：

不存在对应的优先函数f和g

假定存在f和g，则有f(a)=g(a)，f(a)>g(b)，f(b)=g(a)，f(b)=g(b)

导致如下矛盾:f(a)>g(b)=f(b)=g(a)=f(a)如果优先函数存在，则不唯一(无穷多)462023/12/17如果优先函数存在，则可以通过以下三个步骤从优先表构造优先函数:1对于每个终结符a，令其对应两个符号fa和ga，画一以所有符号和为结点的方向图。

如果a

b，则从fa画一条弧至gb。

如果a

b，则画一条弧从gb至fa

。2对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点(包括出发点自身)。赋给fa的数作为f(a)，赋给ga的数作为g(a)。3检查所构造出来的函数f和g是否与原来的关系矛盾。若没有矛盾，则f和g就是要求的优先函数，若有矛盾，则不存在优先函数。472023/12/17现在必须证明：若ab，则f(a)＝g(b)；若ab，则f(a)<g(b)；若ab，则f(a)>g(b)。第一个关系可从函数的构造直接获得。因为，若ab，则既有从fa到gb的弧，又有从gb到fa的弧。所以，fa和gb所能到达的结是全同的。至于ab和ab的情形，只须证明其一。482023/12/17如果ab，则有从fa到gb的弧。也就是，gb能到达的任何结fa也能到达。因此，f(a)

g(b)。我们所需证明的是，在这种情况下，f(a)＝g(b)不应成立。我们将指出，如果f(a)＝g(b)，则根本不存在优先函数。假若f(a)＝g(b)，那么必有如下的回路：492023/12/17

因此有ab,a1b,a1b1,…,ambm,abm对任何优先函数f’和g’来说，必定有f’(a)>g’(b)

f’(a1)

g’(b1)

…

f’(am)

g’(bm)

f’(a)从而导致f’(a)>f’(a)，产生矛盾。因此，不存在优先函数f和g。fa1fafamgb1gbgbm……502023/12/175.3LR分析概述

1、ＬＲ分析器模型总控程序outputInput#S1Xm…S1…X1S0#栈状态文法符号ACTIONGOTOLR分析表产生式表512023/12/17逻辑上说，一个LR分析器由3个部分组成：(1)

总控程序，也可以称为驱动程序。对所有的LR分析器总控程序都是相同的。(2)

分析表或分析函数，不同的文法分析表将不同，同一个文法采用的LR分析器不同时，分析表也不同，分析表又可分为动作表（ACTION）和状态转换（GOTO）表两个部分，它们都可用二维数组表示。

(3)分析栈，包括文法符号栈和相应的状态栈，它们均是先进后出栈。分析器的动作就是由栈顶状态和当前输入符号所决定。2、LR分析方法的逻辑结构522023/12/17

总控程序根据不同的分析表来决定其下一步的处理动作，分析表是根据具体的文法按某种规则构造出来的。LR方法是根据具体文法的分析表对输入串进行分析处理。

LR分析过程的思想是在总控程序的控制下，从左到右扫描输入符号串，根据分析栈中的状态和文法及当前输入符号，按分析表完成相应的分析工作。532023/12/17分析表的组成：(1)分析动作表Action

符号状态a1a2…atS0action[S0,

a1]action[S0,

a2]…action[S0,

at]S1action[S1,

a1]action[S1,

a2]…action[S1,

at]……………Snaction[Sn,

a1]action[Sn,

a2]…action[Sn,

at]542023/12/17

表中action[Si,aj]为二维数组，指出当前栈顶为状态Si，输入符号为aj是所执行的动作。其动作有四种可能，分别为移进(S)、归约(r)、接受(acc)、出错(error)。(2)状态转换表goto552023/12/17

符号状态x1x2…xtS0goto[S0,

x1]goto[S0,

x2]…goto[S0,

xt]S1goto[S1,x1]goto[S1,

x2]…goto[S1,

xt]……………Sngoto[Sn,

x1]goto[Sn,

x2]…goto[Sn,

xt]

表中goto[Si,xj]指出栈顶状态为Si，文法符号为xj时应转到的下一状态。562023/12/175656分析表种类的不同决定使用不同的LR分析方法a)SLR分析表(简单LR分析表)

b)LR分析表(规范LR分析表)构造简单,最易实现,大多数上下文无关文法都可以构造出SLR分析表,所以具有较高的实用价值。使用SLR分析表进行语法分析的分析器叫SLR分析器适用文法类最大,大多数上下文无关文法都能构造出LR分析表,但其分析表体积太大.暂时实用价值不大.572023/12/175757c)LALR分析表(超前LR分析表)这种表适用的文法类及其实现上难易在上面两种之间,在实用上很吸引人.使用LALR分析表进行语法分析的分析器叫LALR分析器。例：YACC

文法规则文件YACC源文件YACC某语言的LALR分析器582023/12/1758581.三种分析表对应三类文法几点说明2.一个SLR文法必定是LALR文法和LR文法592023/12/173、LR分析过程：LR分析步骤：(a)将初始状态S0和句子的左界符#分别进分析栈。(b)根据栈顶状态和当前输入符号查动作表，进行如下的工作。※移进：当前输入符号进符号栈，根据状态转换表新的状态进状态栈，继续扫描，从而下一输入符号变成当前输入符号。

※归约：(1)按某个产生式进行归约，若产生式的右端长度为n，则符号栈顶和状态顶n个元素同时相应退栈。(2)归约后的文法符号进符号栈，(3)查602023/12/17状态转换表，新的状态进状态栈。(c)接受：分析成功，终止分析。

(d)出错：报告出错信息。(2)具体分析过程：举例说明具体分析过程：设文法为G[L]

（假定已存在LR分析表）

(1)LE,L(2)LE(3)Ea(4)Eb612023/12/17

LR分析算法置ip指向输入串w的第一个符号令S为栈顶状态a是ip指向的符号重复beginifACTION[S,a]=Sj

then

beginPUSHj,a(进栈)ip前进(指向下一输入符号)

endelse

ifACTION[S,a]=rj(第j条产生式为A)622023/12/17LR分析算法then

beginpop||项令当前栈顶状态为S’pushGOTO[S’,A]和A(进栈)endelse

ifACTION[s,a]=accthenreturn(成功）elseerrorend.重复632023/12/17

为了介绍LR分析过程，在这里直接给出该文法的分析表，之后再介绍如何生成该表。状态ACTIONGOTOab,#LES0S3S412S1accS2S5r2S3r3r3S4r4r4S5S3S462S6r1ri表示按第i个产生式进行归约Si表示把当前输入符号移进栈，且转第i个状态，即第i个状态进状态栈。i表示转第i个状态，即第i个状态进状态栈。空白表示分析动作出错。642023/12/17

根据上述分析表，即可对输入串进行分析。如输入串为#a,b,a#具体分析过程如下：状态栈符号栈产生式输入符号说明S0#a,b,a#S0和#进栈S0S3#a,b,a#a和S3进栈S0S2#EE

a,b,a#a和S3退栈E和S2进栈S0S2S5#E,b,a#,和S5进栈S0S2S5S4#E,b,a#b和S4进栈S0S2S5S2#E,EE

b,a#b和S4退栈E和S2进栈652023/12/17状态栈符号栈产生式输入符号说明S0S2S5S2S5#E,E,a#,和S5进栈S0S2S5S2S5S3#E,E,a#a和S3进栈S0S2S5S2S5S2#E,E,EE

a#a和S3退栈E和S2进栈S0S2S5S2S5S6#E,E,LL

E#E和S2退栈L和S6进栈S0S2S5S6#E,LL

E,L#E,L和S2S5S6退L和S6进栈S0S1#LL

E,L#E,L和S2S5S6退L和S1进栈acc662023/12/17自底向上分析法的关键问题是在分析过程中如何确定句柄。LR方法中的句柄是通过求可归前缀而求得。672023/12/17例：文法G[S]为：SaAcBeAbAAbBd为产生式加序号变为：SaAcBe[1]Ab[2]AAb[3]Bd[4]对于输入串abbcde句子的最右推导（规范推导）如下：SaAcBe[1]aAcd[4]e[1]aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]活前缀与可归前缀682023/12/17对它的逆过程最左归约(规范归约)为：ab[2]b[3]cd[4]e[1]

aAb[3]cd[4]e[1]

aAcd[4]e[1]

aAcBe[1]

S用哪个产生式继续归约仅取决于当前句型的前部。

我们把每次采取归约动作前的符号串部分称为可归前缀。

LR分析的关键就是识别何时到达可归前缀。为产生式加序号变为：SaAcBe[1]Ab[2]AAb[3]Bd[4]692023/12/17在规范句型中形成可归前缀之前包括可归前缀的所有前缀称为活前缀。活前缀为一个或若干规范句型的前缀。在规范归约过程中的任何时刻只要已分析过的部分即在符号栈中的符号串均为规范句型的活前缀，则表明输入串的已被分析过的部分是某规范句型的一个正确部分。例如：有下面规范句型的前缀：

，a，ab

，a，aA，aAb

，a，aA，aAc，aAcd

，a，aA，aAc，aAcB，aAcBe左部均为活前缀，其中，红色部分为可归前缀702023/12/17G=(Vn,Vt,P,S),若有S’

αAω

αβω,Aβ（β是句柄）γ是αβ的前缀,则称是文法G的活前缀αβ是含句柄的活前缀，并且句柄是αβ的后端，则称αβ是可归前缀或可规范前缀。在LR分析过程中，实际上是把αβ的前缀（即文法G的活前缀）列出放在符号栈中，一旦在栈中出现αβ（形成可归前缀），即句柄已经形成，则用产生式Aβ进行归约。活前缀的定义及在LR分析中的应用712023/12/17识别活前缀的有限自动机对任何一个上下文无关文法，只要能构造出它的识别可归前缀的有限自动机，就可以构造其相应的分析表（状态转换表和动作表）。722023/12/17☆

状态栈:S0,S1,…,Sm

状态S0---初始状态Sm---栈顶状态

栈顶状态概括了从分析开始到该状态的全部分析历史.☆符号栈:

X1X2.....Xm

为从开始状态(S0)到当前状态(Sm)所识别的规范句型的活前缀.#S0x1S1x2......xmSmS0S1......Sm#x1x2.....xm732023/12/17☆分析表是一个矩阵：行---分析器的状态列----文法符号状态符号ETFS0S1S2:SnGOTO表a.状态转移表(GOTO表)742023/12/17GOTO[Si-1,xi]=Si Si-1---当前状态(栈顶状态) xi---新的栈顶符号

Si------

新的栈顶状态(状态转移)Si需要满足条件是:

若X1X2….Xi-1是由S0到Si-1所识别的规范句型的活前缀,则X1X2….Xi是由S0到Si所识别的规范句型的活前缀#S0x1S1x2......xi-1Si-1xiSi状态符号ETFS0S1S2:SnGOTO表752023/12/17通过对有穷自动机的了解,我们可以看出:

状态转移函数GOTO是定义了一个以文法符号集为字母表的有穷自动机，该自动机识别文法所有规范句型的活前缀及可归前缀。M=(S,V,GOTO,S0,Z)S0S1Si-1S2SiX1X2Xi-1Xi762023/12/17b.分析动作表(ACTION表)Sn状态s输入符号ai+*()#S0S1S2:ACTION表ACTION[Si,a]=动作分析a∈Vt识别为活前缀的，则移进；识别为可归前缀的，则归约772023/12/17分析动作：1)移进(shift)ACTION[Si,a]=S动作：将a推进栈，并设置新的栈顶状态SjSj=GOTO[Si,a]，将指针指向下一个输入符号2)规约(reduce)ACTION[Si,a]=rdd：文法规则编号(d)A→β动作：将符号串β(假定长度为n)连同状态从栈内弹出把A推进栈，并设置新的栈顶状态Sj,Sj=GOTO[Si-n,A]3)接受(accept)ACTION[Si,#]=accept4)出错(error)ACTION[Si,a]=error782023/12/17☆控制程序:(DriverRoutine)1)根据栈顶状态和现行输入符号，查分析动作表(ACTION表)，执行有分析表所规定的操作；

2)并根据GOTO表设置新的栈顶状态(即实现状态转移)792023/12/17例：文法G[E] (1)E::=E+T (2)E::=T (3)T::=T*F (4)T::=F (5)F::=(E) (6)F::=i（2）LR分析过程该文法是SLR文法,故可以构造出SLR分析表(ACTION表和GOTO表)802023/12/17ACTION表GOTO表文法G[E]：(1)E::=E+T(2)E::=T(3)T::=T*F(4)T::=F(5)F::=(E)(6)F::=i文法符号状态i+*()#ETF0(S0)S5S41231(S1)S6ACCEPT2(S2)R2S7R2R23(S3)R4R4R4R4

4(S4)S5S48235(S5)R6R6R6R66(S6)S5S4937(S7)S5S4108(S8)S6S119(S9)R1S7R1R110(S10)R3R3R3R311(S11)R5R5R5R5812023/12/17ACTION表GOTO表输入符号状态文法G[E](1)E::=E+T(2)E::=T(3)T::=T*F(4)T::=F(5)F::=(E)(6)F::=iSi：移入，i为状态Ri：规约，i为产生式编号822023/12/17分析过程：

i*i+i步骤 状态栈 符号 输入串 动作1 ＃0 ＃ i*i+i# 初始化2 ＃0i5 ＃i *i+i# S3 ＃0F3 ＃F *i+i# R64 ＃0T2 ＃T *i+i# R45 ＃0T2*7 ＃T* i+i# S6 ＃0T2*7i5 ＃T*i +i# S7 ＃0T2*7F10 ＃T*F +i# R6832023/12/1711 ＃0E1+6i5 #E+i # S12 ＃0E1+6F3 #E+F # R613 ＃0E1+6T9 #E+T # R414 ＃0E1 #E # R115 #E Accept9 ＃0E1 #E +i# R210 ＃0E1+6 #E+ i# S8 ＃0T2 #T +i# R3842023/12/17由分析过程可以看到:(1)每次规约总是规约当前句型的句柄，是规范规约，可以看到语法树(算符优先是规约最左素短语)EET+TT*FFiiFi87564321(2)分析的每一步栈内符号串均是规范句型的活前缀，与输入串的剩余部分构成规范句型.852023/12/17LR方法概述（回顾）LR文法：

如果一个文法能构造一张LR分析表，使其每个入口均是唯一确定的，那么称此文法为LR文法。LR(k)指分析的每步最多只需向前搜索k个字符便能确定采取什么动作。

任何二义文法都不可能是LR(k)的，不管k多大。862023/12/17LR分析法如何分析句子？

移进归约（从左到右扫描(L)自底向上进行规约(R)）移进归约的关键问题是什么？

判断符号栈顶的符号串是否构成句柄。LR分析法如何识别句柄？LR分析法在分析过程中并不是直接分析符号栈中的符号是否形成句柄，而是通过识别可归前缀来识别句柄。

具体地，LR分析法的分析过程可以看作识别活前缀和可归前缀的过程，只要符号栈中的符号串构成活前缀，就表示已分析过的部分是正确的，继续移进；直到符号栈中的符号串构成可归前缀，则表示当前栈顶符号串已形成句柄，则进行归约。872023/12/17如何识别活前缀和可归前缀？

通过有限自动机来识别。如何构造识别活前缀和可归前缀的有限自动机？

根据文法规则：

状态集合：列出所有活前缀的识别状态

符号表：所有的终结符和非终结符

状态转换函数：f(Ki，a)=Kj某一个活前缀的识别状态，在输入符号表中的一个符号之后，转向另一个活前缀的识别状态。

终态集：所有可归前缀的识别状态882023/12/175.4LR(0)分析构造LR分析器的关键是构造其分析表构造LR分析表的方法是:（1）根据文法构造识别规范句型活前缀的有穷自动机DFA（2）由DFA构造LR分析表892023/12/171.构造DFA(1)DFA是一个五元式M=(S,V,GOTO,S0,Z)S：有穷状态集在此具体情况下，S=LR(0)项目集规范族LR(0)。项目集规范族：其元素是由项目所构成的集合.V：文法字汇表Vn∪VtS0：初始状态GOTO:状态转移函数GOTO[Si,X]=SjSi,Sj∈SSi,Sj为项目集合X∈Vn∪Vt表示当前状态Si面临文法符号为X时，应将状态转移到

SjZ：终态集合902023/12/171）确定S集合，即LR（0）项目集规范族，同时确定S02）确定状态转移函数GOTO∴构造DFA方法：912023/12/17LR(0)分析确定状态集合每一个状态对应文法中某一个产生式规则的某一个项目每一个产生式规则的每一个项目代表一个活前缀的识别状态。产生式规则的项目？922023/12/17项目:文法G的每个产生式(规则)的右部添加一个圆点就构成一个项目。例:产生式:A→XYZ

项目:A→.XYZA→X.YZA→XY.ZA→XYZ.

产生式:A→ε

项目:A→.项目的直观意义:指明在分析过程中的某一时刻已经规约的部分和等待规约部分。其中，ε、X、XY、XYZ为活前缀，XYZ是可归前缀。932023/12/17

例如：产生式S

aAcBe对应有6个项目。

[0]S

·aAcBe[1]S

a·AcBe[2]S

aA·cBe[3]S

aAc·Be[4]S

aAcB·e[5]S

aAcBe·942023/12/17项目类型：

项目类型有归约项目、移进项目、待约项目和接受项目。

归约项目：后继符号为空的项目称为归约项目。如：A·此时已把分析结束，已在栈顶，从而可按相应的产生式进行归约。

移进项目：后继符号为终结符的项目称为移进项目。如A

·X

，XVt

此时把X移进，即X进符号栈。

待约项目：后继符号为非终结符的项目，称为待约项目。952023/12/17

此时期待着从余留的输入符号中进行归约而得到X。

接受项目：当归约项目为S’S·时则表明已分析成功，即输入串为该文法的句子，相应状态为接受状态。构造识别活前缀的NFAP131从A

·X

画X弧指向A

X·

；如果XVn，则还需要画空子弧指向X

·w962023/12/17例：文法：S→aAbA→aA|a972023/12/17IIaIbIA确定化为：982023/12/17992023/12/17状态内容是项目集组成的，它分为基本(BASIC)部分和闭包(CLOSURE)部分。※求BASIC和CLOSURE的方法如下：设Si是Sk关于符号X的后继状态，则有

BASIC(Si)的计算：BASIC(Si)={AX·|A·XSk}CLOSURE(Si)的计算：

BASIC(Si)

CLOSURE(Si)LR(0)项目集规范族的构造1002023/12/17

若A

·YCLOSURE(Si),且YVn则Y·rCLOSURE(Si),r为符号串

重复直到CLOSURE(Si)不再增加为止。例如：文法G[S]：S

AA

aAbA

c设开始状态为S0，则S0的状态内容为：BASIC(S0)={S

·A}CLOSURE(S0)={S

·A,A

·aAb,A

·c}1012023/12/17A.项目集闭包closure的定义和计算:

令I是文法G’的任一项目集合，定义closure(I)为项目集合I的闭包，可用一个过程来定义并计算closure(I)。Procedureclosure(I);begin

将属于I的项目加入closure(I);repeatforclosure(I)中的每个项目A→α.Bβ(B∈Vn)do

将B→.r(r∈V*)加入closure(I)untilclosure(I)不再增大end例:G’[E’]令I={E’→.E}closure(I)={E’→.E,E→.E+T,E→.T,T→.T*F,T→.F,F→.(E),F→.i}1022023/12/17B状态转移函数GOTO的定义:GOTO(I,X)=closure(J)I：项目集合

X：文法符号，X∈VJ：项目集合J={任何形如A→αX.β的项目|A→α.Xβ∈I}closure(J):项目集J的闭包仍是项目集合所以,GOTO(I,X)=closure(J)的直观意义是:

它规定了识别文法规范句型活前缀的DFA从状态I(项目集)出发,经过X弧所应该到达的状态(项目集合)1032023/12/17LR(0)项目集规范族的构造算法:P107步骤（1）、（2）、（3）G'→LR(0)ProcedureITEMSETS(G');beginLR(0):={closure({E'→.E})};repeatforLR(0)中的每个项目集I和G'的每个符号XdoifGOTO(I,X)非空,且不属于LR(0)then把GOTO(I,X)放入LR(0)中

untilLR(0)不再增大end1042023/12/17例.求G'[E']的LR(0)V={E,T,F,I,+,*,(,)}G'[E']共有20个项目LR(0)={I0,I1,I2,…I11}有12个项目组成:I0: E'→.E E→.E+T E→.T T→.T*F T→.F F→.(E) F→.iI1: E'→E. E→E.+TClosure({B’→.B})=I0GOTO(I0,E)=closure({E’→E.E→E.+T})=I1(0)E’→E(4)T→FE→E+T(5)F→(E)E→T(6)F→iT→T*F1052023/12/17I2: E→T.GOTO(I0,T)=closure({E→T.T→T.*F})=I2T→T.*FI3: T→F.GOTO(I0,F)=closure({T→F.})=I3I4: F→(.E)GOTO(I0,()=closure({F→(.E)})=I4E→.E+TE→.T T→.T*F T→.F F→.(E) F→.iI5: F→i.GOTO(I0,i)=closure({F→i.})=I5GOTO(I0,*)=φGOTO(I0,+)=φGOTO(I0,))=φI0:E'→.EE→.E+TE→.TT→.T*FT→.FF→.(E)F→.i1062023/12/17I6: E→E+.TGOTO(I1,+)=closure({E→E+.T})=I6 T→.T*FGOTO(I1,其他符号)为空

T→.F F→.(E) F→.iI7: T→T*.F GOTO(I2,*)=closure({T→T*.F})=I7 F→.(E) GOTO(I2,其他符号)为空

F→.i GOTO(I3,其他符号)为空

I1:E'→E.E→E.+TI2:E→T.T→T.*F1072023/12/17I8: F→(E.) GOTO(I4,E)=closure({F→(E.),E→E.+T})=I8 E→E.+T GOTO(I4,T)=I2∈LR(0) GOTO(I4,F)=I3∈LR(0) GOTO(I4,()=I4∈LR(0) GOTO(I4,i)=I5∈LR(0) GOTO(I4,+)=φ GOTO(I4,*)=φ GOTO(I4,))=φGOTO(I5,其他符号)=φI9: E→E+T. GOTO(I6,T)=closure({E→E+T.,T→T.*F})=I9 E→T.*F GOTO(I6,F)=I3 GOTO(I6,()=I4 GOTO(I6,i)=I5

I4: F→(.E)E→.E+TE→.TT→.T*F T→.F F→.(E) F→.i1082023/12/17I10:T→T*F. GOTO(I7,T)=closure({T→T*F.})=I10 GOTO(I7,()=I4 GOTO(I7,i)=I5I11:F→(E). GOTO(I8,))=closure({F→(E).})=I11 GOTO(I7,()=I4 GOTO(I7,i)=I5求完所有Ii的后继GOTO(I8,+)=I6GOTO(I9,*)=I7GOTO(I10,所有符号)=φ,GOTO(I11,所有符号)=φ1092023/12/17构造DFA

M=(S,V,GOTO,S0,Z) S={I0,I1,I2,…,I11}=LR(0) V={+,*,i,(,),E,T,F} GOTO(Im,X)=Im

S0=I0 Z=S-{I0}={I1,I2,…,I11}1102023/12/17I0I5I2I4I3I1I11I8I6I10I7I9startE++iF(TTF(iF(iE(**)+iF1112023/12/17除I0以外,其余状态都是活前缀的识别状态,从I0到每一状态的每条路径都识别和接受一个规范句型的活前缀。1122023/12/17项目集的相容性：〖定义〗满足下列两个条件的项目集称为相容的项目集。

※无移进项目和归约项目并存。※无多个归约项目并存。例如：若有项目集｛A·，B·｝此时栈顶为，根据项目集无法确定是移进还是归约。项目集是不相容的。

对一个文法的LR(0)项目集规范族不存在移进归约或归约归约冲突时，称该文法为LR(0)文法。

1132023/12/17LR(0)分析表的构造LR（0）分析表由两部分组成：动作表表示当前状态下面临输入符号应做的动作是移进、归约、接受或出错；状态转换表表示在当前状态下面临文法符号时应转向的下一个状态。1142023/12/17(2)LR(0)分析表的构造构造原则：

设有文法G[S]，则LR(0)分析表的构造规则为：

对于A·XSi，GOTO(Si,X)=Sj

若X

Vt，则置action[Si,X]=Sj

若XVn，则置goto[Si,X]=j

对于A·Si，若A是文法的第j个产生式，则对所有的xVt，均置action[Si,x]=rj

若S·Si，则置action[Si,#]=acc

其他均置出错。1152023/12/17LR(0)分析表的构造假定C={I0,I1,……，In}，令每个项目集Ik的下标k为分析器的一个状态，因此，G`的LR(0)分析表含有状态0，1，……，n。令那个含有项目S`→．S的Ik的下标k为初态。ACTION和GOTO可按如下方法构造：若项目A→α．aβ属于Ik且GO(Ik,a)=Ij,a为终结符，则置ACTION[k,a]为“把状态j和符号a移进栈”，简记为“sj”;若项目A→α．属于Ik,那么，对任何终结符a,置ACTION[k,a]为“用产生式A→α进行规约”，简记为“rj”;其中，假定A→α为文法G`的第j个产生式；若GO(Ik,A)=Ij,A为非终结符，则置GOTO(k,A)=j;若项目S`→S．属于Ik,则置ACTION[k,#]为“接受”，简记为“acc”;分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”1162023/12/17例子：文法G为：(0)S’E

(1)EaA(2)EbB(3)A

cA(4)A

d(5)B

cB(6)B

d该文法的状态描述序列见下表：1172023/12/17状态项目集后继符号后继状态S0{S’·EE·aAE·bBEabS1S2S3S1{S’E·}#S12S2{Ea·AA·cAA·d}AcdS6S4S10S3{Eb·BB·cBB·d}BcdS7S5S111182023/12/17状态项目集后继符号后继状态S4{Ac·AA·cAA·d}AcdS8S4S10S5{Bc·BB·cBB·d}BcdS9S5S11S6{EaA·}#E

aAS12S7{EbB·}#E

bBS12S8{AcA·}#A

cAS121192023/12/17状态项目集后继符号后继状态S9{BcB·}#B

cBS12S10{Ad·}#A

dS12S11{Bd·}#B

dS12S12{}

根据状态描述序列和分析表的构造规则得到的LR(0)分析表如下：1202023/12/17状态ACTIONGOTOabcd#EABS0S2S31S1accS2S4S106S3S5S117S4S4S108S5S5S119S6r1r1r1r1r1S7r2r2r2r2r2S8r3r3r3r3r3S9r5r5r5r5r5S10r4r4r4r4r4S11r6r6r6r6r61212023/12/17状态栈符号栈产生式输入符actiongoto说明S0#bccd#S3b和S3进栈S0S3#bccd#S5c和S5进栈S0S3S5#bccd#S5c和S5进栈S0S3S5S5#bccd#S11d和S11进栈S0S3S5S5S11#bccdBd#r69d和S11退栈B和S9进栈S0S3S5S5S9#bccBBcB#r59…S0S3S5S9#bcBBcB#r57…S0S3S7#bBE

bB#r21…S0S1#E#acc接受对于输入串#bccd#的分析过程如下：1222023/12/175.5SLR（1）分析

SLR(1)分析表的构造1、问题的提出：只有当一个文法G是LR(0)文法，即G的每一个状态项目集相容时，才能构造出LR(0)分析表；由于大多数适用的程序设计语言的文法不能满足LR(0)文法的条件，因此本节将介绍对于LR(0)规范族中冲突的项目集（状态）用向前查看一个符号的办法进得处理，以解决冲突。因为只对有冲突的状态才向前查看一个符号，以确定做那种动作，因而称这种分析方法为简单的LR(1)分析法，用SLR(1)表示。1232023/12/17文法G为：(0)S’SSrDDD,iDi状态描述序列见下表：状态项目集后继符号后继状态S0S’·SS·rDSrS1S2S1S’

S·#S’

SS71242023/12/17S2S

r·DD·D,iD·iDDiS3S3S4S3S

rD