29
优先函数构造： 优先函数构造：Bell方法 方法
编译原理
30
优先函数构造： 优先函数构造：Floyd方法 方法
编译原理
31
小结
i 简单优先分析方法
编译原理
– 简单优先关系矩阵计算 – 句柄的寻找
i 算符优先分析方法
– 算符优先关系计算 – 最左素短语的寻找
i 构造优先函数的两个方法
– Bell法和Floyd法
编译原理
编译原理
主 讲：温 璞 责任教师：蒋慧平
1
编译原理
第六讲
简单优先和算符 优先分析方法
2
本讲主要内容
编译原理
i 简单优先文法及其分析算法 i 算符优先文法及其分析算法 i 优先函数的构造
3
简单优先文法
编译原理
之所以称为简单是因为在可能称为句柄的那些符号 串两边各取一个符号就能帮助判断它是否是句柄
i 算符文法
编译原理
i 终结符之间存在的三种优先关系
9
编译原理
i 算符优先文法
10
例6.15
编译原理
文法G44[S]： E E+T|T T T*F|F F (E)|i
11
OPG优先关系的构造 优先关系的构造
i 定义如下集合
编译原理
i 它们的传递闭包定义如下
12
编译原理
13
编译原理
14
算法描述
4
简单优先分析算法描述
编译原理
5
例6.13 运用简单优先分析算法检查 ((a),a)是否是文法 42的一个句子 是否是文法G 是否是文法
文法G42[S]： S (R)|a|∧ R T T S,T|S
编译原理
6
编译原理
i 简单优先分析方法的局限性
– 只适用于简单优先文法 – 一般的程序设计语言不是简单优先文法 – 不实用，因为存在于两个符号之间的优先 关系常多于一种
接用前述的优先表，而是用两个优先函数f和 g. i 把每个终结符与两个自然数相对应
28
编译原理
i 使用优先函数优点
– 可减少优先矩阵的存储空间 – 便于比较运算
i 使用优先函数缺点
– 原先不存在优先关系的两个终结符，由于 与自然数相对应，变得可比较了。可能会 掩盖输入串的某些错误.i 优先函源自构造方法：Bell法和Floyd法
i 引入素短语概念替代简单优先关系中
的句柄概念，进行规约
19
素短语及句型的分析
编译原理
20
示例
编译原理
21
算符优先分析算法
编译原理
22
编译原理
23
编译原理
24
编译原理
25
编译原理 文法G44[S]： E E+T|T T T*F|F F (E)|i
26
编译原理
27
优先函数
编译原理
i 在实际实现算符优先分析算法时，一般不直
32
编译原理
The End. Thanks!
33
i 算符优先方法对以上情况有所改善
7
算符优先分析方法
i 算符优先分析方法
编译原理
– 根据算符之间的优先关系来设计的一种字 下而上语法分析方法 – 有利于表达式的分析 – 不是一种规范归约法 – 算符优先分析就是：定义算符之间（终结 符）的某种关系，借助于这种优先关系寻 找“可归约串”并进性归约
8
算符优先文法
编译原理
15
例6.16
文法G44[S]：E E+T|T T T*F|F F (E)|i
编译原理
16
文法G44[S]：E E+T|T T T*F|F 例6.16 F (E)|i
编译原理
17
编译原理
18
编译原理
i 由于未对非终结符定义算符优先关系，
所以不能使用算符优先关系去查找由 单个非终结符组成的句柄