第6章 自底向上优先分析(10月14日修改).ppt

* 第6章 自底向上优先分析 Page * 本章小结 自底向上思想 从输入符号串开始，利用文法的产生式逐步进行归约，试图归约到文法开始符号 算符优先分析法 应用于算符优先文法 构造算符优先关系表和算符优先关系函数 算符优先分析 * Page * 第6章 自底向上优先分析 练习 1. G[B]是算符优先文法吗？ 2. 若G[B]是算符优先文法，请给出输入串ntofat#的分析过程。 已知布尔表达式文法G[B]为： B→BoT|T T→TaF|F F→nF| B |t|f 思路： 1、求FIRSTVT集和LASTVT集，构造算符优先矩阵 2、根据优先矩阵判断是否为算符优先文法 3、若是，根据优先矩阵进行算符优先分析 怎么判断是否为算符优先文法？ 算符优先矩阵！ * Page * 第6章 自底向上优先分析 G[B]： B→BoT|T T→TaF|F F→nF| B |t|f FIRSTVT F ， ， ， FIRSTVT T ， ， ， ， FIRSTVT B ， ， ， ， ， n t f a n t f a n t f o LASTVT F ， ， ， LASTVT T ， ， ， ， LASTVT B ， ， ， ， ， n t f a n t f a n t f o * Page * 第6章 自底向上优先分析 G[B]的算符优先关系矩阵 关系： 由F→ B 得： 由B’ →#B#得：# # o a n t f # o a n t f # G[B]： B→BoT|T T→TaF|F F→nF| B |t|f B’ →#B# * Page * 第6章 自底向上优先分析 FIRSTVT B o, a, n, , t, f FIRSTVT T a, n, , t, f FIRSTVT F n, , t, f o a n t f # o a n t f # G[B]：B→BoT|T T→TaF|F F→nF| B |t|f B’ →#B# 关系： 由oT o FIRSTVT T 由aF a FIRSTVT F 由nF n FIRSTVT F 由 B FIRSTVT B 由#B # FIRSTVT B * Page * 第6章 自底向上优先分析 LASTVT B o, a, n, , t, f LASTVT T a, n, , t, f LASTVT F n, , t, f o a n t f # o a n t f # G[B]：B→BoT|T T→TaF|F F→nF| B |t|f B’ →#B# 关系： 由Bo LASTVT B o 由Ta LASTVT T a 由B LASTVT B 由B# LASTVT B # 由优先关系表可知，终结符之间的优先关系是唯一的，所以G[B]是算符优先文法。 * Page * 第6章 自底向上优先分析 # f t n a o # f t n a o 步骤 符号栈 当前符号 剩余输入串 移进或归约 1 # n tofat# 移进 2 #n t ofat# 移进 3 #nt o fat# 归约F?t 4 #nN o fat# 归约F?nF 5 #N o fat# 移进 6 #No f at# 移进 7 #Nof a t# 归约F?f 优先关系 # n n o n o # o o a * Page * 第6章 自底向上优先分析 # f t n a o # f t n a o 步骤 符号栈 当前符号 剩余输入串 移进或归约 8 #NoN a t# 移进 9 #NoNa t # 移进 10 #NoNat # 归约F?t 11 #NoNaN # 归约T?TaF 12 #NoN # 归约B?BoT 13 #N # 分析成功 优先关系 o a a # a # o # # # * 第6章 自底向上优先分析 Page * 6.3.3 算符优先关系表的构造 最左终结符集FIRSTVT FIRSTVT B b|B?+ b… 或 B?+Cb… ，其中b∈VT, B,C∈VN ε 不属于FIRSTVT 直观上说FIRSTVT B 是由B推导出的最左终结符 允许左边有一个非终结符 的集合。 与FIRST ? a ?VT | ??* a 对照 文法符号串?的开始符号集是由?推导出的开头的终结符（包括ε）组成 * 第6章 自底向上优先分析 Page * 6.3.3 算符优先关系表的构造 例文法： E→E+T|T T→T×F|F F→ E |i