编译技术：第04章03 自下而上的语法分析

1、第04章(03) 自下而上的语法分析概述什么是自下而上的语法分析什么是自下而上的语法分析 从输入串开始分析，直到开始符号从输入串开始分析，直到开始符号可以使用广度、深度搜索法可以使用广度、深度搜索法 但实际中很少使用但实际中很少使用本章重点介绍本章重点介绍“有向的有向的”“”“预测预测”方法方法 有向：从左向右扫描串有向：从左向右扫描串 预测：猜测使用哪个产生式归约预测：猜测使用哪个产生式归约Zhou, Erqiang2School of Information and Software EngineeringSchool of Information and Software Enginee

2、ringZhou, Erqiang3概述自上而下语法分析自上而下语法分析 从文法开始符从文法开始符S S出发出发 猜测输入串猜测输入串的推导序列的推导序列自下而上语法分析自下而上语法分析 从输入串从输入串出发出发 猜测猜测归约序列归约序列，使串，使串归约到归约到S S概述Zhou, Erqiang4School of Information and Software EngineeringE TE E + TT intT (E)ETint+(int+int+int)ETEEETTTSchool of Information and Software EngineeringZhou, Erqia

3、ng5概述E TE E + TT intT (E) int + ( int + int + int ) T + (int + int + int) E + (int + int + int) E + (T + int + int) E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T ESchool of Information and Software EngineeringZhou, Erqiang6概述E TE E + TT intT (E) int + ( int + int + in

4、t ) T + (int + int + int) E + (int + int + int) E + (T + int + int) E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T ESchool of Information and Software EngineeringZhou, Erqiang7概述 int + ( int + int + int ) T + (int + int + int) E + (int + int + int) E + (T + int + int)

5、E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T E每步操作称为每步操作称为归约归约对对句型的子串句型的子串进行归约进行归约将子串归约为将子串归约为非终结符非终结符本例中，每次归约本例中，每次归约 恰为恰为最左归约最左归约自下而上的方法自下而上的方法 是否就是找最左归约呢？是否就是找最左归约呢？School of Information and Software EngineeringZhou, Erqiang8概述 int + ( int + int + int ) T + (int +

6、 int + int) E + (int + int + int) E + (T + int + int) E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EETint+(int+int+int)ETEEETTTint+()+intint+intSchool of Information and Software EngineeringZhou, Erqiang9概述 int + ( int + int + int ) T + (int + int + int) E + (int + i

7、nt + int) E + (T + int + int) E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EETint+(int+int+int)ETEEETTTint+()+intint+intSchool of Information and Software EngineeringZhou, Erqiang10概述 T + (int + int + int) E + (int + int + int) E + (T + int + int) E + (E + int + int)

8、 E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EETint+(int+int+int)ETEEETTT+()+intint+intSchool of Information and Software EngineeringZhou, Erqiang11概述 E + (int + int + int) E + (T + int + int) E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EEint+(int+int+

9、int)ETEEETTT+()+intint+intSchool of Information and Software EngineeringZhou, Erqiang12概述 E + (T + int + int) E + (E + int + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EEint+(int+int+int)ETEEETTT+()+intint+School of Information and Software EngineeringZhou, Erqiang13概述 E + (E + i

10、nt + int) E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EEint+(int+int+int)ETEEETT+()+intint+School of Information and Software EngineeringZhou, Erqiang14概述 E + (E + T + int) E + (E + int) E + (E + T) E + (E) E + T EEint+(int+int+int)ETEEETT+()+int+School of Information and Software Engi

11、neeringZhou, Erqiang15概述 E + (E + int) E + (E + T) E + (E) E + T EEint+(int+int+int)ETEET+()+intSchool of Information and Software EngineeringZhou, Erqiang16概述 E + (E + T) E + (E) E + T EEint+(int+int+int)ETEET+()+School of Information and Software EngineeringZhou, Erqiang17概述 E + (E) E + T EEint+(i

12、nt+int+int)ETE+()School of Information and Software EngineeringZhou, Erqiang18概述 E + T EEint+(int+int+int)ET+School of Information and Software EngineeringZhou, Erqiang19概述分析与总结自下而上语法分析自下而上语法分析 构建输入串的语法树构建输入串的语法树 每一步进行每一步进行“最左归约最左归约” 对语法树进行剪枝对语法树进行剪枝对对哪些串哪些串进行归约？进行归约？对哪些叶结点及边进行剪枝？对哪些叶结点及边进行剪枝？School

13、 of Information and Software EngineeringZhou, Erqiang20概述分析与总结考查：每一步进行考查：每一步进行“最左归约最左归约”E FE E + FF F * TF TT intT (E)int+int*intTFETFE不是不是对对“句柄句柄” 进行归约进行归约School of Information and Software EngineeringZhou, Erqiang21相关概念把每次进行处理的子串称为把每次进行处理的子串称为“句柄句柄” 处理：处理：handle - “handle”handle - “handle” 处理：归约、剪

14、枝处理：归约、剪枝问题一：问题一： 句柄在哪里？句柄在哪里？ 句柄在什么位置？句柄在什么位置？School of Information and Software EngineeringZhou, Erqiang22移进归约分析示例E FE E + FF F * TF TT intT (E)int+int*int+intSchool of Information and Software EngineeringZhou, Erqiang23移进归约分析示例E FE E + FF F * TF TT intT (E)TintintTFFEE+int*int+intSchool of Inform

15、ation and Software EngineeringZhou, Erqiang24移进归约分析示例E FE E + FF F * TF TT intT (E)TintFEE+int*int+intSchool of Information and Software EngineeringZhou, Erqiang25移进归约分析示例E FE E + FF F * TF TT intT (E)TintFEE+int*int+intintTFT FSchool of Information and Software EngineeringZhou, Erqiang26移进归约分析示例E F

16、E E + FF F * TF TT intT (E)TintFEE+*int+intintTFF*School of Information and Software EngineeringZhou, Erqiang27移进归约分析示例E FE E + FF F * TF TT intT (E)TintFEE+*int+intintTFF*intTTFFEESchool of Information and Software EngineeringZhou, Erqiang28移进归约分析示例E FE E + FF F * TF TT intT (E)TintFE+intintTF*intT

17、FEE+School of Information and Software EngineeringZhou, Erqiang29移进归约分析示例E FE E + FF F * TF TT intT (E)TintFE+intintTF*intTFFEE+intTFET FESchool of Information and Software EngineeringZhou, Erqiang30分析方法分析方法 移进：把终结符从移进：把终结符从右区右区移动移动左区左区 归约：把归约：把左区左区的部分符号归约的部分符号归约句柄在哪里？句柄在哪里？ 左区的最右边的符号左区的最右边的符号 栈顶的符号

18、栈顶的符号移进归约示例总结School of Information and Software EngineeringZhou, Erqiang31问题二：问题二： 如何确定句柄？如何确定句柄？ 如何在栈顶部分确定句柄符号串？如何在栈顶部分确定句柄符号串？ 句柄有哪些特征？句柄有哪些特征？移进归约示例总结School of Information and Software EngineeringZhou, Erqiang32如何确定句柄？如何确定句柄？ 句柄在栈顶句柄在栈顶对栈顶符号详细分析对栈顶符号详细分析 栈里的符号有什么特征？栈里的符号有什么特征？ 栈里的符号是不是任意的？栈里的符号是不

19、是任意的？如果找出栈里出现符号的特征如果找出栈里出现符号的特征 也许可以根据特征确定也许可以根据特征确定句柄句柄移进归约示例总结School of Information and Software EngineeringZhou, Erqiang33移进归约示例再分析E FE E + FF F * TF TT intT (E)TintFE+intTF*intTFE+intTFEint+int*int+intSchool of Information and Software EngineeringZhou, Erqiang34移进归约示例再分析E FE E + FF F * TF TT int

20、T (E)TintFE+intTF*intTFE+intTFEint+int*int+intSchool of Information and Software EngineeringZhou, Erqiang35移进归约示例再分析E FE E + FF F * TF TT intT (E)TintFE+intTF*intTFE+intTFEint+int*int+intT F ESchool of Information and Software EngineeringZhou, Erqiang36移进归约示例再分析E FE E + FF F * TF TT intT (E)E+intTF*

21、intTFE+intTFE+int*int+intESchool of Information and Software EngineeringZhou, Erqiang37移进归约示例再分析E FE E + FF F * TF TT intT (E)E+intTF*intTFE+intTFE+int*int+intET F将将 E+F 归约为归约为 E 吗？吗？School of Information and Software EngineeringZhou, Erqiang38移进归约示例再分析E FE E + FF F * TF TT intT (E)E+F*intTFE+intTFE

22、+*int+intEFSchool of Information and Software EngineeringZhou, Erqiang39移进归约示例再分析E FE E + FF F * TF TT intT (E)E+F*intTFE+intTFE+*int+intEFTFESchool of Information and Software EngineeringZhou, Erqiang40移进归约示例再分析E FE E + FF F * TF TT intT (E)E+intTFE+intESchool of Information and Software Engineerin

23、gZhou, Erqiang41移进归约示例再分析E FE E + FF F * TF TT intT (E)E+intTFE+intET FESchool of Information and Software EngineeringZhou, Erqiang42移进归约示例再分析句柄有什么特点？句柄有什么特点？每次每次归约的串归约的串的什么特点？的什么特点？句柄：最左、仅有一代的子树边缘句柄：最左、仅有一代的子树边缘短语：任何子树的边缘是子树根的短语短语：任何子树的边缘是子树根的短语直接短语：仅有一代的子树边缘是子树根的短语直接短语：仅有一代的子树边缘是子树根的短语句柄：最左、直接短语句柄

24、：最左、直接短语School of Information and Software EngineeringZhou, Erqiang43关注当前位置S EE FE E + FF F * TF TT intT (E)TintFE+intTF*intTFE+intTFEint+int*int+intS EE E+FE E+FE FF TT intSchool of Information and Software EngineeringZhou, Erqiang44关注当前位置S EE FE E + FF F * TF TT intT (E)TintFE+intTF*intTFE+intTFEi

25、nt+int*int+intS EE E+FE E+FE FF TT intT F ET intF TE FE E+FE E+FSchool of Information and Software EngineeringZhou, Erqiang45关注当前位置E+intTF*intTFE+intTFE+int*int+intS EE FE E + FF F * TF TT intT (E)E E+FS EEE E+FSchool of Information and Software EngineeringZhou, Erqiang46关注当前位置E+intTF*intTFE+intTFES

26、 EE FE E + FF F * TF TT intT (E)F F*TF TT intE E+FS EE E+F+int*int+intESchool of Information and Software EngineeringZhou, Erqiang47关注当前位置E+intTF*intTFE+intTFES EE FE E + FF F * TF TT intT (E)F F*TF TT intE E+FS EE E+F+int*int+intET intTF TFF F*TSchool of Information and Software EngineeringZhou, Er

27、qiang48关注当前位置E+F*intTFE+intTFES EE FE E + FF F * TF TT intT (E)E E+FS EE E+F+*int+intEFF F*TF F*TT intSchool of Information and Software EngineeringZhou, Erqiang49关注当前位置E+F*intTFE+intTFES EE FE E + FF F * TF TT intT (E)E E+FS EE E+F+*int+intEFF F*TT intT intTF F*TFE E+FEE E+FSchool of Information an

28、d Software EngineeringZhou, Erqiang50关注当前位置E+intTFES EE FE E + FF F * TF TT intT (E)S E+intEE E+FE E+FT intF TSchool of Information and Software EngineeringZhou, Erqiang51关注当前位置E+intTFES EE FE E + FF F * TF TT intT (E)S EE E+F+intET intF TT intF TT FE E+FES ESchool of Information and Software Engine

29、eringZhou, Erqiang52如何找出句柄？如何找出句柄？ 句柄在栈顶句柄在栈顶分析栈中的符号分析栈中的符号 与与 产生式有一定关系产生式有一定关系 分析过程分析过程 可以可以 不依赖语法树！不依赖语法树！ 分析过程分析过程 与与 语法规则直接相关语法规则直接相关识别栈顶符号School of Information and Software EngineeringZhou, Erqiang53任意时刻任意时刻, ,栈中符号可由下面步骤得到栈中符号可由下面步骤得到 1) 1)从开始符号起从开始符号起 跟踪一系列的产生式跟踪一系列的产生式 对每个产生式对每个产生式, ,跟踪当前分析位置

30、跟踪当前分析位置 2) 2)对每个产生式对每个产生式, ,按顺序按顺序, , 输出当前分析位置之前所有符号输出当前分析位置之前所有符号识别栈顶符号School of Information and Software EngineeringZhou, Erqiang54识别栈顶符号+*int+intEFS EE FE E + FF F * TF TT intT (E)E E+FS EE E+FF F*TT intE E+FE E+FF F*TF F*TT intSchool of Information and Software EngineeringZhou, Erqiang55识别栈顶符号+

31、*int+intEFS EE FE E + FF F * TF TT intT (E)E E+FS EE E+FF F*TT intE E+FE E+FF F*TF F*TT intSchool of Information and Software EngineeringZhou, Erqiang56重要发现重要发现 产生式个数有限产生式个数有限 产生式中位置有限产生式中位置有限 任一时刻任一时刻 只需关注在一个产生式中的位置只需关注在一个产生式中的位置 只有有限个选择到下一个产生式只有有限个选择到下一个产生式如何识别栈顶符号？如何识别栈顶符号？识别栈顶符号School of Informa

32、tion and Software EngineeringZhou, Erqiang57 有限自动机有限自动机识别栈顶符号School of Information and Software EngineeringZhou, Erqiang58识别栈顶符号S ES EE T+EE T+EE T+EE T+EE T;E T;E T;T (E)T (E)T (E)T (E)T intT intET+ET;(E)intSET开始开始S EE T + EE T ;T intT (E)School of Information and Software EngineeringZhou, Erqiang5

33、9非终结符对应一个状态非终结符对应一个状态对每个产生式对每个产生式 A 对每个对每个A 创建一个状态创建一个状态 其中其中 = = + 在在A x 与与A x 之间之间 加入状态转移符加入状态转移符x x 对状态对状态A B与与B B之间加入之间加入转移符转移符 构建有限自动机School of Information and Software EngineeringZhou, Erqiang60有限自动机与句柄有什么关系？有限自动机与句柄有什么关系？初始问题初始问题 寻找句柄，根据句柄进行归约寻找句柄，根据句柄进行归约当我们运行这个自动机当我们运行这个自动机 如果一个状态有如果一个状态有A

34、那么那么就就有可能有可能是要寻找的是要寻找的句柄！句柄！用这样的自动机可以寻找句柄！用这样的自动机可以寻找句柄！“不确定不确定”转化为转化为“确定确定”的的构建有限自动机School of Information and Software EngineeringZhou, Erqiang61构建有限自动机S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET

35、 (E) T( int(School of Information and Software EngineeringZhou, Erqiang62以含有以含有S A的状态开始的状态开始 S为文法开始符为文法开始符对每个状态进行如下计算对每个状态进行如下计算 1 1）如果状态里含有）如果状态里含有A B 则对每个产生式则对每个产生式B 将将B 加入到状态中加入到状态中 构建有限自动机School of Information and Software EngineeringZhou, Erqiang63对每个状态进行如下计算对每个状态进行如下计算 2 2）重复下面操作直到没新状态产生）重复下面操

36、作直到没新状态产生 如果如果状态状态m m中有中有A x 且且状态状态n n中有中有A x 那么在状态那么在状态m m与状态与状态n n之间之间 加入转移条件加入转移条件 x构建有限自动机School of Information and Software EngineeringZhou, Erqiang64句柄在什么位置？句柄在什么位置？ 句柄在栈顶！句柄在栈顶！如何找出句柄？如何找出句柄？ 构建自动机！构建自动机！如何确认句柄？如何确认句柄？ 当发现一个可能的句柄，当发现一个可能的句柄， 如何知道该句柄是正确或错误的？如何知道该句柄是正确或错误的？自动机与句柄School of Infor

37、mation and Software EngineeringZhou, Erqiang65自动机告诉我们句柄已经出现自动机告诉我们句柄已经出现 但我们需要对此进行确认但我们需要对此进行确认算法算法1 1：LRLR（0 0） L: L: 从左向右对串进行扫描从左向右对串进行扫描 R: R: 最右推导最右推导 0: 0: 不检查输入串，直接预测不检查输入串，直接预测句柄识别School of Information and Software EngineeringZhou, Erqiang66LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T

38、 int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T) intint+(int+int;);(School of Information and Software EngineeringZhou, Erqiang67LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T

39、 int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T) intint+(int+int;);T(School of Information and Software EngineeringZhou, Erqiang68LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) )

40、+(int+int;);TTint(School of Information and Software EngineeringZhou, Erqiang69LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) ) +(int+int;);TTint(School of Information and Software Engin

41、eeringZhou, Erqiang70LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) ) +(int+int;);TTint(School of Information and Software EngineeringZhou, Erqiang71LR(0)分析方法S EE T + EE T ;T intT (E)S E

42、E T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) ) +(int+int;);TTint(TSchool of Information and Software EngineeringZhou, Erqiang72LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE

43、 T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) ) +(+int;);TTint(TSchool of Information and Software EngineeringZhou, Erqiang73LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)

44、ET (E) ) +(+int;);TTint(TSchool of Information and Software EngineeringZhou, Erqiang74LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) ) +(+int;);TTint(TTSchool of Information and Software

45、 EngineeringZhou, Erqiang75LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) ) +(+;);TTint(TT归约后，重启自动机归约后，重启自动机如何改进？如何改进？School of Information and Software EngineeringZhou, Erqiang76记录自动机上一

46、次状态记录自动机上一次状态 归约后，不重启自动机归约后，不重启自动机 而是从上一次状态开始识别而是从上一次状态开始识别LR(0)分析方法优化School of Information and Software EngineeringZhou, Erqiang77LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( intin

47、t+(int+int;);(01234567890School of Information and Software EngineeringZhou, Erqiang78LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( intint+(int+int;);(01234567890T3 9School of Inform

48、ation and Software EngineeringZhou, Erqiang79LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+(int+int;);(012345678903T5School of Information and Software EngineeringZhou, Erqiang80

49、LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+(int+int;);(012345678903T58School of Information and Software EngineeringZhou, Erqiang81LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE

50、T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+(int+int;);(012345678903T58T3 9School of Information and Software EngineeringZhou, Erqiang82LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; T

51、E T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+(int+int;);(012345678903T58T35School of Information and Software EngineeringZhou, Erqiang83LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT

52、 (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+(int+int;);(012345678903T58T35T3 9School of Information and Software EngineeringZhou, Erqiang84LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T

53、( int+(+;);(012345678903T58T35T3EE742School of Information and Software EngineeringZhou, Erqiang85LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S EET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+();(012345678903T58T E7T36ESchool

54、of Information and Software EngineeringZhou, Erqiang86LR(0)分析方法S EE T + EE T ;T intT (E)S EE T+EE T;T (E)T int开始开始S ET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int+;(012345678903T5T3EE S421School of Information and Software EngineeringZhou, Er

55、qiang87LR(0)分析方法如何表示？分析方法如何表示？ 两个表：两个表：actionaction表表 与与 gotogoto表表actionaction表将表将 状态状态, , 终结符终结符 映射为：移进、归约、接受、报错映射为：移进、归约、接受、报错gotogoto表将表将 状态状态, , 归约后归约后非终结符非终结符 映射为：状态转移映射为：状态转移LR(0)分析方法School of Information and Software EngineeringZhou, Erqiang88LR(0)分析方法状状态态actiongotoint+;()#ET01234567891): S

56、E2): E T + E3): E T ;4): T int5): T (E)School of Information and Software EngineeringZhou, Erqiang89LR(0)分析方法1): S E2): E T + E3): E T ;4): T int5): T (E)ES EE T+EE T;T (E)T int开始开始S ET int intE T+EE T; TE T;E T+EE T+EE T;T (E)T int+E T+E ETintT (E)E T+EE T;T (E)T int(T (E)ET (E) T( int(0123456789Sc

57、hool of Information and Software EngineeringZhou, Erqiang90LR(0)分析方法状态状态actiongotoint+;()#ET0s9s8131acc2r2r2r2r2r2r23s5s44r3r3r3r3r3r35s9s8236r5r5r5r5r5r57s68s9s8739r4r4r4r4r4r41): S E2): E T + E3): E T ;4): T int5): T (E)School of Information and Software EngineeringZhou, Erqiang91LR分析器结构驱动程序驱动程序分析

58、表分析表输入串输入串分析栈分析栈输出输出actiongotos0.sm-1sma1ai.b0.bm-1bm符符号号栈栈状状态态栈栈School of Information and Software EngineeringZhou, Erqiang92LR分析器结构分析栈分析栈 符号栈：存放已识别符号符号栈：存放已识别符号 状态栈：状态信息，隐含分析历史状态栈：状态信息，隐含分析历史初始时初始时 符号栈：符号栈： # 状态栈状态栈 ：0School of Information and Software EngineeringZhou, Erqiang93LR分析器结构分析表之分析表之Acti

59、on表表 状态状态与与终结符终结符的二维矩阵的二维矩阵actions, a 状态为状态为s ，输入符号为，输入符号为 a 时的动作时的动作 移进、归约、接受、出错移进、归约、接受、出错移进：移进：actions, a = sj 状态状态 j j 进栈，进栈，符号符号 a a 进栈进栈 指针指向下一符号指针指向下一符号School of Information and Software EngineeringZhou, Erqiang94LR分析器结构归约：归约：actions, a = rj 按第按第j j个产生式个产生式A归约归约 分析栈中分析栈中| | | |个状态个状态出栈出栈 如果当前

60、栈顶状态为如果当前栈顶状态为i, i, 则根据则根据i及及A, , 查查goto表表, , 并将状态并将状态gotoi,A=k压入栈压入栈School of Information and Software EngineeringZhou, Erqiang95LR分析器结构接受：接受：actions, # = acc 结束分析结束分析, ,输入串被接受输入串被接受出错：出错：actions, a或或gotos, A为空为空 转出错处理程序转出错处理程序School of Information and Software EngineeringZhou, Erqiang96LR分析器结构分析表之