c# - 递归下降解析

Question

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

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

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 后记。感谢您的帮助!

Answer 1

这是一个解析函数参数的示例。这是在 C 中，但想法转移了，即您在解析 token 流时构建 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 的实际内部结构，即正在构建的树的形状或它的实现方式对解析器是不可见的。