自底向上的语法分析学习培训课件.ppt

1、自底向上的语法分析4.51.移进归约的概念4.4 自下而上分析自下而上分析 4.4.1 归约归约例例 S aABe A Abc|bB d4.4 自下而上分析自下而上分析 4.4.1 归约归约例例 S aABe A Abc|bB dabbcde（读入（读入ab）ab4.4 自下而上分析自下而上分析 4.4.1 归约归约例例 S aABe A Abc|bB dabbcdeaAbcde（归约）（归约）abA4.4 自下而上分析自下而上分析 4.4.1 归约归约例例 S aABe A Abc|bB dabbcdeaAbcde（再读入（再读入bc）abAbc4.4 自下而上分析自下而上分析 4.4.1

2、归约归约例例 S aABe A Abc|bB dabbcdeaAbcdeaAde（归约）（归约）abAbAc4.4 自下而上分析自下而上分析 4.4.1 归约归约例例 S aABe A Abc|bB dabbcdeaAbcdeaAde（再读入（再读入d）abAbdAc4.4 自下而上分析自下而上分析 4.4.1 归约归约例例 S aABe A Abc|bB dabbcdeaAbcdeaAdeaABe（归约）（归约）abAbdAcB4.4 自下而上分析自下而上分析 4.4.1 归约归约例例 S aABe A Abc|bB dabbcdeaAbcdeaAdeaABe(再读入再读入e)eabAbdA

3、cB4.4 自下而上分析自下而上分析 4.4.1 归约归约例例 S aABe A Abc|bB dabbcdeaAbcdeaAdeaABeS（归约）（归约）SeabAbdAcB4.4 自下而上分析自下而上分析 4.4.1 归约归约例例 S aABe A Abc|bB dabbcdeaAbcdeaAdeaABeS S rm aABe rm aAde rm aAbcde rm abbcdeSeabAbdAcB4.4 自下而上分析自下而上分析 4.4.2 句柄句柄句型的句型的句柄句柄是和某产生式右部匹配的子串，并且，是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了把它归约成该

4、产生式左部的非终结符代表了最右推最右推导过程的逆过程的一步导过程的逆过程的一步S aABe A Abc|bB dS rm aABe rm aAde rm aAbcde rm abbcde句柄的句柄的右边仅含终结符右边仅含终结符如果文法二义，那么句柄可能不唯一如果文法二义，那么句柄可能不唯一4.4 自下而上分析自下而上分析 v例例 句柄不唯一句柄不唯一E E+E|E E|(E)|id4.4 自下而上分析自下而上分析 v例例 句柄不唯一句柄不唯一E E+E|E E|(E)|idE rm E E rm E E+E rm E E+id3 rm E id2+id3 rm id1 id2+id3 4.4

5、自下而上分析自下而上分析 v例例 句柄不唯一句柄不唯一E E+E|E E|(E)|idE rm E E E rm E+E rm E E+Erm E+id3 rm E E+id3rm E E+id3 rm E id2+id3 rm E id2+id3 rm id1 id2+id3 rm id1 id2+id3 在句型在句型E E+id3中，句柄不唯一中，句柄不唯一2.用栈实现移进归约用栈实现移进用栈实现移进 归约分析归约分析v移进把下一个输入符号移进栈v归约分析器知道句柄的右端已在栈顶，然后确定句柄的左端在栈中的位置，再决定用什么样的非终结符代替句柄v接受分析器宣告分析成功v报错分析器发现语法错

6、误，调用错误恢复例程4.4 自下而上分析自下而上分析 4.4.3 用栈实现移进用栈实现移进 归约分析归约分析先通过先通过移进移进 归约分析器在分析输入串归约分析器在分析输入串id1 id2+id3时时的动作序列的动作序列来了解移进来了解移进 归约分析的工作方式归约分析的工作方式4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上

7、分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 4.4 自下而上分析自下而上分析 3.移进归约的冲突4.4 自下而上分析自下而上分析 v要想很好地使用移进要想很好地使用移进 归约方式，尚需解决一归约方式，尚需解决一些问题些问题如何决策选择移进如何决策选择移

8、进还是还是归约归约进行归约时，确定右句型中将要归约的子串进行归约时，确定右句型中将要归约的子串进行归约时，如何确定选择哪一个产生式进行归约时，如何确定选择哪一个产生式4.4 自下而上分析自下而上分析 4.4.4 移进移进 归约分析的冲突归约分析的冲突 1、移进、移进 归约冲突归约冲突例例stmt if expr then stmt|if expr then stmt else stmt|other如果移进如果移进 归约分析器处于格局归约分析器处于格局栈栈输入输入 if expr then stmtelse$4.4 自下而上分析自下而上分析 2、归约、归约 归约冲突归约冲突stmt id(par

9、ameter_list)|expr=exprparameter_list parameter_list,parameter|parameterparameter idexpr id(expr_list)|idexpr_list expr_list,expr|expr由由A(I,J)开始的语句开始的语句栈栈输入输入 id(id,id)归约成归约成expr还还是是parameter?4.4 自下而上分析自下而上分析 2、归约、归约 归约冲突归约冲突stmt id(parameter_list)|expr=exprparameter_list parameter_list,parameter|par

10、ameterparameter idexpr id(expr_list)|idexpr_list expr_list,expr|expr由由A(I,J)开始的语句开始的语句(词法分析查符号表词法分析查符号表,区分第一个区分第一个id)栈栈输入输入 procid(id,id)需要修改上面的文法需要修改上面的文法4.4 自下而上分析自下而上分析 2、归约、归约 归约冲突归约冲突stmt procid(parameter_list)|expr=exprparameter_list parameter_list,parameter|parameterparameter idexpr id(expr_l

11、ist)|idexpr_list expr_list,expr|expr由由A(I,J)开始的语句开始的语句(词法分析查符号表词法分析查符号表,区分第一个区分第一个id)栈栈输入输入 procid(id,id)4.LR分析器4.5 LR分析器分析器 本节介绍本节介绍LR(k)分析技术分析技术v特点特点适用于一大类上下文无关文法适用于一大类上下文无关文法效率高效率高v主要介绍构造主要介绍构造LR分析表的三种技术分析表的三种技术简单的简单的LR方法（简称方法（简称SLR）规范的规范的LR方法方法向前看的向前看的LR方法（简称方法（简称LALR）4.5 LR分析器分析器 4.5.1 LR分析算法分析

12、算法输入输入LR分析程序分析程序输出输出 栈栈LR分析器的模型分析器的模型actiongotosmXmsm-1Xm-1s0a1aian$vLR语法分析算法实例：图4.37(1)E E+T(2)E T(3)T T F(4)T F(5)F (E)(6)F idLR语法分析 s si i：表示移进并将状态：表示移进并将状态i i压栈。压栈。r rj j：表示按照编号为：表示按照编号为j j的产生式进行归约。的产生式进行归约。AccAcc：表示接受。：表示接受。空白：表示出错。空白：表示出错。LR语法分析 4.5 LR分析器分析器 4.5.2 LR文法和文法和LR分析方法的特点分析方法的特点1、概念、

13、概念可行前缀：右句型的前缀，该前缀不超过最右可行前缀：右句型的前缀，该前缀不超过最右句柄的右端句柄的右端S *rm A w rm w 的任何前缀（包括的任何前缀（包括 和和 本身）都是可行前本身）都是可行前缀缀4.5 LR分析器分析器 4.5.2 LR文法和文法和LR分析方法的特点分析方法的特点1、概念、概念可行前缀：右句型的前缀，该前缀不超过最右可行前缀：右句型的前缀，该前缀不超过最右句柄的右端句柄的右端2、定义、定义LR文法文法：我们能为之构造出所有条目都唯一的我们能为之构造出所有条目都唯一的LR分析表分析表4.5 LR分析器分析器 3、LR分析方法的特点分析方法的特点栈中的文法符号总是形

14、成一个可行前缀栈中的文法符号总是形成一个可行前缀4.5 LR分析器分析器 4.5 LR分析器分析器 3、LR分析方法的特点分析方法的特点栈中的文法符号总是形成一个可行前缀栈中的文法符号总是形成一个可行前缀分析表的转移函数本质上是识别可行前缀的分析表的转移函数本质上是识别可行前缀的DFA4.5 LR分析器分析器 v例例 E E+T|E T 下表绿色部分构成下表绿色部分构成 T T F|T E识别可行前缀识别可行前缀DFA的的 F (E)|F id状态转换表状态转换表4.5 LR分析器分析器 3、LR分析方法的特点分析方法的特点栈中的文法符号总是形成一个可行前缀栈中的文法符号总是形成一个可行前缀分

15、析表的转移函数本质上是识别可行前缀的分析表的转移函数本质上是识别可行前缀的DFA栈顶的状态符号包含了确定句柄所需要的一切信息栈顶的状态符号包含了确定句柄所需要的一切信息4.5 LR分析器分析器 4.5 LR分析器分析器 3、LR分析方法的特点分析方法的特点栈中的文法符号总是形成一个可行前缀栈中的文法符号总是形成一个可行前缀分析表的转移函数本质上是识别可行前缀的分析表的转移函数本质上是识别可行前缀的DFA栈顶的状态符号包含了确定句柄所需要的一切信息栈顶的状态符号包含了确定句柄所需要的一切信息是已知的最一般的无回溯的移进是已知的最一般的无回溯的移进 归约方法归约方法能分析的文法类是预测分析法能分析

16、的文法类的真能分析的文法类是预测分析法能分析的文法类的真超集超集能及时发现语法错误能及时发现语法错误手工构造分析表的工作量太大手工构造分析表的工作量太大4.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较4.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较4.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较在下面的推导中，最后一步用的是在下面的推导中，最后一步用的是A l S rm rm A b w rm l b w LL(1)决定用该决定用该产生式的位置产生式的位置LR(1)决定用该决定用该产生式的位置产生式的位置4.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较4.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较4.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较4.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较4.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较4.5 LR分析器分析器 4、LR分析方法和分析方法和LL分析方法的比较分析方法的比较