递归下降解析

Question

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

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

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 中，但想法转移了，即您在解析令牌流时构建 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 中的一个节点，在这种情况下，对于多个参数，当我们添加一个新参数时，它将被添加到列表或树或您想要的任何数据结构中完成解析后使用。

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

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

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

递归下降解析

Recursive Decent Parsing

c#

parsing

recursive-descent

abstract-syntax-tree