parsing - 为什么需要抽象语法树？为什么递归下降解析器无法解析？

在解释器设计方面，我是一个初学者，在学习了一点语言设计（语法、语言、词法分析器、解析器）之后，我不明白为什么解析器需要构建一个抽象的语法树。为什么不直接使用递归调用的函数来执行操作呢。

标签： parsingcompiler-constructioninterpreter

James：您可能对 Java 很熟悉。想象一下，您的 Java 递归解析器只有源代码文本，没有其他内容……它看到文本“x+y”。它究竟应该执行哪些操作？

您需要的不仅仅是 AST；您还需要符号表、从代码片段到范围的映射以及存储变量值的位置。如果您遵循@EJP 的思路，如果您想要聪明的答案/更快的解释器（例如每次遇到符号表时不要在符号表中查找标识符），则需要缓存一堆关于代码结构和标识符含义的事实.

一旦你同意你必须缓存一些信息以使你的“解释器”更有效率，唯一的争论是关于要缓存的东西的种类。AST 会缓存解析文本的结果，因此您不必每次都解析它。想象一下在每次迭代中解析内部循环的源代码；你会有一个异常缓慢的解释器。

所有这些其他的东西基本上也是对所提供文本的推理结果的缓存。但是在尝试使您的语言处理器足够高效以在实践中使用时，它们确实很有用。