China-pub.com 第5章自底向上的分析 153 下载 (viable prefix)。因此，E、E+和E+n都是右句型E+n的可行前缀，但右句子格式n+n却使 E和n作为它的可行前缓（表5-2的第1步和第2步）。请注意，n+不是n+n的可行前级。 移讲一归约分析程序将终结符从输入移讲到我直到它能执行一个归约以得到下一个右句子 格式。它发生在位于栈顶部的符号串匹配用于下一个归约的产生式的右边。这个串、它在右句 子格式中发生的位置以及用来归约它的产生式被称作右句型的句柄(handle)°。例如，在右句子 格式n+n中，它的句柄是由最左边的单个记号n与用来归约它以产生新的右句型E+n的产生 式E一n组成的串。这个新句型的句柄是整个串E+n(一个可行的前缀)以及产生式E一E+n。 有时由于表示法上的弊端，我们要用串本身来作为句柄。 判断分析中的下一个句柄是移进-归约分析程序的主要任务。请注意，句柄串总是为它的 产生式（在下一步的归约中使用的产生式）构成一个完整的右部，而且当归约发生时，句柄串的 最右边的位置将与栈的顶部相对应。所以对于移进-归约分析程序将要基于产生式右边的位置 来判断它的动作这一点而言，就看起来有些似是而非了。当这些位置到达产生式的右边末端时， 这个产生式就有可能是一个归约，而且句柄还有可能位于栈的顶部。但为了成为句柄，串位于 栈的顶部来匹配产生式的右边并不够。实际上，若￡产生式可用于归约的话（如在例5.1中）， 那么它的右边（空串）总是位于栈的顶部。归约仅发生在结果串实际为一个右句型时。例如，在 表51的第3步中，可完成用S一e归约，但是得到的串(SS并不是右句子格式，所以e在句子 格式（中的这个位置也不是句柄。 5.2LR(O)项的有穷自动机与LR(O)分析 5.2.1LR(0)项 上下文无关文法的LR(O)项(LR(O)item)(或简写为项(item)是在其右边带有区分位置的产 生式选择。我们可用一个句点（当然它就变成了元符号，而不会与真正的记号相混淆）来指出 这个区分的位置。所以若A一α是产生式选择，且若B和y是符号的任何两个串（包括空串e) 且存在若y=a,那么A一BY就是LR(O)项。之所以称作LR(O)项是由于它们不包括先行的显 式引用。 例5.3考虑例5.1的文法： + 这个文法存在着3个产生式选择和8个项目： SS S→.(S)S S→(.S)S S-(S.)S S-(S).S S-(S)5 日如果文法有二义性。那么由此就会存在多于一个的推导，则在右句型中就会有多于一个的句柄。如果文法没 有二义性，则句柄就是唯一的。(viable prefix)。因此，E、E+ 和E + n 都是右句型E + n 的可行前缀，但右句子格式n + n 却使 和n 作为它的可行前缀(表5 - 2的第1步和第2步)。请注意，n + 不是n + n 的可行前缀。 移进-归约分析程序将终结符从输入移进到栈直到它能执行一个归约以得到下一个右句子 格式。它发生在位于栈顶部的符号串匹配用于下一个归约的产生式的右边。这个串、它在右句 子格式中发生的位置以及用来归约它的产生式被称作右句型的句柄 (handle) 。例如，在右句子 格式n + n 中，它的句柄是由最左边的单个记号n 与用来归约它以产生新的右句型E + n的产生 式E→n 组成的串。这个新句型的句柄是整个串 E + n (一个可行的前缀)以及产生式E→E + n。 有时由于表示法上的弊端，我们要用串本身来作为句柄。 判断分析中的下一个句柄是移进-归约分析程序的主要任务。请注意，句柄串总是为它的 产生式(在下一步的归约中使用的产生式 )构成一个完整的右部，而且当归约发生时，句柄串的 最右边的位置将与栈的顶部相对应。所以对于移进-归约分析程序将要基于产生式右边的位置 来判断它的动作这一点而言，就看起来有些似是而非了。当这些位置到达产生式的右边末端时， 这个产生式就有可能是一个归约，而且句柄还有可能位于栈的顶部。但为了成为句柄，串位于 栈的顶部来匹配产生式的右边并不够。实际上，若 产生式可用于归约的话（如在例 5 . 1中)， 那么它的右边(空串)总是位于栈的顶部。归约仅发生在结果串实际为一个右句型时。例如，在 表5 - 1的第3步中，可完成用S→ 归约，但是得到的串(S S)并不是右句子格式，所以 在句子 格式(S)中的这个位置也不是句柄。 5.2 LR(0)项的有穷自动机与L R ( 0 )分析 5.2.1 LR(0)项 上下文无关文法的L R ( 0 )项(LR(0) item)(或简写为项( i t e m ) )是在其右边带有区分位置的产 生式选择。我们可用一个句点 (当然它就变成了元符号，而不会与真正的记号相混淆 )来指出 这个区分的位置。所以若 A→a是产生式选择，且若 b和g 是符号的任何两个串（包括空串 ）， 且存在着bg =a，那么A→b.g 就是L R ( 0 )项。之所以称作 L R ( 0 )项是由于它们不包括先行的显 式引用。 例5.3 考虑例5 . 1的文法： S¢→S S→( S ) S | 这个文法存在着3个产生式选择和8个项目： S¢→.S S¢→S. S→. ( S ) S S→( .S ) S S→( S. )S S→( S ) .S S→( S )S. 第 5章 自底向上的分析 1 5 3 下载 如果文法有二义性，那么由此就会存在多于一个的推导，则在右句型中就会有多于一个的句柄。如果文法没 有二义性，则句柄就是唯一的