如何手动构建AST？

Question

我目前正在学习解析,但我对如何生成AST感到有点困惑.我编写了一个解析器,可以正确地验证表达式是否符合语法(当表达式符合时它是静默的,而当表达式不符合时引发异常).我从哪里开始构建AST？我发现了很多关于构建我的LL(1)解析器的信息,但是很少有人继续构建AST.

我的当前代码(用非常简单的Ruby编写,包括词法分析器和解析器)可以在github上找到:https://gist.github.com/e9d4081b7d3409e30a57

有人能解释我如何从目前的AST到AST吗？

或者,如果您不熟悉Ruby,但知道C,您能告诉我如何在递归下降解析维基百科文章中为C代码构建AST .

请注意,我不想使用像yacc或antlr这样的解析器生成器为我做的工作,我想从头开始做所有事情.

谢谢!

Answer 1

您需要将与匹配的每个符号与构造树的一小部分的回调相关联.例如,让我们采用一个相当常见的结构:嵌套函数调用.

a(b())

你的终端令牌在这里是这样的:

而你的非终结符号是这样的:

显然,规则的上述第二种选择FUNCTION_CALL是递归的.

您已经有一个解析器知道它找到了一个有效的符号.您缺少的一点是将回调附加到规则,该规则接收其组件作为输入并返回表示AST中该节点的值(通常).

想象一下,如果我们FUNCTION_CALL上面的规则中的第一个替代方案有回调:

Proc.new do |id_tok, l_paren_tok, r_paren_tok|
  { item: :function_call, name: id_tok, args: [] }
end

这意味着匹配产生的AST:

a()

将会:

{
  item: :function_call,
  name: "a",
  args: []
}

现在将其推断为更复杂的a(b()).因为解析器是递归的,所以它将识别第b()一个,回调从中返回我们上面的内容,但是使用"b"而不是"a".

现在让我们定义附加到与第二个备选项匹配的规则的回调.它非常相似,除了它还处理它传递的参数:

Proc.new do |id_tok, l_paren_tok, func_call_item, r_paren_tok|
  { item: :function_call, name: id_tok, args: [ func_call_item ] }
end

因为解析器已经识别b()并且从回调中返回了AST的一部分,所以生成的树现在是:

{
  item: :function_call,
  name: "a",
  args: [
    {
      item: :function_call,
      name: "b",
      args: []
    }
  ]
}

希望这会给你一些思考的食物.将您匹配的所有令牌传递给构建AST非常小的部分的例程.