LL(1)分析法 复 习 LL分析程序构造及分析过程 输入串 符号栈 执行程序 此过程有三部分组成: 分析表 执行程序 (总控程序） # 符号栈 执行程序 此过程有三部分组成: 分析表 执行程序 (总控程序） 符号栈 （分析栈） # 分析表

求SELECT E→TE’ FIRST(F)={(,i} FOLLOW(F)={*,+,),#} E’→+TE’|ε T→FT’ T’→*FT’|ε F→(E)|i FIRST(F)={(,i} FIRST(T’)={*,ε} FIRST(T)={(,i} FIRST(E’)={+,ε} FIRST(E)={(,i} FOLLOW(F)={*,+,),#} FOLLOW(T’)={+,),#} FOLLOW(T)={+,),#} FOLLOW(E’)={#,)} FOLLOW(E)={#,)} 求SELECT SELECT(E→TE’)={ (,i } SELECT(E’→+TE’)={ + } SELECT(E’→ ε)={ ),# } SELECT(T→FT’)={ (,i } SELECT(T*FT)={*} SELECT(T’→ε)={ +,),# } SELECT (F→(E)={ ( } SELECT (F→i)={ i }

请用自顶向下的方法分析是否字符串i+i*i∈L(G[E])。 E::=TE’ E’::=+TE’|ε T ::=FT’ E::= E +T | T T::= T * F | F F::=(E)|i 请用自顶向下的方法分析是否字符串i+i*i∈L(G[E])。 E::=TE’ E’::=+TE’|ε T ::=FT’ T’::=*FT’|ε F::=(E)|i 消除左递归 分析表 i + * ( ) # E E→TE’ E’ E’→+TE’ E’→ε T T →FT’ T’ T’→ε T’→*FT’ F F→i F→(E) 3 3 注：矩阵元素空白表示Error

输入串为: i+i*i# 步骤 符号栈 读入符号 剩余符号串 使用规则 1. ＃E E# i +i*i# 步骤 符号栈 读入符号 剩余符号串 使用规则 1. ＃E E# i +i*i# 2. ＃E’T TE’# i +i*i# E::=TE’ 3. ＃E’T’F FT’E’# i +i*i# T::=FT’ 4. ＃E’T’ i iT’E’# i +i*i# F::= i 5. ＃E’T’ T’E’# + i*i# (出栈，读下一个符号） 6. ＃E’ E’# ＋ i*i# T::= ε 7. ＃E’T+ +TE’# ＋ i*i# E::=+TE’

输入串为: i+i*i# 步骤 符号栈 读入符号 剩余符号串 使用规则 8. ＃E’T i *i# 步骤 符号栈 读入符号 剩余符号串 使用规则 8. ＃E’T i *i# 9. ＃E’T’F i *i# T::=FT’ 10. ＃E’T’ i i *i# F::= i 11. ＃E’T’ * i# 12. ＃E’T’F* * i# T’::=*FT’ 13. ＃E’T’F i # 14. ＃E’T’ i i # F::= i 15. ＃E’T’ # 16. ＃E’ # T’::= ε 17. ＃ # E’::= ε 5 5

4.2 自底向上分析 4.2.1 移进-归约分析 (自底向上分析的一般过程) 4.2.2 优先分析法 4.2.3 LR分析法

若Z  S 则 S  L(G[Z]) 否则 S  L(G[Z]) 自顶向下分析算法的基本思想为： 若Z  S 则 S  L(G[Z]) 否则 S  L(G[Z]) + G[Z] 存在主要问题: 左递归问题 回溯问题 主要方法: 递归子程序法 LL分析法 自底向上分析算法的基本思想为： 若Z  S 则 S L(G[Z]) 否则 S  L(G[Z]) + G[Z] 存在主要问题: 句柄的识别问题 主要方法: 算符优先分析法 LR分析法

自底向上分析 基本算法: 若采用自左向右的描述和分析输入串,那么自 底向上的基本算法是： 从输入符号串开始，通过重复查找当前句型的 句柄(最左直接短语)，并利用有关规则进行规约， 若能规约为文法的开始符号，则表示分析成功，输 入符号串是文法的合法句子，否则有语法错误。

4.2.1 移进—归约分析（Shift-reduce parsing) 要点：建立符号栈，用来纪录分析的历史和现状，并根据所面临的状态，确定下一步动作是移进还是归约。 # L.R.P 符号栈 输入串

输入串为bbcde，检查是否是该文法的合法句子。 例：G[S]: S→AcBe A→b A→Ab B→d 输入串为bbcde，检查是否是该文法的合法句子。 若采用自底向上分析，即能否一步步归约当前句型的句柄，最终规约到开始符号S。先设立一个符号栈，我们统一符号“#”作为待分析的符号串的左右分界符。 作为初始状态，先将符号串的分界符推进符号栈，作为栈底符号。 分析过程如下表:

步骤 符号栈 输入符号串 分析动作 1 # bbcde# 移进 2 #b bcde# 归约(Ab) 3 #A bcde# 移进 例：G[S]: S→AcBe A→b A→Ab B→d 步骤 符号栈 输入符号串 分析动作 1 # bbcde# 移进 2 #b bcde# 归约(Ab) 3 #A bcde# 移进 4 #Ab cde# 归约(AAb) 5 #A cde# 移进 6 #Ac de# 移进 7 #Acd e# 归约(Bd) 8 #AcB e# 移进 9 #AcBe # 归约(SAcBe) 10 #S # 接受

说明:例子的分析过程是一步步地归约当前句型的句柄 这一方法简单明了,不断地进行移进归约, 关键是确定当前句型的句柄. 说明:例子的分析过程是一步步地归约当前句型的句柄 该句子输入串为bbcde的 语法树的构造过程为: 例：G[S]: S→AcBe A→b A→Ab B→d A b a) A b b) A b c d B c) c d B e A b S d)

基本问题 检查是否为句柄—归约条件 选用哪一条规则进行归约—归约原则

4.2.2 算符优先分析法概述 算符优先文法 算符优先分析是一种分析过程比较迅速的自底向上的分析方法，特别有利于表达式的分析，便于手工实现。它不是一种严格的最左归约，即不是一种规范归约方法。在算符优先分析方法中，可归约串就是最左素短语。 所谓算符优先就是借鉴了程序语言中，表达式运算的不同优先顺序，在算符，即非终结符之间定义某种优先归约的关系，从而在句型中寻找可归约串。由于非终结符关系的定义和普通算术表达式的算符（如加减乘除）运算的优先关系一致，所以得名算符优先分析方法。 14

为了方便，假设文法中不含形如P的规则 优先关系 a≐b 表示a的优先级等于b的优先级 a⋖b 表示a的优先级小于b的优先级 a⋗b 表示a的优先级大于b的优先级 说明 为了方便，假设文法中不含形如P的规则 15

算符文法 如果某文法G中没有形如ABC的产生式，这里A, B, CVN，则成文法G为算符文法，也称OG文法。 16

优先关系定义 设文法G是不含产生式的算符文法，a, b是任意两个终结符，而A, B, CVN，则优先关系定义如下： a≐b 当且仅当G中存在产生式Aab或 AaBb a⋖b 当且仅当G中存在产生式AaB，且 Bb或BCb a⋗b 当且仅当G中存在产生式ABb，且 Ba或BaC + + + + 17

算符优先文法 如果一个算符文法G中的任何两个终结符a, b至多只满足下述三种关系之一： a≐b a⋖b a⋗b 则称文法G是一个算符优先文法，也称OPG文法。 18

例 考虑文法G[E]： EE+T|T TT*F|F F(E)|i 找出终结符间的优先关系矩阵。 19

FIRSTVT() P是文法G的任意一个非终结符号 FIRSTVT(P) FIRSTVT(P)的构造算法 = { a | P=+>a…或 P=+>Qa… } FIRSTVT(P)的构造算法 若P->a…或P->Qa…，则a属于FIRSTVT(P) 若a属于FIRSTVT(Q)，且P->Q…，则a属于FIRSTVT(P) 20

LASTVT() LASTVT(P) LASTVT(P)的构造算法 = { a | P=+>…a 或 P=+>…aQ } 若P->…a或P->…aQ，则a属于LASTVT(P) 若a属于LASTVT(Q)，且P->…Q，则a属于LASTVT(P) 21

算符优先关系表构造算法 P->..ab…或P->…aQb… P->…aR…，且b属于FIRSTVT(R) P->…Rb…，且a属于LASTVT(R) a>b 22

关于#的特别说明 文法开始符号S #S# 对于算符优先文法，#的优先级小于任何终结符；任何终结符的优先级大于#；#的优先级等于#。 #=# #<FIRSTVT(S) LASTVT(S)># 对于算符优先文法，#的优先级小于任何终结符；任何终结符的优先级大于#；#的优先级等于#。 由于仅对终结符定义优先关系，未对非终结符号定义算符优先关系，不能使用这些关系查找右单个非终结符号组成的句柄。 23

构造FIRSTVT() F->(E)|k T->T*F|F E->E+T|T FIRSTVT(F) = { (, k } FIRSTVT(T) = { * } U FIRSTVT(F) = { *, (, k } E->E+T|T FIRSTVT(E) = { + } U FIRSTVT(T) = { +, *, (, k } 24

构造LASTVT() F->(E)|k T->T*F|F E->E+T|T LASTVT(F) = { ), k } LASTVT(T) = { * } U LASTVT(F) = { *, ), k } E->E+T|T LASTVT(E) = { + } U LASTVT(T) = { +, *, ), k } 25

计算优先关系1 E -> E+T | T T -> T*F | F + < any of FIRSTVT(T) any of LASTVT(E) > + T -> T*F | F * < any of FIRSTVT(F) any of LASTVT(T) > * 26

计算优先关系2 F -> (E) | k #E# ( = ) ( < any of FIRSTVT(E) any of LASTVT(E) > ) #E# # = # # < any of FIRSTVT(E) any of LASTVT(E) > # 27

算符优先关系表 + * （ ） k # > < ( = ) 28

最左素短语 短语——回忆 素短语 最左素短语 若文法的开始符号为S，S=*>αAβ，A=+> γ 则称γ为句型αAβ的一个短语 至少含有一个终结符，并且不再含有更小的素短语 最左素短语 处于句型最左面的素短语 29

素短语举例 短语为：T+T*F+i、T+T*F、T*F，以及最左边的T和最右边的i 直接短语是：T、T*F、i 素短语为：T*F和 i。 E + T Z F i * 短语为：T+T*F+i、T+T*F、T*F，以及最左边的T和最右边的i 直接短语是：T、T*F、i 素短语为：T*F和 i。 T+T*F+i，T+T*F不是素短语，因为其中包含了素短语T*F。 T不是素短语，因为其中没有终结符号。 30

自底向上分析过程的每一步就是寻找句型的最左直接短语（句柄）或者最左素短语，把它们作为可归约串进行归约的。 算符优先分析是自底向上的语法分析方法，它在当前的句型中不断地寻找最左素短语并进行归约，直至把输入串扫描完毕并把分析栈归约成文法的开始符号。 那么，如何利用算符优先关系和分析栈来识别最左素短语并进行归约呢？ 短语 是一个产生式的右部 至少包含一个终结符 直接短语 素短语 最左 LR分析 句柄 最左素短语 算符优先分析 31

算符优先算法 “归约”素短语 最左子串法 由于算符优先文法不含两个连续的非终结符，故可以把括在两个#之间的句型的一般性是写成： #N1a1N2a2NnanNn+1an+1# 其中，ai都是终结符，Nj是非终结符(可有可无)。此时归约的是满足下列条件的最左子串： NjajNj+1aj+1NiaiNi+1 满足： aj-1⋖aj aj≐aj+1≐≐ai ai⋗ai+1 32

算符优先分析法的例子 对于上面的算符优先文法，句型i+(i+i)*i的识别过程如下： 步骤 句型 关系 最左素短语 归约符号 #i+(i+i)*i# #⋖i⋗+ i F #F+(i+i)*i# #⋖+⋖(⋖i⋗+ i F #F+(F+i)*i# #⋖+⋖(⋖+⋖i⋗) i F #F+(F+F)*i# #⋖+⋖(⋖+⋗) F+F E #F+(E)*i# #⋖+⋖(≐) (E) F #F+F*i# #⋖+⋖*⋖i⋗# i F #F+F*F# #⋖+⋖*⋗# F*F T #F+T# #⋖+⋗# F+T E #E# 接受 33

识别句型i+(i+i)*i得到的语法树 E + T * F ) ( i Z F Z + T * E i ) ( (a) 算符优先分析技术得到得到的语法树 (b) 一般分析技术得到得到的语法树 34

4.2.3 LR分析法的概念 LR(K)分析法的含义 L—自左向右扫描输入串(源程序) R—分析过程构成最右推导的逆序 K—每次根据当前的输入符号最多向前(右)查看K个符号就可以唯一地确定下一步动作是移进还是归约以及用哪条规则进行归约，因而也能唯一地确定句柄 35

LR(k)技术包含一组方法：LR(0)、SLR(1)、LR(1)和LALR(1)。 对LR(1)的一种改进叫做向前LR分析（简称LALR(1)，其中LA是向前look ahead的缩写），它在分析能力和构造工作方面都介于SLR(1)和LR(1)，即LALR(1)的使用范围比SLR(1)广泛，实现的工作量也相应地多。 36

LR分析器的逻辑结构 LR分析器组成： 分析表 总控程序 下推分析栈 a1a2an# 输入串(源程序) Sm xm xm-1 S2 x2 输出分 析结果   总控程序 分析表 ACTION GOTO 37

分析栈 符号栈 符号栈内存放分析过程中移进或归约的符号。 状态栈 状态栈存放的是状态(标记)，状态Si概括了栈中位于Si下面的全部信息，也就是记录分析过程从开始的某一归约阶段的整个分析历史或预测扫描可能遇到的分析符号。分析开始时，分析栈压入初始状态S0和输入符号#，分析器处于初始状态S0。S0刻画了当前栈内仅有一个符号#的事实并预示将扫描的输入字符应刚好是可作为句子首符号的那些符号。 38

分析表 动作表(ACTION) 状态转换表(GOTO) 39

ACTION表 ACTION表的结构如下： 终结符 状态 a1 a2  am S1 ACTION[S1, a1] ACTION[S1, am] S2 ACTION[S2, a1] ACTION[S2, a2] ACTION[S2, am] Sn ACTION[Sn, a1] ACTION[Sn, a2] ACTION[Sn, am]     40

分析动作 ACTION表中的元素ACTION[Sm, ai]是一个动作，表示当前状态Sm面临输入符号ai时所完成的分析动作。分析动作可分四类： 移进 归约 接受 出错 41

移进 此时ACTION[Sm, ai]=‘Sj’。分析动作为移进时，表示句柄尚未在分析栈的栈顶形成，正期待继续移进符号，以形成句柄。 ACTION[Sm, ai]=‘Sj’表示当前栈顶状态为Sm，输入符号为ai，应将输入符号ai移进分析栈的符号栈栈顶，同时将Sj移进分析栈的状态栈栈顶。 42

归约 此时ACTION[Sm, ai]=‘rj’。其中rj表示按文法的第j条规则(产生式)进行归约。设第j条规则为： AXm-r+1Xm-r+2 Xm 分析动作为归约时，表明当前分析栈顶部的符号串Xm-r+1Xm-r+2 Xm已是当前句型的句柄，需要立即进行归约。具体是将分析栈自顶向下的r个符号(包括状态栈内相应的状态)弹出，将A压入符号栈内，此时分析栈格局为： 下图所示 再以(Sm-r,A)查GOTO表，若GOTO[Sm-r, A]=Sk，把Sk压入状态栈。 43

输入串 a1a2ai an# A xm-r S2 x2 S1 x1 S0 # Sm-r xm-r S2 x2 S1 x1 S0 # 当符号栈顶形成句柄β时，把它规约成产生式A→β的左部A：设句柄β的长度为r，归约动作就是①把符号栈顶的r个符号删除，移进符号A；②把状态栈顶的r个状态删除，移进新的状态sj＝GOTO[si－m, A]。 44

接受 此时ACTION[Sm, ai]=‘acc’。分析动作接受表示当前输入的符号串分析成功，终止分析器工作。 45

出错 此时ACTION[Sm, ai]=‘error’(error表示出错，在此用空白来表示)。分析动作为出错，表示当前输入的符号串中有语法错误，调用相应的出错处理程序。 46

GOTO表 GOTO表的结构如下： 非终结符 状态 X1 X2  Xm S1 GOTO[S1, X1] GOTO[S1, X2] GOTO[S1, Xm] S2 GOTO[S2, X1] GOTO[S2, X2] GOTO[S2, Xm] Sn GOTO[Sn, X1] GOTO[Sn, X2] GOTO[Sn, Xm]     47

状态转换 GOTO表中的元素GOTO[Sm, Xi]是一个状态，表示当前状态Sm面临输入符号Xi时需转移的下一个状态。 48

总控程序 总控程序是LR分析的实现算法。描述如下： 初始化，将初始状态S0及输入符号串的左界符#推入分析栈； 从输入串中读入当前的输入符号ai，根据当前状态栈栈顶状态Sm与输入符号ai查ACTION表： 若ACTION[Sm, ai]=‘Sj’，完成移进动作； 若ACTION[Sm, ai]=‘rj’，以文法的第j条规则完成归约动作； 若ACTION[Sm, ai]=‘acc’，分析成功，结束； 若ACTION[Sm, ai]=‘error’，出错处理。 重复2)直到出错或接受为止。 49

接受时分析栈的格局 a1a2ai an# 输入串 S1 Z S0 # 50

例1 文法G5.4 （1）S → aAcBe （2）A → b （3）A → Ab （4）B → d LR分析表如表 LR分析表的例子如表5.9，其中ACTION部分的记号的含义如下： si 把下一个状态si和当前符号a移进栈； rj 按照第j个产生式进行归约； acc 接受输入串； 空白 出错标志，调用错误处理子程序。 GOTO部分中的数字表示状态，空白表示出错。 状 态 ACTION GOTO a b c d e $ S A B s2 1 acc 2 s4 3 s6 s5 4 r2 5 s8 7 6 r3 S9 8 r4 9 r1

文法G5.4 （1）S → aAcBe （2）A → b （3）A → Ab （4）B → d LR分析表如表5.9所示，给出了 状 态 ACTION GOTO a b c d e $ S A B s2 1 acc 2 s4 3 s6 s5 4 r2 5 s8 7 6 r3 S9 8 r4 9 r1 文法G5.4 （1）S → aAcBe （2）A → b （3）A → Ab （4）B → d LR分析表如表5.9所示，给出了 输入串abbcde的分析过程 步骤 状态栈 符号栈 输入串 ACTION GOTO 1 $ abbcde$ s2 2 02 $a bbcde$ s4 3 024 $ab bcde$ r2 4 023 $aA s6 5 0236 $aAb cde$ r3 6 s5 7 0235 $aAc de$ s8 8 02358 $aAcd e$ r4 9 02357 $aAcB s9 10 023579 $aAcBe r1 11 01 $S acc

其LR分析表如下页，分析输入串i*i+i 例2 例：文法G[E] (1)E::=E+T (2)E::=T (3)T ::=T*F (4)T::=F (5)F::=(E) (6)F::=i 其LR分析表如下页，分析输入串i*i+i 53 53

i + * ( ) # E T F ACTION表 GOTO表 0(S0) 3 1(S1) 2(S2) 3(S3) 4(S4) 5(S5) 文法符号 状态 i + * ( ) # E T F 0(S0) S5 S4 1 2 3 1(S1) S6 ACCEPT 2(S2) R2 S7 3(S3) R4 4(S4) 8 5(S5) R6 6(S6) 9 7(S7) 10 8(S8) S11 9(S9) R1 10(S10) R3 11(S11) R5 文法G[E] ：(1)E::=E+T (2)E::=T (3)T ::=T*F (4)T::=F (5)F::=(E) (6)F::=i 54

LR分析表说明 sj 把下一个状态j和当前输入符号a进栈 rj 按第j个产生式归约 acc 接受 空格 出错标志，报错 55

Vn Vt GOTO表 ACTION表 状态 E T F i + * ( ) 0(S0) 1 2 3 5 4 1(S1) 6 2(S2) 7 文法符号 E T F i + * ( ) 状态 0(S0) 1 2 3 5 4 1(S1) 6 2(S2) 7 3(S3) 4(S4) 8 2 3 5 4 5(S5) 6(S6) 9 3 5 4 7(S7) 10 5 4 8(S8) 6 11 9(S9) 7 状态 10(S10) 若移入：i为状态 若规约：i为产生式编号 11(S11) 文法G[E] ：(1)E->E+T (2)E->T (3)T ->T*F (4)T->F (5)F-> (E) (6)F->i 56 56

文法G[E] (1)E::=E+T (2)E::=T (3)T ::=T*F (4)T::=F (5)F::=(E) (6)F::=i 分析过程 ： i*i+i 步骤 状态栈 符号 输入串 动作 1 ＃0 ＃ i*i+i# 初始化 2 ＃0i5 ＃i *i+i# S 3 ＃0F3 ＃F *i+i# R6 4 ＃0T2 ＃T *i+i# R4 5 ＃0T2*7 ＃T* i+i# S 6 ＃0T2*7i5 ＃T*i +i# S 7 ＃0T2*7F10 ＃T*F +i# R6 57 57

文法G[E] (1)E::=E+T (2)E::=T (3)T ::=T*F (4)T::=F (5)F::=(E) (6)F::=i 分析过程 ： i*i+i 8 ＃0T2 #T +i# R3 9 ＃0E1 #E +i# R2 10 ＃0E1+6 #E+ i# S 11 ＃0E1+6i5 #E+i # S 12 ＃0E1+6F3 #E+F # R6 13 ＃0E1+6T9 #E+T # R4 14 ＃0E1 #E # R1 15 #E Accept 58

(1) 每次规约总是规约当前句型的句柄，是规范归约，可以看到语法树(算符优先是规约最左素短语) 由分析过程可以看到: E T + * F i 8 7 5 6 4 3 2 1 (1) 每次规约总是规约当前句型的句柄，是规范归约，可以看到语法树(算符优先是规约最左素短语) (2) 分析的每一步栈内符号串与输入串的剩余部分构成规范句型。 59 59

LR分析方法概述 LR方法的实际分析过程并不是去直接分析文法符号栈中的符号是否形成句柄，但它给我们一个启示：我们可以把终结符和非终结符都看成一个有限状态机的输入符号，把每一个符号进栈看成已经识别过了该符号，当识别到可归前缀时，相当在栈顶形成句柄，则认为达到了识别句柄的终态。 LR分析方法的基本原理 把每个句柄（某个产生式的右部）的识别过程划分为若干状态，每个状态从左到右识别句柄中的一个符号，若干状态就可以识别句柄左端的一部分符号。 识别了句柄的这一部分就相当于识别了当前规范句型的左部分，称为活前缀。因此，对句柄的识别就变成了对规范句型活前缀的识别。 LR分析程序实际上就是利用有限自动机来识别给定文法的所有规范句型的活前缀。 60

LR分析方法概述 定义：一个符号串的前缀是指该串的任意部分。一个规范句型的前缀若不含句柄之后的任何符号就称为活前缀。 例如，对于输入串abbcde，其规范推导过程为 S aAcBe aAcde aAbcde abbcde 每个句型都是规范句型。这个过程的逆过程就是归约过程，即从输入串abbcde归约到文法的开始符号S。 我们分析其中的一个规范句型aAbcde，它的句柄是Ab（最左直接短语），前缀有aAbcde，aAbcd，aAbc，aAb，aA，a以及空字符串，活前缀是aAb，在它后面添上终结符串cde就是规范句型。 61

LR分析方法概述 对于一个文法G，可以构造一个识别所有活前缀的有限自动机，在此基础上，可以把这种自动机转变成LR分析表。 在上述LR分析过程的第5步，符号栈就是活前缀aAb，把句柄Ab归约后就得到另外一个规范句型aAcde，它的活前缀是aAcd。因此，在LR分析过程中的符号栈顶的符号串，或者输入串的已扫描过部分保持可规约成一个活前缀，就意味着所扫描过的输入串部分没有错误。 对于一个文法G，可以构造一个识别所有活前缀的有限自动机，在此基础上，可以把这种自动机转变成LR分析表。 62

LR(0)分析表的构造 定义：如果P → αβ是文法G的一个规则，其中α或β可为空串，则称P → α·β是文法G的一个LR(0)项，简称项。 空产生式P 只有一个LR(0)项P →·。 例如，对于产生式E→E+T，有四个LR(0)项，即E→·E+T，E→E·+T，E→E+·T以及E→E+T·。 圆点在产生式最右端的项目称为归约项，如E→E+T· 圆点后面是终结符的项目称为移进项，如E→E·+T 圆点后面是非终结符的项目称为待约项，如E→E+·T 63

LR(0)分析表的构造 LR(0)项指明了在识别过程中以某个非终结符为目标时，某时刻已进行归约到相应规则右部的多大部分。 移进项目表示需要把当前符号，即圆点之后的终结符移进分析栈； 归约项目表示需要把当前句柄，即圆点之前的符号串归约成产生式的左部符号，特别是对于初始项，则表示句子分析成功； 待约项目表示需要把当前符号，即圆点之后的非终结首先归约之后才能和圆点之前的符号串构成可以归约的句柄。 64

LR(0)分析表的构造 定义：设P → α·Xβ是文法G的一个LR(0)项，其中X是G的任意符号，则称P → αX·β是其后继项，X是其后继符号。 直观上看，后继项是把项中圆点右移一个符号位置所得的项。从句型识别的角度看这是显然的：当扫描过的输入符号已与产生式右部的α匹配时，后继的输入符号应该期望与产生式右部后继的符号X项匹配。 为了构造识别文法G的所有活前缀的有限自动机，需要介绍两个集合函数： 项集I的闭包CLOSURE(I)和状态转换函数GO(I, X) 文法G的LR(0)项的集合称为LR(0)项集，简称项集。 65

LR(0)分析表的构造 项集I的闭包CLOSURE(I)是一个项集，计算如下 （1）I中任何项也属于CLOSURE(I)； （2）若A→α·Bβ属于CLOSURE(I)并且B→γ是G的一个产生式，项B→·γ也加到CLOSURE(I)中。 （3）反复使用上述两条规则，直到CLOSURE(I)不再变化为止。 直观上，CLOSURE(I)中的项A→α·Bβ是指：在分析过程的某一时刻，希望看到可以从Bβ归约的符号； 若B→γ也是产生式，那么在同一时刻，当然也希望看到可以从γ归约的符号。因此，也把B→·γ加到CLOSURE(I)中。 66

LR(0)分析表的构造 例如，文法G5.4 （1）S → aAcBe （2）A → b （3）A → Ab （4）B → d 中I={ S → a·AcBe }的闭包 即CLOSURE({ S → a·AcBe })。 根据规则（1）: CLOSURE({ S → a·AcBe })＝{S → a·AcBe}； 根据规则（2）: 检查所有以A为左部的产生式，有 A → b和A → Ab， 则把项目A →·b和A →·Ab加入到 CLOSURE({ S → a·AcBe })中，得 CLOSURE({S → a·AcBe }) ＝{S → a·AcBe，A →·b，A →·Ab}。 67

LR(0)分析表的构造 状态转换函数GO(I, X)的第一个参数I是一个LR(0)项集，第二个参数X是后继符号，它的计算公式为 GO(I, X)=CLOSURE ({所有形如A →αX·β的项 | 项A →α·XβI}) 直观上，若I是某个活前缀γ有效的项集，那么 GO(I, X)就是活前缀γX有效的项集。 例如，对于例5.9，如果I={ S →·aAcBe }，则 GO(I, a) = {S →·aAcBe, A →·b，A →·Ab}。 68

LR(0)分析表的构造 若文法有若干个以开始符号S在左部的产生式，则初始项就不唯一。为此，引进增广文法G’[S’]，即增添一个G中没有出现过的非终结符S’和一个新的产生式S’ → S，从而使得G’[S’]只有一个初始项S’ → S 。 如果把一个文法G的LR(0)项集规范族的每个项集当作一个状态，把GO函数看作是状态之间的转换函数，这样构成了可以识别文法G中所有活前缀的有限状态机，它的初始状态就是包含G’中初始项的状态。 69

LR(0)分析表的构造 识别文法G活前缀的DFA的LR(0)项集规范族按照下列规则构造： （1）令C＝{CLOSURE({S’ →·S})} （2）把C中每一个LR(0)项集I应用转换函数GO(I, X)得到新的项集J，并把J加入到C中； （3）重复步骤（2）直到C不再增大为止。 这样就可以得到一个识别文法G的活前缀的DFA： 状态就是C中的每个LR(0)项集； 状态转换函数就是GO； 包含唯一初始项S’ → S·的LR(0)项集就是初始状态。 70

LR(0)分析表的构造 例 构造识别文法G5.5所有活前缀的DFA。 S → A | B A → aAb | c B → aBb | d 首先把它改造成等价的增广文法G’[S’] （0）S’ → S （1）S → A （2）S →B （3）A → aAb （4）A →c （5）B → aBb （6）B → aBb 其次，按照DFA的构造方法计算 I0 = CLOSURE（{S’ → S}），得 I0： S’ →  S S →  A A →  aAb A →  c S →  B B →  aBb B →  d 71

LR(0)分析表的构造 I0 = CLOSURE（{S’ → S}），得 I0： S’ →  S S →  A A →  aAb A →  c S →  B B →  aBb B →  d LR(0)分析表的构造 构造识别文法G5.5所有活前缀的DFA。 通过考察I0中每个项中圆点后面的第一个符号X可知： X = {S, A, B, a, c, d} 利用GO(I0,X)可以求得I0的后继项集如下： I1= GO(I0, S)=CLOSURE({S’ → S })= {S’ → S·} I2： S →A· I3： S →B· I4= GO(I0, a)=CLOSURE({A →a·Ab, B → a·Bb})，计算可得 I4： A → a·Ab A →·aAb A →·c B → a·Bb B →·aBb B →·d I5： A → c· I6： B → d· 72

LR(0)分析表的构造 构造识别文法G5.5所有活前缀的DFA。 新的项集中只有I4有后继项集，而且X = {A, B, a, c, d}，于是 I7= GO(I4, A)=CLOSURE({A → aA·b })={A → aA·b} I8= GO(I4, B)=CLOSURE({B → aB·b })={A → aB·b} 而GO(I4, a)=CLOSURE({A →a·Ab, B → a·Bb})= I4 GO(I4, c)=CLOSURE({A → c·})= I5 GO(I4, d)=CLOSURE({B → d·})= I6 最后，求I7和I8的后继项集，分别为 I9= GO(I7, b)=CLOSURE({A → aAb·})={ A → aAb·} I10= GO(I8, b)=CLOSURE({A → aBb·})={ A → aBb·} 由于I9和I10没有后继项集，这样就结束了计算文法G’5.5项集规范族C＝{I0, I1..., I10}， 73

LR(0)分析表的构造 若把其中的项集看作状态，根据GO(I, X)就得到识别文法G’5.5所有活前缀的DFA，如图5.5所示。其中每一个状态都是终态，由于I0包含了唯一的初始项，因而I0也是这个DFA的初态。把从初态I0出发，到达某一状态所经过的全部有向弧上的标记符号依次连接起来，就得到该DFA在到达该状态时所识别的某一个规范句型的一个活前缀。例如，状态5识别的活前缀是c，状态1识别的活前缀是S I0： S’ →·S S →·AA →·aAb A →·c S→·B B →·aBb B →·d S I1：S’ → S· A I2：S→ A· I9：A → aAb· B b I3：S→ B· A a I7：A → aA·b I4 ： A → a·Ab A →·aAb A →·c B → a·Bb B →·aBb B →·d c c I8：B → aB·b d B I5：A→ c· b d I10：B → aBb· I6：B→ d· a 74

LR(0)分析表的构造 设C={I0，I1，，In}，每个项目集Ik的下标k作为分析表的状态。则 若GO(Ik, a)=Ij，且项目AaIk (aVT)，则置ACTION[k , a]=Sj； 若GO(Ik, A)=Ij(AVN)，则置GOTO[k, A]=j； 若AIk，则对所有终结符号a和#置GOTO[k, a]=rj和GOTO[k, #]=rj (其中A是文法的第j条规则) 。 若SSIk，则置ACTION[k , #]=acc； 表中空白处置出错标志。 如此构造的分析表叫做LR(0)分析表， 使用LR(0)分析表的语法分析器叫做LR(0)分析器。 75

LR(0)分析表的构造 表5.11 文法G5.5的LR（0）分析表 状 态 ACTION GOTO a b c d $ S A B s4 s4 s5 s6 1 2 3 acc r1 r4 4 7 8 5 r3 6 r6 s9 s10 9 r2 10 r5 76

LR(0)分析表的构造 总结LR(0)分析表的构造步骤如下： （1）写出给定文法G的的增广文法G’； （2）构造G’的LR(0)项集，并根据CLOSURE和GO函数构造G’的项集规范族； （3）构造识别G’的活前缀的DFA； （4）按照算法5.3完成G’的LR(0)分析表。 77

LR(0)分析表的构造 实际上，可以无需先构造文法G的项集规范族，再构造出识别其活前缀的DFA，而可以从CLOSURE和GO函数递增地直接构造出DFA。 如果把DFA看作一个有向图，那么，项集就可以看作该图的结点，有向边就是一个状态转移，即从状态Ii到经过文法的一个符号X到达状态Ij，其中，X是状态Ii表示的项集中项的一个后继符号，而 Ij＝GO(Ii, X)。 只要有一个起始结点，就可以递增地通过GO与CLOSURE函数增加新的状态（结点）和有向边，直到不再增加结点或边为止，这样就完成了DFA的构造。 DFA的这种构造方式可以依据图的深度优先搜索实现，也可以依据图的广度优先搜索来实现。 78

例 设文法G[S]： SA AaA|b 计算G[S]的LR(0)项目集规范族。 79

I0=closure({SA})={SA, AaA, Ab} GO(I0, a)=closure({AaA})={AaA, AaA, Ab}=I1 GO(I0, b)=closure({Ab})={Ab}=I2 GO(I0, A)=closure({SA})={SA}=I3 GO(I1, a)=closure({A a A})=I1 GO(I1, b)=closure({Ab})={Ab}=I2 GO(I1, A)=closure({Aa A  })={AaA}=I4 由于I2，I3 和I4都是归约项目，则G[S]的LR(0)项目集规范族C={I0，I1，I2，I3，I4}。 80

识别文法G[S]的活前缀的DFA I3 A SA I0 I2 SA b AaA Ab Ab I1 I4 AaA 81

G[S]的LR(0)分析表 状 态 ACTION GOTO a b # A S1 S2 3 1 4 2 r2 acc r1 82

例：设拓广文法G[S]的产生式为： S  S S  aA | bB A  cA | d B  cB | d LR(0)项目集规范族 I0: S.S S.aA S.bB I1: (I0,S) SS. I2: (I0,a) Sa.A A.cA A.d I3: (I0,b) Sb.B B.cB B.d I4: (I2,c) (I4,c) Ac.A I5: (I3,c) (I5,c) Bc.B I6: (I2,A) SaA. I7: (I3,B) SbB. I8: (I4,A) AcA. I9: (I5,B) BcB. I10: (I4,d) Ad. I11: (I3,d) Bd. 83

Ac.A A.cA A.d I4 识别文法 活前缀的DFA A AcA. I8 c d Ad. I10 c d Sa.A S.S S.aA S.bB I0 start S SS. I1 B Sb.B B.cB B.d I3 SbB. I7 b d Bd. I11 c d Bc.B B.cB B.d I5 c B BcB. I9 84

LR(0)分析表 85

续例：已知文法G：S→E E→aA | bB A→cA | d B→cB | d G的所有LR(0)项目为： [1] S→·E [2] S→E· [3] E→·aA [4] E→a·A [5] E→a A· [6] E→·bB [7] E→b·B [8] E→bB· [9] A→·cA [10] A→c·A [11] A→cA· [12] A→·d [13] A→d· [14] B→·cB [15] B→c·B [16] B→cB· [17] B→·d [18] B→d· I0=closure({S→·E })={ S→·E, E→·aA , E→·bB }； GO(I0, E)={ S→E·}= I1； GO(I0, a)={ E→a·A , A→·cA, A→·d }= I2； GO(I0, b)={ E→b·B , B→·cB, B→·d }= I3； GO(I2, A)={ E→a A·}= I4； GO(I2, c)={ A→c·A , A→·cA, A→·d }= I5； GO(I2, d)={ A→d·}= I6； GO(I3, B)={ E→bB·}= I7； GO(I3, c)= { B→c·B , B→·cB, B→·d }= I8； GO(I3, d)= { B→d·}= I9； GO(I5, A)={ A→cA·}= I10； GO(I5, c)= { A→c·A , A→·cA, A→·d }= I5； GO(I5, d)= { A→d·}= I6； GO(I8, B)= { B→c B·}= I11； GO(I8, c)= { B→c·B , B→·cB, B→·d }= I8； GO(I8, d)= { B→d·}= I9。 则该文法的LR(0)项目集规范族 C={ I0, I1, I2, I3, I4, I5, I6, I7, I8, I9, I10, I11}。 该文法的LR(0)分析表为： 状态 ACTION GOTO a b c d # E A B S2 S3 1 acc 2 S5 S6 4 3 S8 S9 7 r2 5 10 6 r5 r3 8 11 9 r7 r4 r6

SLR分析表的构造 我们以一个简单的变量声明作为例子来分析冲突问题和解决方法。设整型变量的声明的文法G5.6为 <整型变量声明>→ integer <标识符表> <标识符表> → <标识符表>, v | v 将它缩写后并增广如下： (0) D’ → D (1) D → i L (2) L → L, v (3) L → v 87

SLR分析表的构造 从I0=CLOSURE({R’ → R })出发构造DFA，结果如下图。 分析状态I3可以发现，它包含了归约项D→ i L·和移进项L → L·,v。 依据LR(0)的分析方式，在该状态，不论面临什么输入符号，特别是包括符号逗号“，”都要把i L规约成D；但是，按照移进项L → L·,v则在面临符号“，”时，应该把它移入符号栈，同时转到状态5。 这样，对于ACTION[3, ,]就会有r1和s5两个动作，出现移进－归约冲突，控制程序将不知所措。 I1：D’→ D· I3：D→ i L  L → L·,v I5：L → L,·v I6：L → L, v· ，， v D L I0：D’ →·D D →·iL i I2：D → i·L L →·L,v L →·v v I4：L → v· 88

SLR分析表的构造 对冲突情况有两种解决途径：修改文法，或者对分析方法加以改进。显然，修改文法G5.6以适应LR(0)分析并不可取，更好的措施是改善分析技术，以适应更广泛、实用的文法。 在这种情况下，我们只需考察把句柄iL归约成D时，D之后的跟随符号集是否包含当前所有移进项中移进符号（“，”），如果不包含这样就可以解决这种移进－归约冲突。 例子中FOLLOW(D)={$}，而状态3中移进符号的集合是{,}，所以，在面临输入符号是“$”时，就执行归约，即ACTION[3,$]= r1，在面临输入符号是“,”时，就执行移进操作，即ACTION[3,,]= s5。这种处理冲突的方法只需要对LR(0)分析表简单地进行改动，称作简单LR(0)分析，SLR(1)。 89

SLR分析表的构造 一般，设LR(0)项集规范族的某个项集I含有m个移进项 A1 →α·a1β1 ...... Am →α·amβm 和n个归约项 B1 → γ1· Bn → γn· 若集合{a1,..., am}和FOLLOW(B1),......, FOLLOW(Bn)两两不相交，那么， 隐含在项集I中冲突可以根据当前输入符号a唯一地确定动作，解决冲突： （1）若a{a1,..., ai}，则移进； （2）若a FOLLOW(Bi)，i=1,2,...,m，则用Bi → γi进行归约； （3）否则，报错。 90

SLR分析表的构造 如果一个文法项集中的所有冲突性动作的都可以按这种方法解决，这样的文法称作SLR(1)文法，由此构造的分析表叫做SLR(1)分析表，使用SLR(1)分析表的分析器叫做SLR(1)分析器。 SLR(1)分析表的构造步骤和LR(0)分析表的构造类似，只须在完成DFA以后按照SLR(1)方法解决可能的冲突。类似地，完成SLR(1)分析表的算法也有两种，而且只需对算法5.3A和5.3B做简单修改即可。 91

SLR分析表的构造 从DFA构造SLR(1)分析表的算法5.5A： (1) 修改算法5.3A第（4）句中 for每个a  VT do { ACTION[k, a] = rj}为 for每个a  FOLLOW(A) do { ACTION[k, a] = rj} (2) 其它不变。 从文法G的项集规范族和状态转换函数构造SLR(1)分析表的算法5.5B： (1) 把算法5.3B第（2）条规则“对于任何终结符a（包括$），置ACTION[k, a] = rj”修改为 “对任何属于FOLLOW(A)的a，置ACTION[k, a] = rj” 92

SLR分析表的构造 按照上述算法构造出文法5.6的SLR(1)分析表如表5.12。其中FOLLOW(D)=FOLLOW(D’)={$}，FOLLOW(L)={,，$}。 表5.12 文法G5.6的SLR（1）分析表 状态 ACTION GOTO i , v $ D L s2 1 acc 2 s4 3 s5 r1 4 r3 5 s6 6 r2 93

SLR分析法 文法G 构造G[A]的拓广文法G[S] A->aA A->a|b (0) S->A (1) A->aA 94

A # S->A.# acc S->.A A->.aA A->.b A->.a b A->b. b a 移进还是归约？ a 95

A # S->A.# (1) acc S->.A A->.aA A->.b A->.a (0) b LR(0)分析表 A->b. (2) 状态 a b # A s3 s2 1 acc 2 r2 3 冲突 r3 4 r1 b a A->a.A A->.aA A->.b A->a. (3) A A->aA. (4) a 96

问题分析 问题：存在移进/归约冲突 分析：实际上，A仅在遇到FOLLOW(A)中的元素时，才应当进行归约，否则是出错的。 移进或归约的动作就可以唯一确定。 解决方法——SLR： b属于FOLLOW(A)时，ACTION[A,b]为归约 97

A # S->A.# (1) acc S->.A# A->.aA A->.b A->.a (0) b SLR分析表 b a 状态 a b # A s3 s2 1 acc 2 r2 3 r3 4 r1 A->a.A A->.aA A->.b A->a. (3) A A->aA. (4) a 98

小结 自顶向下分析法 自底向上分析法 递归下降分析 预测分析 LL(1)分析表构造 简单优先分析法 算符优先分析法 LR(0)分析法 SLR分析法 99

第四章 语法分析小结 自顶向上分析法 Z S + S∈L[Z] 语法分析方法: 自顶向上分析法 SZ + (一) 自顶向下分析 1 第四章 语法分析小结 自顶向上分析法 Z S + S∈L[Z] 语法分析方法: 自顶向上分析法 SZ + (一) 自顶向下分析 1 概述自顶向下分析的一般过程 存在问题 左递归问题 回溯问题 消除左递归的方法 无回溯的条件 改写文法 超前扫描 100 100

两种常用方法: 2 a)改写文法,消除作递归,回溯 (1)递归子程序法 b)写递归子程序 LL(1)分析器的逻辑结构及工作过程 1.构造First集合的算法 2.构造Follow\select集合的算法 3.构造分析表的算法 101 101

(二) 自底向上分析 规约过程: (1)一般过程: 移进—规约过程 问题:如何寻找句柄 (2)算法: i)算符优先分析法: (1)一般过程: 移进—规约过程 问题:如何寻找句柄 (2)算法: i)算符优先分析法: 1.分析器的构造,分析过程. 根据算符优先关系矩阵来决定 是移进还是规约. ii)LR分析法 102 102

1.概述----概念、术语 (活前缀、项目) 状态栈 GOTO表 1)逻辑结构 分析表 分析动作表 控制程序 2.LR分析 2)分析过程 1.概述----概念、术语 (活前缀、项目) 状态栈 GOTO表 1)逻辑结构 分析表 分析动作表 控制程序 2.LR分析 2)分析过程 1)构造DFA 3.如何构造LR(0)分析表 2)由DFA构造分析表 103 103

分析表 LL(1)分析表 非终结符 符号栈 αi A A::=αi error αi 除了递归子程序法，其他几种方法逻辑结构很象： 输入串 符号栈(状态栈) 控制程序 分析表 (1)对于LL(1)分析法 终结符 LL(1)分析表 非终结符 符号栈 αi A A::=αi error αi (自顶向下，保证最左推导) 首字符 104 104

栈外终结符 栈内终结符 < > = error (2)对于算法优先分析: 符号栈 栈内终结符 < > = error (3)LR分析: 分析表 状态转移GOTO表 分析动作表 符号栈 S0,S1…Sm #X0,X1…Xm 105 105

符号 状态 下一状态 终结符号 状态 规约(rj) GOTO表 状态 下一状态 根据栈顶状态和栈 顶符号推导出下一 状态 终结符号 分析动作表 状态 移进S 规约(rj) 根据栈顶状态和输入 符号推导出下一动作 106 106

作业2008 第二章作业4、作业５的第３个问。 构造各 非终结符的FIRSTVT和LASTVT集合 3 已知文法G[A]： A->(A)|a，给出G的所有LR(0)项目 ， 构造该文法的LR(0)项目集规范族 ，构造该文法的LR(0)分析表 。 4 已知文法G[S]： S->BB，B->aB|b给出G的所有LR(0)项目 ， 构造该文法的LR(0)项目集规范族 ，构造该文法的LR(0)分析表。 5 求文法G[S] S->aBc | bAB A-> aAb | b B-> b | ε 构造其LL(1)分析表，并分析符号串baabbb是否该文法的句子　 6 给出文法E->E+T T->T*F|F F->(E)|i 找出算符优先级 107

本章要求熟练掌握 LL(1)文法，包括构造first follow select集、预测分析表的构造及证明是LL(1)文法及对输入串的分析　　　消除消除左递归 掌握算符优先算　求FIRSTVT和LASTVT及算符优先表并对输入串进行判断 LR(0)分析表的构造及对输入串进行分析 108