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