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

我对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中的方式完全不同

  • 这里有一个教程,告诉你如何构build你自己的recursion下降parsing器 。

  • Coco是各种语言的parsing器生成器,它还附带有关于如何开始的文档。

  • 如果Python是你的东西,那么pyparsing可能适合你。

我将从一般的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