“简单优先分析法”的意思、由来-中文百科全书

简单优先分析法是预先在文法的各种符号 (终结符号和非终结符号)之间建立所谓优先关系，而在分析一个句型 (指规范句型，下同)时，从左到右依次扫视其中的符号，且每扫视一个符号都检查它和后继符号间的优先关系，以期找到句柄之尾，然后再从此尾符号处回头，进行反向扫描，且每扫视一个符号都检查它和其前的符号间的优先关系，直到找到句柄之头为止。

下面，我们先介绍简单优先关系的定义和简单优先分析的算法，然后再给出为一个文法构造优先矩阵的算法。

简单优先关系的定义

设G=(VN，VT,P,S)是一已化简的文法，V=VN∪VT，并设Si和Sj是V中的任意两个符号，若G中存在这样的规范句型

α=…SiSj…

则此相邻的两个符号Si，Sj和α的句柄之间的关系必然是下述情况之一：

(1) 若Si在句柄中，而Sj不在句柄中 (如图42(a)所示)，则Si显然为句柄的尾符号，故G中必有形如A→…Si的产生式，使Si先于Sj被归约。此时，我们就说符号Si优于Sj，且记为Si>· Sj。此外，由于Sj出现在规范句型的句柄之右，故可知Sj必为终结符号。

(2) 若Si与Sj同时处于α的句柄之中 (如图42(b)所示)，则G中必有形如A→…SiSj…的产生式，使Si和Sj同时被归约。此时，我们就说Si和Sj有相同的优先关系，且记为Si=·Sj。

(3) 若Sj在句柄中，而Si不在句柄之中 (如图42(c)所示)，则Sj显然为句柄的头符号，故G中必有形如A→Sj…的产生式，使Sj先于Si被归约。此时就Si和Sj的优先关系而言，我们说Si低于Sj且记为Si<·Sj。

(4) 若Si和Sj均不在句型α的句柄之中，由于Si和Sj已相邻地在α中出现，则必有G的另一规范句型β，使Si和Sj在β中相邻地出现，且与β的句柄的关系有上述三种情况之一。然而，也可能有这样的情况，对G中的某些符号序偶(Sr,St)而言，G中并不存在任何使Sr和St相邻出现的句型，此时我们就说Sr和St间不存在任何优先关系。

应当指出，上面所引入的三种优先关系都是对文法中的符号序偶来定义的，它们都不具有对称性。即若Sr>· St，并不一定有St<·Sr；即使存在Sr=·St也不意味着St=·Sr必然存在。

定义了上述三种优先关系之后，我们便可给出所谓简单优先文法的定义如下。

定义4?1若一文法G的任何两个符号之间至多存在一种优先关系，且任意两个不同的产生式均无相同的右部，则称G为简单优先文法。

现在的问题是：对于一个给定的文法G来说，如何找出它的各个符号序偶间的优先关系?如何检验G是否为简单优先文法?显然，实质上这是同一问题的两个方面。因为，如果我们有办法找出G的各符号序偶间的优先关系，则第二个问题也就迎刃而解了。

继续考虑其它句型的语法树，我们就可得到G中的全部优先关系。通常，我们把一个文法的全部优先关系用一个矩阵来表示，称为优先矩阵。优先矩阵中的每一个元素P[i,j]指明序偶(Si,Sj)间的优先关系。当序偶(Sr,St)不存在优先关系时，相应的元素P[r,t]则为空白。从所得的优先矩阵可以看出，文法的各符号序偶间至多只有一种优先关系，故此文法为简单优先文法。

上面，我们通过查看文法的若干句型来构造优先矩阵。稍后我们还要介绍一种更为有效的构造优先矩阵的方法。

应当指出，我们之所以把具有上述性质的文法称为简单优先文法，是因为在进行语法分析时，为了寻找一个句型的句柄之头符号和尾符号，只须逐次查看相邻两个符号的优先关系即可。具体地说，也就是从左至右依次扫视句型中的符号X1X2…Xm，并在扫描过程中检查相邻两符号间的优先关系，一旦出现关系Xi+k>·Xi+k+1时，此Xi+k即为句柄的尾符号。然后再从Xi+k开始，从右至左逐个查看已扫过的符号，直到某相邻的两个符号间有优先关系Xi-1<·Xi时，此Xi为句柄的头符号。事实上，我们可以证明：对于简单优先文法的任何规范句型X1X2…Xm而言，它的句柄是该句型中，满足

Xi-1<·Xi

Xi=·Xi+1=·…=·Xi+k

Xi+k>·Xi+k+1

的最左子串XiXi+1…Xi+k。

据此，我们给出采用简单优先分析方法的识别程序如程序44所示。

程序 44简单优先分析驱动程序

#define SUCCESS1

#define ERROR0

#define MAXINPUT300

#define MAXSTACK100

#define STARTSYMBOL ′S′

int stack[MAXSTACK], a[MAXINPUT];

int IsHigherThan (int, int);/*prioriy detection*/

int IsLowerThan (int, int);/*prioriy detection*/

int RightSideOfAProduction (int begin, int end, int len);/*find production*/

int parscr (void)

{int i,k,r;

i=0; k=0;

stack[0]=′#′;

r=a[k++];

do {int j, LeftSide;

while (!IsHigherThan(stack[i],r))

{stack[++i]=r; r=a[k++];}

j=i;

while (!IsLowerThan (stack[j-1],stack[j]))j--;

LeftSide=RightSideOfAProduction (stack[j],stack[i],i-j+1);

if (LeftSide)

{/* LeftSide!=0 means the production exists*/

i=j; stack[i]=LeftSide;

}

else /*There is no production which matches the right side*/

if (i==2 && r==′#′ && stack[i]==STARTSYMBOL) return SUCCESS;

else return ERROR;

}while(1);

}/*end*/

对上述驱动程序所调用的一些函数的功能简述如下：

(1) 函数IsHigher()和IsLower()分别用来检测两个文法符号Si和Sj是否具有关系Si>·Sj和Si<·Sj，并根据关系成立与否分别回送值1和值0。

(2) 函数RightSideOfAProduction()用来在产生式集之中查找这样的产生式，其右部具有指定的头、尾符号及指定的长度，且与出现在栈顶的句柄相匹配，若找到则回送该产生式左部非终结符号的编号 (大于零的整数)，否则回送值0。

简单优先矩阵的构造方法

在上例中，为构造优先矩阵，我们首先为文法的若干句型构造相应的语法树，然后对每一语法树，考察它的直接子树中的末端结点，以确定有关符号对之间的优先关系，接着便剪去此直接子树的末端结点，并对剪枝后的语法树再重复上述过程，如此等等。显然，应用此种方法，有时我们需要考察足够多的语法树之后，才能把文法中的全部优先关系寻找出来。下面，我们再介绍一种确保一次求出全部优先关系的方法，此方法以布尔矩阵运算作为基础。

在给出构造简单优先矩阵的算法之前，我们先在文法G的字汇表V上，定义若干个二元关系，并据此重新定义上述三种优先关系。

定义4?2(关系LEAD)当且仅当G中存在形如A→B…的产生式时，有A LEAD B；当且仅当A?+B…时，A LEAD+B。

定义4?3(关系LAST)当且仅当G中存在形如A→…B的产生式时，有A LAST B；当且仅当A?+…B时，有A LAST+B。

定义4?4设R为一关系，我们将R的转置记为TRANSPOSE(R)，且定义为：当且仅当aRb时，b TRANSPOSE(R) a。

定义4?5当且仅当G中存在形如U→…SiSj…的产生式时，Si=·Sj。

定义4?6当且仅当G中存在形如

U→…SiW…(4?23)

的产生式，且

W?+Sj…(4?24)

时，有Si<·Sj。

由产生式(4?23)及定义4?5，可得

Si=·W

而由推导式(4?24)及定义4?2，又得到

WLEAD+Sj

从而可知，当且仅当

Si(=·)(LEAD)+Sj(4?25)

时，Si<·Sj。

定义4?7当且仅当G中存在形如

U→…W1W2…(4?26)

的产生式，且有

W1?+…Si(4?27)

及W2?*Sj…Sj∈VT(4?28)

时，Si>· Sj。

由产生式(4?26)、推导式(4?27)及(4?28)，有

W1=·W2W1 LAST+ SiW2 LEAD* Sj

(其中，LEAD*=I+LEAD+,I为恒等关系)上面第二个关系可改写为

Si TRANSPOSE(LAST+) W1

于是可知，当且仅当Sj∈VT，且

Si (TRANSPOSE(LAST+))(=·)(I+LEAD+) Sj(4?29)

时，有Si>· Sj，其中I为恒等关系。

现在以文法G：

S→AcA→ASA→AaA→b(4?30)

为例，介绍构造简单优先矩阵的算法。在此过程中，需要计算上面所定义的那些关系的布尔矩阵。这些布尔矩阵的阶数就是文法字汇表所含符号的个数。对于关系R的布尔矩阵，用记号BR表示，且对字汇表{S1,S2,…,Sn}中的两个符号Si和Sj，当且仅当SiR Sj时，BR[i,j]=1，否则BR[i,j]=0，对于文法(4?30)构造相应简单优先矩阵的步骤如下：

1?作布尔矩阵B=·，根据定义4?5，从文法(4?30)中的诸产生式可直接写出

B=·= S[]A[]a[]b[]c〖〗S

c0[]0[]0[]0[]0

1[]0[]1[]0[]1

0[]0[]0[]0[]0

2?作布尔矩阵B<·，为此

(1) 作布尔矩阵

BLEAD=0[]1[]0[]0[]0

0[]1[]0[]1[]0

0[]0[]0[]0[]0

(2) 由Warshall算法[11，17]，计算

BLEAD+=0[]1[]0[]1[]0

0[]1[]0[]1[]0

0[]0[]0[]0[]0

(3) 根据(4?25)，作

B<·=B=·BLEAD+=0[]0[]0[]0[]0

1[]0[]1[]0[]1

0[]0[]0[]0[]0

0[]0[]0[]0[]00[]1[]0[]1[]0

0[]1[]0[]1[]0

0[]0[]0[]0[]0

0[]0[]0[]0[]0=0[]0[]0[]0[]0

0[]1[]0[]1[]0

0[]0[]0[]0[]0

3?作布尔矩阵B>· ，为此

(1) 作布尔矩阵

BLAST=0[]0[]0[]0[]1

1[]0[]1[]1[]0

0[]0[]0[]0[]0

(2) 计算

BLAST+=0[]0[]0[]0[]1

1[]0[]1[]1[]1

0[]0[]0[]0[]0

(3) 作布尔矩阵

BTRANSPOSE(LAST+)=0[]1[]0[]0[]0

0[]0[]0[]0[]0

0[]1[]0[]0[]0

1[]1[]0[]0[]0

(4) 计算

B>·′=BTRANSPOSE(LAST+)B=·BLEAD*=0[]1[]0[]0[]0

0[]0[]0[]0[]0

0[]1[]0[]0[]0

1[]1[]0[]0[]00[]0[]0[]0[]0

1[]0[]1[]0[]1

0[]0[]0[]0[]0

0[]0[]0[]0[]01[]1[]0[]1[]0

0[]1[]0[]1[]0

0[]0[]1[]0[]0

0[]0[]0[]1[]0

0[]0[]0[]0[]1=

S[]A[]a[]b[]c

c1[]1[]1[]1[]1

0[]0[]0[]0[]0

1[]1[]1[]1[]1

(5) 由于在式(4?29)中Sj应为终结符号，故为了得到B>· ，必须在上步所求得的布尔矩阵B>·′ 中，将对应于非终结符号的列置零，于是有

B>· =0[]0[]1[]1[]1

0[]0[]0[]0[]0

0[]0[]1[]1[]1

4?对于所求的B=·,B<·及B>· ，检查如下等式

B=·∧B>·=B=·∧B<·=B>·∧B<·=0

是否成立。若是，则表明所构造的简单优先矩阵无多重定义的元素，因而所给文法为简单优先文法；否则，它就不是简单优先文法。最后，将布尔矩阵B=·、B>·及B<·所分别指出的优先关系组装到一个矩阵之中，便得到了所求的全部简单优先关系。对于本例，有

[]S[]A[]a[]b[]cS[4]>·[]>·[]>·A[]=·[]<·[]=·[]<·[]=·a[4]>·[]>·[]>·b[4]>·[]>·[]>·c[4]>·[]>·[]>·

简单优先分析的局限性

从前面的讨论已看到：上述优先分析技术简单易行，已有一套构造简单优先矩阵的形式化算法，从设计分析程序到具体地进行语法分析都可机械地进行。看来，它似乎是一种可靠和有效的方法，其实在应用上，它却有很大的局限性。这主要表现在对文法有较强的要求。因为对通常的文法而言，它的某些符号对之间的优先关系往往会多于一种，也就是说，所给的文法常常并非简单优先文法。特别是当文法具有左递归时，就往往会导致这种情况的发生。例如，当文法中同时含有形如

U→…SiSj…

及

Sj→Sj…

的产生式时，在符号Si和Sj之间，便同时有Si=·Sj及Si<·Sj两种关系。类似地，当文法具有右递归性时，关系=·及>· 也可能出现在同一符号对之间。

为避免上述矛盾，我们可在文法中引入一新的非终结符号W，而将上面的第一个产生式改写为如下两个产生式

U→…SiW…

W→Sj…

此时，优先关系Si=·Sj及Si<·Sj将为新的优先关系Si=·W及Si<·Sj所代替，从而就解决了上述矛盾。通常，将改写文法的这种方法称为分层法或析出法。

然而，应当指出，上述采用分层技术消除多重优先关系的尝试未必总能得到成功。例如，当Si和Sj间既有Si<·Sj也同时有关系Si>·Sj时，上述方法就不能奏效。有时也可能出现这样的情况，即旧的矛盾虽然解决了，但又引出新的矛盾。特别是对于一些规模较大，而所含矛盾又较多的文法，即使上述方法能够取得成功，为改写文法也十分费力。同时，由于改写文法所引入的一些单产生式，也将增加文法的复杂性和降低语法分析的效率，因此，当我们所面临的不是简单优先文法时，还是以选用另外的语法分析方法为宜。此处我们之所以要介绍这种分析方法，一则因为它比较简单；二则也是因为由它可较容易地过渡到其它更为有效的分析方法。

最后，我们再来分析一下简单优先分析之所以存在上述缺点的内在原因。

从简单优先文法的定义来看，在用这种方法进行分析时，为了识别一个句型的句柄，每次仅使用了句柄周围很少的符号进行判断，即每次只考察句型中相邻两符号的优先关系。可以想像，如果不再局限于相邻的两个符号，而是查看更多的符号，或者取另外的不相邻的符号进行考察，则发生上述矛盾的情况可能会得到改善，例如，为了确定句柄的尾符号，我们不仅要查看Si,Si+1，而且还查看Si-1，Si和Si+1，或者Si,Si+1及Si+2，甚至更多的符号 (如像后面介绍的LR(K)分析那样)。下面，不妨以文法G[E]中的句型E+T*F为例来说明此点。前面已经看到，G[E]不是一个简单的优先文法，但若按简单优先关系来考虑，就会出现下面的情况：

#<·E=·+=·

<·T*F#(4?31)

由于符号+和T之间同时存在优先关系+=·T及+<·T，若以前者为准，则+和T都应是句柄中的符号；若按后者，则T可能是句柄的头符号，而+决不会出现在句柄中，可见，仅根据相邻两个符号间的优先关系尚不足以判断T是否为句柄的头符号，或者说+是否在句柄中。但若除考虑+和T外，再向前查看一个符号，则当句型中出现+T*这样的结构时，由于乘法运算总是先于加法运算，所以+不可能在句柄之中；而当出现形如+T+的结构时，由于加法运算服从左结合规则，此时，最先归约的自然应是子串E+T，即T是句柄的尾符号。显而易见，上述这种决策实际上是根据运算符+和*或者+和+间的优先关系来作出的。于是，就自然启发我们考虑一种更为有效的分析方法——算符优先分析法。

词条	简单优先分析法
释义	简单优先关系的定义简单优先分析的算法简单优先矩阵的构造方法简单优先分析的局限性简单优先分析法是预先在文法的各种符号 (终结符号和非终结符号)之间建立所谓优先关系，而在分析一个句型 (指规范句型，下同)时，从左到右依次扫视其中的符号，且每扫视一个符号都检查它和后继符号间的优先关系，以期找到句柄之尾，然后再从此尾符号处回头，进行反向扫描，且每扫视一个符号都检查它和其前的符号间的优先关系，直到找到句柄之头为止。下面，我们先介绍简单优先关系的定义和简单优先分析的算法，然后再给出为一个文法构造优先矩阵的算法。简单优先关系的定义设G=(VN，VT,P,S)是一已化简的文法，V=VN∪VT，并设Si和Sj是V中的任意两个符号，若G中存在这样的规范句型 α=…SiSj… 则此相邻的两个符号Si，Sj和α的句柄之间的关系必然是下述情况之一： (1) 若Si在句柄中，而Sj不在句柄中 (如图42(a)所示)，则Si显然为句柄的尾符号，故G中必有形如A→…Si的产生式，使Si先于Sj被归约。此时，我们就说符号Si优于Sj，且记为Si>· Sj。此外，由于Sj出现在规范句型的句柄之右，故可知Sj必为终结符号。 (2) 若Si与Sj同时处于α的句柄之中 (如图42(b)所示)，则G中必有形如A→…SiSj…的产生式，使Si和Sj同时被归约。此时，我们就说Si和Sj有相同的优先关系，且记为Si=·Sj。 (3) 若Sj在句柄中，而Si不在句柄之中 (如图42(c)所示)，则Sj显然为句柄的头符号，故G中必有形如A→Sj…的产生式，使Sj先于Si被归约。此时就Si和Sj的优先关系而言，我们说Si低于Sj且记为Si<·Sj。 (4) 若Si和Sj均不在句型α的句柄之中，由于Si和Sj已相邻地在α中出现，则必有G的另一规范句型β，使Si和Sj在β中相邻地出现，且与β的句柄的关系有上述三种情况之一。然而，也可能有这样的情况，对G中的某些符号序偶(Sr,St)而言，G中并不存在任何使Sr和St相邻出现的句型，此时我们就说Sr和St间不存在任何优先关系。应当指出，上面所引入的三种优先关系都是对文法中的符号序偶来定义的，它们都不具有对称性。即若Sr>· St，并不一定有St<·Sr；即使存在Sr=·St也不意味着St=·Sr必然存在。定义了上述三种优先关系之后，我们便可给出所谓简单优先文法的定义如下。定义4?1若一文法G的任何两个符号之间至多存在一种优先关系，且任意两个不同的产生式均无相同的右部，则称G为简单优先文法。现在的问题是：对于一个给定的文法G来说，如何找出它的各个符号序偶间的优先关系?如何检验G是否为简单优先文法?显然，实质上这是同一问题的两个方面。因为，如果我们有办法找出G的各符号序偶间的优先关系，则第二个问题也就迎刃而解了。继续考虑其它句型的语法树，我们就可得到G中的全部优先关系。通常，我们把一个文法的全部优先关系用一个矩阵来表示，称为优先矩阵。优先矩阵中的每一个元素P[i,j]指明序偶(Si,Sj)间的优先关系。当序偶(Sr,St)不存在优先关系时，相应的元素P[r,t]则为空白。从所得的优先矩阵可以看出，文法的各符号序偶间至多只有一种优先关系，故此文法为简单优先文法。上面，我们通过查看文法的若干句型来构造优先矩阵。稍后我们还要介绍一种更为有效的构造优先矩阵的方法。简单优先分析的算法应当指出，我们之所以把具有上述性质的文法称为简单优先文法，是因为在进行语法分析时，为了寻找一个句型的句柄之头符号和尾符号，只须逐次查看相邻两个符号的优先关系即可。具体地说，也就是从左至右依次扫视句型中的符号X1X2…Xm，并在扫描过程中检查相邻两符号间的优先关系，一旦出现关系Xi+k>·Xi+k+1时，此Xi+k即为句柄的尾符号。然后再从Xi+k开始，从右至左逐个查看已扫过的符号，直到某相邻的两个符号间有优先关系Xi-1<·Xi时，此Xi为句柄的头符号。事实上，我们可以证明：对于简单优先文法的任何规范句型X1X2…Xm而言，它的句柄是该句型中，满足 Xi-1<·Xi Xi=·Xi+1=·…=·Xi+k Xi+k>·Xi+k+1 的最左子串XiXi+1…Xi+k。据此，我们给出采用简单优先分析方法的识别程序如程序44所示。程序 44简单优先分析驱动程序 #define SUCCESS1 #define ERROR0 #define MAXINPUT300 #define MAXSTACK100 #define STARTSYMBOL ′S′ int stack[MAXSTACK], a[MAXINPUT]; int IsHigherThan (int, int);/prioriy detection/ int IsLowerThan (int, int);/prioriy detection/ int RightSideOfAProduction (int begin, int end, int len);/find production/ int parscr (void) {int i,k,r; i=0; k=0; stack[0]=′#′; r=a[k++]; do {int j, LeftSide; while (!IsHigherThan(stack[i],r)) {stack[++i]=r; r=a[k++];} j=i; while (!IsLowerThan (stack[j-1],stack[j]))j--; LeftSide=RightSideOfAProduction (stack[j],stack[i],i-j+1); if (LeftSide) {/* LeftSide!=0 means the production exists/ i=j; stack[i]=LeftSide; } else /There is no production which matches the right side/ if (i==2 && r==′#′ && stack[i]==STARTSYMBOL) return SUCCESS; else return ERROR; }while(1); }/end/ 对上述驱动程序所调用的一些函数的功能简述如下： (1) 函数IsHigher()和IsLower()分别用来检测两个文法符号Si和Sj是否具有关系Si>·Sj和Si<·Sj，并根据关系成立与否分别回送值1和值0。 (2) 函数RightSideOfAProduction()用来在产生式集之中查找这样的产生式，其右部具有指定的头、尾符号及指定的长度，且与出现在栈顶的句柄相匹配，若找到则回送该产生式左部非终结符号的编号 (大于零的整数)，否则回送值0。简单优先矩阵的构造方法在上例中，为构造优先矩阵，我们首先为文法的若干句型构造相应的语法树，然后对每一语法树，考察它的直接子树中的末端结点，以确定有关符号对之间的优先关系，接着便剪去此直接子树的末端结点，并对剪枝后的语法树再重复上述过程，如此等等。显然，应用此种方法，有时我们需要考察足够多的语法树之后，才能把文法中的全部优先关系寻找出来。下面，我们再介绍一种确保一次求出全部优先关系的方法，此方法以布尔矩阵运算作为基础。在给出构造简单优先矩阵的算法之前，我们先在文法G的字汇表V上，定义若干个二元关系，并据此重新定义上述三种优先关系。定义4?2(关系LEAD)当且仅当G中存在形如A→B…的产生式时，有A LEAD B；当且仅当A?+B…时，A LEAD+B。定义4?3(关系LAST)当且仅当G中存在形如A→…B的产生式时，有A LAST B；当且仅当A?+…B时，有A LAST+B。定义4?4设R为一关系，我们将R的转置记为TRANSPOSE(R)，且定义为：当且仅当aRb时，b TRANSPOSE(R) a。定义4?5当且仅当G中存在形如U→…SiSj…的产生式时，Si=·Sj。定义4?6当且仅当G中存在形如 U→…SiW…(4?23) 的产生式，且 W?+Sj…(4?24) 时，有Si<·Sj。由产生式(4?23)及定义4?5，可得 Si=·W 而由推导式(4?24)及定义4?2，又得到 WLEAD+Sj 从而可知，当且仅当 Si(=·)(LEAD)+Sj(4?25) 时，Si<·Sj。定义4?7当且仅当G中存在形如 U→…W1W2…(4?26) 的产生式，且有 W1?+…Si(4?27) 及W2?Sj…Sj∈VT(4?28) 时，Si>· Sj。由产生式(4?26)、推导式(4?27)及(4?28)，有 W1=·W2W1 LAST+ SiW2 LEAD* Sj (其中，LEAD=I+LEAD+,I为恒等关系)上面第二个关系可改写为 Si TRANSPOSE(LAST+) W1 于是可知，当且仅当Sj∈VT，且 Si (TRANSPOSE(LAST+))(=·)(I+LEAD+) Sj(4?29) 时，有Si>· Sj，其中I为恒等关系。现在以文法G： S→AcA→ASA→AaA→b(4?30) 为例，介绍构造简单优先矩阵的算法。在此过程中，需要计算上面所定义的那些关系的布尔矩阵。这些布尔矩阵的阶数就是文法字汇表所含符号的个数。对于关系R的布尔矩阵，用记号BR表示，且对字汇表{S1,S2,…,Sn}中的两个符号Si和Sj，当且仅当SiR Sj时，BR[i,j]=1，否则BR[i,j]=0，对于文法(4?30)构造相应简单优先矩阵的步骤如下： 1?作布尔矩阵B=·，根据定义4?5，从文法(4?30)中的诸产生式可直接写出 B=·= S[]A[]a[]b[]c〖〗S A a b c0[]0[]0[]0[]0 1[]0[]1[]0[]1 0[]0[]0[]0[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]0 2?作布尔矩阵B<·，为此 (1) 作布尔矩阵 BLEAD=0[]1[]0[]0[]0 0[]1[]0[]1[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]0 (2) 由Warshall算法[11，17]，计算 BLEAD+=0[]1[]0[]1[]0 0[]1[]0[]1[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]0 (3) 根据(4?25)，作 B<·=B=·BLEAD+=0[]0[]0[]0[]0 1[]0[]1[]0[]1 0[]0[]0[]0[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]00[]1[]0[]1[]0 0[]1[]0[]1[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]0=0[]0[]0[]0[]0 0[]1[]0[]1[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]0 3?作布尔矩阵B>· ，为此 (1) 作布尔矩阵 BLAST=0[]0[]0[]0[]1 1[]0[]1[]1[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]0 (2) 计算 BLAST+=0[]0[]0[]0[]1 1[]0[]1[]1[]1 0[]0[]0[]0[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]0 (3) 作布尔矩阵 BTRANSPOSE(LAST+)=0[]1[]0[]0[]0 0[]0[]0[]0[]0 0[]1[]0[]0[]0 0[]1[]0[]0[]0 1[]1[]0[]0[]0 (4) 计算 B>·′=BTRANSPOSE(LAST+)B=·BLEAD=0[]1[]0[]0[]0 0[]0[]0[]0[]0 0[]1[]0[]0[]0 0[]1[]0[]0[]0 1[]1[]0[]0[]00[]0[]0[]0[]0 1[]0[]1[]0[]1 0[]0[]0[]0[]0 0[]0[]0[]0[]0 0[]0[]0[]0[]01[]1[]0[]1[]0 0[]1[]0[]1[]0 0[]0[]1[]0[]0 0[]0[]0[]1[]0 0[]0[]0[]0[]1= S[]A[]a[]b[]c S A a b c1[]1[]1[]1[]1 0[]0[]0[]0[]0 1[]1[]1[]1[]1 1[]1[]1[]1[]1 1[]1[]1[]1[]1 (5) 由于在式(4?29)中Sj应为终结符号，故为了得到B>· ，必须在上步所求得的布尔矩阵B>·′ 中，将对应于非终结符号的列置零，于是有 B>· =0[]0[]1[]1[]1 0[]0[]0[]0[]0 0[]0[]1[]1[]1 0[]0[]1[]1[]1 0[]0[]1[]1[]1 4?对于所求的B=·,B<·及B>· ，检查如下等式 B=·∧B>·=B=·∧B<·=B>·∧B<·=0 是否成立。若是，则表明所构造的简单优先矩阵无多重定义的元素，因而所给文法为简单优先文法；否则，它就不是简单优先文法。最后，将布尔矩阵B=·、B>·及B<·所分别指出的优先关系组装到一个矩阵之中，便得到了所求的全部简单优先关系。对于本例，有 []S[]A[]a[]b[]cS[4]>·[]>·[]>·A[]=·[]<·[]=·[]<·[]=·a[4]>·[]>·[]>·b[4]>·[]>·[]>·c[4]>·[]>·[]>· 简单优先分析的局限性从前面的讨论已看到：上述优先分析技术简单易行，已有一套构造简单优先矩阵的形式化算法，从设计分析程序到具体地进行语法分析都可机械地进行。看来，它似乎是一种可靠和有效的方法，其实在应用上，它却有很大的局限性。这主要表现在对文法有较强的要求。因为对通常的文法而言，它的某些符号对之间的优先关系往往会多于一种，也就是说，所给的文法常常并非简单优先文法。特别是当文法具有左递归时，就往往会导致这种情况的发生。例如，当文法中同时含有形如 U→…SiSj… 及 Sj→Sj… 的产生式时，在符号Si和Sj之间，便同时有Si=·Sj及Si<·Sj两种关系。类似地，当文法具有右递归性时，关系=·及>· 也可能出现在同一符号对之间。为避免上述矛盾，我们可在文法中引入一新的非终结符号W，而将上面的第一个产生式改写为如下两个产生式 U→…SiW… W→Sj… 此时，优先关系Si=·Sj及Si<·Sj将为新的优先关系Si=·W及Si<·Sj所代替，从而就解决了上述矛盾。通常，将改写文法的这种方法称为分层法或析出法。然而，应当指出，上述采用分层技术消除多重优先关系的尝试未必总能得到成功。例如，当Si和Sj间既有Si<·Sj也同时有关系Si>·Sj时，上述方法就不能奏效。有时也可能出现这样的情况，即旧的矛盾虽然解决了，但又引出新的矛盾。特别是对于一些规模较大，而所含矛盾又较多的文法，即使上述方法能够取得成功，为改写文法也十分费力。同时，由于改写文法所引入的一些单产生式，也将增加文法的复杂性和降低语法分析的效率，因此，当我们所面临的不是简单优先文法时，还是以选用另外的语法分析方法为宜。此处我们之所以要介绍这种分析方法，一则因为它比较简单；二则也是因为由它可较容易地过渡到其它更为有效的分析方法。最后，我们再来分析一下简单优先分析之所以存在上述缺点的内在原因。从简单优先文法的定义来看，在用这种方法进行分析时，为了识别一个句型的句柄，每次仅使用了句柄周围很少的符号进行判断，即每次只考察句型中相邻两符号的优先关系。可以想像，如果不再局限于相邻的两个符号，而是查看更多的符号，或者取另外的不相邻的符号进行考察，则发生上述矛盾的情况可能会得到改善，例如，为了确定句柄的尾符号，我们不仅要查看Si,Si+1，而且还查看Si-1，Si和Si+1，或者Si,Si+1及Si+2，甚至更多的符号 (如像后面介绍的LR(K)分析那样)。下面，不妨以文法G[E]中的句型E+TF为例来说明此点。前面已经看到，G[E]不是一个简单的优先文法，但若按简单优先关系来考虑，就会出现下面的情况： #<·E=·+=· <·TF#(4?31) 由于符号+和T之间同时存在优先关系+=·T及+<·T，若以前者为准，则+和T都应是句柄中的符号；若按后者，则T可能是句柄的头符号，而+决不会出现在句柄中，可见，仅根据相邻两个符号间的优先关系尚不足以判断T是否为句柄的头符号，或者说+是否在句柄中。但若除考虑+和T外，再向前查看一个符号，则当句型中出现+T这样的结构时，由于乘法运算总是先于加法运算，所以+不可能在句柄之中；而当出现形如+T+的结构时，由于加法运算服从左结合规则，此时，最先归约的自然应是子串E+T，即T是句柄的尾符号。显而易见，上述这种决策实际上是根据运算符+和或者+和+间的优先关系来作出的。于是，就自然启发我们考虑一种更为有效的分析方法——算符优先分析法。
随便看	三相电源防雷模块三相电源防雷器三相调功器三相调压器三相短路三相多功能标准电能表三相多功能电力仪表三相多功能电能表三相多功能校验仪三相多功能用电检测仪三相干式变压器三相高压交流电动机修理三相隔离变压器三相功率因数表三相功率源三相供电三相继保测试仪三相继保校验仪三相继电保护测试仪三相继电保护校验仪三相交变电流三相交流电三相交流电流变送器三相交流电路三相交流电压变送器