编译原理 第7章算符优先分析.ppt

《编译原理 第7章算符优先分析.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7章       算符优先分析算符优先文法的定义算符优先关系表的构造算符优先分析算法算符优先分析法的局限性算符优先分析自下而上分析算法模型----移进归约算符优先分析不是规范归约算符优先分析的可归约串是句型的最左素短语定义cfg（上下文无关文法）G的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语文法G[S]SαAδ且A则称是句型αδ相对于非终结符A的短语文法G[E]：(1)E→E+T(2)E→T(3)T→T*F(4)

2、T→F(5)F→PF

3、P(6)P→(E)(7)P→i句型T+T*F+i其短语有：T+T*F+iT+T*FTT*FiEET++ETF*FTTi最左素短语为：T*F句型T+T+F的素短语为：T+TE++TFE句型T+T+i的素短语为：i素短语为：T*F，iETTi分析程序模型总控程序算符优先关系表产生式输入串##输出如何确定算符优先关系？人为确定：（1）i的优先级最高（1）优先级次于i，右结合（2）*和/优先级次之，左结合（3）+和-优先级最低，左结合（4）括号‘(’,‘)’的优先

4、级大于括号外的运算符，小于括号内的运算符，内括号的优先性大于外括号（5）#的优先性低于与其相邻的算符文法G[E]：E→E+E

5、E-E

6、E*E

7、E/E

8、EE

9、(E)

10、i算符优先关系表算符优先文法的定义定义：如果不含空产生式的上下文无关文法G中没有形如A…BC…的产生式，其中B，C∈VN则称G为算符文法（OG）。例7.1G[E]：E→E+E

11、E-

12、E*E

13、E/E

14、EE

15、(E)

16、i例7.2G’[E]:E→E＋T

17、TT→T*F

18、FF→P↑F｜PP→(E)

19、i性质1：在算符文法中任何句型都不包含两个

20、相邻的非终结符.性质2：如Ab或bA出现在算符文法的句型中，其中A∈VN，b∈VT，则中任何含b的短语必含有A。算符优先关系在OG中定义（算符优先关系）a=bG中有形如：A…ab…或A…aBb...的产生式。abG中有形如:A…Bb…的产生式,而B…a或B…aC规定若Sa…或SCa…则##在OG文法G中，若任意两个终结符间至多有一种算符优先关系存在，则称G为算符优先文法(OPG)。注意：允许b>c,

21、c>b;不允许b>c,b“（”。结论:算符优先文法是无二义的。算符优先关系表的构造首先定义如下两个集合：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…,则

22、b∈FIRSTVT(B),则a’关系求出每个非终结符B的LASTVT(B)若A→…Bb…,则a∈LASTVT(B),则a>b计算算符优先关系例文法G’[E’]：(0)E’→#E#(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→PF

23、P(6)P→(E)(7)P→iFIRSTVT(E’)={#}FIRSTVT(E)={+,*,,(,i}FIRSTVT(T)={*,,(,i}FIRSTVT(F)={,(,i}FIRSTVT(P)={(,i}

24、LASTVT(E’)={#}LASTVT(E)={+,*,,),i}LASTVT(T)={*,,),i}LASTVT(F)={,),i}LASTVT(P)={),i}(0)E’→#E#(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→PF

25、P(6)P→(E)(7)P→i3)‘>’关系找形如：A→…Bb…的产生式E#:则LASTVT(E)>#E+:则LASTVT(E)>+T*:则LASTVT(T)>*P:则LASTVT(P)>E):则LASTVT(E)>)

26、2）‘<’关系找形如A→…aB…的产生式#E：则#