c++ - 使用下推自动化创建语法树？

Question

如果我要创建一个接受状态(名称)的下推自动化，并且这些状态接受转换(输入、弹出、推送、下一个状态)。所有这些如何帮助我构建解析树？

我的意思是下推自动机非常适合检查语言中是否包含某些内容，例如标记序列或任何顺序是否正确...但是语法树？

我的意思是考虑以下示例:

Foo {
 Woo {
  Hello World
 }
}

pda 只能记住堆栈中的顶部项目和当前输入。我应该如何构建树？我应该将 PDA 与递归相结合吗？

Answer 1

从广义上讲，堆栈中的每个项目都包含一个语法子树列表。当你推送一个新项目时，它的列表开始时是空的。当您转移(消费)一个 token 时，您将其添加到此列表中。出栈时，取出栈顶项列表中的所有子树，将它们设置为新节点的子节点，并将这个新子树添加到项栈的新顶部列表中。最终，当您将最后一项从堆栈中弹出时，您将得到一个子树，这将是整个语法树。