Regular vs LALR(1)：哪个更快

Question

假设我们有两种定义相同语言的文法:正则文法和LALR(1)文法。

正则和LALR(1)算法都是O(n)，其中n是输入长度。

正则表达式通常是解析常规语言的首选。为什么？是否有正式的证据(或者这一点很明显)表明它们更快？

Answer 1

你应该更喜欢无栈自动机而不是下推自动机，因为对于常规语言自动机来说，有更先进的数学方法。

我们能够对这两种类型的自动机执行判定，但我们无法执行PDA的有效最小化。众所周知的事实是，对于每个PDA，都存在具有唯一状态的等价PDA。这意味着我们应该根据转换次数/最大堆栈深度/一些其他标准最小化它。

此外，检查两个不同的PDA在它们所识别的语言方面是否等价的问题也是无法确定的。

Answer 2

解析和识别之间有很大的不同。尽管您可以构建一个常规语言解析器，但它将是非常有限的，因为大多数有用的语言都不能使用有用的明确的常规语法进行解析。但是，大多数(如果不是全部)正则表达式库都可以识别，可能会添加有限数量的“捕获”。

无论如何，解析已经不再是性能瓶颈了。我的意思是，最好使用工具，这些工具可以明显地解析他们所解析的语言。

另一方面，如果您想要做的只是识别一种语言--并且该语言恰好是正则语言--那么正则表达式要容易得多，并且需要的基础设施要少得多(解析器生成器、专用DSL、稍微复杂一点的Makefile等)。

(作为非常规语言功能的一个例子，我给你:括号。)

Answer 3

人们更喜欢正则表达式，因为它们更容易编写。如果您的语言是常规语言，为什么还要费心为它创建CFG语法呢？