构造带有令牌列表的抽象语法树

2018-06-24 08:19:45

我想从一个令牌列表构建一个AST。我正在编写脚本语言，而且我已经完成了词法分析部分，但我不知道如何创建AST。所以问题是，我如何采取这样的事情：

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

并将其转换为抽象语法树？最好是，我希望没有像ANTLR这样的图书馆，我宁愿自己尝试从头开始。但是，如果这是一个非常复杂的任务，我不介意使用库:)谢谢

基本技巧是认识到解析（无论如何实现）都是以增量步骤发生的，包括逐个读取令牌。

在每个增量步骤中，都有机会通过组合通过其他增量步骤构建的AST片段来构建AST的一部分。这是一个递归的想法，并且它在扫描时构建AST叶节点以获取令牌。这个基本思想发生在几乎所有的AST构建解析器中。

如果构建递归下降解析器，实际上会构建一个递归过程的协作系统，每个过程都可以识别正在实现的任何语法中的非终结符。对于纯解析，每个过程只是返回一个“非终结符（未识别）”的布尔值。

为了使用递归下降解析器构建一个AST，我们设计这些过程以返回两个值：布尔型“已识别”，并且，如果已识别，则为非终结构建（以某种方式）构建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构建goo将会越来越困难。（如果你的语言成功，一年内你会想改变它）。所以即使写AST的建筑规则也会变得尴尬。

理想情况下，人们只是想写一个语法，并得到一个解析器和树。您可以使用一些最新的解析器生成器来完成此任务：我们的DMS Software Reengineering Toolkit接受完整的上下文无关语法，并自动构造AST，而不需要语法工程师的工作; 自1995年以来一直这样做。ANTLR家伙最终在2014年发现了这一点，而ANTLR4现在提供了这样的选择。

最后一点：有一个解析器（即使是AST）也不能解决你解决的实际问题，无论它是什么。它只是一个基础部分，对于大多数解析器新手来说非常震惊，它是操纵代码的工具的最小部分。谷歌我的解析后的生活（或检查我的生物）的更多细节的文章。

这并不难; 事实上，这是我做过的最简单的事情之一。总的想法是，每个结构（aka解析器规则）只是其他结构的列表，并且当调用parse（）函数时，它们只是遍历其子元素，并告诉它们解析。这不是一个无限循环; 令牌是结构体，当它们的parse（）被调用时，它们会扫描词法分析器输出。他们也应该有一个识别名称，但这不是必需的。 parse（）通常会返回一个分析树。解析树就像结构 - 儿童列表。有一个“文本”字段及其父结构用于识别也是很好的。这里有一个例子（你想更好地组织它，并处理实际项目的null）：

public void push(ParseTree tree) { // ParseTree
    children.add(tree);
    text += tree.text;
}

public ParseTree parse() { // Structure
    ParseTree tree = new ParseTree(this);
    for(Structure st: children) {
        tree.push(st.parse());
    }
    return tree;
}

public ParseTree parse() { // Token
    if(!lexer.nextToken() || !matches(lexer.token))
        return null;
    ParseTree tree = new ParseTree(this);
    tree.text = lexer.token;
    return tree;
}

那里。调用主结构的parse（），并得到一个AST。当然，这是一个非常准确的例子，并且不会开箱即用。 “修饰符”也是有用的。例如匹配儿童3一次或多次，儿童2是可选的。这也很容易做到; 将它们存储在一个与您的孩子数量相同的数组中，并在解析时检查它：

public void setModifier(int id, int mod) {
    mods[id] = mod;
}

public ParseTree parse() {
    ...
    ParseTree t;
    switch(mods[i]) {
        case 1: // Optional
            if((t = st.parse()) != null) tree.push(t);
        case 2: // Zero or more times
            while((t = st.parse()) != null) tree.push(t);
        ...
        default:
            tree.push(st.parse());
    }
    ...
}

链接地址: http://www.djcxy.com/p/68209.html

上一篇: Constructing an Abstract Syntax Tree with a list of Tokens

下一篇: Trying to understand lexers, parse trees and syntax trees