《如何判定lr(0)分析程序工作的正确性》由会员分享，可在线阅读，更多相关《如何判定lr(0)分析程序工作的正确性（3页珍藏版）》请在金锄头文库上搜索。
1、如何判定如何判定 LR(0)分析程序工作的正确性？分析程序工作的正确性？ 在实际使用 LR(0)分析器之前，我们需要确信它们可以正确运行。这通常通过陈述并证明一个“正确性定理”来完成。对于我们的目的而言，重要的是包含在这样一个证明中的洞察力。一旦理解了基本思想，也就容易明白证明的细节。 LR(0)分析器的正确性依赖于两点观察。首先，CFSM 仅能读入的符号串是所分析的文法的活前缀。这一点观察非常重要，因为它告诉我们如果看到非法符号，那么该符号将不会被语法分析器所接受，理由是它不可能是活前缀的一部分。 第二点观察是语法分析器的 action 表正确地指示了适当的行动。 即，action 表指示移
2、进直到看到了句柄的结尾。随后它指示必要的归约，用相应的产生式的左部替换句柄。 回忆右句型的活前缀是不超出其句柄的任意前缀。 句柄是可被正确地归约为非终结符的最左短语。直观地说，LR(0)分析器或任何其他的移进-归约分析器会移进符号以形成一个活前缀，直到整个句柄都被移进为止。随后该句柄被归约为单独的非终结符。LR(0)分析器的CFSM 必须能够读入所有活前缀以保证没有漏掉任何合法归约。 CFSM 不需要读入右句型的所有可能的前缀，因为句柄一被移进并识别，就立即被归约。类似地，如果一个符号序列不可能是任何右句型的前缀，则它无法被分析并且不应被 CFSM 接受。 假定有活前缀 ，怎样从其中创建新的活
3、前缀？ 的任意前缀都是活前缀，而且如果 仅包含终结符，这些前缀是可由它创建的仅有的活前缀。如果 至少包含一个非终结符 B，则可以把 写成B。可以使用某个产生式 B 来重写 B 得到。的任意前缀都是活前缀，由于是句柄，因此没有活前缀可以扩展超过。作为一般的规则，我们通过取以非终结符 B 结尾的活前缀并把 B 替换为的任意前缀，来创建新的活前缀，其中 B 。 为证明活前缀和由 CFSM 所读入的字符串的对应关系，从 CFSM 的开始状态 s0开始。s0可通过读入到达，而是所有右句型的活前缀。根据其构造，s0包含一个基本项：S $。s0面临$时有后继。这是正确的，正如我们所知$的所有前缀都是活前缀，
4、因为$可被归约为 S。令C 是$的以非终结符结尾的任意前缀。在读入后，将处于 CFSM 的一个状态 s，其中包含形如 D C的一项。这种形式的一个项目必定出现在 S 中，因为我们知道从状态 s 开始可以读入 C。因为 C 是非终结符，对于左部为 C 的每条产生式，LR(0)闭包操作将包含形如 C 的项目。根据其构造，状态 s 面临输入时有后继状态，这意味着的任意前缀可以从 s0读入。重复这样的论证，容易看出从创建的任意活前缀也能够由 CFSM 读入。因此，以状态 s0开始的 CFSM 能够读入所有可能的活前缀。 为明白 CFSM 仅读入活前缀，假定由 CFSM 所读入的所有长度为 n 的字符串
5、都是活前缀。这对 n = 0 的情况肯定是正确的。令X 是可由 CFSM 读入的长度为 n+1 的字符串。在读入后，必定处于状态 s 中，从它开始可以读入 X。这意味着 s 包含形如 B X的项目。该项目是基本项或者闭包项。如果它是基本项，必定至少一个字符长，否则该项目一定是开始项目 S $。已知$的所有前缀都是活跃的，因此假定| = m 1。X 的最后m 个符号必为，因为 s 中包含 B X。在读入X 开头的 n - m 个符号之后，将处于包含 B X的状态 s。s必须也包含 B 的前面直接为的项目，因为 B X仅能通过预测被创建。因此，B 能够从 s读入，且因此B 能够从 s0读入。由于|
6、B| n，B 是活前缀，且因此X = X 也是活前缀。 如果 B X是闭包项，则必定为空。B X通过求某个基本项的闭包被直接或间接地加入。即，s 必定包含基础项 D C1，其中 C1 C22, C2 C33, , C B+1。利用上一段的论证，可以断定B 是活前缀，且X 也是活前缀。 以上已经证明了 CFSM 精确地接受所分析的文法的活前缀集。 为确信 LR(0)分析器能够正确工作，余下的一切就是要证明相应于 CFSM 状态的语法分析器 action 表总是执行正确的分析动作。 假定正在分析某个有效输入字符串 z， 并且已经完成了零次或多次正确的归约得到右句型y，其中 y 是剩余的输入，而已经
7、被移进分析栈中。我们通过从 y 移进零个或多个终结符号到达下一个句柄。假定 S*rmAw rm w，其中 = x，且 xw = y。即，正确的语法分析器动作是读入 x，随后执行 A 的归约。可以确信这是 LR(0)编译器将要做的么？ 假定在移进之后处于状态 s。x 能够从 s 读入，因为x = 是活前缀。进一步，语法分析器直到移进所有 x 之前不执行归约。 这个结果是根据这样一个事实得出： 在移进 x 时访问的每个状态必须执行移进动作，因此任意归约动作将导致移进-归约冲突，而这对 LR(0)文法来说是不允许的。 因此语法分析器在读入 x 时不执行假归约。已知A 是活前缀。读入之后所到达的状态一定包含一项 B A，并因此也包含一项 A 。该状态面临的后继必须包含一项 A ，此状态在移进 x 之后到达，而且将会执行所期望的归约动作。 以上论述证明，在已经将输入字符串 z 归约为y 之后，语法分析器将正确地执行下面的步骤，并把w 归约为Aw。通过对推导 z 所需步数的归纳，可以确定它将最终被归约为目标符号 S，由此成功地完成分析。 最后一点，如果交给 LR(0)分析器一个不正确的输入字符串将会怎样？ CFSM 仅能够读入活前缀，因此输入若在某些点不能被归约为活前缀，语法错误将会被正确地检测出来。
