编译原理第6章-自底向上语法分析

1、编译原理 自底向上自底向上（Bottom-Up）语法分析语法分析 第六讲第六讲 编译原理 移进移进 归约分析归约分析 LR 分析分析 自底向上语法分自底向上语法分 析析 自底向上分析思想自底向上分析思想 二义文法在二义文法在LR 分析中的应用分析中的应用 LR 分析中的出错处理分析中的出错处理 LR(K)文法（选讲）文法（选讲） 几几类分析文法之间的类分析文法之间的关系（选讲）关系（选讲） 编译原理 自底向上分析思想自底向上分析思想 核心核心问题：识别问题：识别（recognition）与与解析解析（parsing） 对任意对任意上下文无关文法上下文无关文法G = (V ，T ，P，S ) 和

2、任意和任意w T *，是否有，是否有w L(G)？ 若成立，若成立， 则给出分析树或（最左则给出分析树或（最左/右）推导步骤；否右）推导步骤；否 则，进行报错处理。则，进行报错处理。 两种实现途径两种实现途径 自顶向下（自顶向下（top-down）分析）分析 自底向上自底向上（bottom-up）分析分析 语法分析语法分析 编译原理 从所要分析的终结符串开始从所要分析的终结符串开始进行归约；进行归约； 每一步归约每一步归约是在当前串中找到与某个产生式是在当前串中找到与某个产生式 的右部相匹配的子串，然后将该子串用这一的右部相匹配的子串，然后将该子串用这一 产生式的左部非终结符进行替换；如果找不

3、产生式的左部非终结符进行替换；如果找不 到这样的子串，则回退到上一步归约前的状到这样的子串，则回退到上一步归约前的状 态，选择不同的子串或不同的产生式重试；态，选择不同的子串或不同的产生式重试； 重复上一步骤，直到重复上一步骤，直到归约至文法开始符号归约至文法开始符号； 如果不存在任何一个这样的归约，则表明该如果不存在任何一个这样的归约，则表明该 终结符串存在语法错误终结符串存在语法错误 自底向上分析的一般过程自底向上分析的一般过程 自底向上分析思想自底向上分析思想 编译原理 自底向上分析举例自底向上分析举例 aaab （A ） aaaAb （A aA） aaAb （A aA） aAb （B

4、b） aAB （A aA） AB （S AB） S 文法文法 G（S）: S AB A aA | B b | bB 单词序列单词序列 aaab 的一个自底向上分析过程的一个自底向上分析过程 自底向上分析思想自底向上分析思想 编译原理 在每一步归约中，选择哪一个产生式以及匹配在每一步归约中，选择哪一个产生式以及匹配 哪一个位置上的子串都可能是非确定的哪一个位置上的子串都可能是非确定的 这些非确定性导致分析过程会有很高的复杂性这些非确定性导致分析过程会有很高的复杂性 自底向上分析中的非确定性自底向上分析中的非确定性 自底向上分析思想自底向上分析思想 编译原理 改进的方法改进的方法 自底向上分析思想

5、自底向上分析思想 选择选择“可归约串可归约串”进行归约进行归约 在实用的自底向上分析中，总是选择某个在实用的自底向上分析中，总是选择某个“可可 归约串归约串”进行归约，可大大减少回溯进行归约，可大大减少回溯 对于一个句型而言，对于一个句型而言，“可归约串可归约串” 一定是该句一定是该句 型的型的短语短语 对于文法对于文法GS ，若，若 S A且且 A ， 则称则称是句型是句型相对于非终结符相对于非终结符A的短语的短语 + 编译原理 举例：举例：短语短语 文法文法 G（S）: （1）S AB （2）A aA （3）A （4）B b （5）B bB 对于右边的文法对于右边的文法G(S), , 句子

6、句子 aaab 的短语有：的短语有： ：aaab； a：aaab； aa：aaab； aaa：aaab； aaab：aaab b：aaab 句型句型aaAb的短语有：的短语有： aA：aaAb； aaA：aaAb； aaAb：aaAb b：aaAb 自底向上分析思想自底向上分析思想 Aa AB S b Aa Aa 编译原理 直接短语直接短语 自底向上分析思想自底向上分析思想 对于文法对于文法 G = (VN, VT, P , S ) ，以及以及 , , (VN VT)* 若若 S A且且 A ，则称，则称 是句型是句型相对于非终结符相对于非终结符A的直接短语的直接短语 直接短语的作用直接短语的

7、作用 作为当前句型的一步作为当前句型的一步“可归约串可归约串” 编译原理 举例举例：直接短语直接短语 自底向上分析思想自底向上分析思想 文法文法 G（S）: （1）S AB （2）A aA （3）A （4）B b （5）B bB 对于右边的文法对于右边的文法G(S) 句子句子 aaab 的直接短语的直接短语有：有： ：aaab； b：aaab 句型句型aaAb的直接短语的直接短语有：有： aA：aaAb； b：aaAb Aa AB S b Aa Aa 编译原理 句柄句柄 自底向上分析思想自底向上分析思想 rm 对于文法对于文法 G = (VN, VT, P , S ) , 以及以及 , (VN

8、 VT)* , w VT* 若若 S Aw 且且 A ，则称，则称 是右句型是右句型w 相对于非终结符相对于非终结符 A 的句炳的句炳 句柄的作用句柄的作用 当前句型从左到右最先出现的当前句型从左到右最先出现的“一步可归约串一步可归约串” 编译原理 举例举例：句柄句柄 自底向上分析思想自底向上分析思想 文法文法 G（S）: （1）S AB （2）A aA （3）A （4）B b （5）B bB 对于右边的文法对于右边的文法G(S), , 句子句子 aaab 的直接短语的直接短语有：有： ：aaab； b：aaab aaab 的句柄的句柄： 右句型右句型aaAb的直接短语的直接短语有：有： aA

9、：aaAb； b：aaAb aaAb 的句柄的句柄：aA aaabaaaAb aaAb ABS aAb Ab rm rm rm rm rm rm 编译原理 举例举例：句柄不一定唯一句柄不一定唯一 自底向上分析思想自底向上分析思想 对于右边的文法对于右边的文法G(S), , 句子句子 aaab 的直接短语的直接短语有：有： ：aaab； b：aaab aaab 的句柄的句柄： 右句型右句型aaAb的直接短语的直接短语有：有： aA：aaAb； aaA：aaAb； b：aaAb aaAb 的句柄的句柄：aA，aaA 文法文法 G（S）: （1）S AB （2）A aA （3）A aaA （4）A

10、（5）B b （6）B bB 不唯一的原因：不唯一的原因： G（S）是二义是二义 文法，右句型的文法，右句型的 最右推导有多个最右推导有多个 编译原理 举例举例: : 最右推导与最左归约最右推导与最左归约 自底向上分析思想自底向上分析思想 G(S): S (L) | a L L,S | S 编译原理 自底向上分析的实现技术自底向上分析的实现技术 自底向上分析思想自底向上分析思想 移进移进 归约归约（shift-reduce）分析技术）分析技术 LR分析分析和和算符优先分析算符优先分析（参见清华教材第（参见清华教材第 6 章）采用章）采用 移进移进 归约分析技术归约分析技术 编译原理 与自顶向下

11、技术相比与自顶向下技术相比 自底向上分析思想自底向上分析思想 功能较强大功能较强大 原因在于原因在于推导推导和和归约归约过程有如下差别：推导时仅观察过程有如下差别：推导时仅观察 可推导出的输入串的一部分，而归约时可归约的输入可推导出的输入串的一部分，而归约时可归约的输入 串整体已全部出现串整体已全部出现 构造较复杂构造较复杂 手工构造有难度手工构造有难度 但存在很好的自动构造技术但存在很好的自动构造技术 （如（如 Yacc 工具采用工具采用 LALR 分析技术）分析技术） 利于出错处理利于出错处理 输入符号查看后才被移进输入符号查看后才被移进 编译原理 借助一个借助一个下推栈（分析栈）下推栈（

12、分析栈）和一个基于有限状态控制的和一个基于有限状态控制的 分析引擎分析引擎 分析引擎根据分析引擎根据当前当前状态、状态、下推栈当前状态下推栈当前状态/内容、内容、剩余输剩余输 入单词序列来入单词序列来确定确定如下动作之一，如下动作之一，然后进入新状态然后进入新状态： Reduce: 依确定依确定的方式对的方式对位于栈顶的位于栈顶的短语短语进行进行归约归约 Shift: 从输入序列从输入序列移进移进一个单词一个单词 Error: 发现语法发现语法错误错误，进行错误处理，进行错误处理/恢复恢复 Accept：分析分析成功成功 基本原理基本原理 移进移进 归约分析归约分析 编译原理 移进移进 归约分

13、析归约分析 的的一个例子一个例子 移进移进 归约分析归约分析 文法文法 GS: (1) S E (2) E E + T (3) E T (4) T T F (5) T F (6) F ( E ) (7) F v (8) F d 待分析输入串待分析输入串: vv d # + v d #Reduce(7)（1）v + v d #Reduce(5)（2）F v d #（5）E +Shift + v d #（3）TReduce(3) + v d #（4）EShift d #（6）E + vReduce(7) d #（7）E + FReduce(5) d #（8）E + TShift d #（9）E +

14、 T Shift #（10）E + T dReduce(8) #（11）E + T FReduce(4) #（12）E + TReduce(2) #（13）EReduce(1) #（14）SAccept v + v d #Shift（0） 步骤步骤分析栈分析栈余留输入串余留输入串动作动作 编译原理 对应一个对应一个最右推导最右推导 将分析栈中的符号将分析栈中的符号 串和余留输入串并串和余留输入串并 置，若逆向观察从置，若逆向观察从 步骤（步骤（14）至步骤）至步骤 （1）的每一个归约）的每一个归约 步骤，则对应一个步骤，则对应一个 最右推导，也称为最右推导，也称为 规范推导规范推导（canon

15、ical derivation） 此为此为LR分析过程分析过程 句柄作为句柄作为“可归约串可归约串” ( (接上页）接上页） 移进移进 归约分析归约分析 + v d #Reduce(7)（1）v + v d #Reduce(5)（2）F v d #（5）E +Shift + v d #（3）TReduce(3) + v d #（4）EShift d #（6）E + vReduce(7) d #（7）E + FReduce(5) d #（8）E + TShift d #（9）E + T Shift #（10）E + T dReduce(8) #（11）E + T FReduce(4) #（12）

16、E + TReduce(2) #（13）EReduce(1) #（14）SAccept v + v d #Shift（0） 步骤步骤分析栈分析栈余留输入串余留输入串动作动作 编译原理 移进移进 归约分析归约分析 的的另一个例子另一个例子 移进移进 归约分析归约分析 文法文法 GS: (1) S E (2) E E + T (3) E T (4) T T F (5) T F (6) F ( E ) (7) F v (8) F d 待分析输入串待分析输入串: vv d # + v d #Reduce（1）v + v d #Shift（2）F d #（5）F + FShift v d #（3）F +

17、Shift d #（4）F + vReduce #（7）F + F dReduce d #（6）F + F Shift #（11）S v + v d #Shift（0） 步骤步骤分析栈分析栈余留输入串余留输入串动作动作 #（9）F + TReduce #（10）EReduce 对应的推导过程不一定是规范推导对应的推导过程不一定是规范推导 可对应于算符优先分析过程可对应于算符优先分析过程 最左素短语作为最左素短语作为“可归约串可归约串” #（8）F + F FReduce 编译原理 移进移进 归约归约（shift-reduce）冲突冲突 到达一个不能确定下一步应该移进还是应该归约的状态到达一个不

18、能确定下一步应该移进还是应该归约的状态 例如，例如，有产生式有产生式 S if E then S | if E then S else S 考虑对于如下串进行移进考虑对于如下串进行移进 归约分析归约分析 if E then if E then S else S 当当 if E then if E then S 出现在分析栈中时，是出现在分析栈中时，是移进移进 else， 还是还是归约归约 if E then S ? 分析过程确定化的关键：解决两类冲突分析过程确定化的关键：解决两类冲突 移进移进 归约分析归约分析 编译原理 归约归约 归约归约（reduce-reduce）冲突冲突 到达这样的状态

19、：有对到达这样的状态：有对多于一个短语多于一个短语进行归约的选择进行归约的选择 例如，例如，有产生式有产生式 A aA | aaA 考虑对于串考虑对于串 aaab 进行移进进行移进 归约分析归约分析 当分析到某一步时，当分析到某一步时，aaA出现在分析栈中（出现在分析栈中（b 位于剩位于剩 余输入区），是用产生式余输入区），是用产生式 A aA 归约归约 aA，还是用产还是用产 生式生式 A aaA 归约归约 aaA ? 移进移进 归约分析归约分析 分析过程确定化的关键：解决两类冲突分析过程确定化的关键：解决两类冲突 编译原理 借助于借助于分析表分析表 多数移进多数移进 归约分析的实现都是基于

20、表驱动方法归约分析的实现都是基于表驱动方法 分析引擎根据当前状态、分析引擎根据当前状态、输入单词查询输入单词查询分析表，确定分析表，确定 Reduce，Shift，Error 和和Accept 等动作等动作 分析表应当分析表应当可以体现出可以体现出移进移进 归约冲突和归约归约冲突和归约 归约冲归约冲 突的解决方法突的解决方法 LR分析中的分析中的LR分析表分析表以及以及算符优先分析算符优先分析中的中的算符优先算符优先 分析表分析表可用于上述目的可用于上述目的 表驱动方法表驱动方法 移进移进 归约分析归约分析 编译原理 表驱动移进表驱动移进 归约分析模型归约分析模型 移进移进 归约分析归约分析

21、编译原理 LR分析分析 LR分析基础分析基础 SLR（1）分析分析 LR（0）分析分析 LR（1）分析分析 LALR（1）分析分析 编译原理 LR 分析基础分析基础 “L”, 代表从代表从左左（Left）向右扫描输入单词序列）向右扫描输入单词序列 “R”, ,代表产生的是代表产生的是最右最右（Rightmost）推导）推导 LR的的含义含义 编译原理 LR 分析模型分析模型 LR 分析是一种表驱动的移进分析是一种表驱动的移进 归约分析归约分析 LR 分析基础分析基础 编译原理 主要学习四种主要学习四种 LR 分析技术分析技术 LR（0）分析分析 适用于适用于 LR（0）文法文法 SLR（1）分

22、析分析 适用于适用于 SLR（1）文法文法 LR（1）分析分析 适用于适用于 LR（1）文法文法 LALR（1）分析分析 适用于适用于 LALR（1）文法文法 LR 分析基础分析基础 Simple LR(1) LookAhead LR(1) “0” 向前查看向前查看 0 个符号个符号 “1” 向前查看向前查看 1 个符号个符号 编译原理 LR 分析表分析表 LR 分析表的构造是分析表的构造是LR 分析的基础分析的基础 LR（0）, SLR（1）, LR（1）和和 LALR（1） 四种分析方法可共享同样的四种分析方法可共享同样的LR 分析表分析表 本讲的本讲的LR 分析表专指此类分析表专指此类L

23、R 分析表分析表 LR 分析基础分析基础 编译原理 LR 分析表分析表举例举例 文法：文法： GE LR 分析基础分析基础 栈顶栈顶 状态状态 ACTIONGOTO vd+()#ETF 0 1 2 3 4 5 6 7 8 9 10 11 12 123 acc s7 s8r2 （1）E E+T （2） E T （3）T TF （4） T F （5）F (E) （6） F v （7）F d r2r2 r4r4r4 s4s5s6 s5s6s4 923 r4 r6r6r6r6 r7r7r7r7 s5s6s4103 s5s6s411 s12 s8r1r1r1 r3r3r3r3 r5r5r5r5 s7 编

24、译原理 LR 分析表分析表 使用两张表使用两张表 ACTION 表表 告诉分析引擎：在栈顶状态为告诉分析引擎：在栈顶状态为k, 当前输当前输 入符号是入符号是 a 时做什么时做什么 ACTION k,a=si， Shift：状态状态 i 移进栈顶移进栈顶 ACTION k,a=rj， Reduce：按第按第 j 条产生式归约条产生式归约 ACTION k,a=acc， Accept ：分析完成分析完成 ACTION k,a=err，Error ：发现错误发现错误 （常标为空白）（常标为空白） GOTO 表表 GOTOi,A=j 告诉分析引擎：告诉分析引擎： 在依产生式在依产生式 A 归约之后，

25、栈顶状态为归约之后，栈顶状态为i 时，要将新时，要将新 状态状态 j 移进栈顶移进栈顶 （依产生式（依产生式 A 归约时，要将栈顶的归约时，要将栈顶的 | 个状态弹出）个状态弹出） LR 分析基础分析基础 编译原理 LR 分析算法分析算法 LR 分析基础分析基础 置置 ip 指向输入串指向输入串 w 的首符号，置初始栈顶状态为的首符号，置初始栈顶状态为 0 令令 i 为栈顶状态，为栈顶状态，a 是是 ip 指向的符号，重复如下步骤：指向的符号，重复如下步骤： if ( ACTIONi,a=sj ) PUSH j ; ; /*进栈 进栈*/ ip 前进前进 ；/*指向下一输入符号指向下一输入符号

26、*/ else if （ACTIONi,a=rj ) /*第第 j 条产生式为条产生式为 A */ POP | | 项项; ; /*位于栈顶部的位于栈顶部的 | | 个状态退栈个状态退栈*/ 令当前栈顶状态为令当前栈顶状态为 k； PUSH GOTOk,A； else if （ACTIONi,a=acc ) return； /*成功成功*/ else error； /*报错报错/错误恢复错误恢复*/ 编译原理 LR 分析基础分析基础 分析栈分析栈余留输入串余留输入串分析动作分析动作 0v + v d #ACTION 0,v=s5 + v d #ACTION 5,+=r6, GOTO 0,F=3

27、0 5 + v d #ACTION 3,+=r4, GOTO 0,T=20 3 + v d #ACTION 2,+=r2, GOTO 0,E=10 2 + v d #ACTION 1,+=s70 1 v d #ACTION 7,v=s50 1 7 d #ACTION 5,=r6, GOTO 7,F=30 1 7 5 d #ACTION 3,=r4, GOTO 7,T=100 1 7 3 d #ACTION 10,=s80 1 7 10 d #ACTION 8,d=s60 1 7 10 8 #ACTION 6,#=r7, GOTO 8,F=110 1 7 10 8 6 #ACTION 11,#=

28、r3, GOTO 7,T=100 1 7 10 8 11 #ACTION 10,#=r1, GOTO 0,E=10 1 7 10 #ACTION 1,#=acc0 1 LR 分析过程分析过程举例举例 文法：文法：GE 输入串：输入串： v + v d （1）EE+T （2） ET （3）TTF （4）TF （5）F(E) （6） Fv （7）Fd 编译原理 带符号栈的带符号栈的LR 分析模型分析模型 LR 分析基础分析基础 编译原理 带符号栈的带符号栈的 LR 分析算法分析算法 LR 分析基础分析基础 置置 ip 指向输入串指向输入串 w 的首符号，置状态栈顶为的首符号，置状态栈顶为 0，状态

29、状态 栈顶为栈顶为 #，令令 i 为栈顶状态，为栈顶状态，a 是是 ip 指向的符号，重复指向的符号，重复 如下步骤：如下步骤： if ( ACTIONi,a=sj ) PUSH j， ，a; ; /*进栈进栈*/ ip 前进前进 ；/*指向下一输入符号指向下一输入符号*/ else if （ACTIONi,a=rj ) /*第第 j 条产生式为条产生式为 A */ POP | | 项项; ; /*位于两个栈顶部的位于两个栈顶部的 | | 个元素退栈个元素退栈*/ 令当前状态栈顶为令当前状态栈顶为 k； PUSH GOTOk,A， A ； else if （ACTIONi,a=acc ) re

30、turn； /*成功成功*/ else error； /*报错报错/错误恢复错误恢复*/ 编译原理 LR 分析基础分析基础 分析栈分析栈余留输入串余留输入串分析动作分析动作 0#v + v d #ACTION 0,v=s5 + v d #ACTION 5,+=r6, GOTO 0,F=30# 5v + v d #ACTION 3,+=r4, GOTO 0,T=20# 3F + v d #ACTION 2,+=r2, GOTO 0,E=10# 2T + v d #ACTION 1,+=s70# 1E v d #ACTION 7,v=s50# 1E 7+ d #ACTION 5,=r6, GOTO

31、 7,F=30# 1E 7+ 5v d #ACTION 3,=r4, GOTO 7,T=100# 1E 7+ 3F d #ACTION 10,=s80# 1E 7+ 10T d #ACTION 8,d=s60# 1E 7+ 10T 8 #ACTION 6,#=r7, GOTO 8,F=110# 1E 7+ 10T 8 6d #ACTION 11,#=r3, GOTO 7,T=100# 1E 7+ 10T 8 11F #ACTION 1,#=acc0# 1E 带分析栈的带分析栈的LR 分析过程分析过程举例举例 文法：文法：GE 输入串：输入串： v + v d （1）EE+T （2） ET （3

32、）TTF （4）TF （5）F(E) （6） Fv （7）Fd #ACTION 10,#=r1, GOTO 0,E=10# 1E 7+ 10T 编译原理 如何获得如何获得 LR 分析表分析表 LR（0）, SLR（1）, LR（1）和和 LALR（1） 四种分析方法分别讨论四种分析方法分别讨论 LR 分析基础分析基础 编译原理 LR（0）分析分析 核心概念核心概念 增广文法增广文法（augmented grammar） 对于文法对于文法 G = (VN, VT, P , S ) , 增加增加如下如下产生式产生式 S S 其中，其中，S VN VT ，得到，得到 G 的增广文法的增广文法 G =

33、 (VN, VT, P , S ) 注：注：增广文法等价于原文法；增广文法的开始增广文法等价于原文法；增广文法的开始 符号不会出现在任何产生式的右部符号不会出现在任何产生式的右部 编译原理 LR（0）分析分析 核心概念核心概念 活前缀活前缀（viable prefix） 对于文法对于文法 G = (VN, VT, P , S ) , 设设 S 是其增广是其增广 文法的开始符号（即有产生式文法的开始符号（即有产生式 S S），且），且 , (VN VT)* , w VT* 若若 S Aw 且且 A ，即，即 为为句柄句柄， 则则 的任何前缀的任何前缀 都是文法都是文法 G 的活前缀的活前缀 注：

34、注：由于由于 S S 且且 S S，故，故 S 是是 G 的活前缀的活前缀 rm rm 编译原理 LR（0）分析分析 活前缀活前缀举例举例 文法文法 G（S）: （1）S AB （2）A aA （3）A （4）B b （5）B bB 对于右边的文法对于右边的文法G(S), , 句子句子 aaab 是一个右句型，其是一个右句型，其 唯一的句柄为：唯一的句柄为： ：aaab； 所以所以 aaa 的任何前缀都是文法的任何前缀都是文法 的活前缀：的活前缀：， a ， aa ， aaa 右句型右句型 aaAb 的唯一的句柄为：的唯一的句柄为： aA：aaAb； 所以所以 aaA 的任何前缀都是文法的任何

35、前缀都是文法 的活前缀：的活前缀：， a ， aa ， aaA 编译原理 LR（0）分析分析 活前缀与句柄的关系活前缀与句柄的关系 一个活前缀是某一一个活前缀是某一右句型的前缀右句型的前缀，它，它不超过不超过该右句型的该右句型的 某个某个句柄句柄 活前缀活前缀已含有该句柄的全部符号已含有该句柄的全部符号，表明该句柄对应的，表明该句柄对应的 产生式产生式 A的右部的右部已出现在栈顶已出现在栈顶 活前缀只含该句柄的一部分符号活前缀只含该句柄的一部分符号，表明该句柄对应的，表明该句柄对应的 产生式产生式 A12 的右部子串的右部子串1 已出现在栈顶，期待已出现在栈顶，期待 从输入串中看到从输入串中看

36、到2 推导出的符号串推导出的符号串 活前缀不含有该句柄的任何符号活前缀不含有该句柄的任何符号，此时期待从输入串，此时期待从输入串 中看到该句柄对应的产生式中看到该句柄对应的产生式 A的右部所推导出的的右部所推导出的 符号串符号串 编译原理 LR（0）分析分析 活前缀集合的归纳定义活前缀集合的归纳定义 （证明略）（证明略） 文法文法 G = (VN, VT, P , S ) 的的活前缀集合活前缀集合 VPrefix 归纳归纳 定义为定义为 令令 S VPrefix （基础）（基础） 若若 v VPrefix，则，则 v 的任一前缀的任一前缀 u 都是活前缀，即都是活前缀，即 u VPrefix

37、若若 v VPrefix，且，且 v 中至少包含一个非终结符，即中至少包含一个非终结符，即 可以将可以将 v 写成写成 B ，其中，其中 B 为非终结符。若有产生为非终结符。若有产生 式式B ，则，则 的任一前缀的任一前缀u都是活前缀，即都是活前缀，即 u VPrefix VPrefix中的元素只能通过上述步骤产生中的元素只能通过上述步骤产生 编译原理 LR（0）分析分析 核心概念核心概念 LR（0）FSM 每个上下文无关文法每个上下文无关文法 G 都对应一个都对应一个LR（0）FSM 由由 G 的增广文法的增广文法 G 直接构造其直接构造其 LR（0）FSM 文法文法 G = (VN, VT

38、, P , S ) 的的 LR（0）FSM 可以看可以看 作一个字母表为作一个字母表为 VN VT 的的 DFA 编译原理 LR（0）分析分析 LR（0）FSM 的构造的构造 LR（0）FSM 的状态的状态 LR（0）FSM 的状态是一个特殊的的状态是一个特殊的 LR（0）项目项目 （item）集集 一个一个LR（0）项目项目是在是在右端右端某一位置某一位置有圆点的产生式有圆点的产生式 如，产生式如，产生式 Axyz 对应如下对应如下 4 个个 LR（0）项目：项目： A.xyz Ax.yz Axy.z Axyz. 圆点标志圆点标志着已着已分析分析过的串与该产生式过的串与该产生式匹配的位置匹配

39、的位置 编译原理 LR（0）分析分析 LR（0）FSM 的构造的构造 LR（0）项目解析项目解析 设设 G S 是文法是文法 G = (VN, VT, P , S )的增广文法的增广文法 根据圆点所在的位置和圆点后是终结符还是非终结符根据圆点所在的位置和圆点后是终结符还是非终结符 或为空，把项目分为以下几种或为空，把项目分为以下几种： 移进项目移进项目: 形如形如 A .a , 其中其中a VT , , (VN VT)* 待约项目待约项目: 形如形如 A .B 归约项目归约项目: 形如形如 A . 接受项目接受项目: 形如形如 S S . 编译原理 LR（0）分析分析 LR（0）FSM 的构造

40、的构造 LR（0）FSM 的状态的状态 LR（0）FSM 的状态是一个的状态是一个 LR（0）项目集的闭包项目集的闭包 （closure） 计算计算LR（0）项目集项目集 I 的闭包的闭包 CLOSURE( (I) )的算法：的算法： function CLOSURE( (I） J := I; repeat for J 中的每个项目中的每个项目A .B 和和 产生式产生式 B do 若若 B . 不在不在 J 中，则加中，则加 B . 到到 J 中中 until 上一次循环不再有新项目加到上一次循环不再有新项目加到J中中 return J ; 编译原理 LR（0）分析分析 LR（0）FSM 的

41、构造的构造 LR（0）FSM 的初态的初态 设文法设文法 GS 的增广文法为的增广文法为 G S, 则则 G 的的LR（0）FSM 的初态的初态 I0 = CLOSURE(S.S) GE: (1) E E+T (2) E T (3) T ( E ) (4) T d 例例 右边文法右边文法GE的的增广文法为增广文法为 G E ， 其其 LR（0）FSM 的初态的初态 I0 = E .E， E .E+T， E .T， T .( E ), T . d 编译原理 LR（0）分析分析 LR（0）FSM 的构造的构造 LR（0）FSM 的状态转移函数的状态转移函数 GO (I,X) = CLOSURE(J

42、) 其中，其中，I为为LR（0）FSM 的状态（闭包的的状态（闭包的项目集），项目集），X 为为 文法符号，文法符号，J= AX. | A.X I 从从 LR（0）FSM 的初态出发，应用上述转移函的初态出发，应用上述转移函 数，可逐步构造出完整的数，可逐步构造出完整的 LR（0）FSM 编译原理 LR（0）FSM 的构造的构造 计算计算 LR（0）FSM 的所有状态的集合的所有状态的集合 设文法设文法 GS 的增广文法为的增广文法为 G S, 则则 LR（0）FSM 的的 所有状态的集合所有状态的集合 C 可由如下算法计算：可由如下算法计算： C:= CLOSURE (S.S) Repeat

43、 For C 中每一项目集中每一项目集 I 和每一文法符号和每一文法符号X Do if GO(I,X) 非空且不属于非空且不属于C Then 把把 GO(I,X) 放入放入C中中 Until C 不再增大不再增大 LR（0）分析分析 编译原理 LR（0）分析分析 LR（0）FSM 的构造的构造举例举例 GE的的增广文法增广文法G E 的的 LR（0）FSM GE: (1) E E+T (2) E T (3) T ( E ) (4) T d I0: E .E E .E+T E .T T .(E) T .d I4: T (.E) E .E+T E .T T .( E ) T .d I1: E E.

44、 E E.+T I2: E T. I3: T d. I5: T (E.) E E.+T I2 I3 I6: E E+.T T .( E ) T .d I7: T (E). I6 I8: E E+T. I4 I3 ( E T d E T d ( + ) + T d ( 编译原理 LR（0）分析分析 LR（0）FSM 的语言的语言 结论结论 文法文法 G = (VN, VT, P , S ) 的的 LR（0）FSM 可以看可以看 作一个字母表为作一个字母表为 VN VT 的的 DFA（所有状态都是所有状态都是 终态；严格地说，还应该有一个死状态，它不是终态；严格地说，还应该有一个死状态，它不是 终

45、态终态），可以证明，可以证明: 该该 DFA 的语言是的语言是 G 的所有活前缀的集合的所有活前缀的集合 （证明略）（证明略） 由此可知，对任何句型，我们不会错过任何可归由此可知，对任何句型，我们不会错过任何可归 约的句柄，或者说不会错过任何最右推导约的句柄，或者说不会错过任何最右推导 编译原理 LR（0）分析分析 LR（0）分析表分析表的构造的构造 假定假定C=I0, I1,，In，令状态，令状态Ik对应的对应的 LR（0）分析表分析表 的栈顶状态为的栈顶状态为k；令含有项目；令含有项目S.S 的状态为的状态为I0, 因此因此 0 为初态。为初态。ACTION 表项和表项和 GOTO 表项可

46、按如下方法构表项可按如下方法构 造：造： 若项目若项目A.a属于属于 Ik 且且 GO (Ik, a)= Ij, a 为终结符，则置为终结符，则置 ACTIONk, a 为为“把状态把状态j和符号和符号a移进栈移进栈”，简记为，简记为“sj”; 若项目若项目A. 属于属于Ik, 那么，对任何终结符那么，对任何终结符a, 置置ACTIONk, a为为“用用 产生式产生式A进行归约进行归约”，简记为，简记为“rj”;其中，假定其中，假定A为文法为文法G 的的 第第j个产生式；个产生式； 若项目若项目SS. 属于属于Ik, 则置则置ACTIONk, #为为“接受接受”，简记为，简记为“acc”; 若

47、若GO (Ik, A)= Ij, A为非终结符，则置为非终结符，则置GOTO(k, A)=j; 分析表中凡不能用上述规则填入信息的空白格均置上分析表中凡不能用上述规则填入信息的空白格均置上“出错标志出错标志” 编译原理 LR（0）分析表的构造分析表的构造举例举例 增广增广文法：文法： G E 栈顶栈顶 状态状态 ACTIONGOTO d+()#ET 0 1 2 3 4 5 6 7 8 12 accs6 r2 （0）EE （1）EE+T （2） ET （3）T (E) （4）T d r2r2 r4r4r4 s4s3 s3s4 52 s6s7 s3s4 8 r2r2 r4r4 r3r3r3r3r3

48、 r1r1r1r1r1 LR（0）分析分析 编译原理 LR（0）分析分析 LR（0）文法文法 按上述算法构造的分析表，如果各表项均无多按上述算法构造的分析表，如果各表项均无多 重定义，则称它为文法重定义，则称它为文法 G 的一张的一张 LR（0）表表， 并称并称 G 为一个为一个 LR（0）文法文法 LR（0）文法的文法的 LR（0）FSM 中，每个状态中，每个状态 （闭包项目集）都满足：（闭包项目集）都满足： 不同时含有移进项目和归约项目不同时含有移进项目和归约项目 不含有两个以上归约项目不含有两个以上归约项目 编译原理 SLR（1）分析分析 LR（0）分析的局限性）分析的局限性 满足满足

49、LR（0）要求的文法不多要求的文法不多 如：文法中含有产生式如：文法中含有产生式 A 通常会遇到问题，对应通常会遇到问题，对应 的项目的项目A . 是归约项目是归约项目，容易引起移进容易引起移进 归约冲突归约冲突 将会看到，对上述将会看到，对上述 LR（0）文法的例子作很小的扩）文法的例子作很小的扩 充就会变成非充就会变成非 LR（0）文法）文法 只根据栈顶的当前状态确定下一步动作只根据栈顶的当前状态确定下一步动作 根据栈顶状态，就可确定进行移进还是归约：根据栈顶状态，就可确定进行移进还是归约： ACTION 表同一行中，不会既有移进又有归约；表同一行中，不会既有移进又有归约； 同一行中，归约

50、动作同时存在且都是一样的同一行中，归约动作同时存在且都是一样的 编译原理 SLR（1）分析分析 不是不是 LR（0）的文法）的文法举例举例 验证如下文法不是验证如下文法不是 LR（0）的的 文法文法 GE: (1) E E + T (2) E T (3) T T F (4) T F (5) F ( E ) (6) F v (7) F d GE 的增广的增广文法文法 G S: (0) S E (1) E E + T (2) E T (3) T T F (4) T F (5) F ( E ) (6) F v (7) F d 编译原理 SLR（1）分析分析 验证文法验证文法G不是不是 LR（0）文法

51、文法 构造构造GE的的增广文法增广文法G S的的LR（0）FSM I0: S .E E .E+T E .T T .T F T .F F .(E) F .v F .d I1: S E. E E.+T I3: TF. I6: F d. E ( + I4: F (.E) E .E+T E .T T .T F T .F F .(E) F .v F .d I9: F (E.) E E.+T I12: F (E). I5: F v. I2: E T. T T. F I7: E E+.T T .T F T .F F .(E) F .v F .d I8: T T .F F .(E) F .v F .d I10

52、: E E+T. T T. F I11: T T F. T ( Fvd E I2 T I3 F I5 v I6 d ) I7 + F ( I4 v I5 d I6 T I3 F I4 ( I5 v I6 d I8 增广增广文法文法G S: (0) S E (1) E E + T (2) E T (3) T T F (4) T F (5) F ( E ) (6) F v (7) F d 编译原理 SLR（1）分析分析 验证文法验证文法G不是不是 LR（0）文法文法 从前一页从前一页的的 LR（0）FSM 可以发可以发 现如下两个状态（项目集）存在现如下两个状态（项目集）存在 移进移进 归约冲突归

53、约冲突 I1: S E . E E . + T I2: E T . T T . F I10: E E + T . T T . F 注意：由于注意：由于 S E . 是是接受项目，所以如下接受项目，所以如下 状态不存在冲突状态不存在冲突 增广增广文法文法G S: (0) S E (1) E E + T (2) E T (3) T T F (4) T F (5) F ( E ) (6) F v (7) F d 编译原理 SLR（1）分析分析 向前查看一个符号向前查看一个符号可可解决冲突解决冲突 文法文法 G 中，中， Follow(E) = +, ),# 在如下存在移进在如下存在移进 归约冲突的状

54、归约冲突的状 态态 I2 和和 I10 中，可以根据下一个中，可以根据下一个 输入符号是否属于输入符号是否属于 Follow(E) 来来 决定是否进行归约，同时决定是否进行归约，同时可以根可以根 据下一个输入符号是否为据下一个输入符号是否为 来决来决 定是否移进定是否移进 增广增广文法文法G S: (0) S E (1) E E + T (2) E T (3) T T F (4) T F (5) F ( E ) (6) F v (7) F d I2: E T . T T . F I10: E E + T . T T . F 编译原理 SLR（1）分析分析 SLR（1）分析思想分析思想 向前查看

55、一个符号向前查看一个符号来来改进改进对对LR（0）状态（项目集）状态（项目集） 中移进中移进 归约和归约归约和归约 归约归约冲突的解决冲突的解决 根据下一个输入符号是否属于要归约的非终结符的根据下一个输入符号是否属于要归约的非终结符的 Follow 集来决定是否进行归约集来决定是否进行归约 如果如果LR（0）状态（项目集）中的所有归约项状态（项目集）中的所有归约项中中要归要归 约的非终结符的约的非终结符的 Follow 集互不相交，则可以解决集互不相交，则可以解决归归 约约 归约归约冲突冲突 如果如果LR（0）状态（项目集）中的所有归约项状态（项目集）中的所有归约项中中要归要归 约的非终结符的

56、约的非终结符的 Follow 集集与所有移进项目要移进的与所有移进项目要移进的 符号集符号集互不相交，则可以解决互不相交，则可以解决移进移进 归约归约冲突冲突 编译原理 SLR（1）分析分析 SLR（1）分析思想分析思想 SLR（0）分析表的构造也基于分析表的构造也基于LR（0）FSM 只需对只需对 LR（0）分析表进行简单修改分析表进行简单修改 使得归约表项只适用于相应非终结符使得归约表项只适用于相应非终结符Follow 集集 中的输入符号中的输入符号 编译原理 SLR（1）分析分析 SLR（1）分析表分析表的构造的构造 假定假定GS的增广文法为的增广文法为G S，其其LR（0）FSM 的状

57、态集的状态集 为为C=I0, I1,，In；令状态；令状态Ik对应的对应的 SLR（1）分析表的分析表的 栈顶状态为栈顶状态为k ；并令含有项目；并令含有项目S.S 的项目集为的项目集为I0, 因此因此 0为初态为初态. ACTION表项和表项和GOTO表项可按如下方法构造：表项可按如下方法构造： 若项目若项目A.a属于属于 Ik 且且 GO (Ik, a)= Ij, a 为终结符，则置为终结符，则置 ACTIONk, a 为为“把状态把状态j和符号和符号a移进栈移进栈”，简记为，简记为“sj”; 若项目若项目A. 属于属于Ik, 那么，对任何那么，对任何aFollow(A), 置置ACTIO

58、Nk, a为为 “用产生式用产生式A进行归约进行归约”，简记为，简记为“rj”;其中，假定其中，假定A为文法为文法G 的第的第j个产生式；个产生式； 若项目若项目SS. 属于属于Ik, 则置则置ACTIONk, #为为“接受接受”，简记为，简记为“acc”; 若若GO (Ik, A)= Ij, A为非终结符，则置为非终结符，则置GOTO(k, A)=j; 分析表中凡不能用上述规则填入信息的空白格均置上分析表中凡不能用上述规则填入信息的空白格均置上“出错标志出错标志” 编译原理 SLR（1）分析表分析表 的构造的构造举例举例 增广增广文法：文法：G S SLR（1）分析分析 栈顶栈顶 状态状态

59、ACTIONGOTO vd+()#ETF 0 1 2 3 4 5 6 7 8 9 10 11 12 123 acc s7 s8r2r2r2 r4r4r4 s4s5s6 s5s6s4 923 r4 r6r6r6r6 r7r7r7r7 s5s6s4103 s5s6s411 s12 s8r1r1r1 r3r3r3r3 r5r5r5r5 s7 （0）SE （1）E E+T （2） E T （3）T TF （4） T F （5）F (E) （6） F v （7）F d 编译原理 SLR（1）文法文法 按上述算法构造的分析表，如果各表项均无多按上述算法构造的分析表，如果各表项均无多 重定义，则称它为文法重

60、定义，则称它为文法 G 的一张的一张 SLR（1）表表， 并称并称 G 为一个为一个 SLR（1）文法文法 SLR（1）文法的文法的LR（0）FSM中，每个状态都中，每个状态都 满足：满足： 对该状态的任何项目对该状态的任何项目Au.av（a为终结符为终结符），不存在不存在 项目项目 Bw. 使得使得 aFollow(B) 对该状态的任何两个项目对该状态的任何两个项目Au.和和Bv.，满足满足 Follow(A) Follow(B) = SLR（1）分析分析 编译原理 SLR（1）分析分析 比较比较 LR（0）表和表和 SLR（1）表表 在在 LR（0）表的表的 ACTION 表中，归约表项总