上下文无关文法的所有可行前缀
All viable prefixes of a Context Free Grammer
我被著名的编译龙书Design.How中的一个问题所困扰，以找到以下语法的所有可行前缀：
S -> 0S1 | 01
语法其实就是正则表达式0n1n的语言。
我假设所有可行前缀的集合可能作为正则表达式 too.I 提出以下解决方案
0+
0+S
0+S1
0+1
S
（加号，我的意思是没有零是 1..inf）
通过以下步骤减少字符串 000111 后：
stack input
000111
0 00111
00 0111
000 111
0001 11
00S 11
00S1 1
0S 1
0S1 $
S $
我的解决方案是正确的还是遗漏了什么？
0<sup>n</sup>1<sup>n</sup> 不是正则语言； regexen 没有像 n 这样的变量，它们不能强制两个不同子序列的重复次数相等。尽管如此，对于任何上下文无关文法，可行前缀集都是一种常规语言。 （以某种形式证明这一事实的证据出现在 Donald Knuth 1965 年的开创性论文 On the Translation of Languages from Left to Right 的第二部分的开头，它证明了一个测试LR(k) 属性 和线性时间解析 LR(k) 文法的算法。）
好的，进入正题。语法的可行前缀（根据定义）是句子形式的前缀，它可以在使用该语法进行解析期间出现在堆栈上。它之所以被称为“可行的”（意思是“还活着”或“可以继续生长”）正是因为它必须是某些正确的句子形式的前缀，其后缀不包含非终结符号。换句话说，存在一系列可以附加到可行前缀以产生正确句子形式的终结符；可行的前缀可以增长。
Knuth 展示了如何创建一个生成所有可行前缀的 DFA，但如果我们已经拥有由 LR(k) 算法生成的 LR(k) 解析器，则更容易看到此 DFA。该解析器是一个有限状态机，其字母表是文法的终结符和非终结符的集合。为了获得可行的前缀语法，我们使用完全相同的状态机，但我们删除了堆栈（这样它就变成了一个状态机）和 reduce 动作，只留下 shift 和 goto 动作作为转换。活前缀机中的所有状态都在接受状态，因为活前缀的任何前缀本身就是一个活前缀。
这个新自动机的一个关键特性是它不能使用 reduce 操作扩展前缀（因为我们删除了所有 reduce 操作）。带有 reduce 动作的前缀是一个以句柄结尾的前缀——回想一下句柄是某些产生式的右侧——所以可行前缀的另一个定义是它是一种右句形式（即，推导中的一个可能步骤）不超出最右边的句柄。
您正在使用的语法只有两个产生式，因此只有两个句柄，01 和 0S1。请注意 10 和 1S 不能是任何右句形式的子序列，右句形式也不能包含多个 S。任何右句形式必须是句子 0<sup>n</sup>1<sup>n</sup> 或句子形式 0<sup>n</sup>S1<sup>n</sup> 其中 n>0。但是每个句柄都在句子形式的第一个 1 处结束，因此可行的前缀必须在第一个 1 处或之前结束。这恰好产生了您列出的四种可能性，我们可以将其压缩为正则表达式 0*0(S1?)?.
去掉后缀从公式中删除了第二个n，因此不再需要一致性并且语言是规则的。
注：
像这样的问题和他们的答案请求使用 MathJax 呈现。不幸的是，Whosebug 不提供此扩展，这显然被认为对于 编程 是不必要的。但是，StackExchange 星座中有一个站点专门用于 计算科学 问题，http://cs.stackexchange.com, and another one dedicated to mathematical questions, http://math.stackexchange.com。形式语言理论是计算科学和数学的一部分。这两个站点都允许 MathJax，并且这些站点上的问题不会被关闭，因为它们不是编程问题。我建议您在解决此类问题时考虑这些信息。
我被著名的编译龙书Design.How中的一个问题所困扰，以找到以下语法的所有可行前缀：
S -> 0S1 | 01
语法其实就是正则表达式0n1n的语言。 我假设所有可行前缀的集合可能作为正则表达式 too.I 提出以下解决方案
0+
0+S
0+S1
0+1
S
（加号，我的意思是没有零是 1..inf）
通过以下步骤减少字符串 000111 后：
stack input
000111
0 00111
00 0111
000 111
0001 11
00S 11
00S1 1
0S 1
0S1 $
S $
我的解决方案是正确的还是遗漏了什么？
0<sup>n</sup>1<sup>n</sup> 不是正则语言； regexen 没有像 n 这样的变量，它们不能强制两个不同子序列的重复次数相等。尽管如此，对于任何上下文无关文法，可行前缀集都是一种常规语言。 （以某种形式证明这一事实的证据出现在 Donald Knuth 1965 年的开创性论文 On the Translation of Languages from Left to Right 的第二部分的开头，它证明了一个测试LR(k) 属性 和线性时间解析 LR(k) 文法的算法。）
好的，进入正题。语法的可行前缀（根据定义）是句子形式的前缀，它可以在使用该语法进行解析期间出现在堆栈上。它之所以被称为“可行的”（意思是“还活着”或“可以继续生长”）正是因为它必须是某些正确的句子形式的前缀，其后缀不包含非终结符号。换句话说，存在一系列可以附加到可行前缀以产生正确句子形式的终结符；可行的前缀可以增长。
Knuth 展示了如何创建一个生成所有可行前缀的 DFA，但如果我们已经拥有由 LR(k) 算法生成的 LR(k) 解析器，则更容易看到此 DFA。该解析器是一个有限状态机，其字母表是文法的终结符和非终结符的集合。为了获得可行的前缀语法，我们使用完全相同的状态机，但我们删除了堆栈（这样它就变成了一个状态机）和 reduce 动作，只留下 shift 和 goto 动作作为转换。活前缀机中的所有状态都在接受状态，因为活前缀的任何前缀本身就是一个活前缀。
这个新自动机的一个关键特性是它不能使用 reduce 操作扩展前缀（因为我们删除了所有 reduce 操作）。带有 reduce 动作的前缀是一个以句柄结尾的前缀——回想一下句柄是某些产生式的右侧——所以可行前缀的另一个定义是它是一种右句形式（即，推导中的一个可能步骤）不超出最右边的句柄。
您正在使用的语法只有两个产生式，因此只有两个句柄，01 和 0S1。请注意 10 和 1S 不能是任何右句形式的子序列，右句形式也不能包含多个 S。任何右句形式必须是句子 0<sup>n</sup>1<sup>n</sup> 或句子形式 0<sup>n</sup>S1<sup>n</sup> 其中 n>0。但是每个句柄都在句子形式的第一个 1 处结束，因此可行的前缀必须在第一个 1 处或之前结束。这恰好产生了您列出的四种可能性，我们可以将其压缩为正则表达式 0*0(S1?)?.
去掉后缀从公式中删除了第二个n，因此不再需要一致性并且语言是规则的。
注：
像这样的问题和他们的答案请求使用 MathJax 呈现。不幸的是，Whosebug 不提供此扩展，这显然被认为对于 编程 是不必要的。但是，StackExchange 星座中有一个站点专门用于 计算科学 问题，http://cs.stackexchange.com, and another one dedicated to mathematical questions, http://math.stackexchange.com。形式语言理论是计算科学和数学的一部分。这两个站点都允许 MathJax，并且这些站点上的问题不会被关闭，因为它们不是编程问题。我建议您在解决此类问题时考虑这些信息。