有向图法 (即Bell方法)

构造优先函数的Floyd方法

无论是简单优先分析还是算符优先分析，都需要一个优先矩阵，用来指示各符号对间的优先关系。如果在编译程序工作时，把优先矩阵存放在内存中，则势必占用大量的存储空间。例如，对于一个100阶的优先矩阵，它的元素共有10 000个，而每一元素至少需用两个二进位表示 (因为每个符号对间都有4种可能的状态之一)，故存放这样的矩阵共需20 000个二进位，即2 500个字节。因此就很有必要寻找一种既反映符号对间的优先关系，而所需的存储空间又不太大的表示方法。

通常，解决上述问题的一个途径是根据所给的优先矩阵 (在下面的讨论中，我们将不对简单优先文法和算符优先文法加以区分，因为讨论所得的结论对两者都是适用的)，构造两个离散函数f和g，并用它们去代替原来的优先矩阵，此f和g把符号Si映射为自然数，且满足：

当Si<·Sj时，f(Si)<·g(Sj)

当Si=·Sj时，f(Si)=·g(Sj)

当Si>·Sj时，f(Si)>·g(Sj)

我们把f和g分别称为入栈优先函数和比较优先函数。显然，如果这样的函数能够构造出来，那么，在用优先分析法进行语法分析的过程中，每当需要查询一个符号对(Si,Sj)间的优先关系时，就只须比较f(Si)和g(Sj)的大小即可。这样一来，就把记录优先关系所需的存储空间由n2个单位压缩至2n个单位。因此，我们通常把上述做法称为优先矩阵的线性化。例如，对于算符优先文法G[E]的优先矩阵 (见图46)，经线性化之后，可得如下的优先函数。

[]+[]*[]([])[]i[]#f[]2[]4[]0[]4[]4[]0g[]1[]3[]5[]0[]5[]0

在介绍构造优先函数的具体方法之前，我们先指出下面的重要事实：

(1) 不是所有的优先矩阵都能线性化。例如，优先矩阵

[]S1[]S2[]S3S1[]>·[]<·S2[][]=·[]<·S3[]=·[][]=·

就不能线性化。这是因为，若假定优先函数f和g存在，则由上述矩阵所给出的优先关系，f和g应满足

f(S1)>g(S1)f(S3)=g(S1)f(S3)=g(S3)

f(S2)<g(S3)f(S2)=g(S2)f(S1)<g(S2)

但另一方面，从上述关系式可以推出

f(S1)>f(S1)

这就出现了矛盾，故可知满足上述关系的f和g并不存在。

(2) 对给定的优先矩阵而言，若优先函数存在，则必存在无穷多对，即优先函数不惟一。例如，对于文法G[E]，除上述优先函数之外，以下所示也是它的优先函数。

[]+[]*[]([])[]i[]#f[]3[]5[]1[]5[]5[]1g[]2[]4[]6[]1[]6[]1

(3) 当一个优先矩阵线性化后，就对每一符号都赋予了一对优先数。这样一来，对于那些原先不存在关系的符号对 (如G[E]中的符号对(i,i)等)，现在也可比较其优先数了，因而在语法分析过程中，就可能掩盖 (至少推迟发现)输入串中的语法错误。对此问题，需要通过其它语法检查手段来解决。

下面，我们介绍两种将优先矩阵线性化的方法。

有向图法 (即Bell方法)

设已给的优先文法G[S]有n个符号S1,S2,…,Sn (若G为简单优先文法，Si∈V∪{#}；若G为算符优先文法，则Si∈VT∪{#}，下同)，如果优先函数f,g存在，则可按如下的步骤来构造：

(1) 对于每一Si，分别作以fi和gi为标记的结点，并按下述方式构造以f1,f2,…,fn及g1,g2,…,gn为结点的有向图：

若有Si>·Sj或Si=·Sj，则从结点fi引一条至结点gi的矢线；若有Si<·Sj或Si=·Sj，则从结点gj引一条至结点fi的矢线。

(2) 对有向图中每一结点，我们都赋给一个整数，此整数就是从该结点出发，沿着矢线所能到达的结点个数 (包括出发结点在内)，赋给结点fi的整数就是函数值f(Si)；赋给结点gi的整数就是函数值g(Si)。

(3) 对所构造的函数f和g进行检验，若它们与原优先关系相容，则f和g即为所求的优先函数；否则，原优先矩阵就不能线性化。

构造优先函数的Floyd方法

对于给定的优先矩阵，如果它可以线性化，也可按下面的算法求出它的优先函数f和g。

1?首先，给f和g赋初值，即对每一符号Si，置

f(Si)=g(Si)=1(i=1,2,…,n)

2?进行迭代，即对每一符号对(Si,Sj)：

(1) 若Si>·Sj，但有f(Si)≤g(Sj)，则执行f(Si)=g(Sj)+1；

(2) 若Si<·Sj，但有f(Si)≥g(Sj)，则g(Sj)=f(Si)+1；

(3) 若Si=·Sj，但f(Si)≠g(Sj)，则令f(Si)和g(Sj)中的最小者等于其中的最大者。

3?重复步骤2，直到过程收敛为止。