基本技巧是要认识到，无论解析如何完成，解析都是以增量步骤进行的，包括一一读取标记。
在每个增量步骤中，都有机会通过组合其他增量步骤构建的 AST 片段来构建部分 AST。这是一个递归的想法，它在扫描令牌时为令牌构建 AST 叶节点时触底反弹。这个基本思想几乎出现在所有 AST 构建解析器中。
如果构建一个递归下降解析器，那么实际上构建了一个递归过程的协作系统，其中每个递归过程都识别正在实现的任何语法中的非终结符。对于纯解析，每个过程仅返回一个“非终结符（未）识别”的布尔值。
为了使用递归下降解析器构建 AST，我们将这些过程设计为返回两个值：“已识别”布尔值，以及（如果已识别）为非终结符构造（以某种方式）的 AST。 （常见的 hack 是返回一个指针，如果“无法识别”则该指针无效，或者如果“已识别”则指向构造的 AST）。构建单个过程的 AST 的方式是组合来自它调用的子过程的 AST。对于叶子过程来说，这是非常简单的，叶子过程读取输入标记并可以立即构建一棵树。
所有这一切的缺点是必须手动编码递归下降，并通过树构建步骤对其进行增强。从总体上看，对于小型语法来说，这实际上很容易编写。
对于OP的例子，假设我们有这个语法：
GOAL = ASSIGNMENT
ASSIGNMENT = LHS '=' RHS ';'
LHS = IDENTIFIER
RHS = IDENTIFIER | NUMBER
好的，我们的递归下降解析器：
boolean parse_Goal()
{ if parse_Assignement()
then return true
else return false
}
boolean parse_Assignment()
{ if not Parse_LHS()
then return false
if not Parse_equalsign()
then throw SyntaxError // because there are no viable alternatives from here
if not Parse_RHS()
then throw SyntaxError
if not Parse_semicolon()
the throw SyntaxError
return true
}
boolean parse_LHS()
{ if parse_IDENTIFIER()
then return true
else return false
}
boolean parse_RHS()
{ if parse_IDENTIFIER()
then return true
if parse_NUMBER()
then return true
else return false
}
boolean parse_equalsign()
{ if TestInputAndAdvance("=") // this can check for token instead
then return true
else return false
}
boolean parse_semicolon()
{ if TestInputAndAdvance(";")
then return true
else return false
}
boolean parse_IDENTIFIER()
{ if TestInputForIdentifier()
then return true
else return false
}
boolean parse_NUMBER()
{ if TestInputForNumber()
then return true
else return false
}
现在，我们来修改它，构建一个抽象语法树：
AST* parse_Goal() // note: we choose to return a null pointer for "false"
{ node = parse_Assignment()
if node != NULL
then return node
else return NULL
}
AST* parse_Assignment()
{ LHSnode = Parse_LHS()
if LHSnode == NULL
then return NULL
EqualNode = Parse_equalsign()
if EqualNode == NULL
then throw SyntaxError // because there are no viable alternatives from here
RHSnode = Parse_RHS()
if RHSnode == NULL
then throw SyntaxError
SemicolonNode = Parse_semicolon()
if SemicolonNode == NULL
the throw SyntaxError
return makeASTNode(ASSIGNMENT,LHSNode,RHSNode)
}
AST* parse_LHS()
{ IdentifierNode = parse_IDENTIFIER()
if node != NULL
then return IdentifierNode
else return NULL
}
AST* parse_RHS()
{ RHSnode = parse_IDENTIFIER()
if RHSnode != null
then return RHSnode
RHSnode = parse_NUMBER()
if RHSnode != null
then return RHSnode
else return NULL
}
AST* parse_equalsign()
{ if TestInputAndAdvance("=") // this can check for token instead
then return makeASTNode("=")
else return NULL
}
AST* parse_semicolon()
{ if TestInputAndAdvance(";")
then return makeASTNode(";")
else return NULL
}
AST* parse_IDENTIFIER()
{ text = TestInputForIdentifier()
if text != NULL
then return makeASTNode("IDENTIFIER",text)
else return NULL
}
AST* parse_NUMBER()
{ text = TestInputForNumber()
if text != NULL
then return makeASTNode("NUMBER",text)
else return NULL
}
我显然掩盖了一些细节，但我认为读者填写它们不会有任何困难。
像 JavaCC 和 ANTLR 这样的解析器生成器工具基本上生成递归下降解析器，并且具有用于构造与此非常相似的树的工具。
构建自下而上解析器的解析器生成器工具（YACC、Bison、GLR...）也以相同的风格构建 AST 节点。然而，不存在递归函数集；相反，这些工具管理看到并简化为非终结符的一堆标记。 AST节点构建在并行堆栈上；当发生归约时，被归约覆盖的堆栈部分上的 AST 节点将被组合起来，生成一个非终结 AST 节点来替换它们。这种情况发生在语法规则的“零大小”堆栈段上，这些堆栈段也为空，导致 AST 节点（通常用于“空列表”或“缺少选项”）似乎不知从何而来。
使用小型语言，编写构建树的递归下降解析器非常实用。
真实语言（无论是像 COBOL 这样古老而陈旧的语言，还是像 Scala 这样炙手可热的语言）的一个问题是，语法规则的数量相当大，并且由于语言的复杂性以及对负责它的语言委员会的坚持而变得复杂。不断添加其他语言提供的新功能（“语言羡慕”，请参阅 Java、C# 和 C++ 之间的进化竞赛）。现在，编写递归下降解析器变得一发不可收拾，人们倾向于使用解析器生成器。但即使使用解析器生成器，编写所有自定义代码来构建 AST 节点也是一场大战（我们还没有讨论如何设计一个好的“抽象”语法与首先想到的事情）。随着规模的扩大和不断的发展，维护语法规则和 AST 构建变得越来越困难。 （如果你的语言很成功，一年之内你就会想改变它）。因此，即使编写 AST 构建规则也会变得很尴尬。
理想情况下，人们只想编写一种语法，并获得一个解析器和树。你可以使用一些最新的解析器生成器来做到这一点：我们的 DMS 软件重新工程工具包接受完整的上下文无关语法，并自动构建 AST，语法工程师不做任何工作；自 1995 年以来一直在这样做。ANTLR 人员终于在 2014 年解决了这个问题，ANTLR4 现在提供了这样的选项。
最后一点：拥有一个解析器（即使使用 AST）很难解决您要解决的实际问题，无论它是什么。它只是一个基础部分，令大多数解析器新手感到震惊的是，它是smallest操作代码的工具的一部分。谷歌我关于解析后的生活的文章（或查看我的简历）以获取更多详细信息。
