递归下降解析和语法树

Question

所以我一直在研究和试验几个月的语言设计,我比几个月前的理解要好得多.我仍然对一些事情感到困惑...我已经在没有研究的情况下砍掉了一些糟糕的解析器,但我需要更好的东西.所以我正在尝试编写一个递归下降解析器,因为我已经读过它是手工编写的最合理的解析器.据我所知,每个规则都实现在它自己的功能中.所以我想我理解我将如何写这些但只有前半部分...解析器的工作是创建一个语法树或类似的东西,对吗？我也一直在尝试研究这个主题,但我还没有找到任何关于如何用语言表示树的例子.我正在写D因为它是我最喜欢的语言,但它'

我所看到的有很多类互相继承,所以可能有一个语句类,例如IfStatement类扩展.但是我无法找到所有这些在树中的表现方式,甚至以后如何走路.

如果有人能够向我展示一个例子或者更深入地谈论这些事情,那将是太棒了.任何帮助真的意味着很多,并有助于我的好奇心和目标,提前感谢!

Answer 1

树通常表示为包含指向其子node节点的指针的结构,或者它具有存储其节点类型的成员,或者它具有某个类,以便您可以派生其实际类型(即,如果它包含算术表达式, if语句,循环等).

if正如你所提到的,一个简单的例子确实就是陈述.为此,你会做这样的事情(伪C跟随):

enum AST_Node {
    Node_if,
    Node_and,
    Node_or,
    Node_not,
    Node_equal,
    Node_less,
    // etc., other node types follow
};

struct AST {
    struct AST *children[MAX_CHILDREN]; // don't do this
    enum AST_Node node;
};

struct AST *parse_if_statement()
{
    // expect tokens in order
    expect("if");

    // parse condition
    expect("(");
    struct AST *condition = parse_expression();
    expect(")");

    // parse two child statements
    struct AST *then_branch = parse_statement();
    struct AST *else_branch = NULL;
    if (accept("else")) {
        else_branch = parse_statement();
    }

    // create AST, fill in children
    struct AST *if_statement = new_AST_node(Node_if);
    if_statement->children[0] = condition;
    if_statement->children[1] = then_branch;
    if_statement->children[2] = else_branch;

    return if_statement;
}

所以基本上你只是期望/接受永久词法元素("if",条件周围的括号等),然后你将子树(条件和两个分支)的解析交给适当的解析器函数.

这就是你走树的方式:你基本上是按照深度优先步行,按顺序编译或解释每个孩子.然后添加当前正在解释/编译的子树的节点类型暗示的额外语义.

Value *interpret_if_statement(struct AST *ast)
{
    assert(ast->node == Node_if);

    struct AST *condition = ast->children[0];
    struct AST *then_branch = ast->children[1];
    struct AST *else_branch = ast->children[2];

    // evaluate condition
    Value *condval = interpret_expression(condition);

    if (condval->bool_value == TRUE) {
        // if condition is true, interpret "then" branch
        return interpret_statement(then_branch);
    } else if (else_branch != NULL) {
        // otherwise interpret "else" branch, if any
        return interpret_statement(else_branch);
    } else {
        return NULL;
    }
}