[第六章自低而上的优先分析法.ppt

* * 文法G[E]：E→E+E|E-E|E*E|E/E|E?E|(E)|i 步骤 符号栈 输入符号串 动作 1） # i+i*i# #i,移进 2） #i +i*i# #i+,归约 3） #E +i*i# #+,移进 4） #E+ i*i# +i,移进 5） #E+i *i# +i*,归约 6） #E+E *i# +*,移进 7） #E+E* i# *i,移进 8） #E+E*i # *i#,归约 9） #E+E*E # +*#,归约 10） #E+E # #+#,归约 11） #E # 接受 对输入串i+i*i的算符优先分析过程 算符优先关系表 归约成功标志：栈中只剩#E，输入符号串剩# Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * * 6.3.2 算符优先文法的定义 定义6.1 如果不含空产生式的上下文无关文法 G 中没有形如 A?…BC…的产生式，其中B, C∈VN，则称G 为算符文法（OG）。 例如：表达式文法E→E+E|E*E|(E)|i Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 性质1：在算符文法中任何句型都不包含两个相邻的非终结符。（数学归纳法） 性质2：如 Ab 或 bA 出现在算符文法的句型? 中，其中A∈VN, b∈VT, 则?中任何含b的短语必含有A。（反证法） 注意：含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. * * 算符优先关系的定义6.2 在OG中 定义 （算符优先关系） a b G中有形如A?…ab…或A ? …aBb.. 的产生式。 a b G中有形如A ? …aB…的产生式，而 B b….或B Cb… a b G中有形如A ? …Bb…的产生式，而B …a或B … aC 规定 若 S a… 或 S Ba… 则 # a S …a 或 S …aB 则 a # Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 由语法树结构决定优先性 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * * 算符优先文法的定义6.3 在一不含?产生式的OG文法G中，若任意两个终结符间至多有一种算符优先关系存在，则称G 为算符优先文法(OPG)。 E→E+E|E*E|(E)|i 不是算符优先文法。 结论 算符优先文法是无二义的。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * * 6.3.3 算符优先关系表的构造 由定义直接构造 由关系图法构造算符