编译原理课件ch06.pptVIP

1 1 cdNe# 1.为什么要引进优先函数？ 用算符优先分析法，如果文法有n个结符时，需要用(n+1)2 　个内存单元 在实际应用中，往往用优先函数来代替优先矩阵表示优先 关系，只需要2(n+1)个内存单元存放优先函数值 五.优先函数 2.优先函数定义：　 　可以定义两个函数f，g满足如下条件： 当a　　b则令f(a)=g(b) 当a　　b则令f(a)g(b) 当a　　b则令f(a)g(b) 　　对f，g我们称它为优先函数，它的值用整数表示 ＝ . . . 3.优先函数构造方法： （1）由定义直接构造优先函数（也叫Floyd方法） ①对每个终结符a∈VT(包括＃号在内)令f(a)=g(a)=1(也可以 　是其它整数) ②对每一终结符对逐一比较 如果a　　b，而f(a) ≤g(b)则令f(a)=g(b)+1 如果a　　b，而f(a) ≥g(b)则令g(b)=f(a)+1 如果a　　b，而f(a) ≠g(b)则令min{f(a),g(b)}=max{f(a),g(b)} 重复②直到过程收敛。如果重复过程中有一个值大于2n，则 　表明该算符优先文法不存在算符优先函数 ＝ . . . # ) ( i ↑ * + # ) ( i ↑ * + ＝ . ＝ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 例如：若已知表达式文法的算符优先矩阵如下表所示，按上 述规则构造它的优先函数 f g 首先把所有f(a) ，g(a)的值置为1，如表6.9中的初值（0次迭 　代） 然后对算符优先关系矩阵逐行扫描，按前述步骤②的规则修 改函数f(a)，g(a)的值，这是个迭代过程，一直进行到优先 函数的值再无变化为止 表达式文法优先函数计算过程： g f g f g f g f 0 # ) ( i ↑ * + 迭代次数 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 4 6 1 6 1 2 3 5 5 5 1 1 1 2 3 3 5 5 7 1 7 1 2 4 6 6 6 1 1 与第2次迭代结果相同 第一次迭代过程： # ) ( i ↑ * + # ) ( i ↑ * + ＝ . ＝ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . f g g=1 g=1 g=1 g=1 g=1 g=1 g=1 f=1 f=1 f=1 f=1 f=1 f=1 f=1 f= 2 g= 3 g= 3 g= 3 g= 3 f= 2 f= 4 g= 5 g= 5 g= 5 f= 2 f= 4 f= 2 f= 4 f= 6 g= 2 f= 3 f= 4 f= 6 第二次迭代过程： # ) ( i ↑ * + # ) ( i ↑ * + ＝ . ＝ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . f g g=2 g=3 g=5 g=5 g=5 g=1 g=1 f=2 f=4 f=4 f=6 f=1 f=6 f=1 f= 3 g= 4 f= 5 g= 6 g= 6 g= 6 f= 5 f= 7 f= 7 第三次迭代过程： # ) ( i ↑ * + # ) ( i ↑ * + ＝ . ＝ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . f g g=2 g=4 g=6 g=6 g=6 g=1 g=1 f=3 f=5 f=5 f=7 f=1 f=7 f=1 对优先函数每个元素的值都增加同一个常数，优先关系不 变，因而，对同一个文法的优先关系矩阵对应的优先函数 不唯一 也有一些优先关系矩阵中的优先关系是唯一的，却不存在 　优先函数，例如下面优先关系矩阵： b a b a . ＝ . ＝ . ＝ . 由矩阵第一行：f(a)=g(a) ,f(a)g(b) 由矩阵第二行：f(b)=g(a) ,f(b)=g(