China-pub.Co 下载 第5章 自底向上的分析 本章要点 ·自底向上分析概览 ·Yacc:LALR(I)分析程序的生成器 LR(O)项的有穷自动机及LRO)分析 ·使用Yacc生成TINY分析程序 ·SLR(1)分析 ·自底向上分析程序中的错误校正 ·一般的LR(I)和LALR(I)分析 前一章涉及到了递归下降和预测分析的自项向下分析的基本算法。在本章中，我们将描述 主要的自底向上的分析技术及其相关的构造。如在自顶向下的分析一样，我们将主要学习利用 最多 一个先行符号的分析算法，此外再谈一下如何扩展这个算法。 与LL(1)分析程序的术语相类似，最普通的自底向上算法称作LR(1)分析(LR(1) parsing)L表示由左向右处理输入，R表示生成了最右推导，而数字1则表示使用了先行的 个符号)。自底向上分析的作用还表现在它使得LR(O)分析(LR(O)parsing)也具有了意义，此 时在作出分析决定时没有考虑先行（因为可在先行记号出现在分析栈上之后再检查它，而且 倘若是这样发生的，它也就不会被算作先行了，所以这是可能的)SLR(I)分析(SLR( parsing,可简写为LR(I)分析)是对LR(1)分析的改进，它使用了一些先行。LALR(1)分析 (LALR(I)parsing,意即先行LR(I)分析)是比SLR(I)分析略微强大且比一般的LR(I)分析简 单的方法。 在本章节中将会谈到以上每一个分析方法的必要构造。这将包括LR(O)的DFA构造以及 LR(I)各项：SLR(I、LR(I)和LALR(I)分析算法的描述，以及相关分析表的构造。我们还将描 述Yacc(一个LALR(I)分析程序生成器)的用法，并为TINY语言使用Yacc生成一个分析程序，该 TNY语言构造出与在第5意中由递归下降分析程序开发的相同的语法树。 般而言，自底向上的分析算法的功能比自顶向下的方法强大（例如，左递归在自底向上 分析中就不成问题)。但是这些算法所涉及到的构造却更为复杂。因此，需要小心对它们的描 述，我们还需要利用文法的十分简单的示例来介绍它们。本章的开头先给出了这样的两个例 子，本章还会一直用到这两个例子。此外还会用到一些前章中的例子（整型算术表达式、语 句等等)。但是由于为全TNY语言用手工执行任何的自底向上的分析算法非常复杂，所以我 们并不打算完成它。实际上，所有重要的自底向上方法对于手工编码而言都太复杂了，但是 对于诸如Ycc的分析程序生成器却很合适。但是了解方法的操作却很重要，这样作为编译程 序的编写者就可对分析程序生成器的行为进行正确地分析了。由于分析程序生成器可以用 BNF中建议的语言语法来识别可能的问题，所以程序设计语言的设计者还可从这个信息中获 益不少。 为了掌握好自底向上的分析算法，读者还需要了解前面讲过的内容，这其中包括了有穷自 动机、从一个NFA中构造DFA的子集（第2章的2.3节和2.4节）、上下文无关文法的一般特性、推 导和分析树（第3章的3.2节和3.3节）。有时也需要用到FolIow集合（第4章的4.3节）。这一章从自底 向上的分析的概况开始谈起
下载 第5章 自底向上的分析 本章要点 • 自底向上分析概览 • Yacc: LALR(1)分析程序的生成器 • LR(0)项的有穷自动机及L R ( 0 )分析 • 使用Ya c c生成T I N Y分析程序 • SLR(1)分析 • 自底向上分析程序中的错误校正 • 一般的L R ( 1 )和L A L R ( 1 )分析 前一章涉及到了递归下降和预测分析的自顶向下分析的基本算法。在本章中，我们将描述 主要的自底向上的分析技术及其相关的构造。如在自顶向下的分析一样，我们将主要学习利用 最多一个先行符号的分析算法，此外再谈一下如何扩展这个算法。 与L L ( 1 )分析程序的术语相类似，最普通的自底向上算法称作 L R ( 1 )分析 ( L R ( 1 ) p a r s i n g ) ( L表示由左向右处理输入， R表示生成了最右推导，而数字 1则表示使用了先行的一 个符号 )。自底向上分析的作用还表现在它使得 L R ( 0 )分析(LR(0) parsing)也具有了意义，此 时在作出分析决定时没有考虑先行 (因为可在先行记号出现在分析栈上之后再检查它，而且 倘若是这样发生的，它也就不会被算作先行了，所以这是可能的 )。S L R ( 1 )分析 ( S L R ( 1 ) p a r s i n g，可简写为 L R ( 1 )分析)是对L R ( 1 )分析的改进，它使用了一些先行。 L A L R ( 1 )分析 (LALR(1) parsing，意即先行 L R ( 1 )分析)是比S L R ( 1 )分析略微强大且比一般的 L R ( 1 )分析简 单的方法。 在本章节中将会谈到以上每一个分析方法的必要构造。这将包括 L R ( 0 )的D FA构造以及 L R ( 1 )各项：S L R ( 1 )、L R ( 1 )和L A L R ( 1 )分析算法的描述，以及相关分析表的构造。我们还将描 述Ya c c (一个L A L R ( 1 )分析程序生成器)的用法，并为T I N Y语言使用Ya c c生成一个分析程序，该 T I N Y语言构造出与在第5章中由递归下降分析程序开发的相同的语法树。 一般而言，自底向上的分析算法的功能比自顶向下的方法强大 (例如，左递归在自底向上 分析中就不成问题 )。但是这些算法所涉及到的构造却更为复杂。因此，需要小心对它们的描 述，我们还需要利用文法的十分简单的示例来介绍它们。本章的开头先给出了这样的两个例 子，本章还会一直用到这两个例子。此外还会用到一些前章中的例子 (整型算术表达式、 i f语 句等等)。但是由于为全 T I N Y语言用手工执行任何的自底向上的分析算法非常复杂，所以我 们并不打算完成它。实际上，所有重要的自底向上方法对于手工编码而言都太复杂了，但是 对于诸如Ya c c的分析程序生成器却很合适。但是了解方法的操作却很重要，这样作为编译程 序的编写者就可对分析程序生成器的行为进行正确地分析了。由于分析程序生成器可以用 B N F中建议的语言语法来识别可能的问题，所以程序设计语言的设计者还可从这个信息中获 益不少。 为了掌握好自底向上的分析算法，读者还需要了解前面讲过的内容，这其中包括了有穷自 动机、从一个N FA中构造D FA的子集(第2章的2 . 3节和2 . 4节)、上下文无关文法的一般特性、推 导和分析树(第3章的3 . 2节和3 . 3节)。有时也需要用到F o l l o w集合(第4章的4 . 3节)。这一章从自底 向上的分析的概况开始谈起
China-pub.com 第5章自底向上的分析 151 下载 5.1自底向上分析概览 自底向上的分析程序使用了显式栈来完成分析，这与非递归的自顶向下的分析程序相类似 分析栈包括记号和非终结符，以及一些后面将讨论到的其他信息。自底向上的分析开始时栈是 空的，在成功分析的末尾还包括了开始符号。因此，可将自底向上的分析示意为： InputString StartSymbol accept 其中，分析栈在左边，输入位于正中间，而分析程序的动作则在右边（此时，“接受”是所指出 的唯一动作) 自底向上的分析程序有两种可能的动作（除“接受”之外）： )将终结符从输入的开头移进到栈的顶部。 2)假设有BNF选择A→a,将栈顶部的串α归约为非终结符A。 因此自底向上的分析程序有时称作是移进-归约分析程序⊙。移进动作是由书写单词shi指 出的。归约动作则由书写reduce单词给出且指出在归约中所用的BNF选择⊙。自底向上的分析 程序的另一个特征是：出于后面要讲到的技术原因，总是将文法与一个新的开始符号一同扩充 (augmented)。这就意味着若S是开始符号，那么就将新的开始符号S增加到文法中，同时还添 加一个单元产生式到前面的开始符号中： SS 下面是两个示例，之后再讨论这两个例子所表现出的自底向上分析的一些特性。 例5.1考虑以下用于成对括号的扩充文法： S-S S·(S)lE 表51给出了使用该文法的串()的自底向上的分析。 表5-1例5.1中文法的自底向上分析程序的分析动作 分析栈 输入 动作 ()s 移进 2 s( 用S一归约 3 S (S )S 移进 4 S IS) 用S+e白约 s 用S一()S归约 6 55 s 用S一S阳约 7 SS 接受 是惯例却是添加rede
5.1 自底向上分析概览 自底向上的分析程序使用了显式栈来完成分析，这与非递归的自顶向下的分析程序相类似。 分析栈包括记号和非终结符，以及一些后面将讨论到的其他信息。自底向上的分析开始时栈是 空的，在成功分析的末尾还包括了开始符号。因此，可将自底向上的分析示意为： $ I n p u t S t r i n g $ . . . . . . . . . . . . $ S t a rt S y m b o l $ a c c e p t 其中，分析栈在左边，输入位于正中间，而分析程序的动作则在右边 (此时，“接受”是所指出 的唯一动作)。 自底向上的分析程序有两种可能的动作(除“接受”之外)： 1) 将终结符从输入的开头移进到栈的顶部。 2) 假设有B N F选择A→a，将栈顶部的串a归约为非终结符A。 因此自底向上的分析程序有时称作是移进-归约分析程序 。移进动作是由书写单词s h i f t指 出的。归约动作则由书写 re d u c e单词给出且指出在归约中所用的 B N F选择 。自底向上的分析 程序的另一个特征是：出于后面要讲到的技术原因，总是将文法与一个新的开始符号一同扩充 ( a u g m e n t e d )。这就意味着若S是开始符号，那么就将新的开始符号 S¢ 增加到文法中，同时还添 加一个单元产生式到前面的开始符号中： S¢ → S 下面是两个示例，之后再讨论这两个例子所表现出的自底向上分析的一些特性。 例5.1 考虑以下用于成对括号的扩充文法： S¢ → S S → ( S ) S | 表5 - 1给出了使用该文法的串( )的自底向上的分析。 表5-1 例5 . 1中文法的自底向上分析程序的分析动作 分 析 栈 输 入 动 作 1 $ ( ) $ 移进 2 $ ( ) $ 用S→e 归约 3 $ (S ) $ 移进 4 $ ( S ) $ 用S→ 归约 5 $ (S) S $ 用S→ (S) S归约 6 $ S $ 用S¢→S归约 7 $ S¢ $ 接受 第 5章 自底向上的分析 1 5 1 下载 由于相同的原因，自顶向下的分析程序可被称作生成-匹配分析程序，但这并未成为惯例。 在归约的情况中，可如同在自顶向下分析中为一个生成动作所做的一样，仅仅由 B N F选择自身写出即可，但 是惯例却是添加re d u c e
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 编译原理及实践 下载
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 下载 如果文法有二义性，那么由此就会存在多于一个的推导，则在右句型中就会有多于一个的句柄。如果文法没 有二义性，则句柄就是唯一的
154翁译原理及实我 China-pub.co 下载 S 例5.4例5.2的文法存在着以下的8个项目： E→.E E→E. E-.E+n E→E.+n E-E+.n E-E+n. E-.n E-n. 项目概念的思想就是指项目记录了特定文法规则右边识别中的中间步骤。特别地，项目A 一B.y是由文法规则选择A一构成（其中α=y),这一点意味着早已看到了B,且可能从 一个 输入记号中获取Y。从分析栈的观点来看，这就意味着B必须出现在栈的顶部。项目A一.α意味 着将要利用文法规则选择A一a识别4（将这样的项目称作初始项(initiate)。项目A→a.意味着 α现在位于分析栈的顶部，而且若A一α在下一个归约中使用的话，它有可能就是句柄（将这样 的项目称作完整项(complete item)。 5.2.2项目的有穷自动机 LR(O)项可作为一个保持有关分析栈和移进-归约分析过程的信息的有穷自动机的状态来 使用。这将从作为非确定性的有穷自动机开始。从这个LR(O)项的NFA中可利用第2章的子集构 造来构建出LR(O)项集合的DFA。正如将要看到的一样，直接构造LR(O)项集合的DFA也是很简 单的。 LR(O)项的NFA的转换是什么呢？若有项目A一aY,且假设y以符号开始，其中X可以是 记号或非终结符，所以该项目就可写作A→αX.。那么在符号X上就有一个从由该项目代表的 状态到由项目A一αXn代表的状态的转换。把它写在一般格式中，就是： 若X是一个记号，那么该转换与X的一个在分析中从输入到栈顶部的移进相对应。另一方面， (A一a可X一(A一a可 若X是一个非终结符，因为X永远不会作为输入符号出现，所以该转换的解释就复杂了。实际 上，这样的转换仍与在分析时将X压入到栈中相对应，但是它只发生在由产生式X一β形成的归 约时。由于这样的归约前面必须有一个B的识别，而且由初始项X一阝给出的状态代表了这个处 理的开始（句点指出将要识别一个B),则对于每个项目A→αX,必须为X的每个产生式X一B添 加一个e产生式， 它指示通过识别它的产生式的右边的任意匹配来产生X。 这两种情况只表示LR(O)项的NFA中的转换，它并未讨论到NFA的初始状态和接受状态
S→. 例5.4 例5 . 2的文法存在着以下的8个项目： E¢→.E E¢→E. E→.E + n E→E. + n E→E + .n E→E + n. E→.n E→n. 项目概念的思想就是指项目记录了特定文法规则右边识别中的中间步骤。特别地，项目 A →b.g 是由文法规则选择A→a构成（其中a = b g），这一点意味着早已看到了b，且可能从下一个 输入记号中获取g。从分析栈的观点来看，这就意味着 b必须出现在栈的顶部。项目 A→.a意味 着将要利用文法规则选择A→a识别A(将这样的项目称作初始项(initial item)。项目A→a.意味着 a现在位于分析栈的顶部，而且若 A→a在下一个归约中使用的话，它有可能就是句柄（将这样 的项目称作完整项（complete item））。 5.2.2 项目的有穷自动机 L R ( 0 )项可作为一个保持有关分析栈和移进-归约分析过程的信息的有穷自动机的状态来 使用。这将从作为非确定性的有穷自动机开始。从这个 L R ( 0 )项的N FA中可利用第2章的子集构 造来构建出L R ( 0 )项集合的D FA。正如将要看到的一样，直接构造 L R ( 0 )项集合的D FA也是很简 单的。 L R ( 0 )项的N FA的转换是什么呢？若有项目 A→a.g，且假设g 以符号X开始，其中X可以是 记号或非终结符，所以该项目就可写作 A→aX.h。那么在符号X上就有一个从由该项目代表的 状态到由项目A→aX.h代表的状态的转换。把它写在一般格式中，就是： 若X是一个记号，那么该转换与 X的一个在分析中从输入到栈顶部的移进相对应。另一方面， 若X是一个非终结符，因为 X永远不会作为输入符号出现，所以该转换的解释就复杂了。实际 上，这样的转换仍与在分析时将 X压入到栈中相对应，但是它只发生在由产生式 X→b形成的归 约时。由于这样的归约前面必须有一个 b的识别，而且由初始项X→.b给出的状态代表了这个处 理的开始(句点指出将要识别一个b），则对于每个项目A→a.Xh，必须为X的每个产生式X→b添 加一个 产生式， 它指示通过识别它的产生式的右边的任意匹配来产生 X。 这两种情况只表示 L R ( 0 )项的N FA中的转换，它并未讨论到 N FA的初始状态和接受状态。 1 5 4 编译原理及实践 下载