我正在自学编写编程语言解释器，了解到抽象语法树(Abstract Syntax Trees)。我对它们有一定的了解，但不知道它们的用途。
为什么抽象语法树很有用？
抽象语法树有什么用途？
13
- RacecaR
1
没有抽象语法树，你打算如何建模语言的语法？例如，在编写解析器/编译器/解释器等时。 - Kirk Woll
5个回答
6
他们代表代码的逻辑/语法，自然是一棵树而不是一行行的列表，并且不会陷入具体语法问题，比如你应该在哪里放置你的星号。
然后可以以更一致和方便的方式从后端的角度操作逻辑，这可以（对于除了Lisp之外的所有东西;)）与我们编写的具体语法非常不同。
然后可以以更一致和方便的方式从后端的角度操作逻辑，这可以（对于除了Lisp之外的所有东西;)）与我们编写的具体语法非常不同。
- Roger Pate
10
那么，我为什么要使用AST呢？而不是只创建一个“IDENTIFIER blah ASTERISK NUMBER 4”的数据流，然后让一个有限状态机或其他东西每次处理一个标记？ - RacecaR
2@Rac：你所描述的是原始文件和生成AST之间的一个步骤。也就是说：原始文件 -> 令牌 -> AST。对于后端来说，BinaryOp(Multiply, Identifier("blah"), Integer(4)) 更加方便。 - Roger Pate
@RacecaR，你的有限状态机用于解析将会读取流并生成AST；你的代码生成和优化例程将使用AST。 - Steven A. Lowe
有没有一个特定的名称？另外，我可以想到这样一种情况，解释器沿着代码走，遇到一个if语句，字节码或者其他提供了一个条件，如果条件为真，解释器应该向前移动8个标记，如果条件不满足，则不移动（或类似的操作）。对于这样的情况，抽象语法树（AST）如何工作？也许给出接下来应该遍历的路径（下一个节点）的指示？ - RacecaR
词法分析。AST 将有一个节点，用于表示包含两个子节点的条件：true 和 false。AST 与字节码/汇编语言非常不同（它们是相同的东西，只是针对不同的机器），在其中你需要“向前跳转 X 条指令”（而不是标记）。 - Roger Pate
显示剩余5条评论
5
使用AST的主要优点是将解析和验证逻辑与实现部分分离。作为AST实现的解释器更易于理解和维护。如果您在解析某些奇怪的语法时遇到问题，可以查看AST解析器；如果代码块未产生预期结果，则应查看解释AST的代码。
另一个巨大的优势是当您的语法需要“向前看”时，例如，如果您的语法允许在定义子程序之前使用它，则在使用AST时验证子程序的存在非常简单-这对于“即时”解析器来说更加困难。
另一个巨大的优势是当您的语法需要“向前看”时，例如，如果您的语法允许在定义子程序之前使用它，则在使用AST时验证子程序的存在非常简单-这对于“即时”解析器来说更加困难。
- James Anderson
1
1谢谢。我刚刚在学习使用Java构建解析器，书中提到对于简单的语言来说，构建AST比它所值得的麻烦。你是这个页面上唯一一个承认可以在不构建AST的情况下做出有用工作的人。 - kybernetikos
3
您需要“语法树”来表示大多数编程语言的结构，以便对包含编程语言文本的文档进行分析或转换。(您可以通过我的个人简介看到一些花哨的例子)。
无论该树是抽象的(AST)还是具体的(CST)，这都是品味、方便和工程汗水的问题。CST这个术语特别用于描述当语法用于解构源代码时的解析导出树；它通常包含许多具体语法的树元素，例如语句终止符分号。AST用于指代“比CST简单的东西”，例如省略分号树节点，因为它们不会对程序分析产生太大影响，因此编写处理AST的分析器比在CST上编写相同的分析器所需的概念和工程工作更少。更好的理解方法是意识到AST通常是CST的同构等价物，也就是说，您应该能够从AST中重新生成CST。如果您想要“转换”源文本并重新生成它，则CST通常是更好的选择，因为它从原始程序中丢失的信息较少(而我的花哨示例使用了这种方法)。
我认为您会发现关于抽象语法树与具体语法树的SO讨论（点击此处）非常有帮助。
无论该树是抽象的(AST)还是具体的(CST)，这都是品味、方便和工程汗水的问题。CST这个术语特别用于描述当语法用于解构源代码时的解析导出树；它通常包含许多具体语法的树元素，例如语句终止符分号。AST用于指代“比CST简单的东西”，例如省略分号树节点，因为它们不会对程序分析产生太大影响，因此编写处理AST的分析器比在CST上编写相同的分析器所需的概念和工程工作更少。更好的理解方法是意识到AST通常是CST的同构等价物，也就是说，您应该能够从AST中重新生成CST。如果您想要“转换”源文本并重新生成它，则CST通常是更好的选择，因为它从原始程序中丢失的信息较少(而我的花哨示例使用了这种方法)。
我认为您会发现关于抽象语法树与具体语法树的SO讨论（点击此处）非常有帮助。
- Ira Baxter
1
这是该主题的最佳答案。这需要更多的赞成票。 - gordon_freeman
0
有点晚回答这个问题，但我想补充一些内容。实际上，你不必构建一个AST（抽象语法树）。在解析源代码时直接发出指令是可能的。在这种情况下，AST被隐含在解析语法中。对于简单的语言，特别是动态类型语言，这是一个完全可以接受的策略。对于更复杂的语言或需要进一步分析源代码的情况，AST非常有用。例如，如果你的语言是静态类型的，即你的变量声明了固定类型，那么AST可以用来检查你是否将错误的类型赋给了变量。例如，将字符串赋给一个声明为保存整数的变量是错误的，这可以通过AST更方便地捕获。
此外，正如其他人所提到的，AST提供了语法分析和代码生成之间的清晰分离，并使代码更加模块化。
此外，正如其他人所提到的，AST提供了语法分析和代码生成之间的清晰分离，并使代码更加模块化。
- rhody
0
总的来说，你需要将代码解析为某种形式的AST，这可能是一个更或者更少正式的模型。所以我认为Kirk Woll在他上面的评论中所指的是，当你解析语言时，很常见地使用解析器来创建一些数据模型，这个模型可以对读取到的原始内容进行组织，通常是以树形式展现。因此，除非你在做一个非常简单的翻译器，否则很难避免使用AST。
我经常使用ANTLR解析复杂的语言，在这种情况下，AST具有稍微更具体的含义。ANTLR有一种便捷的方式，在解析器语法中使用相当简单的操作来生成AST。然后，你可以为这个AST编写一个通常要简单得多的解析器，而且你可以像处理一个更简单版本的该语言一样操作它。构建两个解析器是否会增加额外的工作量，取决于语言的复杂性和你打算解析后如何处理它。
关于这个主题，有一本很好的书是由ANTLR作者Terrence Parr所著的《Language Implementation Patterns》。他对这个主题进行了非常彻底的讲解。话虽如此，直到我开始使用AST之前，我并不真正理解它们，所以（像往常一样）最好的方法是使用它们来理解。
我经常使用ANTLR解析复杂的语言，在这种情况下，AST具有稍微更具体的含义。ANTLR有一种便捷的方式，在解析器语法中使用相当简单的操作来生成AST。然后，你可以为这个AST编写一个通常要简单得多的解析器，而且你可以像处理一个更简单版本的该语言一样操作它。构建两个解析器是否会增加额外的工作量，取决于语言的复杂性和你打算解析后如何处理它。
关于这个主题，有一本很好的书是由ANTLR作者Terrence Parr所著的《Language Implementation Patterns》。他对这个主题进行了非常彻底的讲解。话虽如此，直到我开始使用AST之前，我并不真正理解它们，所以（像往常一样）最好的方法是使用它们来理解。
- JeffW
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接