递归体面解析

本文关键字：体面 递归 | 更新日期: 2023-09-27 18:35:34

我基于语法构建了一个递归体面的解析器。目前，我的解析器只告诉语法是否接受令牌的输入序列。如果语法接受输入和抽象语法树，我想返回。我不知道该怎么做。

到目前为止，我所拥有的是一个对应于语法中每个生产规则的函数。我改变了语法，使终端始终是每个生产规则的第一个元素。下面是我尝试为其构建语法树的语法子集。

program -> VAR = exp
exp -> NUM term
exp -> LEFTPAR exp RIGHTPAR
term -> MUL NUM term
term -> DIV NUM term
term -> . (empty)

规则函数的示例如下：

public Pair<bool, Token> exp(Token tok)
{
    if (tok.type == NUM)
    {
         return term(tok.next);
    }
    if (tok.type = LEFTPAR)
    {
         Pair<bool, Token> temp = exp(tok.next);
         if (temp.left && temp.right.type == RIGHTPAR)
             return new Pair<bool, Token>(true,temp.right.next);
         return new Pair<bool, Token>(false,null);
    }
}

将这样的函数转换为语法树生成器的策略是什么？我尝试将树节点作为所有函数的输入传递，但是当存在具有多个非终端的规则时，它会变得更加混乱。似乎构建一个解析树，然后将其转换为 AST 后记会更容易。任何帮助不胜感激！

递归体面解析

下面是将参数解析为函数的示例。这是在 C 中，但这个想法转移了，即您在解析令牌流时构建 AST。

此函数解析字符串，如下所示foo : double 

static void parse_arg(parser_obj *obj, AstFunc *func) {
  Token   * tok;
  TokenId   tid = peek(obj);
  if(tid == T_PAREN_R) {
    return;
  }
  EXPECT(T_ID);
  tok = t(obj);
  char *arg_name = tok_value(tok);
  EXPECT_EAT(T_COLON);
  tok = t(obj);
  ctype arg_type = tokid_to_type(tok_id(tok));
  func->ops->new_arg(func, arg_name, arg_type);
}

func对象实际上是 AST 中的一个节点，在这种情况下，当我们添加新参数时，对于多个参数，它将被添加到列表或树中，或者完成解析后要使用的任何数据结构中。

在下一行中，我们将向对象func添加一个 arg。

func->ops->new_arg(func, arg_name, arg_type);

func的实际内部结构，即正在构建的树的形状或其实现方式对解析器不可见。

相关文章：