LL(1)解析器用堆栈实现:如何构建AST？

Question

我目前正在手工构建解析器.它是LL(1)解析器.目前,它是一个很好的识别器:它的函数解析(List tokens)决定令牌是否是该语言的成员.

现在,我想为该输入构建相应的AST.但是,我知道如何以递归下降的方式实现它(已经做到了).也就是说,对于挑战,我使用经典算法的堆栈实现我的堆栈:

next <- first token of the input
stack <- START_SYMBOL
do {
    top <- stack.pop()
    if (top is a terminal and top == next) {
        next <- next token of the input
    } else if (top is a non terminal and PARSING_TABLE[top, next] exists) {
        stack.push(PARSING_TABLE[top, next]);
    } else {
         return invalid input;
    }
} while (stack is not empty);
return valid input;

其中PARSING_TABLE是LL(1)表.但是,我想知道如何在这样的配置中实现构建AST的部分.我不要求完整的实现,更多的是实现的想法.

谢谢 !

Answer 1

您的堆栈可以进行注释，以便它包含 AST 条目引用（即规则编号 + 规则中的位置 + 目标数据的存储位置）+ （终端/非终端）

您的initial stack <- START_SYMBOL结果被注释为将其结果存储在 AST 根中。

基本上，您pop()选择当前的 AST 构造。然后next <- next token将值保存在 AST 中。打开stack.push(PARSING_TABLE[top, next]);一个新的AST列表并将其写入对应的构造中top，并在堆栈的每个条目中生成“规则编号+位置+目标列表”。

解析完成后，您就拥有了整棵树。

在精确的 AST 中，您可能想要忽略一些标记。这可以通过在 push() 部分期间堆栈集中的适当注释来完成。典型的方法是为每个规则（A -> BC）附加一些元信息，例如，要保留什么以及结果的性质是什么。