算符优先分析法算法思想
时间:2025-07-10
时间:2025-07-10
编译原理中算符优先分析算法思想
算符优先分析法
算符文法:即它的任一产生式的右部都不含两个相继的非终结符的文法。如果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的产生式
便可得。
假定G是一个不含空字符产生式的算符文法。对于任何一对终结符a,b,
(1)a=b,当且仅当G中含有形如P->…ab…或P->…aQb…的产生式;
(2)a<b, 当且仅当G中含有形如P->…aR…的产生式,而R-〉b…或R->Qb…;
(3)a>b, 当且仅当G中含有形如P->…Rb…的产生式,而R->…a或R->…aQ;
编译原理中算符优先分析算法思想
这样再结合上次的FirststVT和LastVT集的概念便可以由文法自动构造出算符优先表。
再定义一个素短语的概念:它至少含有一个终结符,并且,除它自身之外不再含任何更小的素短语,所谓最左素短语就是处于句型最左边的素短语。而一个算符优先文法G的任何句型的最左素短语是满足以下条件的最左子串NaNb…NcNdN(N是非终结符,a,b,c,d是终结符)
a<b b=…=c c>d
这样形成一个驼峰结构,当找到这样一个子串的时候,它们优先级相等的一段就可以归约为一个非终结符,否则报错。
因此算符优先文法分析就是找到这样的字串并归约,最终所有终结符都被成功归约为##时表明这个句子符合所定义的文法要求。
构造优先表的算法是:
For每条产生式P-〉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)中的每个a DO
置 xi<a;
If xi为非终结符而xi+1为终结符 then
For LastVt(xi)中的每个a DO
置 a>xi;
END
算符优先算法:
K=1; s[k]=’#’
Repeat
把下一个输入符号读进a中;
Ifs[k]属于Vt,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=’#’
下一篇:客户管理实务 第1章