6.1 Recursive Descent and AST: Embedding Precedence into Call Structure

The lexer turns 1 + 2 * 3 into five tokens. Parsing recovers their structure: multiplication becomes the right subtree of addition, expressing that it binds more tightly. The tokens are in order; the operations do not simply get served first come, first served.

Learning Objectives

• Map grammars suitable for predictive analysis into recursive functions;
• Construct an abstract syntax tree (AST) during parsing;
• Correctly implement operator precedence and left- and right-associativity;
• Preserve span information and error nodes, rather than simply returning success or failure.

1. Start with a Layered Grammar

expression → additive
additive   → multiplicative (("+" | "-") multiplicative)*
multiplicative → unary (("*" | "/") unary)*
unary      → ("-" | "!") unary | primary
primary    → NUMBER | IDENT | "(" expression ")"

The parser call direction goes from lower to higher precedence: parse_additive calls parse_multiplicative first, so the multiplicative subtree is completed before being combined into the additive expression.

Additive operations are left-associative. a - b - c iteratively combines the existing left subtree with each new right operand to form (a-b)-c. Right-associative operations such as assignment or exponentiation can recurse on the right side or use an explicit stack. Reusing this loop, which immediately combines the left subtree, would give the wrong associativity.

2. AST Nodes Represent Semantic Structure

The C code below is an integration skeleton, not a standalone program. Its host supplies <stddef.h>, <stdbool.h>, <assert.h>, token kinds, an arena, a diagnostic container, and the make_* constructors. Here, Token contains kind, span, and integer_value; adapt the previous chapter’s start/end fields into Span and range-check integer conversion to long long. Constructors must return valid nodes or terminate parsing safely; an unchecked null result is not supported.

typedef struct { size_t start, end; } Span;

typedef enum {
    EXPR_NUMBER,
    EXPR_NAME,
    EXPR_UNARY,
    EXPR_BINARY,
    EXPR_ERROR
} ExprKind;

typedef struct Expr Expr;
struct Expr {
    ExprKind kind;
    Span span;
    union {
        long long number;
        struct { Span name; } name;
        struct { TokenKind op; Expr *operand; } unary;
        struct { Expr *left; TokenKind op; Expr *right; } binary;
    } as;
};

Implementing production logic also requires determining memory ownership of nodes. A common approach is to use an arena: the entire AST lives for the same lifetime and can be released in bulk, avoiding individual node malloc/free. If incremental updates are needed, immutable green trees or reference-counted structures may be employed.

3. Parser Cursor and Consumption Primitives

typedef struct {
    const Token *tokens;
    size_t count;
    size_t current;
    Arena *arena;
    DiagnosticList *diagnostics;
} Parser;

static const Token *peek(const Parser *p) {
    assert(p->count > 0 && p->current < p->count);
    return &p->tokens[p->current];
}

static bool match(Parser *p, TokenKind kind) {
    if (peek(p)->kind != kind) return false;
    if (kind != TOK_EOF) p->current++;
    return true;
}

static const Token *expect(Parser *p, TokenKind kind, const char *message) {
    if (peek(p)->kind == kind) {
        const Token *found = peek(p);
        if (kind != TOK_EOF) p->current++;
        return found;
    }
    report(p->diagnostics, peek(p)->span, message);
    return NULL;
}

The host validates a nonempty buffer with EOF only at the end, an initial current of zero, and token and arena lifetimes that cover parsing. The consumption helpers below leave the cursor at EOF. Assertions check internal invariants; they do not replace validation of external input. After expect raises an error, whether or not to consume the token cannot be decided arbitrarily: consuming incorrectly might skip valid syntax, while not consuming could cause the upper-level loop to stall. The recovery strategy will be addressed in detail in the next lesson.

4. primary Constructing Leaf and Parenthesized Structures

static Expr *parse_expression(Parser *p);
static Expr *parse_unary(Parser *p);

static Expr *parse_primary(Parser *p) {
    const Token *current = peek(p);
    if (match(p, TOK_NUMBER)) {
        return make_number(p->arena, current->integer_value, current->span);
    }
    if (match(p, TOK_IDENTIFIER)) {
        return make_name(p->arena, current->span);
    }
    if (match(p, TOK_LEFT_PAREN)) {
        const Token *left = current;
        Expr *inside = parse_expression(p);
        const Token *right = expect(p, TOK_RIGHT_PAREN, "Missing closing parenthesis");
        inside->span = (Span){
            left->span.start, right != NULL ? right->span.end : inside->span.end
        };
        return inside;
    }

    report(p->diagnostics, current->span, "Expression needed");
    if (current->kind != TOK_EOF && current->kind != TOK_RIGHT_PAREN) p->current++;
    return make_error(p->arena, current->span);
}

An AST does not need to retain independent parenthesized nodes, but it should still preserve the span that covers the parentheses, or store a parenthesized marker separately. Formatters and precise source code transformations may require the full CST; the claim that "an AST with parenthesized nodes is always wrong" is an overgeneralization.

5. Constructing a Left-Associative Binary Tree with Loops

static Expr *parse_multiplicative(Parser *p) {
    Expr *left = parse_unary(p);
    while (peek(p)->kind == TOK_STAR || peek(p)->kind == TOK_SLASH) {
        TokenKind op = p->tokens[p->current++].kind;
        Expr *right = parse_unary(p);
        left = make_binary(p->arena, left, op, right);
    }
    return left;
}

static Expr *parse_additive(Parser *p) {
    Expr *left = parse_multiplicative(p);
    while (peek(p)->kind == TOK_PLUS || peek(p)->kind == TOK_MINUS) {
        TokenKind op = p->tokens[p->current++].kind;
        Expr *right = parse_multiplicative(p);
        left = make_binary(p->arena, left, op, right);
    }
    return left;
}

For 1 + 2 * 3, the multiplication function first returns *(2,3), and then the addition function constructs +(1,*(2,3)).

6. Unary Operations and Right Recursion

static Expr *parse_unary(Parser *p) {
    if (peek(p)->kind == TOK_MINUS || peek(p)->kind == TOK_BANG) {
        const Token *op = &p->tokens[p->current++];
        Expr *operand = parse_unary(p);
        return make_unary(p->arena, op->kind, operand, op->span.start);
    }
    return parse_primary(p);
}

Recursion supports !!-x. This skeleton has no depth counter yet; before accepting untrusted input, bound both prefix chains and parenthesis nesting or use an explicit stack. A token-count limit alone does not ensure that the process stack is large enough: tens of thousands of prefix operators can exhaust it.

7. Complete Consumption Is the Entry Responsibility

static Expr *parse_expression(Parser *p) {
    return parse_additive(p);
}

Expr *parse(Parser *p) {
    Expr *result = parse_expression(p);
    if (peek(p)->kind != TOK_EOF) {
        report(p->diagnostics, peek(p)->span, "Unexpected token after expression");
    }
    return result;
}

Here, parse_expression delegates to the lowest-precedence layer. A returned node can coexist with diagnostics; the caller must check the diagnostic container before executing or compiling the tree.

Calling only parse_expression without checking for EOF can mistakenly treat a valid prefix of 1 + 2 garbage as a complete success. When parsing embedded statements, the parser must check for the terminating token in the current context, such as a semicolon or a closing parenthesis.

Common Misconceptions

• Every grammar can be directly translated into recursive descent: Left recursion and predictive conflicts must be addressed.
• Once parentheses are removed from the AST, their positions can be discarded: Diagnostics and source code tools still require complete span information.
• A successful return of a node means all input has been consumed: The entry point must check for context termination tokens.
• Theoretical recursive descent depth is unbounded, so implementation need not impose limits: In practice, call stacks and memory are finite.

Exercise

1. Add a comparison operation layer to ensure that comparison operators have lower precedence than addition.
2. Implement right-associative assignment a = b = 1 and draw the resulting AST.
3. Compute the span for each node to cover both its left and right child nodes and the operator itself.
4. Design depth limits and diagnostics for ten thousand prefix ! operators and for deeply nested parentheses.

Summary

Recursive descent transforms grammar hierarchy into function call hierarchy, mapping associativity into loop or recursive traversal direction. AST construction proceeds in parallel with syntax parsing, but source spans, error nodes, and memory ownership must be considered from the very first interface design.

The next lesson uses FIRST/FOLLOW sets to explain "why a single token is sufficient to select a production rule," and designs a synchronization strategy that enables parsing to continue even in the presence of errors.