编译原理清华大学第6章自底向上优先分析法解读.ppt

* * * * * * * * * (4) 算符优先关系表的构造 算符文法中任何两个终结符对(a,b)之间的优先关系，其计算算法如下： 首先定义如下两个集合： FIRSTVT(B)={b|B b… 或 B Cb…} 　LASTVT(B)={a|B …a 或 B …aC} + ? + ? + ? + ? 三种优先关系的计算为： a) 关系: 可直接查看产生式的右部，对如下形式的产生式 　　A→…ab… , A→…aBb…　有a b成 立。 b)＜·关系:　求出每个非终结符B的FIRSTVT(B)，在如下形式的产生式 　　A→…aB… 中，对每一 b∈FIRSTVT(B),有a＜·b成立。 c)·＞关系:　计算每个非终结符B的LASTVT(B)，在如下形式的产生式 　　A→…Bb… 中，对每一a∈LASTVT(B)，有a·＞b成立。 · · 例6.5：现在可用上述算法计算下列表达式文法的算符优先关系。 若有表达式文法为： (0)? E′→#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 解：计算表达式文法的优先关系为： a) 关系 由产生式(0) E′→#E# 和(6) P→(E) ,可得# # ， （ ）成立。 · · · 为了求＜·和·＞关系 ，需先由定义6.2计算每个非终结符的FIRSTVT集合和LASTVT集合，结果为： FIRSTVT(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} 在计算每个非终结符的FIRSTVT集合和LASTVT集合时，可先考虑文法中含有E→T，T→F，F→P形式的产生式，由定义6.2的推论可知P的FIRSTVT集合和LASTVT集合也属于F的FIRSTVT集合和LASTVT集合，同样F的也属于T的，T的也属于E的。集合中的其它元素可根据定义由产生式直接计算。 然后逐条扫描产生式寻找终结符在前非终结符在后的相邻符号对和非终结符在前终结符在后的相邻符号对，即产生式右部有形如 　　A→…aB… 和 A→…Bb… 的产生式。 b) ＜·关系：对所给表达式文法中终结符在前非终结符在后的相邻符号对有： 　 # E 则有： # ＜· FIRSTVT(E) 　 + T 则有： + ＜· FIRSTVT(T) 　 * F 则有： * ＜· FIRSTVT(F) 　 ↑F 则有：↑＜·FIRSTVT(F) ( E 则有： ( ＜· FIRSTVT(E) c)·＞关系：对表达式文法中非终结符在前终结符在后的相邻符号对有： E # 则有：LASTVT(E) ·＞ # E + 则有：LASTVT(E) ·＞ + T * 则有：LASTVT(T) ·＞ * P↑ 则有：LASTVT(P) ·＞↑ E ) 则有：LASTVT(E) ·＞ ) 从而可以构造优先关系矩阵为下表6.5 表6.5 表达式文法算符优先关系表 ＜· ＜· ＜· ＜· ＜· # ·＞ ·＞ ·＞ ·＞ ·＞ ) ＜· ＜· ＜· ＜· ·＞ ( ·＞ ·＞ ·＞ ·＞ ·＞ i ·＞ ·＞ ＜· ＜· ＜· ·＞ ·＞ ↑ ·＞ ·＞ ＜· ＜· ＜· ·＞ ·＞ * ·＞ ·＞ ＜· ＜· ＜· ＜· ·＞ + # ) ( i ↑ * + · · （5） 算符优先分析算法： 定义：素短语是这样的一个短语，它至少含有一个终结符，并且除它之外不再含更小的素短语 定义：最左素短语是指处于句型最左边的素短语。 定理：设N1S1N2S2…NnSn是算符优先文法的句型，其子串NiSiNi+1Si+1…NjSj是满足下列条件的最左子串： (Si是是终结符，Nn是可有可无的非终结符， ) Si-1 Si Si Si+1 Si+2 …=Sj Sj Sj+1 ｝ 则NiSiNi+1Si+1…NjSj是N1S1N2S2…NnSn的最左素短语。 （2）简单优先法是任意两个文法符号之间的优先关系，而算符优先法是任意两个终结符之间的优先关系。简单优先法关系矩阵比算符优先关系矩阵要大。 （3）算符优先法是在任意两个终结符之间建立优先关系，在归约过