如何构造一个抽象的语法树

我对AST是什么有一个总体的了解，但我想知道如何构build一个。

如果给你一个语法和一个分析树，你怎么构buildAST？

如果给你一个语法和expression方式，你怎么做呢？

那么首先，语法用来从expression式构造一个分析树。所以，如果你已经有一个parsing树，你不需要语法。

取决于parsing器的工作量，parsingexpression式形成的结果树可能已经是抽象语法树。或者它可能是一个简单的parsing树，需要第二遍来构buildast。

要从语法和expression式构造分析树，首先必须将语法转换为有效代码。通常情况下，您将工作分成一个标记器，将表示expression式的inputstream拆分为一个标记列表，以及一个parsing器，该parsing器获取标记列表并从中构build一个parsing树\ ast。

所以expression式1 + 2*(3+4)可能会被拆分成如下forms的令牌列表：

 1 - int + - add_operator 2 - int * - mul_operator ( - lparen 3 - int + - add_operator 4 - int ) - rparen

第一列是实际的文本值。第二个表示令牌types。这些令牌被馈送到parsing器中，parsing器是从你的语法构build的，并识别令牌并构buildparsing树。

那么，如何编写词法标记器和实际的parsing器呢？你可以自己动手。或者更常见的是，使用像coco或antlr或lex / yacc这样的parsing器生成器。这些工具会对您的语法进行描述并生成令牌和parsing器的代码。（代码生成器存在于大多数stream行语言中，也有一些不受欢迎的语言。）

你如何构build你的parsing器很大程度上取决于你使用的是什么语言。你如何在Haskell中编写一个parsing器与你在C中的方式完全不同

我将从一般的angular度回答这个问题，而不是试图谈论词法分析器。

分析树包含非终结符号，它们是上下文无关语法的一部分，并且显示产生链以recursion方式或非recursion方式获得由terminal符号组成的string。所以当你有parsing树时，你不需要语法 – 你可以从parsing树中派生语法。

AST不包含任何非terminal符号。它只包含符号。

例：

E | E + T | | TM * M | | | M ab | b

这是显示a+a*b一个非常快速的版本。注意，抽象语法树的解释方式取决于树的优先顺序，你所做的遍历types（按顺序，预定顺序，后顺序）这将是你编码到你的search树中的一个通用函数。但是，一般来说，该分析树的AST可能如下所示：

+ | | a * | | ab