二、算符优先算法

设置两个工作栈：一个是用来寄存运算符的OPTR，另一个为用来寄存操作数或结果的OPND。算法描述如下：

(1)首先置操作数栈OPND为空，将#入OPTR栈。

(2)依次读入表达式中每个单词，若是操作数则进OPND栈，若是运算符则转[3]。

(3)查算符优先关系表，将当前读入的运算符θ2与OPTR栈顶元素θ1进行比较， 若 θ1<θ2，则：θ2进栈，转(2)；若 θ1＝θ2 ,如θ2为#，则分析成功；否则，OPTR栈顶元素θ1出栈，并转（（3）；若θ1＞θ2,则出栈OPND栈顶元素至b，又出栈其栈顶元素至a，出栈OPTR栈顶元素至t，进行运算r=a t b (t为运算符)，并将结果r存 入栈OPND后转（（2）。若θ1和θ2之间无优先关系，则报错。

例：根据前例文法，对5*(1+(4)作直观算符优先分析，其过程如下：

6.3.2算符优先文法

如果文法G=（ VN，VT，P，S）中不存在形如 A→…BC…的产生式，其中B、C为非终结符，则称之为算符文法(OG —operator Grammar)。即如果文法Ｇ中不存在具有相邻非终结符的产生式，则称为算符文法。 一、算符间的优先关系

设G=（VN，VT，P，S）为OG，则定义:

?a≡b A→…ab…∈P或者 A→…aBb…∈P

a≮ A→…aB…?b∈P且(B=+>b…或者B=+>Cb…) a≯ A→…Bb…?b∈P且(B=+>…a或者B=+>…aC)

二、算符优先文法

设G=（V，T，P，S）为OG，如果 a,b?∈VT, a≡b,a≮b,a≯b至多有一个成立，则称之为算符优先文法(OPG —Operator Precedence Grammar)。

在无ε产生式的算符文法Ｇ中，如果任意两个终结符之间至多有一种优先关系，则称为算符优先文法。 授课顺序：10

教学目的：让学生掌握算符优先关系表的构造、算符优先分析算法、优先函数

的计算，了解算符优先分析法的局限性。

教学重点：算符优先关系表的构造、算符优先分析法的应用、优先函数的计算 教学难点：算符优先关系表的构造、算符优先分析法的应用、优先函数的计算 授课学时：2学时

教学方式：多媒体讲授 教学内容：

6.3.3算符优先关系表的构造

一、由定义直接构造优先矩阵 对语法变量A定义：

1、FIRSTVT(A) ={b| A?+b…或者 A?+Cb…} 2、LASTVT(A) ={b|A?+…b或者A?+…bC}

则对产生式A→X1X2…Xn按如下方法构造各文法符号对之间的优先关系后填入算符优先关系表：

(1)如果XiXi+1∈ VTVT 则： Xi≡Xi+1

(2)如果XiXi+1Xi+2∈VTVNVT 则：Xi≡Xi+2

(3)如果XiXi+1∈VTVN 则： a?∈FIRSTVT(Xi+(1)，Xi≮a (4)如果XiXi+1∈VNVT 则：a?∈LASTVT(Xi)， a≯Xi+1

例：文法G[E?]： E?→#E# E→E+T|T T→T*F|F F→P^F|P P→(E) |i,则求出非终结符的FIRSTVT、 LASTVT集：

现对形如A→…aB…的规则根据FIRSTVT集求≮关系，对形如A→…Bb…的规则根据LASTVT集求≯关系，如下表：

由定义直接求出前例的优先矩阵为 ：

二、用算法构造优先矩阵

1、优先矩阵的构造算法基于两条原则

(1)若有规则A→a…或A→Ba…,则a∈FIRSTVT(A) ;

(2)若a∈FIRSTVT(B)且有规则A→B…,则a∈FIRSTVT(A) ; 2、求FIRSTVT集的算法步骤

先设立一个布尔数组F[A,a]，其值为真时，当且仅当a∈FIRSTVT(A)，则：

第1步：按原则(1)对每个数组元素F[A,a]置初值，并对F[A,a]初值为真的符号对(A,a)入栈；

第2步：处理栈。当栈不空时，弹出栈项元素(B,a)，再按原则(2)，对形如A→B…的

规则若有F[A,a]为假，则使其变为真，再让(A,a)入栈； 第3步：重复至栈空为止。

3、求FIRSTVT集的算法描述

void insert(A,a) { if !F[A,a] then

{ F[A,a]=1; push(A,a) to stack; } } void main()

{ for (每一个非终结符A和终结符a) F[A,a]=0;

for (每一个形如A→a…或A→Ba…的规则) insert(A,a) ; while (stack不空)

{ op(B,a) ; for(每一个形如A→B…的规则) insert(A,a) ; } }

对前例G[E?]：E?→#E# E→E+T|T T→T*F|F F→P^F|P P→(E) |i 对各非终结符第一次扫描规则后，栈初值如下：

(6) (p,i) (5) (p,() (4) (F,^) (3) (T,*) (2) (E,+) (1) (E?,#)

对栈项(6) (p,i)，由规则 F→P,T→F ,E→T，使(6)依次变为：(F,i) ,(T,i) ,(E,i)。当(E,i)出栈后，无入栈项，此时栈顶为：(5) (p,()。 同理，可得下述栈项：(4) (F,^)、(3) (T,*)、(2) (E,+)、(1) (E?,#)。最后，当(E?,#)出栈后，无入栈项，栈为空。 4、根据算法求FIRSTVT集

凡在栈中出现过的(A,a)，其 F[A,a]值必为1。根据各个A的F[A,a]值，即可求出FIRSTVT(A)。对前例，有：

5、由关系图求FIRSTVT集 （1）图中结点为FIRSTVT(A)和a；

（2）对形如A→a…或A→Ba…的规则,从FIRSTVT(A)连弧到a； （3）对形如A→B…的规则,从FIRSTVT(A)连弧到FIRSTVT(B)；

（4）凡是从FIRSTVT(A)经所有路径可达到a，都有a∈FIRSTVT(A) 。 对前例按关系图求出各非终结符的FIRSTVT如下：

用类似方法求出各非终结符的LASTVT集。 6、构造优先矩阵的算法

void table()

{ for (每个规则X1X2…Xn)?A for (k=1;k< SPAN>

{ if (XkXk+1∈VTVT) Xi≡Xi+1;

if (k && (XkXk+1Xk+2∈VTVNVT) Xk≡Xk+2;

if ( XkXk+1∈VTVN )

for (FIRSTVT(Xk+(1)中每个b) Xk≮b; if ( XkXk+1∈VN VT)

for (LASTVT(Xk+(1)中每个a) a≯Xk+1; } }

用算法求出优先矩阵为 ：

6.3.4 算符优先分析

算符优先分析和规范归约的核心均为寻找句柄。规范归约的句柄是“最

左直接短语”。算符优先分析的句柄是“最左素短语”。

一、素短语与最左素短语 1、什么是素短语？ Ｓ=*> αＡβ and A=+>γ，γ至少含一个终结符，且不含更小的含终结符的

短语，则称γ是句型αγβ的相对于变量A的素短语。句型的至少含一个终结符且不含其它素短语的短语。

最左边的素短语称为最左素短语。 2、例： E→T+E|T T→T*F|F F→(E) |id

解：句型 T+T*F+i的短语有：T*F，i，T*F+i, T+T*F+i;其中的素短语

为：T*F和 i;

3、T*F为最左素短语，是被归约的对象。

课堂作业：按照文法E→E+E|E*E|(E) |id，求i+E*i+i的短语和素短语。 解：

句型i+E*i+i的短语：i，E*i,i, i,i+E*i和i+E*i+i;其中的素短语为：i, i, i。 3、最左素短语总结

设句型的一般形式为#N1a1 N2a2… Nnan #,其中：

Ni∈VN∪{ε},ai∈VT，则它的最左素短语是满足下列条件的最左子串Niai Ni+1ai+1… Njaj Nj+1， 其中： ai-1≮ai, ai≡ai+1≡…≡aj-1≡aj，aj≯aj+1。

二、算符优先分析法的实现 1、分析算法描述

设单元a中存放当前输入符，S为一个符号栈，则： (1)将当前输入符存放到a中，将#入符号栈。

(2)将栈顶第一个终结符b与a比较。如果b≡a，而 b== #且栈中只剩一

个非终结符时，则成功；否则a入栈；如果b≮a,则a入栈；如果b≯a,在栈顶寻找最左素短