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