1、第六章 自下而上的语法分析清华大学计算机系1 自下而上语法分析概述 简单优先分析 算符优先分析2自下而上语法分析概述 As the name suggests, bottom-up parsing begins with a string and tries to backwards to the start symbol by applying the productions in reverse. 也称为移进 -归约分析自底向上的语法分析.VAR ；A BEGIN ENDREAD （ ）A VAR A; BEGIN READ(A) END.移进规约接受错误3自下而上语法分析概述 如名字如示
2、，自下而上语法分析试图将一个字符串反向归约至开始符号。 自下而上语法分析比自上而下语法分析更有效率，对语法的限制更少4文法 GS：(1) S aAcBe(2) A b(3) A Ab(4) B da b b c d e步骤 符号栈 输入符号串 动作1） # abbcde# 移进2） #a bbcde# 移进A3） #ab bcde# 归约 (A b)4） #aA bcde# 移进A5） #aAb cde# 归约 (A Ab)6） #aA cde# 移进7） #aAc de# 移进B8） # aAcd e# 归约 (B d)9） #aAcB e# 移进11） #S # 接受S10） #aAcBe
3、 # 归约 (S aAcBe)分析符号串 abbcde是否 GS的句子对输入串 abbcde#的移进 -规约分析过程SaAcBeaAcdeaAbcdeabbcde5自下而上语法分析算法的一般描述Let I = input stringrepeatpick a non-empty substring of Iwhere X is a productionif no such , backtrackreplace one by X in Iuntil I = “S” (the start symbol) or all possibilities are exhausted6算法应考虑的问题 算法是
4、否能够终止？ 算法是否快速？ 算法是否能够处理所有的情况？ 在每一步中如何选择子串进行归约？7 自下而上语法分析的策略：移进 -规约分析； 移进 就是将一个终结符推进栈 归约 就是将 0个或多个符号从栈中弹出，根据产生式将一个非终结符压入栈 移进 -归约过程是自顶向下最右推导的逆过程（规范归约）8规约 T intT + int | 移进T + | int移进int | * int + int移进int * | int + int移进|int * int + intE |规约 E T + ET + E |规约 E TT + T |移进T | + int规约 T int * Tint * T | + int规约 T intint * int | + int文法 GE：E T + E | TT int * T | int | (E)ET E+ int*intTintT9A Shift-Reduce Parse in Detail (1)+ int*int int|int * int + int10
