Recursive descent and tree syntax

Question

So, I have been studying and experimenting for months with language design, and I have a much better understanding than I did a couple of months ago. I am still confused by a few things, though ... I hacked into some bad parsers without research, but I need something better. Therefore, I am trying to write a recursive descent parser, since I read it the most logical for manual recording. As far as I understand, each rule is embedded in its own function. Therefore, I think I understand how I will write about it, but only in the first half ... The parser’s job is to create a syntax tree or something similar, right? I also tried to research this topic, but I could not find examples of how the tree is represented in this language. I write in D because it is my favorite language, but it is very similar to C / C ++, so I will understand any examples,written in these languages ​​or pseudocode.

From what I saw there, there is a ton of classes that inherit from each other, so there may be a class of operators to which, for example, the IfStatement class extends. But I could not find how all this is represented in a tree or even how it went later.

It would be fantastic if someone could set an example for me or talk about these things in a little more detail. Any help really means a lot and helps with my curiosity and goals, thanks in advance!

Answer 1

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

, / ( "", ..), ( ) .

: - , . , node , /.

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