How to Build a Recursive Descent Parser in C++ with an AST

In Chapter 3, we built a lexer that turns Si source code into a stream of tokens. A token stream tells us what the individual pieces of source code are, but it does not describe how those pieces fit together. It cannot tell us which expressions belong together, which statements form a function body, or whether multiplication should bind more tightly than addition.

In this chapter, we build the next compiler stage: a recursive descent parser in C++. The parser performs syntax analysis, checks whether the token sequence matches the Si grammar, preserves operator precedence, reports useful syntax errors, and converts valid input into an Abstract Syntax Tree (AST) for later compiler stages.

By the end, the front end will be able to move from source text to tokens and then from tokens to a structured AST that can be inspected and tested.

What You Will Learn

By the end of this chapter, you will be able to:

• explain what a recursive descent parser does in a compiler front end;
• design AST nodes for functions, statements, and expressions;
• translate lexer tokens into compiler-specific types and operators;
• build a recursive descent parser in modern C++;
• map grammar rules to parser functions;
• parse expressions with correct precedence and left associativity;
• produce syntax errors with useful line and column information;
• inspect the generated tree with an AST printer;
• test valid syntax, precedence rules, nested calls, and parser failures with CTest.

What Is a Recursive Descent Parser?

A recursive descent parser is a top-down parsing technique in which parser functions correspond closely to grammar rules. A function responsible for one syntactic construct calls other parsing functions for the constructs nested inside it.

For example, a function declaration parser can read the function name and parameters before delegating the function body to a block parser. An expression parser can delegate increasingly tighter-binding operations to lower-level functions so that multiplication is grouped before addition.

This close relationship between grammar rules and C++ functions makes recursive descent especially useful for a small compiler or language implementation because the control flow remains visible and easy to debug.

How Does a Recursive Descent Parser Work?

The parser in this chapter starts with the token vector produced by the lexer and advances through it with a cursor. At a high level, parsing follows this process:

1. parseProgram() begins at the root of the source file.
2. Statement-parsing functions select the correct grammar rule from the current token.
3. Expression-parsing functions descend through a precedence hierarchy.
4. Successful rules create AST nodes and connect child nodes to their parents.
5. expect() stops parsing with a source-aware error when required syntax is missing.
6. The completed ProgramNode becomes the root of the AST.

The compiler front end therefore has three distinct responsibilities:

Stage	Input	Main responsibility	Output
Lexer	Source characters	Recognise tokens	Token stream
Parser	Token stream	Validate grammatical structure	AST
Semantic analysis	AST	Validate names, types, calls, and other meaning	Semantically validated program

Keeping these stages separate is important. The parser determines whether the source has a valid grammatical shape; it does not yet decide whether that source is meaningful according to the language’s type and symbol rules.

What Is an Abstract Syntax Tree (AST)?

An Abstract Syntax Tree (AST) is the compiler’s structured representation of a program after parsing. Unlike the original token stream, an AST records the relationships between declarations, statements, operators, identifiers, and literal values.

The CPU never sees this tree directly. Instead, later compiler stages use the AST for semantic analysis, intermediate representation generation, optimisation, and code generation.

Consider this expression:

x + 5 * 10

The parser must preserve the fact that multiplication binds more tightly than addition:

BinaryExpression(+)
├── Identifier(x)
└── BinaryExpression(*)
    ├── IntLiteral(5)
    └── IntLiteral(10)

The AST removes syntax that is no longer useful to later stages while preserving the relationships that affect the program’s meaning:

• A ProgramNode owns the top-level declarations.
• A FunctionDeclarationNode owns its parameters and body.
• A BlockNode owns its statements.
• Expression nodes form smaller trees inside statements.
• Leaf nodes contain identifiers and literal values.

Parser Architecture at a Glance

Before implementing each phase, it helps to see how the pieces fit together:

File	Responsibility
Type.hpp	Compiler-level data types
Operator.hpp	Binary and unary operator representations
AST.hpp	AST node hierarchy and visitor interface
Parser.hpp	Parser state, helpers, and grammar-function declarations
Parser.cpp	Recursive descent parser implementation
ASTPrinter.hpp	Human-readable AST traversal
main.cpp	Lexer → parser → AST printer pipeline
ParserTests.cpp	Parser and precedence regression tests

The parser is the bridge between the lexer and the rest of the compiler. Tokens describe what the lexer recognised; AST nodes describe the structure later compiler stages need.

Internal Compiler Types

The lexer works with tokens such as TokenType::IntType, TokenType::Plus, and TokenType::DoubleEquals. The AST should not depend directly on lexer-specific token names. Instead, the parser converts lexical tokens into compiler concepts that remain useful after tokenisation:

int  -> Type::Int
bool -> Type::Bool
+    -> BinaryOp::Add
-    -> BinaryOp::Subtract
!    -> UnaryOp::Not

This separation keeps later compiler stages independent from the exact spelling of the source language.

Data Types: Type.hpp

Create gsisi/include/Type.hpp:

#pragma once

#include <ostream>

//--------------------------------------
// Language Types
//--------------------------------------
enum class Type {
    Int,
    Bool,
    Void,
    Unknown
};

//--------------------------------------
// Helpers
//--------------------------------------
[[nodiscard]] inline const char* toString(Type type) noexcept {
    switch (type) {
        case Type::Int:     return "int";
        case Type::Bool:    return "bool";
        case Type::Void:    return "void";
        case Type::Unknown: return "unknown";
    }
    return "unknown";
}

inline std::ostream& operator<<(std::ostream& os, Type type) {
    return os << toString(type);
}

Type::Unknown gives later compiler stages a safe placeholder when a type has not yet been resolved.

Operators: Operator.hpp

Create gsisi/include/Operator.hpp:

#pragma once

#include <ostream>

//--------------------------------------
// Binary Operators
//--------------------------------------
enum class BinaryOp {
    Add,
    Subtract,
    Multiply,
    Divide,

    Less,
    LessEqual,
    Greater,
    GreaterEqual,
    Equal,
    NotEqual
};

//--------------------------------------
// Unary Operators
//--------------------------------------
enum class UnaryOp {
    Negate,
    Not
};

//--------------------------------------
// Helpers
//--------------------------------------
[[nodiscard]] inline const char* toString(BinaryOp op) noexcept {
    switch (op) {
        case BinaryOp::Add:          return "+";
        case BinaryOp::Subtract:     return "-";
        case BinaryOp::Multiply:     return "*";
        case BinaryOp::Divide:       return "/";
        case BinaryOp::Less:         return "<";
        case BinaryOp::LessEqual:    return "<=";
        case BinaryOp::Greater:      return ">";
        case BinaryOp::GreaterEqual: return ">=";
        case BinaryOp::Equal:        return "==";
        case BinaryOp::NotEqual:     return "!=";
    }
    return "?";
}

[[nodiscard]] inline const char* toString(UnaryOp op) noexcept {
    switch (op) {
        case UnaryOp::Negate: return "-";
        case UnaryOp::Not:    return "!";
    }
    return "?";
}

inline std::ostream& operator<<(std::ostream& os, BinaryOp op) {
    return os << toString(op);
}

inline std::ostream& operator<<(std::ostream& os, UnaryOp op) {
    return os << toString(op);
}

The parser now has a clean boundary: tokens describe what the lexer recognised, while Type, BinaryOp, and UnaryOp describe what the AST means.

Recursive Descent Grammar and Operator Precedence

The parser functions in this chapter mirror the Si grammar. Each function is responsible for recognising one syntactic level and can call other parser functions for nested constructs.

The expression rules are arranged as a precedence ladder. Lower-precedence rules call tighter-binding rules, which allows the structure of the parser itself to encode operator precedence.

This chapter implements the following simplified grammar:

program             -> statement* EOF ;
statement           -> functionDeclaration
                    | letStatement
                    | ifStatement
                    | whileStatement
                    | returnStatement
                    | assignment
                    | expressionStatement ;
functionDeclaration -> "fn" IDENTIFIER "(" parameters? ")"
                        (":" type)? block ;
parameters          -> parameter ("," parameter)* ;
parameter           -> IDENTIFIER ":" type ;
type                -> "int" | "bool" | "void" ;
letStatement        -> "let" IDENTIFIER ":" type
                        "=" expression ";" ;
ifStatement         -> "if" "(" expression ")" block
                        ("else" (ifStatement | block))? ;
whileStatement      -> "while" "(" expression ")" block ;
returnStatement     -> "return" expression? ";" ;
assignment          -> IDENTIFIER "=" expression ";" ;
expressionStatement -> expression ";" ;
expression          -> equality ;
equality            -> comparison (("==" | "!=") comparison)* ;
comparison          -> additive (("<" | "<=" | ">" | ">=") additive)* ;
additive            -> multiplicative (("+" | "-") multiplicative)* ;
multiplicative      -> unary (("*" | "/") unary)* ;
unary               -> ("!" | "-") unary | primary ;
primary             -> INT_LITERAL
                    | BOOL_LITERAL
                    | IDENTIFIER
                    | IDENTIFIER "(" arguments? ")"
                    | "(" expression ")" ;
arguments           -> expression ("," expression)* ;
block               -> "{" statement* "}" ;

The order of the expression rules is important. Each level calls the next, tighter-binding level. That is how the parser gives * higher precedence than +, and relational operators higher precedence than equality operators.

The grammar also avoids direct left recursion in the expression rules. A direct rule such as expression -> expression + term would repeatedly call itself before consuming input, so a hand-written recursive descent parser instead uses the iterative pattern shown in the grammar above.

Phase 1: Define the AST

The first implementation step is to define the tree that the parser will build. Every AST node stores a source position so later compiler stages can report errors such as an unknown variable or an invalid return type at the correct location.

Ownership is represented with std::unique_ptr. A parent node owns its children, so destroying the root automatically destroys the complete tree without requiring manual lifetime management.

Create gsisi/include/AST.hpp:

#pragma once

#include <memory>
#include <string>
#include <vector>

#include "Operator.hpp"
#include "Type.hpp"

//--------------------------------------
// Forward declarations
//--------------------------------------
struct IntLiteralNode;
struct BoolLiteralNode;
struct IdentifierNode;
struct BinaryExpressionNode;
struct UnaryExpressionNode;
struct FunctionCallNode;

struct BlockNode;
struct LetStatementNode;
struct ReturnStatementNode;
struct FunctionDeclarationNode;
struct ExpressionStatementNode;
struct AssignmentNode;
struct WhileStatementNode;
struct IfStatementNode;
struct ProgramNode;

//--------------------------------------
// Visitor interface
//--------------------------------------
class ASTVisitor {
public:
    virtual ~ASTVisitor() = default;

    virtual void visit(IntLiteralNode&) = 0;
    virtual void visit(BoolLiteralNode&) = 0;
    virtual void visit(IdentifierNode&) = 0;
    virtual void visit(BinaryExpressionNode&) = 0;
    virtual void visit(UnaryExpressionNode&) = 0;
    virtual void visit(FunctionCallNode&) = 0;

    virtual void visit(BlockNode&) = 0;
    virtual void visit(LetStatementNode&) = 0;
    virtual void visit(ReturnStatementNode&) = 0;
    virtual void visit(FunctionDeclarationNode&) = 0;
    virtual void visit(ExpressionStatementNode&) = 0;
    virtual void visit(AssignmentNode&) = 0;
    virtual void visit(WhileStatementNode&) = 0;
    virtual void visit(IfStatementNode&) = 0;
    virtual void visit(ProgramNode&) = 0;
};

//--------------------------------------
// Base nodes
//--------------------------------------
struct ASTNode {
    int line{};
    int column{};

    virtual ~ASTNode() = default;
    virtual void accept(ASTVisitor& visitor) = 0;
};

struct ExpressionNode : ASTNode {};
struct StatementNode : ASTNode {};

//--------------------------------------
// CRTP visitable helper
//--------------------------------------
template <typename Derived, typename Base>
struct Visitable : Base {
    void accept(ASTVisitor& visitor) override {
        visitor.visit(static_cast<Derived&>(*this));
    }
};

//--------------------------------------
// Expression nodes
//--------------------------------------
struct IntLiteralNode : Visitable<IntLiteralNode, ExpressionNode> {
    int value{};
};

struct BoolLiteralNode : Visitable<BoolLiteralNode, ExpressionNode> {
    bool value{};
};

struct IdentifierNode : Visitable<IdentifierNode, ExpressionNode> {
    std::string name;
};

struct BinaryExpressionNode : Visitable<BinaryExpressionNode, ExpressionNode> {
    std::unique_ptr<ExpressionNode> left;
    BinaryOp oper;
    std::unique_ptr<ExpressionNode> right;
};

struct UnaryExpressionNode : Visitable<UnaryExpressionNode, ExpressionNode> {
    UnaryOp oper;
    std::unique_ptr<ExpressionNode> right;
};

struct FunctionCallNode : Visitable<FunctionCallNode, ExpressionNode> {
    std::string name;
    std::vector<std::unique_ptr<ExpressionNode>> arguments;
};

//--------------------------------------
// Statement nodes
//--------------------------------------
struct BlockNode : Visitable<BlockNode, StatementNode> {
    std::vector<std::unique_ptr<StatementNode>> statements;
};

struct LetStatementNode : Visitable<LetStatementNode, StatementNode> {
    std::string identifier;
    Type type{Type::Unknown};
    std::unique_ptr<ExpressionNode> initialiser;
};

struct ReturnStatementNode : Visitable<ReturnStatementNode, StatementNode> {
    std::unique_ptr<ExpressionNode> expression;
};

struct ParameterNode {
    std::string name;
    Type type{Type::Unknown};
};

struct FunctionDeclarationNode : Visitable<FunctionDeclarationNode, StatementNode> {
    std::string name;
    std::vector<ParameterNode> parameters;
    Type returnType{Type::Void};
    std::unique_ptr<BlockNode> body;
};

struct ExpressionStatementNode : Visitable<ExpressionStatementNode, StatementNode> {
    std::unique_ptr<ExpressionNode> expression;
};

struct AssignmentNode : Visitable<AssignmentNode, StatementNode> {
    std::string identifier;
    std::unique_ptr<ExpressionNode> expression;
};

struct WhileStatementNode : Visitable<WhileStatementNode, StatementNode> {
    std::unique_ptr<ExpressionNode> condition;
    std::unique_ptr<BlockNode> body;
};

struct IfStatementNode : Visitable<IfStatementNode, StatementNode> {
    std::unique_ptr<ExpressionNode> condition;
    std::unique_ptr<BlockNode> thenBranch;
    std::unique_ptr<BlockNode> elseBranch;
};

struct ProgramNode : Visitable<ProgramNode, ASTNode> {
    std::vector<std::unique_ptr<StatementNode>> nodes;
};

The Visitable helper implements the visitor dispatch shared by every node. This lets the semantic analyser, AST printer, and future IR generator traverse the same tree without adding stage-specific logic to the AST classes.

Phase 2: Build the Parser Interface

With the AST structure in place, the next step is to define the parser itself. The parser owns the token vector and keeps a cursor named _pos, which identifies the next token to inspect. Four helpers control the stream:

• peek() reads the current token without consuming it.
• peekNext() performs one-token lookahead.
• advance() consumes one token.
• expect() consumes a required token or reports a syntax error.

The constructor also verifies that the lexer supplied an EOF token. That gives the parser a safe sentinel and prevents out-of-bounds reads.

Create gsisi/include/Parser.hpp:

#pragma once

#include <memory>
#include <stdexcept>
#include <vector>
#include <algorithm>

#include "AST.hpp"
#include "Token.hpp"
#include "Type.hpp"
#include "Operator.hpp"

//--------------------------------------
// Parser
//--------------------------------------
class Parser
{
public:
    explicit Parser(std::vector<Token> tokens) : _tokens(std::move(tokens)) {
        if (_tokens.empty() || _tokens.back().type != TokenType::EOF_Token) {
            throw std::invalid_argument("Parser requires a token stream ending with EOF");
        }
    }

    [[nodiscard]] std::unique_ptr<ProgramNode> parseProgram();

private:
    //--------------------------------------
    // State
    //--------------------------------------
    std::vector<Token> _tokens;
    size_t _pos{0};

    //--------------------------------------
    // Core helpers
    //--------------------------------------
    [[nodiscard]] const Token& peek() const noexcept {
        return _tokens[_pos];
    }

    [[nodiscard]] const Token& peekNext() const noexcept {
        return (_pos + 1 < _tokens.size())
            ? _tokens[_pos + 1]
            : _tokens.back();
    }

    const Token& advance() noexcept {
        if (!isAtEnd()) {
            return _tokens[_pos++];
        }

        return peek();
    }

    [[nodiscard]] bool check(TokenType type) const noexcept {
        return peek().type == type;
    }

    [[nodiscard]] bool isAtEnd() const noexcept {
        return check(TokenType::EOF_Token);
    }

    bool match(TokenType type) noexcept {
        if (!check(type)) {
            return false;
        }

        advance();
        return true;
    }

    const Token& expect(TokenType type, const std::string& message) {
        if (check(type)) {
            return advance();
        }

        error(peek(), message);
    }

    [[noreturn]] void error(const Token &token, const std::string &message) const {
        const std::string found =
            token.type == TokenType::EOF_Token
                ? "end of file"
                : "'" + std::string(token.lexeme) + "'";

        throw std::runtime_error(
            "Parse error at " +
            std::to_string(token.line) + ":" +
            std::to_string(token.column) + ": " +
            message + "; found " + found);
    }

    //--------------------------------------
    // Node helper
    //--------------------------------------
    template <typename T>
    [[nodiscard]] std::unique_ptr<T> createNode(const Token &token) {
        auto node = std::make_unique<T>();
        node->line = token.line;
        node->column = token.column;
        return node;
    }

    //--------------------------------------
    // Conversion helpers
    //--------------------------------------
    Type parseType();
    BinaryOp toBinaryOp(const Token &token) const;
    UnaryOp toUnaryOp(const Token &token) const;

    std::unique_ptr<ExpressionNode> parseBinaryExpression(
        std::unique_ptr<ExpressionNode> (Parser::*nextLevel)(),
        std::initializer_list<TokenType> operators);

    //--------------------------------------
    // Grammar
    //--------------------------------------
    std::unique_ptr<StatementNode> parseStatement();
    std::unique_ptr<FunctionDeclarationNode> parseFunctionDeclaration();
    std::unique_ptr<LetStatementNode> parseLetStatement();
    std::unique_ptr<IfStatementNode> parseIfStatement();
    std::unique_ptr<WhileStatementNode> parseWhileStatement();
    std::unique_ptr<ReturnStatementNode> parseReturnStatement();
    std::unique_ptr<BlockNode> parseBlock();
    std::unique_ptr<StatementNode> parseAssignment();
    std::unique_ptr<StatementNode> parseExpressionStatement();

    std::unique_ptr<ExpressionNode> parseExpression();
    std::unique_ptr<ExpressionNode> parseEquality();
    std::unique_ptr<ExpressionNode> parseComparison();
    std::unique_ptr<ExpressionNode> parseAdditive();
    std::unique_ptr<ExpressionNode> parseMultiplicative();
    std::unique_ptr<ExpressionNode> parseUnary();
    std::unique_ptr<ExpressionNode> parsePrimary();
};

The error helper reports both the source location and the token that caused the failure. At EOF, it prints end of file instead of an empty lexeme.

Phase 3: Convert Tokens into AST Values

Create gsisi/src/Parser.cpp and begin with the type and operator conversion functions:

#include "Parser.hpp"

#include <charconv>
#include <system_error>

//--------------------------------------
// Type and operator conversion
//--------------------------------------
Type Parser::parseType() {
    const Token& token = peek();

    switch (token.type) {
        case TokenType::IntType:
            advance();
            return Type::Int;
        case TokenType::BoolType:
            advance();
            return Type::Bool;
        case TokenType::VoidType:
            advance();
            return Type::Void;
        default:
            error(token, "Expected type");
    }
}

BinaryOp Parser::toBinaryOp(const Token& token) const {
    switch (token.type) {
        case TokenType::Plus:         return BinaryOp::Add;
        case TokenType::Minus:        return BinaryOp::Subtract;
        case TokenType::Star:         return BinaryOp::Multiply;
        case TokenType::Slash:        return BinaryOp::Divide;
        case TokenType::Less:         return BinaryOp::Less;
        case TokenType::LessEqual:    return BinaryOp::LessEqual;
        case TokenType::Greater:      return BinaryOp::Greater;
        case TokenType::GreaterEqual: return BinaryOp::GreaterEqual;
        case TokenType::DoubleEquals: return BinaryOp::Equal;
        case TokenType::NotEqual:     return BinaryOp::NotEqual;
        default:
            error(token, "Invalid binary operator");
    }
}

UnaryOp Parser::toUnaryOp(const Token& token) const {
    switch (token.type) {
        case TokenType::Minus: return UnaryOp::Negate;
        case TokenType::Not:   return UnaryOp::Not;
        default:
            error(token, "Invalid unary operator");
    }
}

parseType() checks the current token before consuming it. This matters at the end of an incomplete declaration: the parser can now report a normal syntax error instead of accidentally reading the previous token.

Phase 4: Parse Programs and Statements

A program is the root of the AST. parseProgram() repeatedly parses statements until the EOF sentinel is reached.

The statement router examines the current token to select a grammar rule. An identifier followed by = is parsed as an assignment. Other expressions become expression statements, which allows stand-alone function calls such as out(sum);.

Continue gsisi/src/Parser.cpp:

//--------------------------------------
// Program and statements
//--------------------------------------
std::unique_ptr<ProgramNode> Parser::parseProgram() {
    auto program = createNode<ProgramNode>(peek());

    while (!isAtEnd()) {
        program->nodes.push_back(parseStatement());
    }

    return program;
}

std::unique_ptr<StatementNode> Parser::parseStatement() {
    switch (peek().type) {
        case TokenType::Fn:
            return parseFunctionDeclaration();
        case TokenType::Let:
            return parseLetStatement();
        case TokenType::If:
            return parseIfStatement();
        case TokenType::While:
            return parseWhileStatement();
        case TokenType::Return:
            return parseReturnStatement();
        case TokenType::Identifier:
            if (peekNext().type == TokenType::Equals) {
                return parseAssignment();
            }
            return parseExpressionStatement();
        default:
            return parseExpressionStatement();
    }
}

std::unique_ptr<FunctionDeclarationNode>
Parser::parseFunctionDeclaration() {
    const Token& fnToken = expect(TokenType::Fn, "Expected 'fn'");
    auto node = createNode<FunctionDeclarationNode>(fnToken);

    node->name = std::string(
        expect(TokenType::Identifier, "Expected function name").lexeme
    );

    expect(TokenType::OpenParen, "Expected '('");

    if (!check(TokenType::CloseParen)) {
        do {
            ParameterNode parameter;
            parameter.name = std::string(
                expect(
                    TokenType::Identifier,
                    "Expected parameter name"
                ).lexeme
            );

            expect(TokenType::Colon, "Expected ':' after parameter name");
            parameter.type = parseType();
            node->parameters.push_back(std::move(parameter));
        } while (match(TokenType::Comma));
    }

    expect(TokenType::CloseParen, "Expected ')' after parameters");

    node->returnType =
        match(TokenType::Colon)
            ? parseType()
            : Type::Void;

    node->body = parseBlock();
    return node;
}

std::unique_ptr<BlockNode> Parser::parseBlock() {
    const Token& brace =
        expect(TokenType::OpenBrace, "Expected '{'");

    auto node = createNode<BlockNode>(brace);

    while (!check(TokenType::CloseBrace) && !isAtEnd()) {
        node->statements.push_back(parseStatement());
    }

    expect(TokenType::CloseBrace, "Expected '}' after block");
    return node;
}

std::unique_ptr<LetStatementNode> Parser::parseLetStatement() {
    const Token& letToken =
        expect(TokenType::Let, "Expected 'let'");

    auto node = createNode<LetStatementNode>(letToken);

    node->identifier = std::string(
        expect(TokenType::Identifier, "Expected variable name").lexeme
    );

    expect(TokenType::Colon, "Expected ':' after variable name");
    node->type = parseType();

    expect(TokenType::Equals, "Expected '=' after variable type");
    node->initialiser = parseExpression();

    expect(
        TokenType::SemiColon,
        "Expected ';' after variable declaration"
    );

    return node;
}

std::unique_ptr<StatementNode> Parser::parseAssignment() {
    const Token& identifier =
        expect(TokenType::Identifier, "Expected identifier");

    auto node = createNode<AssignmentNode>(identifier);
    node->identifier = std::string(identifier.lexeme);

    expect(TokenType::Equals, "Expected '=' after identifier");
    node->expression = parseExpression();
    expect(TokenType::SemiColon, "Expected ';' after assignment");

    return node;
}

std::unique_ptr<ReturnStatementNode>
Parser::parseReturnStatement() {
    const Token& returnToken =
        expect(TokenType::Return, "Expected 'return'");

    auto node = createNode<ReturnStatementNode>(returnToken);

    if (!check(TokenType::SemiColon)) {
        node->expression = parseExpression();
    }

    expect(TokenType::SemiColon, "Expected ';' after return value");
    return node;
}

std::unique_ptr<StatementNode>
Parser::parseExpressionStatement() {
    auto node = createNode<ExpressionStatementNode>(peek());
    node->expression = parseExpression();

    expect(TokenType::SemiColon, "Expected ';' after expression");
    return node;
}

Several details make this implementation more reliable:

• Each node receives the position of the token that begins the construct.
• Blocks stop at } but still detect an unexpected EOF.
• Error messages explain what should follow a name, type, expression, or block.
• Empty returns such as return; remain valid for void functions.

Phase 5: Parse Control Flow

An if statement owns a condition, a then-branch, and an optional else-branch. An else if chain is represented as an else block containing another IfStatementNode.

A while statement owns its condition and body.

Continue gsisi/src/Parser.cpp:

//--------------------------------------
// Control flow
//--------------------------------------
std::unique_ptr<IfStatementNode> Parser::parseIfStatement() {
    const Token& ifToken = expect(TokenType::If, "Expected 'if'");
    auto node = createNode<IfStatementNode>(ifToken);

    expect(TokenType::OpenParen, "Expected '(' after 'if'");
    node->condition = parseExpression();
    expect(TokenType::CloseParen, "Expected ')' after condition");

    node->thenBranch = parseBlock();

    if (match(TokenType::Else)) {
        if (check(TokenType::If)) {
            auto elseBlock = createNode<BlockNode>(peek());
            elseBlock->statements.push_back(parseIfStatement());
            node->elseBranch = std::move(elseBlock);
        } else {
            node->elseBranch = parseBlock();
        }
    }

    return node;
}

std::unique_ptr<WhileStatementNode>
Parser::parseWhileStatement() {
    const Token& whileToken =
        expect(TokenType::While, "Expected 'while'");

    auto node = createNode<WhileStatementNode>(whileToken);

    expect(TokenType::OpenParen, "Expected '(' after 'while'");
    node->condition = parseExpression();
    expect(TokenType::CloseParen, "Expected ')' after condition");

    node->body = parseBlock();
    return node;
}

At this stage, the parser only validates structure. It does not require an if or while condition to have type bool; semantic analysis will enforce that in Chapter 5.

Phase 6: Parse Expressions with Precedence

Operator precedence is one of the most important jobs of an expression parser. In this recursive descent design, expressions are parsed from the lowest-precedence rule to the highest:

equality
  -> comparison
      -> additive
          -> multiplicative
              -> unary
                  -> primary

Each binary-precedence level follows the same pattern:

1. Parse the left operand using the next tighter level.
2. Consume matching operators in a loop.
3. Parse each right operand using the same tighter level.
4. Replace the left operand with a new binary-expression node.

The loop makes binary operators left-associative. For example:

10 - 3 - 2

becomes:

(10 - 3) - 2

Continue gsisi/src/Parser.cpp:

//--------------------------------------
// Expressions
//--------------------------------------
std::unique_ptr<ExpressionNode>
Parser::parseBinaryExpression(
    std::unique_ptr<ExpressionNode> (Parser::*nextLevel)(),
    std::initializer_list<TokenType> operators
) {
    auto left = (this->*nextLevel)();

    while (
        std::find(
            operators.begin(),
            operators.end(),
            peek().type
        ) != operators.end()
    ) {
        const Token& operatorToken = advance();
        auto right = (this->*nextLevel)();

        auto node =
            createNode<BinaryExpressionNode>(operatorToken);

        node->oper = toBinaryOp(operatorToken);
        node->left = std::move(left);
        node->right = std::move(right);
        left = std::move(node);
    }

    return left;
}

std::unique_ptr<ExpressionNode> Parser::parseExpression() {
    return parseEquality();
}

std::unique_ptr<ExpressionNode> Parser::parseEquality() {
    return parseBinaryExpression(
        &Parser::parseComparison,
        {
            TokenType::DoubleEquals,
            TokenType::NotEqual
        }
    );
}

std::unique_ptr<ExpressionNode> Parser::parseComparison() {
    return parseBinaryExpression(
        &Parser::parseAdditive,
        {
            TokenType::Less,
            TokenType::LessEqual,
            TokenType::Greater,
            TokenType::GreaterEqual
        }
    );
}

std::unique_ptr<ExpressionNode> Parser::parseAdditive() {
    return parseBinaryExpression(
        &Parser::parseMultiplicative,
        {
            TokenType::Plus,
            TokenType::Minus
        }
    );
}

std::unique_ptr<ExpressionNode>
Parser::parseMultiplicative() {
    return parseBinaryExpression(
        &Parser::parseUnary,
        {
            TokenType::Star,
            TokenType::Slash
        }
    );
}

std::unique_ptr<ExpressionNode> Parser::parseUnary() {
    if (check(TokenType::Minus) || check(TokenType::Not)) {
        const Token& operatorToken = advance();

        auto node =
            createNode<UnaryExpressionNode>(operatorToken);

        node->oper = toUnaryOp(operatorToken);
        node->right = parseUnary();
        return node;
    }

    return parsePrimary();
}

std::unique_ptr<ExpressionNode> Parser::parsePrimary() {
    const Token& token = advance();

    switch (token.type) {
        case TokenType::Identifier: {
            if (match(TokenType::OpenParen)) {
                auto call = createNode<FunctionCallNode>(token);
                call->name = std::string(token.lexeme);

                if (!check(TokenType::CloseParen)) {
                    do {
                        call->arguments.push_back(
                            parseExpression()
                        );
                    } while (match(TokenType::Comma));
                }

                expect(
                    TokenType::CloseParen,
                    "Expected ')' after function arguments"
                );
                return call;
            }

            auto identifier =
                createNode<IdentifierNode>(token);

            identifier->name = std::string(token.lexeme);
            return identifier;
        }

        case TokenType::IntLiteral: {
            int value{};
            const char* begin = token.lexeme.data();
            const char* end = begin + token.lexeme.size();

            const auto [ptr, errorCode] =
                std::from_chars(begin, end, value);

            if (
                errorCode == std::errc::result_out_of_range
            ) {
                error(token, "Integer literal is out of range");
            }

            if (
                errorCode != std::errc{} ||
                ptr != end
            ) {
                error(token, "Invalid integer literal");
            }

            auto number = createNode<IntLiteralNode>(token);
            number->value = value;
            return number;
        }

        case TokenType::BoolLiteral: {
            auto boolean =
                createNode<BoolLiteralNode>(token);

            boolean->value = token.lexeme == "true";
            return boolean;
        }

        case TokenType::OpenParen: {
            auto expression = parseExpression();
            expect(
                TokenType::CloseParen,
                "Expected ')' after expression"
            );
            return expression;
        }

        default:
            error(token, "Expected expression");
    }
}

The integer-literal branch uses std::from_chars, avoiding a temporary string and allowing the parser to report out-of-range values cleanly.

Parentheses restart parsing at parseExpression(), which lets them override normal precedence:

(1 + 2) * 3

Phase 7: Print the AST

A parser becomes much easier to debug when its output is visible. The ASTPrinter implements every visitor method and uses indentation to make parent-child relationships in the generated tree immediately visible.

Create gsisi/include/ASTPrinter.hpp:

#pragma once

#include <cstddef>
#include <ostream>
#include <string>
#include <string_view>

#include "AST.hpp"

class ASTPrinter final : public ASTVisitor {
public:
    explicit ASTPrinter(std::ostream& output)
        : _output(output) {}

    void print(ProgramNode& node) {
        node.accept(*this);
    }

    void visit(IntLiteralNode& node) override {
        line("IntLiteral " + std::to_string(node.value));
    }

    void visit(BoolLiteralNode& node) override {
        line(
            std::string("BoolLiteral ") +
            (node.value ? "true" : "false")
        );
    }

    void visit(IdentifierNode& node) override {
        line("Identifier " + node.name);
    }

    void visit(BinaryExpressionNode& node) override {
        line(
            "BinaryExpression " +
            std::string(toString(node.oper))
        );

        withIndent([&] {
            node.left->accept(*this);
            node.right->accept(*this);
        });
    }

    void visit(UnaryExpressionNode& node) override {
        line(
            "UnaryExpression " +
            std::string(toString(node.oper))
        );

        withIndent([&] {
            node.right->accept(*this);
        });
    }

    void visit(FunctionCallNode& node) override {
        line("FunctionCall " + node.name);

        withIndent([&] {
            for (auto& argument : node.arguments) {
                argument->accept(*this);
            }
        });
    }

    void visit(BlockNode& node) override {
        line("Block");

        withIndent([&] {
            for (auto& statement : node.statements) {
                statement->accept(*this);
            }
        });
    }

    void visit(LetStatementNode& node) override {
        line(
            "Let " + node.identifier +
            ": " + std::string(toString(node.type))
        );

        withIndent([&] {
            node.initialiser->accept(*this);
        });
    }

    void visit(ReturnStatementNode& node) override {
        line("Return");

        if (node.expression) {
            withIndent([&] {
                node.expression->accept(*this);
            });
        }
    }

    void visit(FunctionDeclarationNode& node) override {
        line(
            "Function " + node.name +
            ": " + std::string(toString(node.returnType))
        );

        withIndent([&] {
            if (!node.parameters.empty()) {
                line("Parameters");

                withIndent([&] {
                    for (const auto& parameter : node.parameters) {
                        line(
                            parameter.name +
                            ": " +
                            std::string(toString(parameter.type))
                        );
                    }
                });
            }

            node.body->accept(*this);
        });
    }

    void visit(ExpressionStatementNode& node) override {
        line("ExpressionStatement");

        withIndent([&] {
            node.expression->accept(*this);
        });
    }

    void visit(AssignmentNode& node) override {
        line("Assignment " + node.identifier);

        withIndent([&] {
            node.expression->accept(*this);
        });
    }

    void visit(WhileStatementNode& node) override {
        line("While");

        withIndent([&] {
            line("Condition");

            withIndent([&] {
                node.condition->accept(*this);
            });

            node.body->accept(*this);
        });
    }

    void visit(IfStatementNode& node) override {
        line("If");

        withIndent([&] {
            line("Condition");

            withIndent([&] {
                node.condition->accept(*this);
            });

            line("Then");
            withIndent([&] {
                node.thenBranch->accept(*this);
            });

            if (node.elseBranch) {
                line("Else");

                withIndent([&] {
                    node.elseBranch->accept(*this);
                });
            }
        });
    }

    void visit(ProgramNode& node) override {
        line("Program");

        withIndent([&] {
            for (auto& statement : node.nodes) {
                statement->accept(*this);
            }
        });
    }

private:
    std::ostream& _output;
    std::size_t _indent{0};

    void line(std::string_view text) {
        _output << std::string(_indent * 2, ' ')
                << text << '\n';
    }

    template <typename Function>
    void withIndent(Function&& function) {
        ++_indent;
        function();
        --_indent;
    }
};

For this Si program:

fn main(): int {
    return 1 + 2 * 3;
}

the printer produces:

Program
  Function main: int
    Block
      Return
        BinaryExpression +
          IntLiteral 1
          BinaryExpression *
            IntLiteral 2
            IntLiteral 3

The output confirms that multiplication is nested below addition and therefore evaluated first.

Phase 8: Connect the Front End

At this point, the lexer and parser can be connected into one front-end pipeline. The compiler entry point now performs four steps:

source file
    ↓
lexer
    ↓
tokens
    ↓
parser
    ↓
AST
    ↓
AST printer

Update gsisi/src/main.cpp:

#include <exception>
#include <fstream>
#include <iostream>
#include <memory>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

#include "ASTPrinter.hpp"
#include "Lexer.hpp"
#include "Parser.hpp"

/**
 * Usage: ./si_compiler <source_file.si>
 */
int main(int argc, char* argv[]) {
    if (argc != 2) {
        std::cerr
            << "Usage: " << argv[0]
            << " <source_file.si>\n";
        return 1;
    }

    std::ifstream inputFile(argv[1], std::ios::binary);

    if (!inputFile) {
        std::cerr
            << "Error: Could not open file '"
            << argv[1] << "'\n";
        return 1;
    }

    std::stringstream buffer;
    buffer << inputFile.rdbuf();

    if (inputFile.bad()) {
        std::cerr
            << "Error: Failed while reading file '"
            << argv[1] << "'\n";
        return 1;
    }

    try {
        Lexer lexer(buffer.str());
        std::vector<Token> tokens = lexer.tokenise();

        Parser parser(std::move(tokens));
        std::unique_ptr<ProgramNode> ast =
            parser.parseProgram();

        std::cout << "Successfully parsed AST\n\n";

        ASTPrinter printer(std::cout);
        printer.print(*ast);
    } catch (const std::exception& error) {
        std::cerr
            << "Compilation error: "
            << error.what() << '\n';
        return 1;
    }

    return 0;
}

Build and run the compiler:

cmake -S . -B build
cmake --build build
./build/si_compiler tests/test.si

Phase 9: Test the Parser

Printing an AST is useful while developing, but automated tests are what protect the parser from regressions. Parser tests should inspect the actual node types, operators, and parent-child relationships rather than comparing one large block of formatted output.

The tests below cover:

• Function declarations and parameters.
• Multiplication taking precedence over addition.
• Parentheses overriding normal precedence.
• Nested function calls.
• A missing semicolon producing a source-aware parser error.

Update CMakeLists.txt

Use a small front-end library so the compiler executable and the test executable can share the lexer and parser:

cmake_minimum_required(VERSION 3.10)

# Name of your project
project(gsisi LANGUAGES CXX)

# Use C++20
set(CMAKE_CXX_STANDARD 20)
set(CMAKE_CXX_STANDARD_REQUIRED ON)
set(CMAKE_CXX_EXTENSIONS OFF)

file(GLOB SOURCES "src/*.cpp")
list(REMOVE_ITEM SOURCES "${CMAKE_CURRENT_SOURCE_DIR}/src/main.cpp")

add_library(gsisi_frontend ${SOURCES})

target_include_directories(gsisi_frontend
    PUBLIC
        ${CMAKE_CURRENT_SOURCE_DIR}/include
)

add_executable(si_compiler src/main.cpp)

target_link_libraries(si_compiler
    PRIVATE
        gsisi_frontend
)

# --------------------------------------------------
# Tests
# --------------------------------------------------
option(BUILD_TESTING "Build the gsisi tests" ON)

if(BUILD_TESTING)
    enable_testing()

    add_executable(parser_tests
        tests/ParserTests.cpp
        ${SOURCES}
    )

    target_include_directories(parser_tests PRIVATE include)

    add_test(
        NAME parser_tests
        COMMAND parser_tests
    )

    add_test(
        NAME semantic_sample
        COMMAND si_compiler
            ${CMAKE_CURRENT_SOURCE_DIR}/tests/test-2.si
    )
endif()

Create tests/ParserTests.cpp

This test runner uses only the C++ standard library, so no external test framework is required:

#include <functional>
#include <iostream>
#include <memory>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>

#include "AST.hpp"
#include "Lexer.hpp"
#include "Parser.hpp"

namespace {

void require(bool condition, const std::string& message) {
    if (!condition) {
        throw std::runtime_error(message);
    }
}

template <typename Expected, typename Actual>
Expected& requireNode(Actual& node, const std::string& message) {
    auto* result = dynamic_cast<Expected*>(&node);

    if (result == nullptr) {
        throw std::runtime_error(message);
    }

    return *result;
}

std::unique_ptr<ProgramNode> parse(std::string source) {
    Lexer lexer(std::move(source));
    std::vector<Token> tokens = lexer.tokenise();

    Parser parser(std::move(tokens));
    return parser.parseProgram();
}

void parsesFunctionDeclaration() {
    auto program = parse(R"(
        fn add(a: int, b: int): int {
            return a + b;
        }
    )");

    require(program->nodes.size() == 1, "Expected one top-level node");

    auto& function = requireNode<FunctionDeclarationNode>(
        *program->nodes.at(0),
        "Expected a function declaration"
    );

    require(function.name == "add", "Expected function name 'add'");
    require(function.parameters.size() == 2, "Expected two parameters");
    require(function.returnType == Type::Int, "Expected int return type");
    require(function.body->statements.size() == 1, "Expected one statement");
}

void respectsOperatorPrecedence() {
    auto program = parse(R"(
        fn main(): int {
            return 1 + 2 * 3;
        }
    )");

    auto& function = requireNode<FunctionDeclarationNode>(
        *program->nodes.at(0),
        "Expected a function declaration"
    );

    auto& returnStatement = requireNode<ReturnStatementNode>(
        *function.body->statements.at(0),
        "Expected a return statement"
    );

    auto& addition = requireNode<BinaryExpressionNode>(
        *returnStatement.expression,
        "Expected addition at the expression root"
    );

    require(addition.oper == BinaryOp::Add, "Expected root operator '+'");

    auto& multiplication = requireNode<BinaryExpressionNode>(
        *addition.right,
        "Expected multiplication on the right"
    );

    require(
        multiplication.oper == BinaryOp::Multiply,
        "Expected '*' to bind more tightly than '+'"
    );
}

void parenthesesOverridePrecedence() {
    auto program = parse(R"(
        fn main(): int {
            return (1 + 2) * 3;
        }
    )");

    auto& function = requireNode<FunctionDeclarationNode>(
        *program->nodes.at(0),
        "Expected a function declaration"
    );

    auto& returnStatement = requireNode<ReturnStatementNode>(
        *function.body->statements.at(0),
        "Expected a return statement"
    );

    auto& multiplication = requireNode<BinaryExpressionNode>(
        *returnStatement.expression,
        "Expected multiplication at the expression root"
    );

    require(
        multiplication.oper == BinaryOp::Multiply,
        "Expected root operator '*'"
    );

    auto& addition = requireNode<BinaryExpressionNode>(
        *multiplication.left,
        "Expected parenthesised addition on the left"
    );

    require(addition.oper == BinaryOp::Add, "Expected left operator '+'");
}

void parsesNestedFunctionCalls() {
    auto program = parse(R"(
        fn main(): int {
            out(add(1, 2));
            return 0;
        }
    )");

    auto& function = requireNode<FunctionDeclarationNode>(
        *program->nodes.at(0),
        "Expected a function declaration"
    );

    auto& statement = requireNode<ExpressionStatementNode>(
        *function.body->statements.at(0),
        "Expected an expression statement"
    );

    auto& outerCall = requireNode<FunctionCallNode>(
        *statement.expression,
        "Expected outer function call"
    );

    require(outerCall.name == "out", "Expected call to 'out'");
    require(outerCall.arguments.size() == 1, "Expected one argument");

    auto& innerCall = requireNode<FunctionCallNode>(
        *outerCall.arguments.at(0),
        "Expected nested function call"
    );

    require(innerCall.name == "add", "Expected nested call to 'add'");
    require(innerCall.arguments.size() == 2, "Expected two arguments");
}

void reportsMissingSemicolon() {
    try {
        parse(R"(
            fn main(): int {
                let x: int = 1
                return x;
            }
        )");

        throw std::runtime_error("Expected parsing to fail");
    } catch (const std::runtime_error& error) {
        const std::string message = error.what();

        require(
            message.find("Expected ';'") != std::string::npos,
            "Expected a missing-semicolon error"
        );

        require(
            message.find("Parse error at") != std::string::npos,
            "Expected source location in parser error"
        );
    }
}

} // namespace

int main() {
    using Test = std::pair<std::string, std::function<void()>>;

    const std::vector<Test> tests{
        {"parses function declaration", parsesFunctionDeclaration},
        {"respects operator precedence", respectsOperatorPrecedence},
        {"parentheses override precedence", parenthesesOverridePrecedence},
        {"parses nested function calls", parsesNestedFunctionCalls},
        {"reports missing semicolon", reportsMissingSemicolon}
    };

    int failed = 0;

    for (const auto& [name, test] : tests) {
        try {
            test();
            std::cout << "[PASS] " << name << '\n';
        } catch (const std::exception& error) {
            ++failed;
            std::cerr
                << "[FAIL] " << name
                << ": " << error.what() << '\n';
        }
    }

    if (failed != 0) {
        std::cerr << failed << " test(s) failed\n";
        return 1;
    }

    std::cout << "All parser tests passed\n";
    return 0;
}

The requireNode() helper uses dynamic_cast to verify the concrete AST node type. This is more precise than checking the AST printer’s text output.

Run the Tests

Configure the project with testing enabled, build it, and run CTest:

cmake -S . -B build -DBUILD_TESTING=ON
cmake --build build
ctest --test-dir build --output-on-failure

Expected result:

Test project .../build
    Start 1: parser_tests
1/1 Test #1: parser_tests ..................... Passed

100% tests passed, 0 tests failed

You can also run the test executable directly to see each individual case:

./build/parser_tests

[PASS] parses function declaration
[PASS] respects operator precedence
[PASS] parentheses override precedence
[PASS] parses nested function calls
[PASS] reports missing semicolon
All parser tests passed

Add More Parser Tests

Useful follow-up cases include:

• An empty parameter list.
• Multiple function parameters.
• Unary negation and logical not.
• if, else if, and else branches.
• A while loop with assignments.
• An unexpected closing brace.
• A missing closing parenthesis.
• An integer literal outside the supported range.

Common Recursive Descent Parser Mistakes

A recursive descent parser is conceptually simple, but a few implementation mistakes can produce subtle bugs:

• Giving every operator the same precedence. If addition and multiplication are parsed at the same level, an expression such as 1 + 2 * 3 can produce the wrong AST.
• Using direct left recursion. A rule that immediately calls itself before consuming a token can recurse forever in a conventional recursive descent parser.
• Consuming a token too early. Checking the current token before advancing makes syntax errors easier to report at the correct location.
• Mixing syntax analysis with semantic analysis. The parser should build grammatical structure; type rules, symbol lookup, and function validation belong to later stages.
• Discarding source positions. Keeping line and column information on AST nodes makes later compiler diagnostics much more useful.
• Testing only successful input. Invalid syntax, missing delimiters, nested calls, precedence, and boundary conditions all deserve dedicated parser tests.

Frequently Asked Questions

What is a recursive descent parser?

A recursive descent parser is a top-down parser organised as a set of mutually cooperating functions that correspond closely to grammar rules. Each function recognises one syntactic construct and can call other parsing functions for nested constructs.

How does a recursive descent parser build an AST?

As parser functions recognise declarations, statements, expressions, identifiers, and literals, they create AST nodes and attach child nodes to their parents. The completed program node becomes the root of the tree.

How does recursive descent handle operator precedence?

One common approach is to give each precedence level its own parsing function. Lower-precedence functions call tighter-binding functions, so multiplication can be nested below addition and therefore evaluated first.

What is the difference between a lexer and a parser?

The lexer converts source characters into tokens. The parser consumes those tokens, checks whether they follow the grammar, and turns valid syntax into an AST.

Can a recursive descent parser use a left-recursive grammar directly?

A conventional recursive descent parser cannot use direct left recursion as written because the parser function would call itself before consuming input. The grammar must be transformed, or that part of the language must be parsed with another strategy.

Is recursive descent the same as LL(1)?

Not exactly. Recursive descent is an implementation technique. It is commonly used with predictive LL-style grammars, and this parser uses limited lookahead, but the term does not by itself guarantee that every grammar is LL(1).

Why use std::unique_ptr for AST nodes?

The AST has a natural ownership hierarchy: parent nodes own their children. std::unique_ptr expresses that ownership directly and allows the complete tree to be destroyed automatically when the root is destroyed.

Does the parser check types and variable declarations?

No. This parser checks grammatical structure. Type compatibility, name resolution, function-call validation, and related meaning are responsibilities of semantic analysis.

Syntax Analysis vs Semantic Analysis: What the Parser Does Not Check

The parser validates grammar, not program meaning. That separation is fundamental to a clean compiler front end. For example, this program is syntactically valid:

fn main(): int {
    let x: int = true + 5;
    return 1;
}

The parser can build an AST because the declaration has the expected shape:

let IDENTIFIER : TYPE = EXPRESSION ;

However, adding a boolean to an integer is not meaningful. The semantic analyser will reject it in the next chapter.

Keeping lexical analysis, parsing, and semantic analysis separate makes the implementation easier to reason about and produces clearer compiler diagnostics:

Lexer:    Can the characters form valid tokens?
Parser:   Are the tokens arranged according to the grammar?
Semantic: Do declarations, names, calls, and types make sense?

Recursive Descent Parser: Key Takeaways

• A recursive descent parser converts a flat lexer token stream into a structured Abstract Syntax Tree.
• Parser functions mirror the grammar of the Si language, making the implementation straightforward to trace and debug.
• AST nodes own their children with std::unique_ptr.
• Equality, comparison, addition, multiplication, unary operators, and primary expressions form a precedence ladder.
• The precedence hierarchy ensures that tighter-binding operators are nested correctly in the AST.
• Source positions are preserved so parser and later compiler errors can point to useful locations.
• The AST printer makes the generated tree visible during development.
• CTest verifies successful parsing, operator precedence, nested calls, and syntax-error handling.
• Parsing validates structure; semantic analysis will validate names, types, calls, and other meaning.

Next Chapter

In Chapter 5, we will build a semantic analyser that consumes this AST, manages symbols and scopes, validates types and function calls, and checks return statements.