使用堆栈实现的LL(1)解析器:如何构建AST? [英] LL(1) parser implemented with stack: how to build AST?

问题描述

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

I am currently building a parser by hand. It is a LL(1) parser. At the moment, it is a great recognizer: its function parse(List tokens) decides whether or not tokens is a member of the language or not.

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

Now, I want to build the corresponding AST for that input. However, I know how to implement it in a recursive descent way (already did it). That is, for the challenge, I implement my stack using a stack with the classical algorithm:

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的部分.我不要求完整的实施，而是要求实施的想法.

where the PARSING_TABLE is the LL(1) table. However, I wonder how to implement the part which build the AST in such a configuration. I do not ask for complete implementation, more for implementation idea.

谢谢！

推荐答案

可以注释您的堆栈，使其包含AST条目引用(即规则编号+规则在位置中的位置+目标数据的存储位置)+(终端/非终端)

Your stack can be annotated so that it contains the AST entry reference (i.e. rule number + position in rule + target data where to store) + (terminal/non terminal)

您的初始堆栈<-START_SYMBOL 已注释为将其结果存储在AST根目录中.

Your initial stack <- START_SYMBOL is annotated to store its result in the AST root.

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

Basically, your pop() selects the current AST construct. Then the next <- next token saves the value in your AST. The stack.push(PARSING_TABLE[top, next]); opens a new AST list and writes it in the construct corresponding to top, and generates in each entry of the stack the 'rule number + position + target list'.

解析完成后，便有了整棵树.

When you parsing is finished, you have the entire tree.

在精确的AST中，您可能希望忽略某些标记.这可以通过在push()部分的堆栈集中的适当注释来完成.典型的方法是在每个规则(A-> B C)上附加一些元信息，例如，要保留的内容以及结果的性质.

In a precise AST, you might want to ignore some tokens. This can be done via appropriate annotations in the stack set during the push() part. The typical way is to attach to each of your rules (A -> B C) some meta information, for example, what is to be kept and what is the nature of the result.

这篇关于使用堆栈实现的LL(1)解析器:如何构建AST?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！