众所周知，给定一个正则语法，我们有算法来获取它的正则表达式。
但是如果给定的语法是上下文无关语法(但它只生成常规语言)，例如
S->aAb <br/>
A->bB <br/>
B->cB|d <br/>
有没有现成的算法可以得到通用的正则表达式？
谢谢!
最佳答案
从最一般的意义上来说，没有解决方案。确定 CFG 是否正则的问题是不可判定的(Greibach 定理，http://www.cis.upenn.edu/~jean/gbooks/PCPh04.pdf 的最后 3 页)如果我们可以将 CFG 转换为正则表达式，我们可以在任何语法上使用该算法，并使用其成功/失败来确定是否语言是有规律的。
因此，当已知 CFG 生成正则语言时，要么其语言已知(因此可以直接转换为正则表达式)，要么存在可以利用的语法的某些属性。每个属性都有自己的转换为正则表达式的算法。
例如，如果语法为 right linear ，每个产生式都是 A->bC 或 A->a 的形式。这可以转换为 NFA，其中:
1) 每个非终结符都有一个状态，外加一个接受状态。
2)起始符号S为起始状态。
3) A->bC 是输入 b 上从 A 到 B 的转换
4) A->a 是从 A 到输入 a 的接受状态的转换。
然后可以通过状态消除将该 NFA 转换为正则表达式(http://www.math.uaa.alaska.edu/~afkjm/cs351/handouts/regular-expressions.pdf 的第 5-8 页)。 左线性语法的类似过程将交换开始和接受状态。
除此之外，我们还可以利用常规语言的闭包属性。例如，问题中的语言不是线性的，但可以写成S->S'b，S'->aA。现在 S' 是右线性的，S 是两个不相交线性文法的串联。连接两个表达式作为最终表达式。 union 的逻辑类似。
关于regex - 如果我们知道一个CFG只生成正则语言，那么我们能得到对应的正则表达式吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10611171/