算符优先分析法算法思想

编译原理中算符优先分析算法思想

算符优先分析法

算符文法：即它的任一产生式的右部都不含两个相继的非终结符的文法。如果G是一个不含空字符的算法文法，那么只要它的任一对终结符都只满足>，=，<的关系的一种，则称G是一个算符优先文法。

对于一个算符优先文法，只要能够造出它的算符优先表，就可以利用算符优先分析方法，分析一个句子是否符合这个文法的定义。

那么定义FirstVT(P)={a|P->a、、、或P->Qa、、、，a属于终结字符集，而Q属于非终结字符集}

LastVT（P）={a|P->...a或P->...aQ，a属于终结字符集，而Q属于非终结字符集}

由以下两条规则来构造FirstVT集：

(1) 若有产生式P-〉a…、或P->Qa…，则a属于FirstVT（P）；

(2) 若有a属于FirstVT（Q），且有产生式P-〉Q…，则a属于FirstVT(P); 类似的有构造LastVT集的规则：

(1) 若有产生式P->…a或P->…aQ，则a属于LastVT集。

(2) 若a属于LastVT（Q），且有产生式P-〉…Q，则a属于LastVT集。 构造FirstVT集的算法：

Begin

For 每个非终结符P和终结符a Do F[P，a]=FALSE；

For 每个形如P-〉a…或P-〉Qa…的产生式……（1） DO insert（P，a）

While Stack 非空 Do

Begin

把Stack 的顶项，记为（Q，a），上托出去；

For每条形如P-〉Q…的产生式DO …….（2）

Insert（P，a）

End of while；

END

构造LastVT集的算法：

将上述算法的对应的（1），（2）分别修改为

For 每个形如P-〉…a或P-〉…aQ的产生式,

For每条形如P-〉…Q的产生式

便可得。

假定Ｇ是一个不含空字符产生式的算符文法。对于任何一对终结符ａ,ｂ,

(1)a=b,当且仅当Ｇ中含有形如Ｐ－>…ab…或Ｐ－>…aQb…的产生式；

(2)a<b, 当且仅当Ｇ中含有形如Ｐ－>…aR…的产生式,而Ｒ－〉ｂ…或Ｒ->Qb…；

(3)a>b, 当且仅当Ｇ中含有形如Ｐ－>…Rb…的产生式,而Ｒ－>…a或Ｒ->…aQ；

编译原理中算符优先分析算法思想

这样再结合上次的FirststVT和LastVT集的概念便可以由文法自动构造出算符优先表。

再定义一个素短语的概念：它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语，所谓最左素短语就是处于句型最左边的素短语。而一个算符优先文法Ｇ的任何句型的最左素短语是满足以下条件的最左子串NaNb…NcNdN(N是非终结符，a,b,c,d是终结符)

a<b b=…=c c>d

这样形成一个驼峰结构，当找到这样一个子串的时候，它们优先级相等的一段就可以归约为一个非终结符，否则报错。

因此算符优先文法分析就是找到这样的字串并归约，最终所有终结符都被成功归约为＃＃时表明这个句子符合所定义的文法要求。

构造优先表的算法是：

For每条产生式Ｐ－〉X1X2…Xn DO

For i=1;to n-1 Do

Begin

If xi和xi+1 均为终结符 then 置 xi=xi+1

If i<=n-2 且 xi 和 xi+2都为终结符

但Xi+1为非终结 then 置 xi=xi+1

If xi为终结符而xi+1为非终结符 then

For FirstVt(xi+1)中的每个ａ ＤＯ

置 xi<a;

If xi为非终结符而xi+1为终结符 then

For LastVt(xi)中的每个ａ ＤＯ

置 a>xi;

END

算符优先算法:

K=1; s[k]=’#’

Repeat

把下一个输入符号读进a中；

Ifｓ[k]属于Ｖｔ，then j=k else j=k-1;

While s[j]> a do

Begin

Reapeat

Q=s[j];

If s[j-1]属于Vt then j=j-1 else j=j-2

Until s[j]<Q

把s[j+1]…s[k]归约某个N；

K=j+1

编译原理中算符优先分析算法思想

S[k]=N

End of while

If s[j]<a or s[j]=a then Begin k=k+1; s[k]=a end Else 出错

UNTIL a=’#’