使用标记列表构造抽象语法树

Question

我想从一个令牌列表中构造一个AST.我正在编写脚本语言,我已经完成了词法分析部分,但我不知道如何创建AST.所以问题是,我该怎么做这样的事情:

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

并将其转换为抽象语法树？最好,我想在没有像ANTLR之类的库那样的情况下这样做,我宁愿自己尝试从头开始.但是,如果这是一项非常复杂的任务,我不介意使用库:)谢谢

Answer 1

根本的技巧是认识到解析,无论如何完成,都是以递增的步骤发生的,包括逐个读取令牌.

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

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

要使用递归下降解析器构建AST,可以设计这些过程以返回两个值:布尔"已识别",如果已识别,则为非终结符构造(以某种方式)AST.(常见的hack是返回指针,对于"未识别"是空的,或者如果"识别"则指向构造的AST).构建单个过程的结果AST的方法是组合它调用的子过程中的AST.这对于leaf程序来说非常简单,它可以读取输入标记并立即构建树.

所有这一切的缺点是必须手动编码递归下降,并使用树构建步骤来增强它.在宏观方案中,这对于小型语法来说实际上很容易编码.

对于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建设goo变得越来越难.(如果您的语言成功,一年之内您就会想要改变它).因此,即使编写AST构建规则也会变得尴尬.

理想情况下,人们只想写一个语法,并获得一个解析器和树.您可以使用一些最新的解析器生成器执行此操作:我们的DMS软件重新设计工具包接受完整的上下文无关语法,并自动构建AST,无需语法工程师的工作; 自1995年以来,它一直在这样做.ANTLR的家伙终于在2014年解决了这个问题,而ANTLR4现在提供了这样的选择.

最后一点:拥有一个解析器(即使使用AST)几乎不能解决你想要解决的实际问题,无论它是什么.它只是一个基础部分,对于大多数解析器 - 新手的震撼而言,它是操作代码的工具中最小的部分.谷歌我的解析后的生活文章(或检查我的生物)了解更多细节.