算符优先分析编译原理

算符优先分析编译原理1第一页，共十八页，编辑于2023年，星期一6.1自底向上优先分析概述有两种优先分析法：1。简单优先分析法：求出文法所有符号（终结符，非终结符）之间优先关系，按这种关系确定规约过程中的句柄。2。算符优先分析法：考虑算符之间优先关系的规约（非规范规约）2第二页，共十八页，编辑于2023年，星期一6.3

算符优先分析法算符优先文法的定义

算符优先关系表的构造算符优先分析算法

算符优先分析法的局限性3第三页，共十八页，编辑于2023年，星期一6.3.1算符优先分析自下而上分析算法模型----移进归约算符优先分析不是规范归约算符优先分析的可归约串是句型的最左素短语定义:cfg（上下文无关文法）G的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语.文法G[S]的短语：

SαAδ且A，则称是句型αδ相对于非终结符A的短语

4第四页，共十八页，编辑于2023年，星期一文法G[E]：

(1)E→E+T

(2)E→T

(3)T→T*F

(4)T→F

(5)F→PF|P

(6)P→(E)

(7)P→i句型T+T*F+i

其短语有：

T+T*F+i

T+T*F

T

T*F

iEET++ETF*FTTi最左素短语为：T*F句型T+T+F的素短语为：T+TE++TFE句型T+T+i的素短语为：T+T,

i素短语为：T*F，iETTi5第五页，共十八页，编辑于2023年，星期一分析程序模型

总控程序算符优先关系表产生式输入串##输出6第六页，共十八页，编辑于2023年，星期一例G’[E]:E→E＋T|T

T→T*F|F

F→P↑F｜P

P→(E)|i

算符优先关表7第七页，共十八页，编辑于2023年，星期一

6.3.2算符优先文法的定义算符文法定义：如果不含空产生式的上下文无关文法G中，没有形如A…BC…的产生式，其中B，C∈VN则称G为算符文法（OG）。例1G[E]：E→E+E|E-|E*E|E/E|EE|(E)|i例2G’[E]:E→E＋T|TT→T*F|FF→P↑F｜PP→(E)|i性质1：在算符文法中任何句型都不包含两个相邻的非终结符.性质2：如Ab

或bA出现在算符文法的句型中，其中A∈VN，b∈VT，则中任何含b

的短语必含有A。8第八页，共十八页，编辑于2023年，星期一算符优先关系在OG中定义

算符优先关系：

a=bG中有形如：A…ab…

或A…aBb...的产生式。

a<bG中有形如:A…aB…的产生式, 而

Bb…或BCb…a>bG中有形如:A…Bb…的产生 式,而

B…a

或B…aC

规定

若

Sa…或

SCa…则

#

<

a

若

S…a

或

S…aC则

a

>

#（认为存在#S#）9第九页，共十八页，编辑于2023年，星期一算符优先文法OPG定义在OG文法G中，若任意两个终结符间至多有一种算符优先关系存在，则称G为算符优先文法(OPG)。注意：允许b>c,c>b;不允许b>c,b<c,b=c中任两个同时存在。b=c不一定c=b。例1中：“（”=“）”，“）”<>“（”。

结论:算符优先文法是无二义的。10第十页，共十八页，编辑于2023年，星期一6.3.3算符优先关系表的构造首先定义如下两个集合：FIRSTVT(B)=｛b｜Bb…或BCb…｝LASTVT(B)=｛a｜B…a或B…aC｝按如下算法计算出给定文法中任何两个终结符对(a,b)之间的优先关系：

1)‘=‘关系直接看产生式的右部，若出现了

A→…ab…或A→…aBb,则a=b2)’<‘关系求出每个非终结符B的FIRSTVT(B)若A→…aB…,则b∈FIRSTVT(B),则a<b3)’>’关系求出每个非终结符B的LASTVT(B)若A→…Bb…,则a∈LASTVT(B),则a>b11第十一页，共十八页，编辑于2023年，星期一计算算符优先关系例文法G’[E’]：

(0)E’→#E#

(1)E→E+T

(2)E→T

(3)T→T*F

(4)T→F

(5)F→PF|P

(6)P→(E)

(7)P→iFIRSTVT(E’)={#}

FIRSTVT(E)={+,*,,(,i}

FIRSTVT(T)={*,,(,i}

FIRSTVT(F)={,(,i}

FIRSTVT(P)={(,i}

LASTVT(E’)={#}

LASTVT(E)={+,*,,),i}

LASTVT(T)={*,,),i}

LASTVT(F)={,),i}

LASTVT(P)={),i}12第十二页，共十八页，编辑于2023年，星期一(0)E’→#E#(1)E→E+T(2)E→T(3)T→T*F(4)T→F

(5)F→PF|P(6)P→(E)(7)P→i

3)‘>’关系

找形如：A→…Bb…的产生式

E#:则LASTVT(E)>#

E+:则LASTVT(E)>+

T*:则LASTVT(T)>*

P:则LASTVT(P)>

E):则LASTVT(E)>)2）‘<’关系

找形如A→…aB…的产生式

#E：则#<FIRSTVT(E)

+T:则+<FIRSTVT(T)

*F:则*<FIRSTVT(F)

F:则<FIRSTVT(F)

(E:则(<FIRSTVT(E)1)‘=’关系

由产生式(0)和(6),得

#=#，(

=)13第十三页，共十八页，编辑于2023年，星期一

例G’[E’]的算符优先关表(注意加入#)14第十四页，共十八页，编辑于2023年，星期一6.3.4算符优先分析算法

算符优先文法句型的性质：算符文法的任何一个句型应为如下形式：＃N1a1N2a2...NnanNn+1＃其中Nk(1≤k≤n+1)为非终结符或空，ak(1≤k≤n)为终结符。算符优先文法句型的最左素短语NiaiNi+1ai+1...NjajNj+1满足：ai-1

＜aiai=ai+1=……=aj-1=ajaj

＞aj+1即：ai-1<ai=ai-1=...=aj-1=aj>aj+115第十五页，共十八页，编辑于2023年，星期一算符优先分析算法

1k:=1;S[k]:=“#”2 repeat

read

下一符号到a;3 ifS[k]Vtthenj:=kelsej:=k-1;4 whileS[j]>ado5 {repeat6 Q:=S[j];7 ifS[j-1]Vt

thenj:=j-18 elsej:=j-29 untilS[j]<Q;10将

S[j+1]S[j+2]…S[k]归约到某个N;//11 k:=j+1;12 S[k]:=N;13 }14 if(S[j]<aorS[j]=a)15 then{k:=k+1;S[k]:=a}16 else

error17 untila=“#”16第十六页，共十八页，编辑于2023年，星期一算符优先分析法简单，直观，有利于表达式分析，易于手工实现比规范归约快可能导致把错