parsing - 使用堆栈 : how to build AST? 实现的 LL(1) 解析器

Question

我目前正在手工构建一个解析器。它是一个 LL(1) 解析器。目前，它是一个很棒的识别器:它的函数 parse(List tokens) 决定 token 是否是该语言的成员。

现在，我想为该输入构建相应的 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 -> B C)附加一些元信息，例如要保留什么以及结果的性质是什么。