regex - 正则表达式适用于常规语法，而____适用于上下文无关语法

Question

我刚刚了解到，Regular Grammars有它们对应Finite State Acceptors的将对应Regular Expressions。

是否有等效的转换Context Free Grammars？据我所知，上下文无关语法可以用Push Down Automatawhich 来表示，而后者又对应于什么？

感谢任何能让我摆脱这种想法的人。

Answer 1

来自维基百科上下文免费语法：

上下文无关文法的流行表示法是Backus-Naur 形式

…就像正则表达式是常规语法的符号一样。

Answer 2

Actually, the answer could still be "Regex".

Modern regex dialects, specifically those that support recursion (like PHP, Perl, .NET, JGSoft and others) can handle context-free languages perfectly.

Answer 3

现代编程语言本身在很大程度上由上下文无关语法描述。尽管理论上短语结构化语法是最强大的（英语就是一个例子），但已经发现，对于解决计算机上下文无关语法的问题，结合强大的记忆模型（变量）就足够了。接受这些上下文无关语言的程序是现代语言解析器。

一些示例语言 BNF

• 帕斯卡的 BNF
• Ruby 的 BNF
• 用于 Javascript 的 BNF
• 用于 Python 的 BNF
• 用于 Java 的 BNF
• C 的 BNF

鉴于 BNF 是上下文无关的，解析器可以自动生成，最原始的和最著名的例子当然是Yacc其他人已经创建，因为Bison被发明用于创建 gcc。现在有许多解析器生成器，它们的输出是用一种流行语言编写的解析器。

Answer 4

问题的措辞存在问题，因为它指的是语法而不是语言。

正则语言是一种可以通过联合、连接和闭包操作在集合上定义的语言。正则表达式和正则语法都是表示正则语言的便捷方式。

Context Free Language的问题在于它被定义为Context Free Grammar接受的语言，因此 OP 问题的答案在语言类别定义本身之内。