parsing - 递归下降解析器的运行时/堆栈空间分析的良好来源是什么？

Question

我想更多地了解递归下降解析器的运行时间。我还对递归下降解析器使用的堆栈空间（以及运行时和堆栈空间之间的权衡）感兴趣。 有哪些好的信息来源？

我已经阅读了维基百科的文章并在网上搜索，但我没有找到任何详细的内容。

Answer 1

递归下降解析的运行时间非常快；通常使用机器 CALL/RET 指令来实现递归。不回溯或不向前看的手写版本通常应该非常快。但重要的不是解析令牌流的时间。重要的是处理字符以构造标记和/或语义检查/代码生成所花费的时间。你为什么担心这个？

堆栈空间基本上由解析程序所需的最深嵌套决定。如果您的解析器在表达式中接受 (...)，并且有人编写了一个包含 50,000 个嵌套括号的表达式，则递归下降解析将递归 50,000 次。您可以通过制定关于解析器的递归深度的任意规则来防止这种行为（几乎每个人都这样做）。我发现 100 个关卡可以让你处理极其复杂的程序。