ruby – 如何手动构建AST？

发布时间：2020-12-16 19:08:10 所属栏目：百科来源：网络整理

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

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

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

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

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

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

谢谢！

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

a(b())

你的终端代币在这里是这样的：

> L_PAREN ='(”
> R_PAREN =’)’
> IDENTIFIER = [a-z]

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

> FUNCTION_CALL = IDENTIFIER,L_PAREN,R_PAREN
>或;
> FUNCTION_CALL = IDENTIFIER,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,func_call_item,args: [ func_call_item ] }
end

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

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!