用一个令牌列表构造一个抽象语法树

Question

我想从令牌列表构造一个AST。我正在制作一种脚本语言，我已经完成了词法分析部分，但我不知道如何创建AST。所以问题是，我如何使用这样的东西:

WORD, int
WORD, x
SYMBOL, =
NUMBER, 5
SYMBOL, ;

并将其转换为抽象语法树?最好，我想这样做没有像ANTLR之类的库，我宁愿尝试从头开始自己做。然而，如果这是一个非常复杂的任务，我不介意使用库:)谢谢

Answer 1

基本技巧是要认识到，无论解析如何完成，都是在增量步骤中进行的，包括逐个读取标记。

在每个增量步骤中，都有机会通过组合由其他增量步骤构建的AST片段来构建AST的一部分。这是一种递归思想，它在扫描令牌时为令牌构建AST叶节点。这个基本思想几乎出现在所有ast构建解析器中。

如果构建递归下降解析器，则实际上构建了一个递归过程的协作系统，其中每个递归过程都可以识别正在实现的语法中的非终结符。对于纯解析，每个过程只是返回一个布尔值，表示"非终结符(未识别)"。

要使用递归下降解析器构建AST，可以将这些过程设计为返回两个值:布尔值"recognized"，如果被识别，则为非终结符构造一个AST(以某种方式)。(一种常见的方法是返回一个指针，如果"未识别"则为空，如果"已识别"则指向构造的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)几乎不能解决您打算解决的实际问题，无论它是什么。它只是一个基础部分，对于大多数解析器新手来说，它是操作代码的工具中最小的部分。谷歌我的文章《解析后的生活》(或查看我的个人简介)了解更多细节。