1、自底向上的语法分析,4.5,1. 移进归约的概念,4.4 自下而上分析,4.4.1 归约例S aABe A Abc | bB d,4.4 自下而上分析,4.4.1 归约例S aABe A Abc | bB dabbcde（读入ab）,4.4 自下而上分析,4.4.1 归约例S aABe A Abc | bB dabbcdeaAbcde（归约）,4.4 自下而上分析,4.4.1 归约例S aABe A Abc | bB dabbcdeaAbcde（再读入bc）,4.4 自下而上分析,4.4.1 归约例S aABe A Abc | bB dabbcdeaAbcdeaAde（归约）,4.4 自下而上
2、分析,4.4.1 归约例S aABe A Abc | bB dabbcdeaAbcdeaAde（再读入d）,4.4 自下而上分析,4.4.1 归约例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABe（归约）,4.4 自下而上分析,4.4.1 归约例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABe(再读入e),4.4 自下而上分析,4.4.1 归约例S aABe A Abc | bB dabbcdeaAbcdeaAdeaABeS（归约）,4.4 自下而上分析,4.4.1 归约例S aABe A Abc | bB dabbcdeaAbcde
3、aAdeaABeS S rm aABe rm aAde rm aAbcde rm abbcde,4.4 自下而上分析,4.4.2 句柄句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符代表了最右推导过程的逆过程的一步S aABe A Abc | bB dS rm aABe rm aAde rm aAbcde rm abbcde句柄的右边仅含终结符如果文法二义，那么句柄可能不唯一,4.4 自下而上分析,例句柄不唯一E E + E | E E | (E ) | id,4.4 自下而上分析,例句柄不唯一E E + E | E E | (E ) | idE rm E E rm
4、 E E + E rm E E + id3 rm E id2 + id3 rm id1 id2 + id3,4.4 自下而上分析,例句柄不唯一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. 用栈实现移进归约,用栈实现移进归约分析,移进把下一个输入符号移进栈归约分析器知道句柄的右端已在栈顶，然
5、后确定句柄的左端在栈中的位置，再决定用什么样的非终结符代替句柄接受分析器宣告分析成功报错分析器发现语法错误，调用错误恢复例程,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 自下而上分析,4.4 自下而上分析,4.4 自下而上分析,4.4 自下而上分析,4.4 自下而上分析,4.4 自下
6、而上分析,4.4 自下而上分析,4.4 自下而上分析,4.4 自下而上分析,4.4 自下而上分析,4.4 自下而上分析,4.4 自下而上分析,4.4 自下而上分析,3. 移进归约的冲突,4.4 自下而上分析,要想很好地使用移进归约方式，尚需解决一些问题如何决策选择移进还是归约进行归约时，确定右句型中将要归约的子串进行归约时，如何确定选择哪一个产生式,4.4 自下而上分析,4.4.4 移进归约分析的冲突 1、移进归约冲突例stmt if expr then stmt | if expr then stmt else stmt | other如果移进归约分析器处于格局栈输入 if expr the
7、n stmtelse $,4.4 自下而上分析,2、归约归约冲突stmt id (parameter_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 = exprp
8、arameter_list parameter_list, parameter | parameterparameter 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 | parameterparam
9、eter idexpr id (expr_list) | idexpr_list expr_list, expr | expr由A(I, J)开始的语句(词法分析查符号表,区分第一个id)栈输入 procid ( id, id ),4. LR分析器,4.5 LR分析器,本节介绍LR(k)分析技术特点适用于一大类上下文无关文法效率高主要介绍构造LR分析表的三种技术简单的LR方法（简称SLR）规范的LR方法向前看的LR方法（简称LALR）,4.5 LR分析器,4.5.1 LR分析算法,LR语法分析算法实例：图4.37(1) E E + T (2) E T (3) T T F (4) T F(5)
10、F ( E ) (6) F id,LR语法分析,si：表示移进并将状态i压栈。rj：表示按照编号为j的产生式进行归约。Acc：表示接受。空白：表示出错。,LR语法分析,4.5 LR分析器,4.5.2 LR文法和LR分析方法的特点1、概念可行前缀：右句型的前缀，该前缀不超过最右句柄的右端S *rm A w rm w 的任何前缀（包括和 本身）都是可行前缀,4.5 LR分析器,4.5.2 LR文法和LR分析方法的特点1、概念可行前缀：右句型的前缀，该前缀不超过最右句柄的右端2、定义LR文法：我们能为之构造出所有条目都唯一的LR分析表,4.5 LR分析器,3、LR分析方法的特点栈中的文法符号总是形成
11、一个可行前缀,4.5 LR分析器,4.5 LR分析器,3、LR分析方法的特点栈中的文法符号总是形成一个可行前缀分析表的转移函数本质上是识别可行前缀的DFA,4.5 LR分析器,例E E + T | E T 下表绿色部分构成 T T F | T E识别可行前缀DFA的 F (E ) | F id状态转换表,4.5 LR分析器,3、LR分析方法的特点栈中的文法符号总是形成一个可行前缀分析表的转移函数本质上是识别可行前缀的DFA栈顶的状态符号包含了确定句柄所需要的一切信息,4.5 LR分析器,4.5 LR分析器,3、LR分析方法的特点栈中的文法符号总是形成一个可行前缀分析表的转移函数本质上是识别可行
12、前缀的DFA栈顶的状态符号包含了确定句柄所需要的一切信息是已知的最一般的无回溯的移进归约方法能分析的文法类是预测分析法能分析的文法类的真超集能及时发现语法错误手工构造分析表的工作量太大,4.5 LR分析器,4、LR分析方法和LL分析方法的比较,4.5 LR分析器,4、LR分析方法和LL分析方法的比较,4.5 LR分析器,4、LR分析方法和LL分析方法的比较在下面的推导中，最后一步用的是A lS 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分析方法的比较,
