[编译原理课程教案第4章.自下而上语法分析.ppt

例：E→E+E | E*E | (E) | i 证明不是算符优先文法。 因 为：E→E+E ，E?E*E 则有 + *(由规则2) 又因为：E→E*E, E?E+E 则有 + *(由规则3) 所以不是算符优先文法。 3.算符优先文法 算符文法G的任何终结符a,b之间要么没有优先关系，若有优先关系,至多有 = , , 中的一种成立,则G为一算符优先文法。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 练 习 对右边的文法G，计算终结符+，*，?和 )之间的优先关系： E?E + T T?T * F F?P ? F P?(E) 因为： E?E + T ，T=T*F，所以：+ * (规则2) 因为： E?E + T ， E = E + T ，所以：+ + (规则3) 因为： T ?T * F ，F = P ? F，所以：* ? (规则2) 因为： T ?T * F ， T = T * F，所以：* * (规则3) 因为： P?(E) ， E = E + T ，所以：+ ) (规则3) 因为：F?P ? F, P = (E)，所以：） ? (规则3) 因为： F?P ? F， F =P ? F，所以： ? ? (规则2) …… Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 算符优先关系表的构造 用表格形式来表示各终结符号的优先关系，这种表称为优先表。 构造优先关系表的方法： ①按照定义手工计算 ②使用算法 例:　P:　　E ? E+T|T　　 　　 T ? T*F|F　　　　 　F ? (E)|i 求算符优先矩阵。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 由F?(E) 得 ( = ) 由E-E+T T = i, 得 + i T = T*F, 得 + * T = (E), 得 + ( E = i, 得i + E = E+T, 得+ + E = T*F, 得* + E = (E), 得 ) + + * i ( ) # + * i ( ) # 例:　P:　　E?E+T|T　　 　　 T?T*F|F　　　　 　F? (E)|i 求算符优先矩阵 终结符+‘#’ 终结符+‘#’ 对于结束符#和其它终结符a之间若有关系,则必有: # a ;a # ，计算方法是拓展成E‘?#E# * * * * * * * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 注意： 在优先表中，空白部分是一种错误关系 相同的终结符之间的优先关系不一定是 如果有a = b,不一定有b = a(不具传递性) 如果有a b,不一定有b a(不具传递性)，因为只定义相邻运算符之间的优先关系，a,b相邻时，不一定b,a相邻。 a,b之间未必有优先关系( , , ) Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 算符优先关系表的自动构造算法 1.FirstVT集 定义：对每个非终结符P, FirstVT(P)={a|P=a...或P=Qa...,a为终结符,P，Q为非终结符} + + 由优先性低于的定义和firstVT集合的定义可以得出： 若存在某个产生式：Q-…aP…， 对所有：b∈FirstVT(P) 都有：a b。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.