《编译原理》课程书籍文献（编译原理及实践）第5章自底向上的分析.pdf_大学文库

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节)。这一章从自底向上的分析的概况开始谈起

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 编译原理及实践下载

China-pub.com 第5章自底向上的分析 155 下载 NFA的初始状态应与分析程序的初始状态相对应：栈是空的，而且将要识别一个S,其中S是文法的开始符号。因此，任何由S的产生式选择构造的初始项S一α都可作为开始状态。不幸的是，S可能有许多这样的产生式，如何知道该选择哪一个呢？实际上，我们是无法做到这一点的。其解决办法是通过产生式S→S扩充(augment)文法，其中S是一个新的非终结符。接着， S成为扩充文法(augmented grammar)的开始状态，且初始项S.S也成为NFA的开始状态。这就是为什么扩充前面例子文法的原因。在这个NFA中，哪些状态将成为接受状态呢？读者此时必须记住NFA的任务是用于了解分析的状态，而不是如第2章中自动机那样被设计为完全识别串。因此，分析程序本身将决定何时接受，而NFA则无需包含这一信息，所以NFA实际上根本就没有接受状态(NFA存在着有关接受的一些信息，但并不是在接受状态中。在描述使用自动机制分析算法时还会讨论到这一占)。这样一来，LR(O)项的NFA的描述就完整了。现在来讨论前面两个例子的简单文法以及构造它们的LR(O)项的NFA。例5.55.3列出了例5.1的文法的8个LR(0)项，所以这个NFA就有8个状态，如图5-1所示。请注意，图中在非终结符S之前带有一个句点的每个项目都有一个到S的每个初始项的ε-转换。 →5 (S)S. →(S).S 图-1例5.5中文法的LR(O)项的NFA 例5.6在例5.4中，我们列出了与例5.2中的文法相关的LR(0)项。图5-2是这些项目的NFA。请注意，初始项E一E+·有一个到它自身的e转换（这种情况会出现在带有直接左递归的所有文法中)。为了完成项目用于了解分析状态的描述，我们必须根据第2章的子集构造来构建与项目的 NFA相对应的项目集合的DFA,这样之后就可说明LR(O)分析算法了。我们将执行前面刚给出的NFA的两个例子的子集构造。例5.7考虑图5-1的NFA。相关的DFA的开始状态是由项目S一S组成的集合的e-闭包，而这又是3个项目的集合{S一S,S一.(S)S,S一.}由于S有一个从S一S到S一S的转换，所以也就存在着一个从开始状态到DFA状态{S一S.}的对应转换（不存在从S一S到任何其他项目的E

N FA的初始状态应与分析程序的初始状态相对应：栈是空的，而且将要识别一个 S，其中S 是文法的开始符号。因此，任何由 S的产生式选择构造的初始项S→.a都可作为开始状态。不幸的是，S可能有许多这样的产生式，如何知道该选择哪一个呢？实际上，我们是无法做到这一点的。其解决办法是通过产生式 S¢→S 扩充( a u g m e n t )文法，其中S¢是一个新的非终结符。接着， S¢ 成为扩充文法(augmented grammar)的开始状态，且初始项S¢→.S 也成为N FA的开始状态。这就是为什么扩充前面例子文法的原因。在这个N FA中，哪些状态将成为接受状态呢？读者此时必须记住 N FA的任务是用于了解分析的状态，而不是如第 2章中自动机那样被设计为完全识别串。因此，分析程序本身将决定何时接受，而N FA则无需包含这一信息，所以 N FA实际上根本就没有接受状态 ( N FA存在着有关接受的一些信息，但并不是在接受状态中。在描述使用自动机制分析算法时还会讨论到这一点)。这样一来，L R ( 0 )项的N FA的描述就完整了。现在来讨论前面两个例子的简单文法以及构造它们的L R ( 0 )项的N FA。例5.5 5 . 3列出了例5 . 1的文法的8个L R ( 0 )项，所以这个N FA就有8个状态，如图5 - 1所示。请注意，图中在非终结符S之前带有一个句点的每个项目都有一个到S的每个初始项的 - 转换。图5-1 例5 . 5中文法的L R ( 0 )项的N FA 例5.6 在例5 . 4中，我们列出了与例5 . 2中的文法相关的L R ( 0 )项。图5 - 2是这些项目的N FA。请注意，初始项E→.E + n 有一个到它自身的 - 转换(这种情况会出现在带有直接左递归的所有文法中)。为了完成项目用于了解分析状态的描述，我们必须根据第 2章的子集构造来构建与项目的 N FA相对应的项目集合的 D FA，这样之后就可说明 L R ( 0 )分析算法了。我们将执行前面刚给出的N FA的两个例子的子集构造。例5.7 考虑图5 - 1的N FA。相关的D FA的开始状态是由项目S¢→.S组成的集合的 -闭包，而这又是3个项目的集合{ S¢→.S, S→. ( S ) S, S →. }。由于S有一个从S¢→ .S到S¢→ S.的转换，所以也就存在着一个从开始状态到D FA状态{ S¢→ S. }的对应转换(不存在从S¢→ S.到任何其他项目的第 5章自底向上的分析 1 5 5 下载

China-pub.com 第5章自底向上的分析 157 下载中是整个DFA .E E E'→E (0 4E+,a ③ ④ 图5-4与图5-2中的NFA相对应的项目集合的DFA 在LR(O)项集合的DFA中，有时需要区分在E闭包步骤中添加到状态中的项目与引起状态作为非e-转换的目标的那些项目。前者被称作闭包项(closure item),后者被称作核心项(kernel item)。在图5-4的状态0中，E'一E是（唯一的）核心项，而E一E+n和E,n则是闭包项。在图 53的状态2中，S一(.S)S是核心项，而S一.(S)S和S一.是闭包项。根据项目的NFA的E转换的定义，所有的闭包项都是初始项。区分核心项与闭包项的重要性在于：若有一个文法，核心项唯一地判断出状态以及它的转换，那么只需指出核心项就可以完整地表示出项目集合的DFA来。因此，构造DFA的分析程序生成器只报告核心项（例如对于Yacc而言，这也是正确的）。若项目集合的DFA是直接运算的，这样就比首先计算项目的NFA之后再应用子集构造要更简化一些。从项目的集合确实可很容易地立即判断出什么是-转换以及初始项指向哪里。因此，如Yacc的分析程序生成器总是从文法直接计算DFA,本章后面的内容也是这样做的。 5.2.3LR(0)分析算法现在开始讲述LR(O)分析算法。由于该算法取决于要了解项目集合的DFA的当前状态，所以须修改分析栈以使不但能存储符号而且还能存储状态数。这是通过在压入一个符号之后再将新的状态数压入到分析栈中完成的。实际上，状态本身就包含了有关符号的所有信息，所以可完全将符号省掉而只在分析栈中保存状态数。但是为了方便和清晰起见，我们仍将在栈中保留了符号。为了能开始分析，我们将底标记$和开始状态0压入到栈中，所以分析在开始时的状况表示为分析栈输入 InputString S 现在假设下一步是将记号n移进到栈中并进入到状态2（当DFA如在图5-4中所示一样，且n 是输入中的下一个记号时，结果就是这样的)。表示如下：分析栈输入的剩余部分

中是整个D FA。图5-4 与图5 - 2中的N FA相对应的项目集合的D FA 在L R ( 0 )项集合的D FA中，有时需要区分在闭包步骤中添加到状态中的项目与引起状态作为非 - 转换的目标的那些项目。前者被称作闭包项 (closure item)，后者被称作核心项 ( k e r n e l i t e m )。在图5 - 4的状态0中，E¢→.E是(唯一的)核心项，而E→.E + n 和E→.n 则是闭包项。在图 5 - 3的状态2中，S→ (. S ) S是核心项，而S→. ( S ) S和S→. 是闭包项。根据项目的N FA的转换的定义，所有的闭包项都是初始项。区分核心项与闭包项的重要性在于：若有一个文法，核心项唯一地判断出状态以及它的转换，那么只需指出核心项就可以完整地表示出项目集合的 D FA来。因此，构造D FA的分析程序生成器只报告核心项(例如对于Ya c c而言，这也是正确的)。若项目集合的D FA是直接运算的，这样就比首先计算项目的 N FA之后再应用子集构造要更简化一些。从项目的集合确实可很容易地立即判断出什么是 -转换以及初始项指向哪里。因此，如Ya c c的分析程序生成器总是从文法直接计算D FA，本章后面的内容也是这样做的。 5.2.3 LR(0)分析算法现在开始讲述L R ( 0 )分析算法。由于该算法取决于要了解项目集合的 D FA的当前状态，所以须修改分析栈以使不但能存储符号而且还能存储状态数。这是通过在压入一个符号之后再将新的状态数压入到分析栈中完成的。实际上，状态本身就包含了有关符号的所有信息，所以可完全将符号省掉而只在分析栈中保存状态数。但是为了方便和清晰起见，我们仍将在栈中保留了符号。为了能开始分析，我们将底标记 $和开始状态0压入到栈中，所以分析在开始时的状况表示为：分析栈输入 $ 0 InputString $ 现在假设下一步是将记号n 移进到栈中并进入到状态2 (当D FA如在图5 - 4中所示一样，且n 是输入中的下一个记号时，结果就是这样的 )。表示如下：分析栈输入 $ 0 n 2 InputString $ 的剩余部分第 5章自底向上的分析 1 5 7 下载

158 翁译原理及实践 China-pub.co 下载 LR(O)分析算法根据当前的DFA状态选择一个动作，这个状态总是出现在栈的顶部。定义：LR(O)分析算法(LR(O)parsing algorithm)。令s为当前的状态（位于分析栈的顶部)。则动作定义如下： 1.若状态s包含了格式A→α邓的任何项目，其中X是一个终结符，则动作就是将当前的输入记号移进到栈中。若这个记号是X,且状态s包含了项目A一→αX郑，则压入到栈中的新状态就是包含了项目A→αXB的状态。若由于位于刚才所描述的格式的状态s中的某个项目，这个记号不是X,则声明一个错误。 2.若状态s包含了任何完整的项目（格式A→a.的一个项目），则动作是用规则A→α 归约。假设输入为空，用规则S一S归约（其中S是开始状态）与接受相等价：若输入不为空，则出现错误。在所有的其他情况中，新状态的计算如下：将串α及它的所有对应状态从分析栈中删去（根据DFA的构造方式，串α必须位于栈的顶部）。相应地，在DFA中返回到由a开始构造的状态中（这须是由α的刷除所揭示的状态)。由于构造DFA,这个状态就还须包含格式B一QAB的一个项目。将A压入到栈中，并压入包含了项目B一AB的状态（作为新状态）。（请注意，由于正将压入到栈中，所以这与在DFA中跟随A的转换相对应（这实际上是合理的）。若以上的规则都是无歧义的，则文法就是LR(O)文法(LR(O)grammar)。这就意味着若状态包含了完整项目A→α.，那么它就不能再包含其他项目了。实际上，若这样的状态还包含了一个“移进的”项目A→α郑(X是一个终结符)，就会出现一个到底是执行动作(1)还是执行动作(2)的二义性。这种情况称作移进-归约冲突(shift-reduce confliet)。类似地，如果这样的状态包含了另一个完整项目B一B.,那么也会出现一个关于为该归约使用哪个产生式(4→α 或B一B)二义性。这种情况称作归约-归约冲突(reduce-reduce conflict))。所以，当仅当每个状态都是移进状态（仅包含了“移进”项目的状态）或包含了单个完整项目的归约时，该文法才是LR(O). 我们注意到上面例子中所用到的两个文法都不是LR(O)文法。在图5-3中，状态0、状态2和状态4都包括了对于LR(O)分析算法的移进-归约冲突：在图5-4的DFA中，状态1包含了一个移进-归约冲突。由于几乎所有“真正的”文法都不是LR(O),所以这并不奇怪。但下面将会给出一个文法是LR(O)的示例。例5.9考虑文法 A-(A)川a 扩充的文法具有如图5-5所示的项目集合的DFA,而这就是LR(O)。为了看清LR(O)分析算法是如何工作的，可考虑一下串(a)。该串的分析是根据表5-3各步骤所给出的LR(O)分析算法进行。分析开始于状态0，因为这个状态是一个移进状态，所以将第1个记号（移进到栈中。接着，由于DFA指出了在符号（上从状态0到状态3的转换，所以将状态3压入到栈中。状态3 也是一个移进状态，所以下一个（也被移进到栈中，而且在（上的转换返回到状态3。移进再一次将a放入到栈中，而且a上的转换由状态3进入到状态2。现在位于表5-3的第4步，而且己到达了第1个归约状态。这里的状态2和符号a都是由栈弹出的，并回到处理中的状态3。接着，将A压入到栈中，且得到由状态3到状态4的4转换。状态4是一个移进状态，所以)被移进到栈中，且)上的转换使分析转到状态5。这里发生了一个由规则A一(A)进行的归约它从栈中弹出状态5、状态4、状态3以及符号)、A和)。现在的分析位于状态3中，而且A和

L R ( 0 )分析算法根据当前的D FA状态选择一个动作，这个状态总是出现在栈的顶部。定义：L R ( 0 )分析算法(LR(0) parsing algorithm)。令s 为当前的状态(位于分析栈的顶部)。则动作定义如下： 1. 若状态s 包含了格式A→a.Xb的任何项目，其中X是一个终结符，则动作就是将当前的输入记号移进到栈中。若这个记号是 X，且状态s 包含了项目A→a.Xb，则压入到栈中的新状态就是包含了项目 A→aX.b的状态。若由于位于刚才所描述的格式的状态s 中的某个项目，这个记号不是X，则声明一个错误。 2. 若状态s 包含了任何完整的项目(格式A→a. 的一个项目)，则动作是用规则A→a 归约。假设输入为空，用规则S¢→S归约(其中S是开始状态)与接受相等价；若输入不为空，则出现错误。在所有的其他情况中，新状态的计算如下：将串a及它的所有对应状态从分析栈中删去（根据DFA的构造方式，串a必须位于栈的顶部）。相应地，在D FA中返回到由a开始构造的状态中（这须是由a的删除所揭示的状态）。由于构造D FA，这个状态就还须包含格式B→a.Ab的一个项目。将A压入到栈中，并压入包含了项目B→aA.b的状态（作为新状态）。（请注意，由于正将A 压入到栈中，所以这与在DFA中跟随A的转换相对应(这实际上是合理的)。若以上的规则都是无歧义的，则文法就是 L R ( 0 )文法(LR(0) grammar)。这就意味着若一个状态包含了完整项目A→a.，那么它就不能再包含其他项目了。实际上，若这样的状态还包含了一个“移进的”项目 A→a.Xb（X是一个终结符 )，就会出现一个到底是执行动作 ( 1 )还是执行动作( 2 )的二义性。这种情况称作移进-归约冲突 (shift-reduce conflict)。类似地，如果这样的状态包含了另一个完整项目 B→b.，那么也会出现一个关于为该归约使用哪个产生式 (A→a 或B→b）二义性。这种情况称作归约-归约冲突 (reduce-reduce conflict)。所以，当仅当每个状态都是移进状态(仅包含了“移进”项目的状态 )或包含了单个完整项目的归约时，该文法才是L R ( 0 )。我们注意到上面例子中所用到的两个文法都不是 L R ( 0 )文法。在图5 - 3中，状态0、状态2和状态4都包括了对于L R ( 0 )分析算法的移进-归约冲突；在图 5 - 4的D FA中，状态1包含了一个移进-归约冲突。由于几乎所有“真正的”文法都不是 L R ( 0 )，所以这并不奇怪。但下面将会给出一个文法是L R ( 0 )的示例。例5.9 考虑文法 A→ ( A ) | a 扩充的文法具有如图 5 - 5所示的项目集合的 D FA，而这就是 L R ( 0 )。为了看清 L R ( 0 )分析算法是如何工作的，可考虑一下串 ( ( a ) )。该串的分析是根据表 5 - 3各步骤所给出的 L R ( 0 )分析算法进行。分析开始于状态 0，因为这个状态是一个移进状态，所以将第 1个记号(移进到栈中。接着，由于 D FA指出了在符号 (上从状态0到状态3的转换，所以将状态 3压入到栈中。状态 3 也是一个移进状态，所以下一个 (也被移进到栈中，而且在 (上的转换返回到状态 3。移进再一次将a放入到栈中，而且 a上的转换由状态 3进入到状态 2。现在位于表 5 - 3的第4步，而且已到达了第1个归约状态。这里的状态 2和符号a都是由栈弹出的，并回到处理中的状态 3。接着，将A压入到栈中，且得到由状态 3到状态4的A转换。状态 4是一个移进状态，所以 )被移进到栈中，且 )上的转换使分析转到状态 5。这里发生了一个由规则 A→ ( A ) 进行的归约，它从栈中弹出状态 5、状态 4、状态3以及符号)、A和)。现在的分析位于状态 3中，而且A和 1 5 8 编译原理及实践下载

状态4又被压入到栈中。 )再一次被移进到栈中，且压入状态 5。由A→ ( A ) 进行的另一个归约从栈中(向后地)删除了串( 3 A 4 ) 5，而将分析留在状态 0中。现在A已被压入且也得到了由状态0到状态1的A转换。状态1是接受状态。由于输入现在是空的，则分析算法承认它。图5-5 例5 . 9的项目集合的D FA 表5-3 例5 . 9的分析动作分析栈输入动作 1 $ 0 ( ( a ) ) $ 移进 2 $ 0 ( 3 ( a ) ) $ 移进 3 $ 0 ( 3 ( 3 a ) ) $ 移进 4 $ 0 ( 3 ( 3 a 2 ) ) $ 用A→ a归约 5 $ 0 ( 3 ( 3 A 4 ) )$ 移进 6 $ 0 ( 3 ( 3 A 4 ) 5 ) $ 用A→ ( A ) 归约 7 $ 0 ( 3 A 4 ) $ 移进 8 $ 0 ( 3 A 3 ) 5 $ 用A→ ( A ) 归约 9 $ 0 A 1 $ 接受也可将项目集合的 D FA以及由L R ( 0 )分析算法指定的动作合并到分析表中，所以 L R ( 0 ) 分析就变成一个表驱动的分析方法了。其典型结构是：表的每行用 D FA的状态标出，而每一个列也如下标出。由于 L R ( 0 )分析状态是“移进的”状态或“归约的”状态，所以专门利用一列来为每个状态指出它。若是“归约的”状态，就用另一个列来指出在归约中所使用的文法规则选择。若是移进的状态，将被移进的符号会判断出下一个状态 (通过D FA )，所以每个记号都会有一个列，而这些记号的各项都是有关该记号移进后将移到的新状态。由于不能在输入中真正地看到它们，所以尽管分析程序的行为好像是它们被移进了，非终结符上的转换 (在归约时被压入 )仍代表着一个特殊情况。因此，在“移进的”状态中还需要为每个非终结符有一个列，而且按照惯例，这些列被列入到称为 g o t o部分的表的一个单独部分中。表5 - 4就是这样的分析表的一个例子，它是例 5 . 9中文法的表格。读者可以证实这个表将引出如在表5 - 3中给出的示例的分析动作。第 5章自底向上的分析 1 5 9 下载

《编译原理》课程书籍文献（编译原理及实践）第5章 自底向上的分析

《编译原理》课程书籍文献（编译原理及实践）第5章自底向上的分析