c# - 递归下降解析

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

到目前为止，我所拥有的是与语法中每个生成规则相对应的函数。我对语法进行了转换，以使终端始终是每个生产规则的第一要素。以下是我要为其构建语法树的语法的子集。

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中的一个Node，在这种情况下，当我们添加新参数时，该参数可用于多个参数，一旦完成，它将被添加到列表，树或要使用的任何数据结构中解析。

在下面的行中，我们向对象func添加arg。

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

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