假设我们有两种定义相同语言的语法:常规语法和 LALR(1) 语法。
常规算法和 LALR(1) 算法都是 O(n)，其中 n 是输入长度。
正则表达式通常是解析常规语言的首选。为什么？是否有正式的证据(或者可能是显而易见的)表明它们更快？
最佳答案
您应该更喜欢无堆栈自动机而不是下推式自动机，因为常规语言自动机有更发达的数学。
我们能够对两种类型的自动机执行确定化，但我们无法对 PDA 执行有效的最小化。众所周知的事实是，对于每个 PDA，都存在具有唯一状态的等效 PDA。这意味着我们应该根据转换计数/最大堆栈深度/其他一些标准来最小化它。
检查两个不同的 PDA 就其识别的语言是否等效的问题也是无法确定的。
关于regex - 常规与 LALR(1) : what is faster，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14532118/