第4章语法分析自底向上分析方法算符优先分析

1、编译原理 (Principle of Compiler)王 荣 波Email: Tel: Office: 一教5012第四章 语法分析语法分析器概述语法分析-自顶向下分析(预测分析器)语法分析-自底向上分析算符优先分析法LR分析器34.3 自底向上分析自底向上分析：从叶子到根来建立句子的分析树。或，给出一个从句子出发到开始符号的归约序列44.3 自底向上分析例：文法 G：E T + E | TT int * T | int | (E)ETE+int*intTintT句子:54.3 自底向上分析步骤 (1)+int*intint|int * int + int64.3 自底向上分析步骤 (2)+

2、int*intint|int * int + intint | * int + int74.3 自底向上分析步骤 (3)+int*intint|int * int + intint | * int + intint * | int + int84.3 自底向上分析步骤 (4)+int*intint|int * int + intint | * int + intint * | int + intint * int | + int94.3 自底向上分析步骤 (5)+int*intint|int * int + intint | * int + intint * | int + intint *

3、int | + intint * T | + intT104.3 自底向上分析步骤 (6)+int*intint|int * int + intint | * int + intint * | int + intint * int | + intint * T | + intTT | + intT114.3 自底向上分析步骤 (7)+int*intint|int * int + intint | * int + intint * | int + intint * int | + intint * T | + intTT | + intTT + | int124.3 自底向上分析步骤 (8)+i

4、nt*intint|int * int + intint | * int + intint * | int + intint * int | + intint * T | + intTT | + intTT + | intT + int | 134.3 自底向上分析步骤 (9)+int*intint|int * int + intint | * int + intint * | int + intint * int | + intint * T | + intTT | + intTT + | intT + int | T + T | T144.3 自底向上分析步骤 (10)+int*intin

5、tint * int | + intint * T | + intTT | + intTT + | intT + int | T + T | TT + E | E154.3 自底向上分析步骤 (11)+int*intintint * int | + intint * T | + intTT | + intTT + | intT + int | T + T | TT + E | EE | E164.3 自底向上分析注：右句型（规范句型）：最右推导得到的句型每一步都是将右句型的最左可归约串（句柄）归约为产生式的左部符号输出的是一个产生式序列应用这个产生式序列对句子进行一个规范归约，或应用这个产生式

6、序列的逆序列作一个最右推导，可以同时构造句子的分析树。分析过程是寻找一个（最左）归约序列的过程174.3 自底向上分析自底向上分析法，又称为移进-归约法，它的实现思想：对输入符号串自左向右进行扫描，并将输入符逐个移入一个先进后出栈中，边移进边分析，一旦栈顶符号串形成某个句型的可归约串时，就用相应产生式的左部非终结符代替此可归约串。重复这一过程，直到归约到栈中只剩下文法的开始符号时分析成功。18文法GS：(1) S aAcBe(2) A b(3) A Ab(4) B dabbcde步骤符号栈输入符号串动作 1） $ abbcde$ 移进 2） $ a bbcde $ 移进A 3） $ ab bc

7、de $ 归约(Ab) 4） $ aA bcde $ 移进A 5） $ aAb cde $ 归约(AAb) 6） $ aA cde $ 移进 7） $ aAc de $ 移进B 8） $ aAcd e $ 归约(Bd) 9） $ aAcB e $ 移进11） $ S $ 接受S10） $ aAcBe $ 归约(SaAcBe)对输入串abbcde#的移进-规约分析过程SaAcBeaAcdeaAbcdeabbcde194.3 自底向上分析自底向上分析法的关键问题是：在右句型中寻找可归约串（对于规范归约来说是寻找句柄）不同的寻找可归约串的方法就形成了不同的自底向上分析法20第四章 语法分析语法分析器

8、概述语法分析-自顶向下分析(预测分析器)语法分析-自底向上分析算符优先分析法LR分析器214.4 算符优先分析算符文法：算符文法 G 中不含形如 A A BC 的产生式在算符文法中，任何句型都不包含两个相邻的非终结符号224.4 算符优先分析算符优先关系：设 G 是一个算符文法，a、b是两个终结符号， a、b之间的优先关系定义如下：1、a b（a、b的优先级相等） 当且仅当G 中含有形如 A ab或 A aBb的产生式234.4 算符优先分析2、a b（a的优先级大于b） 当且仅当 G中含有形如 A Bb的产生式，且有 B a 或 B aC244.4 算符优先分析算符优先文法：如果一个算符文法

9、 G 的任意两个终结符号之间最多只有、 、三种关系的一种成立，则称 G 为算符优先文法。254.4 算符优先分析算符优先关系表的构造由定义直接构造通过计算 FIRSTVT 集与 LASTVT 集构造264.4 算符优先分析FIRSTVT(B)= b | B b或 B Cb 对于非终结符 B，其往下推导所可能出现的首个算符（终结符号）LASTVT(B)= a | B a或 B aC 对于非终结符 B，其往下推导所可能出现的最后一个算符274.4 算符优先分析1） “ ”关系 直接看产生式的右部，若有 A ab 或 A aBb,则a b2） “”关系 求出每个非终结符 B 的 FIRSTVT(B)

10、 若 AaB,则 bFIRSTVT(B),a”关系 求出每个非终结符 B 的 LASTVT(B) 若 ABb,则 aLASTVT(B),ab294.4 算符优先分析例:文法GE：(0) E$E$(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF | P(6) P(E)(7) PiFIRSTVT(E)= $ FIRSTVT(E)= + , * , , ( , i FIRSTVT(T)= * , , ( , i FIRSTVT(F)= , ( , i FIRSTVT(P)= ( , i LASTVT(E)= $ LASTVT(E)= + , * , , ) , i LASTVT

11、(T)= * , , ) , i LASTVT(F)= , ) , i LASTVT(P)= ) , i 304.4 算符优先分析例:文法GE：(0) E$E$(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF | P(6) P(E)(7) Pi1) “ = ”关系 由产生式(0)和(6),得: $ $，（ ）2）“ ”关系 找形如：AaB的产生式 $E: 则 $ FIRSTVT(E) +T: 则 + FIRSTVT(T) *F: 则 * FIRSTVT(F) F: 则 FIRSTVT(F) (E: 则 ( ”关系 找形如：ABb的产生式 E$：则 LASTVT(E) $

12、E+：则 LASTVT(E) + T*：则 LASTVT(T) * P：则 LASTVT(P) E)：则 LASTVT(E) )324.4 算符优先分析例:文法GE：(0) E$E$(1) EE+T(2) ET(3) TT*F(4) TF(5) FPF | P(6) P(E)(7) Pi算符优先关系表334.4 算符优先分析算符优先关系的性质： a a ，a b 也不一定意味着 b a，且 a b、a b 可能一个也不成立 * a 和 b 之间的优先关系与 b 和 a 之间的优先关系是根本不同的。344.4 算符优先分析例子：P81 文法( 4.12 )该文法不是算符优先文法由于文法的简单直观

13、性，在实际使用中往往人为地给出此文法的算符优先关系，用此文法来分析表达式354.4 算符优先分析算符优先分析的基本思想：利用算符优先关系来寻找可归约串算法：P 84364.4 算符优先分析设置 ip , 使之指向 w$ 的第一个符号;repeat 令 a 是栈顶终结符号并且 b 是 ip 所指向的符号; if ( a b ) then repeat 从栈中弹出符号 until 栈顶终结符号 最近弹出的终结符号 else error() until 栈顶终结符号 = $ 并且 ip 指向 $374.4 算符优先分析例子：用例子文法分析 id + id步骤栈优先关系当前符号剩余串动作1$+id$归

14、约（Nid）3$N+id$移进4$N+$归约（Nid）6$N+N $归约（NN+N）7$N$接受384.4 算符优先分析注：由于在归约过程中，只考虑终结符之间的优先关系来确定可归约串，而与非终结符无关，这样去掉了单非产生式（A B）的归约，所以算符优先分析法的规约过程与规范归约是不同的输出的是一个产生式的序列，将此产生式序列逆序推导得到一个分析树的基架394.4 算符优先分析+EEididTFFT分析树+NNididN分析树基架最左素短语：id、id、F+F404.4 算符优先分析注：算符优先分析中的可归约串是最左素短语只能判断句子是否是给定文法的句子，不能给出完整的分析树414.4 算符优先

15、分析优先函数：在实现算符优先分析时，往往不用算符优先关系表，而是用两个优先函数 f 和 g ：当 ab 时，f(a)b 时，f(a)g(b) 424.4 算符优先分析例子：P 87优先函数的优点：节约存储空间；便于执行比较运算 优先函数的缺点：损失了错误检测能力；并不是每个优先关系表都存在优先函数 434.4 算符优先分析例子：P 87 例4.13f*fidf+f$gidg+g*g$444.4 算符优先分析算符优先分析法的出错处理 ：算符优先分析时在两种情况下发现错误：1、栈顶终结符号与当前输入符号无优先关系2、归约时没有产生式的右部与可归约串匹配454.4 算符优先分析情况 2 的处理：若包含+、-、*、/、的可归约串被归约，检查两端是否出现非终结符号（E，表达式），若否，出错，输出“缺少运算对象”若归约 id，检查两端是否出现非终结符号，若有，出错，输出“缺少运算符号”若归约（），检查括号之间是否有一个非终结符号，若无，出错，输出“括号之间无表达式”464.4 算符优先分析情况 1 的处理：e1 $ ：插入 id ，输出信息“缺少运算对象”在优先关系表的空白处填入错误处理子程序的入口指针e2 $） ：删除），输出