抽象语法树有什么用?

问题描述 投票:0回答:5

我正在自学如何为编程语言编写解释器,并且我已经阅读了有关抽象语法树的内容。我知道它们是什么,但我不知道它们的用途。

为什么 AST 有用?

terminology abstract-syntax-tree
5个回答
6
投票

它们代表代码的逻辑/语法,这自然是一棵树而不是行列表,而不会陷入具体的语法问题,例如您放置星号的位置。

然后可以从后端的 POV 以更加一致和方便的方式操纵逻辑,这可以(并且对于除了 Lisp 之外的所有内容)与我们编写具体语法的方式非常不同。


5
投票

使用 AST 的主要好处是将解析和验证逻辑与实现部分分开。作为 AST 实现的解释器确实更容易理解和维护。如果你在解析一些奇怪的语法时遇到问题,你可以查看 AST 解析器,如果一段代码没有产生预期的结果,那么你可以查看解释 AST 的代码。

另一个巨大的优势是当你的语法需要“先行”时,例如如果您的语法允许在定义子例程之前使用它,那么在使用 AST 时验证子例程的存在是微不足道的 - 使用“动态”解析器要困难得多。


3
投票

你需要“语法树”来表示大多数编程语言的结构,以便对包含编程语言文本的文档进行分析或转换。 (你可以通过我的简历看到一些奇特的例子)。

该树是抽象的 (AST) 还是具体的 (CST) 取决于品味、便利性和工程汗水。 术语CST专门用于描述当语法用于解构源代码时的解析推导树;它通常包含许多具体语法的树元素,例如语句终止符分号。 AST 用于表示“比 CST 更简单的东西”,例如,省略分号树节点,因为它们不会对程序分析产生太大影响,因此编写处理 AST 的分析器比在国家标准时间。 理解这一点的更好方法是认识到 AST 通常与 CST 是同构等价的,也就是说,您应该能够从中重新生成 CST。 如果您想转换源文本并重新生成它,那么 CST 通常是更好的选择,因为它从原始程序中丢失的信息较少(我的奇特示例使用了这种方法)。

我想你会发现关于 抽象与具体语法树 的讨论非常有帮助。


0
投票

一般来说,你会将代码解析为某种形式的 AST,它可能或多或少是一个正式的模型。 因此,我认为柯克·沃尔(Kirk Woll)通过他上面的评论得到的意思是,当你解析语言时,你经常使用解析器来创建你正在阅读的原始内容的某种数据模型,通常以树的方式组织。 因此,根据这个定义,AST 是很难避免的,除非你正在做一个非常简单的翻译器。

我经常使用 ANTLR 来解析复杂的语言,在这种情况下,AST 有一个稍微更具体的含义。 ANTLR 有一种使用非常简单的操作在解析器语法中生成 AST 的便捷方法。 然后,您可以为该 AST 编写一个通常更简单的解析器,您可以像正在处理的语言的更简单版本一样对其进行操作。 构建两个解析器的额外工作是否是净收益取决于语言复杂性以及解析后您计划用它做什么。

您可能想看一下关于该主题的一本好书,即 ANTLR 作者 Terrence Parr 所著的《语言实现模式》。 他非常彻底地讨论了这个话题。 也就是说,在开始使用 AST 之前我并没有真正了解它们,因此(像往常一样)这是理解它们的最佳方式。


0
投票

这个问题迟到了,但我想我应该补充一些东西。

© www.soinside.com 2019 - 2025. All rights reserved.