我想从 token 列表中构建一个 AST。我正在制作一种脚本语言，并且已经完成了词法分析部分，但我不知道如何创建 AST。所以问题是，我该如何处理这样的事情:

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

最佳答案

基本的技巧是认识到解析，无论如何完成，都是以增量步骤发生的，包括一个一个地读取标记。

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

如果构建一个递归下降解析器，那么实际上构建了一个递归过程的协作系统，每个递归过程都识别出正在实现的任何语法中的非终结符。对于纯解析，每个过程只返回一个 boolean 值来表示“非终端(未)识别”。

要使用递归下降解析器构建 AST，可以设计这些过程以返回两个值:“已识别” boolean 值，以及(如果被识别)为非终结符(以某种方式)构造的 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
}

关于java - 使用标记列表构建抽象语法树，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25049751/