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

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）也几乎不能解决您打算解决的实际问题。它只是基础，对于大多数解析器新手来说，震惊的是，它是操纵代码的工具的 最小
组成部分。谷歌我的文章后解析生活（或检查我的简历）的更多细节。