我正在为编译成 JS 的模板语言编写解析器（如果相关的话）。我从一些简单的正则表达式开始，这似乎可以工作，但是正则表达式非常脆弱，所以我决定改写一个解析器。我首先编写了一个简单的解析器，它通过推送/弹出堆栈来记住状态，但事情一直在升级，直到我手头有一个递归下降解析器。
不久之后，我比较了我之前所有的解析方法的性能。递归下降解析器是迄今为止最慢的。我被困住了：是否值得为简单的事情使用递归下降解析器，还是我有理由走捷径？我很想走纯正则表达式路线，它速度非常快（几乎比 RD 解析器快 3 倍），但在某种程度上非常笨拙且无法维护。我认为性能并不是非常重要，因为编译的模板被缓存了，但是递归下降解析器是每项任务的正确工具吗？我想我的问题更像是一个哲学问题：为了性能牺牲可维护性/灵活性到什么程度值得？
递归下降解析器可以非常快。
这些通常由词法分析器组织，该词法分析器使用正则表达式来识别提供给解析器的语言标记。处理源文本的大部分工作是由词法分析器使用 RE 通常编译成的快速 FSA 逐个字符完成的。
与词法分析器看到字符的速度相比，解析器只偶尔看到标记，因此它的速度通常无关紧要。然而，当比较解析器到解析器的速度时，忽略 lex 标记所需的时间，递归下降解析器可以非常快，因为它们使用函数调用来实现解析器堆栈，与一般解析器 push-current-state- 相比，这些函数调用已经非常有效-在模拟堆栈上。
所以，你也可以吃蛋糕。对词位使用正则表达式。使用解析器（任何类型的递归下降都可以）来处理词位。您应该对性能感到满意。
这种方法也满足了其他答案的观察结果：以使其可维护的方式编写它。我向你保证，Lexer/Parser 分离非常好。
首先是可读性，然后是性能......
因此，如果您的解析器使代码更具可读性，那么它就是正确的工具
为了性能而牺牲可维护性/灵活性到什么程度值得？
我认为将编写清晰的可维护代码作为首要任务非常重要。在您的代码不仅表明它是一个瓶颈，而且您的应用程序性能也因此受到影响之前，您应该始终认为清晰的代码是最好的代码。
不要重新发明轮子也很重要。关于查看另一个解析器的评论是一个非常好的评论。经常找到编写此类例程的通用解决方案。
当应用于适用的事物时，Recusion 非常优雅。在我自己的经验中，由于递归导致的慢代码是一个例外，而不是常态。
递归下降解析器应该更快
...或者你做错了什么。
首先，您的代码应分为 2 个不同的步骤。词法分析器+解析器。
一些在线参考示例会首先将整个语法标记化为一个大型中间数据结构，然后将其传递给解析器。虽然有利于演示；不要这样做，它会使时间和内存复杂性加倍。相反，一旦词法分析器确定匹配，就通知解析器状态转换或状态转换+数据。
至于词法分析器。这可能是您发现当前瓶颈的地方。如果词法分析器与解析器完全分离，您可以尝试在 Regex 和非 Regex 实现之间切换以比较性能。
无论如何，正则表达式并不比读取原始字符串快。默认情况下，它只是避免了一些常见错误。具体来说，不必要地创建字符串对象。理想情况下，你的词法分析器应该扫描你的代码并产生一个中间数据为零的输出，除了在你的解析器中跟踪状态所需的最低限度。记忆方面你应该有：
例如，如果您当前的词法分析器匹配一个非终端并一个接一个地复制每个字符，直到它到达下一个终端；您实际上是在为每个匹配的字母重新创建该字符串。请记住，字符串数据类型是不可变的，concat 将始终创建一个新字符串。您应该使用指针算法或等效方法扫描文本。
要解决此问题，您需要从非终端的 startPos 扫描到非终端的末尾，并仅在匹配完成时复制。
Regex 默认开箱即用地支持所有这些，这就是为什么它是编写词法分析器的首选工具。与其尝试编写一个解析整个语法的正则表达式，不如编写一个只关注匹配终端和非终端作为捕获组的正则表达式。跳过标记化，并将结果直接传递到您的解析器/状态机。
这里的关键是，不要尝试将 Regex 用作状态机。充其量它只适用于Regular（即Chomsky Type III，无堆栈）声明性语法——因此得名Regular Expression。例如，HTML 是一种无上下文（即 Chomsky Type II，基于堆栈）的声明性语法，这就是为什么仅靠 Rexeg 永远不足以解析它的原因。您的语法以及通常所有的模板语法都属于这一类。您显然已经达到了 Regex 的极限，因此您走在正确的轨道上。
仅使用 Regex 进行标记化。如果您真的关心性能，请重写您的词法分析器以消除任何和所有不必要的字符串复制和/或中间数据。看看你是否能超越 Regex 版本。
关键是。Regex 版本更易于理解和维护，而如果编写正确，您的手动词法分析器可能会更快一点。传统智慧说，帮自己一个忙，更喜欢前者。就 Big-O 复杂性而言，两者之间应该没有任何区别。它们是同一事物的两种形式。