China-pub.com 第5章自底向上的分析 161 下载 均满足时，文法为SLR(I): 若第1个条件不满足，就表示这是一个移进-归约冲突(shin-reduce conflict)。若第2个条件 不满足，就表示这是一个归约-归约冲突(reduce-reduce conflict)。 这两个条件同前一章中所述的LL()分析的两个条件在本质上是类似的。但是如同使用所 有的移进-归约分析方法一样，可将决定使用哪个文法规则推迟到最后，同时还可考虑一个更 强大的分析程序。 SLR(I)分析的分析表也可以用与前一节所述的LR(O)分析的分析表的类似方式构造。两者 的差别如下：由于状态在SL(1)分析程序中可以具有移进和归约（取决于先行），输入部分中的 每项现在必须要有一个“移进”或“归约”的标签，而且文法规则选择也必须被放在标有“归 约”的项中。这还使得动作和规则列成为多余。由于输入结束符号$也可成为一个合法的先行， 所以必须为这个符号在输入部分建立一个新的列。我们将SLR(1)分析表的构造放在SLR(1)分析 的第1个示例中。 例5.10考虑例5.8中的文法，它的项目集合的DFA已列在了图5-4中。正如前面所述的，这个 文法不是LR(O),而是SLR(I)。非终结符的Follow集合是Follow(E)={$}和Follow(E)={$,+}。 表5-5是SLR(1)分析表。在表中，移进由表项中的字母s指出，归约由字母r指出。因此，在输 入+的状态1中，指出了一个移进，以及一个到状态3的转换。另一方面，在输入+的状态2中， 指出了利用产生式E一n归约。在输入$的状态1中还用动作“接受”代替了r(E一E)。 表5-5例5.10的SLR(1)分析表 翰入 Goto n + E 接受 r(En r(E-n) E-E+) r(E-E+n) 这个示例的最后是串n+n+n的分析。表5-6是它的分析步骤。该图的步骤1以输入记号n 的状态0开始，接着分析表指出动作“s2”,即：将记号移进到栈中并进入到状态2。在表5-6中， 将它与阶段“shin2” 起指出来。在该图的步骤2中，分析程序是在状态2中且带有输入记号 +,表还指出了用规则E·n归约。此时，从栈中弹出状态2和记号n。使状态0腿盛出来。将符 号E压入且将E的Goo从状态0带到状态1。第3步中的分析程序是带有输入记号+的状态1，且表 还指出了移进以及指向状态3的转换。在输入的状态3中，表也指出了一个移进和到状态4的 转换。在输入+的状态4中，表指出用规则E一E+n归约。这个归约是由将串E+n和与它相结 合的来自栈的状态弹出来完成的，并再一次禁露状态0，将E压入并将Gto带到状态1中。分析 的其他步骤是类似的。 表5-6例5.10的分析动作 分析栈 输入 动作 n+atas 移进2均满足时，文法为S L R ( 1 )。 若第1个条件不满足，就表示这是一个移进-归约冲突 (shift-reduce conflict)。若第2个条件 不满足，就表示这是一个归约-归约冲突(reduce-reduce conflict)。 这两个条件同前一章中所述的 L L ( 1 )分析的两个条件在本质上是类似的。但是如同使用所 有的移进-归约分析方法一样，可将决定使用哪个文法规则推迟到最后，同时还可考虑一个更 强大的分析程序。 S L R ( 1 )分析的分析表也可以用与前一节所述的 L R ( 0 )分析的分析表的类似方式构造。两者 的差别如下：由于状态在S L R ( 1 )分析程序中可以具有移进和归约 (取决于先行)，输入部分中的 每项现在必须要有一个“移进”或“归约”的标签，而且文法规则选择也必须被放在标有“归 约”的项中。这还使得动作和规则列成为多余。由于输入结束符号 $也可成为一个合法的先行， 所以必须为这个符号在输入部分建立一个新的列。我们将 S L R ( 1 )分析表的构造放在S L R ( 1 )分析 的第1个示例中。 例5.10 考虑例5 . 8中的文法，它的项目集合的D FA已列在了图5 - 4中。正如前面所述的，这个 文法不是L R ( 0 )，而是S L R ( 1 )。非终结符的F o l l o w集合是F o l l o w (E¢) = {$}和Follow (E) = {$, +}。 表5 - 5是S L R ( 1 )分析表。在表中，移进由表项中的字母 s 指出，归约由字母r 指出。因此，在输 入+的状态1中，指出了一个移进，以及一个到状态 3的转换。另一方面，在输入 +的状态2中， 指出了利用产生式E→n 归约。在输入$的状态1中还用动作“接受”代替了r ( E→E )。 表5-5 例5 . 1 0的S L R ( 1 )分析表 状 态 输 入 G o t o n + $ E 0 s 2 1 1 s 3 接受 2 r (E→n) r (E→n) 3 s 4 4 r ( E→E + n) r (E→E + n) 这个示例的最后是串n + n + n 的分析。表5 - 6是它的分析步骤。该图的步骤1以输入记号n 的状态0开始，接着分析表指出动作“s 2”，即：将记号移进到栈中并进入到状态2。在表5 - 6中， 将它与阶段“shift 2”一起指出来。在该图的步骤 2中，分析程序是在状态2中且带有输入记号 +，表还指出了用规则E→n 归约。此时，从栈中弹出状态 2和记号n。使状态0曝露出来。将符 号E压入且将E的G o t o从状态0带到状态1。第3步中的分析程序是带有输入记号+的状态1，且表 还指出了移进以及指向状态 3的转换。在输入n 的状态3中，表也指出了一个移进和到状态 4的 转换。在输入+的状态4中，表指出用规则E→E + n归约。这个归约是由将串E + n和与它相结 合的来自栈的状态弹出来完成的，并再一次暴露状态 0，将E压入并将G o t o带到状态1中。分析 的其他步骤是类似的。 表5-6 例5 . 1 0的分析动作 分 析 栈 输 入 动 作 1 $ 0 n + n + n $ 移进2 第 5章 自底向上的分析 1 6 1 下载