152 翁译原理及实践 China-pub.Co 下载 例5.2考虑以下基本算术表达式的扩充文法（没有括号，只有一种运算）： E'-E E→E+nln 表5-2是串n+n使用这个文法的自底向上的分析。 表5-2例5.2中文法的自底向上分析程序的分析动作 分析栈 输入 动作 $ n+nS 移进 2 +n 用E+n归的 3 SE 移进 SE+ ns 移选 SE+ 用E一E+a归约 6 SE 用E一E白约 7 SE 接受 在使用先行上，自底向上的分析程序比自项向下的分析程序的困难要小。实际上，自底向 上的分析程序可将输入符号移进到栈里直到它判断出要执行的是何种动作为止（假设判断一个 动作可以不要求将符号移进到输入中)。但是为了判断要完成的动作，自底向上的分析程序会 需要在栈内看得更深，而不仅仅是项部。例如，在表5-1中的第5行，S位于栈的项部，且分析 程序用产生式S一(S)S归约，而第6行在栈的顶部也有S,但是分析程序却用S一S归约。为了 能够了解S一(SS在第5步中是一个有效的归约，我们必须知道实际上栈在该点包含了串(S)S。 因此，自底向上的分析要求任意的“栈先行”。由于分析程序本身建立了钱且可使恰当的信息 成为可用的，所以这几乎同输入先行一样重要。此时所用的机制是“项”的确定性的有穷自动 机，下一节将会讲到它。 当然，仅仅了解栈的内容并不足以可唯一地判断出移进-归约分析的下一步，还需将输入 中的记号作为一个先行来考虑。例如在表5-2的第3行，E在栈中，且发生了一个移进：但在第6 行中，E又在栈中，但却用了E一E归约。两者的区别在于：在第3行中，输入的下一个记号是 “+”:但在第6行中，下一个输入记号却是$。因此， 任何执行那个分析的算法必须使用下一个 输入记号（先行）来判断出适当的动作。不同的移进-归约分析方法以不同的方式使用先行，而 这将导致具有不同能力和复杂性的分析程序。在看到单个算法之前，我们首先做一些普通的观 察来看看自底向上分析的直接步骤是如何表现特征的。 首先，我们再次注意到移进-归约分析程序描绘出输入串的最右推导，但推导步骤的顺序 却是颠倒的。在表5-1中，共有4个归约，它们与最右推导的4个步骤对应的顺序相反： S→S→(S→S(S)→() 在表5-2中，相对应的推导是 E'SE三E+n-n+n 我们将这样的推导中的终结符和非终结符的每个中间串都称作右句型(right sentential f「m)。在移讲-归约分析中，每个这样的白型都被分析线和输入分摄开。例如，发生在前面推 导中的第3步的右句子格式E+出现在表5-2的第3、第4和第5步。如果通过符号指出每一时 刻栈的顶部位于何处（即：当在栈和输入之间发生了分隔），则表5-2的第3步就由E‖+给出， 而其第4步则由E+‖给出。在每一种情况下，分析栈的符号序列都被称作右句型的可行前缀 例5.2 考虑以下基本算术表达式的扩充文法(没有括号，只有一种运算)： E¢→ E E → E + n | n 表5 - 2是串n + n 使用这个文法的自底向上的分析。 表5-2 例5 . 2中文法的自底向上分析程序的分析动作 分 析 栈 输 入 动 作 1 $ n + n $ 移进 2 $ n + n $ 用E→n 归约 3 $ E + n $ 移进 4 $ E + n $ 移进 5 $ E + n $ 用E→E + n 归约 6 $ E $ 用E¢→ E归约 7 $ E¢ $ 接受 在使用先行上，自底向上的分析程序比自顶向下的分析程序的困难要小。实际上，自底向 上的分析程序可将输入符号移进到栈里直到它判断出要执行的是何种动作为止 (假设判断一个 动作可以不要求将符号移进到输入中 )。但是为了判断要完成的动作，自底向上的分析程序会 需要在栈内看得更深，而不仅仅是顶部。例如，在表 5 - 1中的第5行，S位于栈的顶部，且分析 程序用产生式S→ (S) S归约，而第6行在栈的顶部也有S，但是分析程序却用S¢→S归约。为了 能够了解S→(S) S在第5步中是一个有效的归约，我们必须知道实际上栈在该点包含了串(S) S。 因此，自底向上的分析要求任意的“栈先行”。由于分析程序本身建立了栈且可使恰当的信息 成为可用的，所以这几乎同输入先行一样重要。此时所用的机制是“项”的确定性的有穷自动 机，下一节将会讲到它。 当然，仅仅了解栈的内容并不足以可唯一地判断出移进-归约分析的下一步，还需将输入 中的记号作为一个先行来考虑。例如在表 5 - 2的第3行，E在栈中，且发生了一个移进；但在第6 行中，E又在栈中，但却用了E¢→E 归约。两者的区别在于：在第3行中，输入的下一个记号是 “+”；但在第6行中，下一个输入记号却是$。因此，任何执行那个分析的算法必须使用下一个 输入记号(先行)来判断出适当的动作。不同的移进-归约分析方法以不同的方式使用先行，而 这将导致具有不同能力和复杂性的分析程序。在看到单个算法之前，我们首先做一些普通的观 察来看看自底向上分析的直接步骤是如何表现特征的。 首先，我们再次注意到移进-归约分析程序描绘出输入串的最右推导，但推导步骤的顺序 却是颠倒的。在表5 - 1中，共有4个归约，它们与最右推导的4个步骤对应的顺序相反： S¢ Þ S Þ (S) Þ S (S) Þ ( ) 在表5 - 2中，相对应的推导是 E¢ Þ E Þ E + n Þ n + n 我们将这样的推导中的终结符和非终结符的每个中间串都称作右句型 (right sentential f o r m )。在移进-归约分析中，每个这样的句型都被分析栈和输入分隔开。例如，发生在前面推 导中的第3步的右句子格式E + n 出现在表5 - 2的第3、第4和第5步。如果通过符号 || 指出每一时 刻栈的顶部位于何处(即：当在栈和输入之间发生了分隔 )，则表5 - 2的第3步就由E || + n给出， 而其第4步则由E + || n给出。在每一种情况下，分析栈的符号序列都被称作右句型的可行前缀 1 5 2 编译原理及实践 下载