5

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

我所看到的有大量的类相互继承，因此可能有一个语句类，例如，IfStatement 类扩展了该类。但我一直无法找到所有这一切是如何在一棵树中表示的，甚至它后来是如何行走的。

如果有人能给我举个例子或者更深入地讨论这些事情，那就太好了。任何帮助真的很重要，有助于我的好奇心和目标，在此先感谢！

4

1 回答 1

9

树通常表示为包含指向其子节点的指针的结构，并且它具有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;
    }
}
于 2013-10-27T17:57:27.337 回答