假设我们有两种定义相同语言的文法：常规文法和 LALR(1) 文法。
常规和 LALR(1) 算法都是 O(n)，其中 n 是输入长度。
正则表达式通常是解析常规语言的首选。为什么？是否有正式的证据（或者可能很明显）证明它们更快？
问问题
482 次
3 回答
2
解析和识别之间有很大的区别。尽管您可以构建正则语言解析器，但它会受到极大的限制，因为大多数有用的语言都无法使用有用的明确正则语法进行解析。但是，大多数（如果不是全部）正则表达式库都可以识别，可能会添加有限数量的“捕获”。
无论如何，解析真的不再是性能瓶颈了。恕我直言，最好使用能够明显解析它们似乎解析的语言的工具。
另一方面，如果你想要做的只是识别一种语言——而且该语言恰好是正则——正则表达式更容易并且需要更少的基础设施（解析器生成器、专用 DSL、稍微复杂的 Makefile ， ETC。）
（作为不规则语言特征的一个例子，我给你：括号。）
于 2013-01-26T00:07:41.987 回答
2
您应该更喜欢无堆栈自动机而不是下推自动机，因为常规语言自动机的数学要发达得多。
我们能够对这两种类型的自动机进行确定，但我们无法对 PDA 进行有效的最小化。众所周知的事实是，对于每个 PDA，都存在一个具有唯一状态的等价物。这意味着我们应该在转换计数/最大堆栈深度/其他一些标准方面最小化它。
此外，检查两个不同的 PDA 在它们识别的语言方面是否等效的问题也是无法确定的。
于 2017-04-15T14:55:38.897 回答
0
人们更喜欢正则表达式，因为它们更容易编写。如果您的语言是常规语言，为什么还要为它创建 CFG 语法？
于 2013-01-25T23:50:10.763 回答