j9qb6OPG.pptVIP免费

1第6章补充算符优先分析算符优先文法的定义算符优先关系表的构造算符优先分析算法算符优先分析法的局限性2算符优先分析•自下而上分析算法模型----移进归约•算符优先分析不是规范归约算符优先分析的可归约串是句型的最左素短语定义cfg（上下文无关文法）G的句型的素短语是一个短语，它至少包含一个终结符，且除自身外不再包含其他素短语。处于句型最左边的素短语为最左素短语文法G[S]SαAδ且A则称是句型αδ相对于非终结符A的短语*3文法G[E]：(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→PF|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的素短语为：T+T,i素短语为：T*F，iETTi4分析程序模型总控程序算符优先关系表产生式输入串##输出5例G’[E]:E→E＋T|TT→T*F|FF→P↑F｜PP→(E)|i算符优先关表+*()i#+><<<><>*>><<><>>><<><>(<<<<=<)>>>>>i>>>>>#<<<<<=6算符优先文法的定义•定义：如果不含空产生式的上下文无关文法G中没有形如A…BC…的产生式，其中B，C∈VN则称G为算符文法（OG）。例1G[E]：E→E+E|E-|E*E|E/E|EE|(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。7算符优先关系在OG中定义（算符优先关系）a=bG中有形如：A…ab…或A…aBb...的产生式。abG中有形如:A…Bb…的产生式,而B…a或B…aC规定若Sa…或SCa…则##8在OG文法G中，若任意两个终结符间至多有一种算符优先关系存在，则称G为算符优先文法(OPG)。注意：允许b>c,c>b;不允许b>c,b“（”。结论:算符优先文法是无二义的。9算符优先关系表的构造首先定义如下两个集合：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’关系–求出每个非终结符B的LASTVT(B)–若A→…Bb…,则a∈LASTVT(B),则a>b...