递归下降分析和语法树

Question

递归下降分析和语法树

c++parsingrecursiondabstract-syntax-tree

5

所以我已经研究和实验了几个月的语言设计，现在比几个月前更好地理解了。但是我仍然有一些困惑......我已经放弃了一些没有研究的糟糕解析器，但我需要更好的东西。因此，我尝试编写递归下降解析器，因为我读到它是最合乎逻辑的手写解析器方法。据我理解，每个规则都被实现为自己的函数。所以我认为我知道如何编写其中之一，但只是前半部分......解析器的工作是创建语法树或类似的东西，对吗？我也一直在尝试研究这个主题，但是我没有找到任何关于如何在语言中表示树的例子。我用D语言编写，因为它是我最喜欢的语言，但它非常类似于C / C ++，因此我将理解用这些语言或伪代码编写的任何示例。

从我所看到的，有很多从彼此继承的类，因此可能会有一个语句类，例如IfStatement类扩展。但是我没有找到所有这些在树中是如何表示甚至在稍后如何遍历的方法。

如果有人能向我展示一个示例或更深入地讨论这些事情，那将是太棒了。任何帮助都意味着很多，并有助于满足我的好奇心和目标，提前致谢！

- APott

你看过维基百科上关于PL/0的精彩示例吗？https://en.wikipedia.org/wiki/Recursive_descent_parser - Michael Rawson

哦，我还没有！这有助于我的递归下降解析器的一半问题。感谢链接，Michael！ - APott

2

@ceving，你是在说“没有必要学习如何编写解析器”吗？如果他只是想为了好玩而这样做呢？（此外，手写的解析器更容易修改和扩展。个人经验。） - user529758

是的，每当我问类似问题时，像@H2CO3这样的人推荐lex/yacc和ANTLR，但关键不在于学习如何使用程序生成它... - APott

@H2CO3 作业的标签在哪里？ - ceving

显示剩余2条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user529758 · Accepted Answer

一棵树通常表示为一种包含指向其子节点的指针和一个存储其节点类型的node成员的结构，或者是某个特定类的实例，因此您可以派生出其实际类型（即如果它包含算术表达式、if语句、循环等）。

一个简单的示例确实是if语句，正如您所提到的那样。对于这个，您会做类似于以下的操作（伪代码如下）：

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;
    }
}