小编use*_*136的帖子

我目前正在手工构建解析器.它是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的部分.我不要求完整的实现,更多的是实现的想法.

谢谢 !