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到任何其他项目的EN 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 下载