ruby - 如何手动构建 AST？

Question

我目前正在学习解析，但我对如何生成 AST 有点困惑。我编写了一个解析器，可以正确验证表达式是否符合语法(当表达式符合时它会保持沉默，否则会引发异常)。我从这里去哪里构建 AST？我找到了很多关于构建我的 LL(1) 解析器的信息，但是关于构建 AST 的信息却很少。

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

有人能解释一下我是如何从目前拥有的东西变成 AST 的吗？

或者，如果您不熟悉 Ruby，但知道 C，您能告诉我如何为 recursive descent parsing 中的 C 代码构建 AST维基百科文章。

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

谢谢!

Answer 1

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

a(b())

你的终端 token 是这样的:

• L_PAREN = '('
• R_PAREN = ')'
• 标识符 = [a-z]+

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

• FUNCTION_CALL = IDENTIFIER、L_PAREN、R_PAREN
• 或；
• FUNCTION_CALL = IDENTIFIER、L_PAREN、FUNCTION_CALL、R_PAREN

显然，上述规则 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 的非常小部分的例程中。