Define Abstract Syntax Tree (AST) Nodes in Rust

Mục tiêu: Create the Rust structs and enums that form the building blocks of the Abstract Syntax Tree (AST). This task involves defining the data structures for programs, functions, statements, and expressions in a new ast/nodes.rs file and integrating it into the project’s module system.

---

Congratulations on building and thoroughly testing your lexer! You’ve successfully conquered the first major phase of compilation, transforming a raw string of source code into a clean, linear sequence of tokens. This is a monumental step.

However, a flat list of tokens is like a pile of English words—it has the raw materials, but it lacks grammatical structure. The token stream [Let, Identifier("x"), Colon, Identifier("int"), Assign, Int(5), Semicolon] doesn’t inherently understand that 5 is the initial value for a variable named x of type int. To give the compiler this deep structural understanding, we must move on to the next phase: parsing.

The parser’s job is to consume the token stream from the lexer and build a tree-like data structure called an Abstract Syntax Tree (AST). The AST is a hierarchical representation of the code that captures its grammatical structure. Each node in the tree represents a construct in the language, like a function definition, a let statement, or an arithmetic expression.

Before we can write the logic to build this tree, we must first define the blueprints for its nodes. This task is all about creating the Rust structs and enums that will form the building blocks of our AST. These definitions are a direct translation of the EBNF grammar you so carefully designed into concrete Rust types.

Creating the Home for Our AST Definitions

The AST is a central data structure that will be created by the parser, analyzed by the semantic analyzer, and consumed by the code generator. Therefore, its definitions belong in our shared ast module.

Let’s create a new file, src/ast/nodes.rs, to house these new definitions.

touch src/ast/nodes.rs

Now, open this new file. We will define our AST structures from the largest construct (a program) down to the smallest (a literal value).

Defining the AST Nodes

Add the following code to your newly created src/ast/nodes.rs file. Each section is explained in detail below.

// src/ast/nodes.rs

use crate::ast::PrimitiveType;

/// The top-level node of the AST, representing a complete SimpliLang program.
/// A program is simply a collection of function definitions.
///
/// #[derive(...)] is a Rust attribute that asks the compiler to automatically
/// generate implementations for certain traits (behaviors).
/// - `Debug`: Allows us to print the AST for debugging (e.g., using `dbg!(my_ast);`).
/// - `PartialEq`: Allows us to compare two AST nodes for equality, which is essential for testing the parser.
/// - `Clone`: Allows us to create a deep copy of an AST node.
#[derive(Debug, PartialEq, Clone)]
pub struct Program {
    pub functions: Vec<FunctionDefinition>,
}

/// Represents a complete function definition.
/// e.g., `fn add(a: int, b: int) -> int { ... }`
#[derive(Debug, PartialEq, Clone)]
pub struct FunctionDefinition {
    pub name: String,
    pub parameters: Vec<(String, PrimitiveType)>,
    pub return_type: Option<PrimitiveType>,
    pub body: Block,
}

/// Represents a block of statements, enclosed in curly braces `{}`.
/// A block is essentially a list of statements.
#[derive(Debug, PartialEq, Clone)]
pub struct Block {
    pub statements: Vec<Stmt>,
}

/// Represents a statement. Statements do not produce values.
#[derive(Debug, PartialEq, Clone)]
pub enum Stmt {
    /// A `let` binding, e.g., `let x: int = 5;`
    Let {
        var_name: String,
        var_type: PrimitiveType,
        initializer: Expr,
    },
    /// A `return` statement, e.g., `return x + 1;`
    Return(Expr),
    /// An expression used as a statement, e.g., a function call: `my_func();`
    Expression(Expr),
}

/// Represents an expression. Expressions evaluate to a value.
#[derive(Debug, PartialEq, Clone)]
pub enum Expr {
    Literal(LiteralValue),
    Variable(String),
    Binary {
        op: BinaryOp,
        // `Box<T>` is a "smart pointer" that allocates memory on the heap.
        // We use it here because `Expr` is a recursive type. For the Rust
        // compiler to know the size of an `Expr` at compile time, we must
        // put the recursive parts behind a pointer (Box) which has a known size.
        left: Box<Expr>,
        right: Box<Expr>,
    },
    Unary {
        op: UnaryOp,
        operand: Box<Expr>,
    },
    If {
        condition: Box<Expr>,
        then_block: Block,
        // The `else` block is optional.
        else_block: Option<Block>,
    },
    FunctionCall {
        fn_name: String,
        arguments: Vec<Expr>,
    },
}

/// Represents a literal value like a number or a boolean.
#[derive(Debug, PartialEq, Clone)]
pub enum LiteralValue {
    Int(i64),
    Float(f64),
    Bool(bool),
}

/// Represents a binary operator (`+`, `*`, `==`, etc.).
#[derive(Debug, PartialEq, Clone, Copy)]
pub enum BinaryOp {
    Add,
    Subtract,
    Multiply,
    Divide,
    Equal,
    NotEqual,
    LessThan,
    GreaterThan,
}

/// Represents a unary operator (e.g., `-` for negation).
#[derive(Debug, PartialEq, Clone, Copy)]
pub enum UnaryOp {
    Negate,
}

Dissecting the AST Definitions

• Program: This is the root of our tree. It’s a simple struct that holds a Vec<FunctionDefinition>, perfectly matching our grammar rule program = { function_definition };.
• FunctionDefinition: This struct captures everything about a function: its name, a vector of parameters (as name-type pairs), an optional return type, and its body, which is a Block.
• Block: A block is simply a list of statements. We wrap this Vec<Stmt> in its own struct to make the AST more explicit and easier to work with.
• Stmt Enum: This enum represents the different kinds of statements. A let statement has a name, type, and initializer. A return statement has a value. An Expression statement just wraps an Expr (for cases like a function call that doesn’t return a value we care about, e.g., print();).
• Expr Enum: This is the most complex node and the heart of our AST. It’s an enum because an expression can take many forms:
  • Literal: A raw value.
  • Variable: A reference to a variable by its name.
  • Binary: The node for arithmetic and comparisons. It contains the operator and its left and right-hand sides.
  • The Box<Expr> Explained: This is a crucial Rust concept. An enum’s size must be known at compile time. If a variant like Binary contained Expr directly, the type would be infinitely recursive (Expr contains an Expr which contains an Expr…), and the compiler couldn’t determine its size. Box<T> solves this by storing the inner Expr on the heap and putting a pointer to it on the stack. The pointer has a known, fixed size, which satisfies the compiler and allows us to build our tree.
  • Unary: For operations like -5.
  • If: This directly models our if/else expression, including the optional else block.
  • FunctionCall: Captures the function’s name and a vector of argument expressions.
• Helper Enums: LiteralValue, BinaryOp, and UnaryOp are smaller, focused enums that make the Expr enum cleaner and more organized.

Integrating the New Nodes into the ast Module

Now that we’ve defined our AST nodes, we must make them available to the rest of the compiler. We do this by updating our ast module’s main file, src/ast/mod.rs.

Open src/ast/mod.rs and add the new module declaration and re-export line.

// src/ast/mod.rs

// This line declares a new public module named `types` based on the file `ast/types.rs`.
pub mod types;
// NEW: This line declares our new AST nodes module.
pub mod nodes;

// Re-export types like `PrimitiveType`.
pub use types::*;
// NEW: Re-export all our new AST node structs and enums.
pub use nodes::*;

With these definitions in place, you have created the entire data model for your language’s structure. You now have the “scaffolding” upon which the parser will build.

Next Steps

We have the blueprints for our AST nodes, but we don’t have a builder yet. The next task is to choose and set up the tool we will use to construct these nodes from our token stream. We will be using a powerful technique called parser-combinators and will set up the chumsky crate to help us build our parser in a declarative and robust way.

Further Reading

• Abstract Syntax Tree (Wikipedia): A high-level overview of the concept and its role in compilers.
  • https://en.wikipedia.org/wiki/Abstract_syntax_tree
• The Rust Programming Language - Enums: Revisit the official documentation on Rust’s powerful enums.
  • https://doc.rust-lang.org/book/ch06-01-defining-an-enum.html
• Using Box<T> to Point to Data on the Heap: The official book chapter explaining Box and its use in recursive types. This is a critical concept for our Expr enum.
  • https://doc.rust-lang.org/book/ch15-01-box.html

Integrate Chumsky and Set Up Parser Boilerplate

Mục tiêu: Add the ‘chumsky’ parser-combinator library as a dependency, create the necessary module files for the parser, and implement the initial boilerplate code. This task establishes the foundation for parsing a token stream into an Abstract Syntax Tree (AST).

---

In the last task, you masterfully laid out the entire blueprint for our language’s structure by defining the AST nodes. You have the Program, FunctionDefinition, Stmt, and Expr structs and enums ready. These are the “Lego bricks” of our language. Now, we need to build the “Lego master”—the code that knows how to read the instruction manual (our token stream) and assemble these bricks into a coherent structure. This master builder is our parser.

From a Flat Stream to a Hierarchical Tree: The Role of a Parser-Combinator

There are many ways to write a parser. A common approach is a “hand-written recursive descent parser,” which involves writing a series of mutually recursive functions. This is powerful but can be complex and error-prone. Another approach is using a “parser generator” (like ANTLR or Yacc), which generates Rust code from a separate grammar file. This can be fast, but adds another tool and a layer of indirection to your build process.

For SimpliLang, we will use a modern, powerful, and elegant approach that fits perfectly with Rust’s strengths: parser-combinators. The philosophy is simple and beautiful:

1. A parser is just a function (or, in Rust, a type that implements a Parser trait) that takes some input (our token stream) and tries to produce a piece of our AST.
2. You start by writing very small, simple parsers. For example, a parser that only succeeds if the next token is a let keyword.
3. You then use special functions called combinators to combine these simple parsers into more complex ones. For instance, you can “chain” a let keyword parser, an identifier parser, a colon parser, and so on, to create a parser for an entire let statement.

This approach is declarative, type-safe (it’s all just Rust code!), and allows for building incredibly sophisticated parsers from small, reusable pieces. For this, we’ll use one of the best parser-combinator libraries in the Rust ecosystem: chumsky. chumsky is particularly well-suited for our project because it is known for its excellent error recovery and reporting capabilities, which will be invaluable later on.

Our goal in this task is to get chumsky added to our project and to set up the basic boilerplate for our parser module.

Step 1: Add chumsky to Your Project

The first step is to tell cargo that our project now depends on the chumsky crate. Open your Cargo.toml file at the root of your project and add the following line under the [dependencies] section.

[dependencies]
inkwell = { version = "0.2.0", features = ["llvm15-0"] }
clap = { version = "4.4.18", features = ["derive"] }
# Add the chumsky crate below
chumsky = "0.9.3"

After saving the file, cargo will automatically download and compile chumsky the next time you build or run your project.

Step 2: Create the Parser Module

Just as we did for the lexer and ast, we need a dedicated home for our parser code. Create a new directory named parser inside your src directory.

mkdir src/parser

Inside this new src/parser directory, create two files: mod.rs to declare the module and parser.rs where our main parsing logic will live.

touch src/parser/mod.rs
touch src/parser/parser.rs

Step 3: Set Up the Parser Boilerplate

Now, let’s write the initial code that sets up the structure of our parser. This code won’t parse anything yet, but it will define the main entry point and the necessary types, preparing us for the tasks ahead.

First, open src/parser/parser.rs and add the following boilerplate code. This is the most important part of this task, so let’s break it down in detail.

// src/parser/parser.rs

// Import necessary items from chumsky and our own modules.
use chumsky::prelude::*;
use crate::ast::*; // AST nodes (Program, Stmt, Expr, etc.)
use crate::lexer::{Token, TokenKind}; // The Token and TokenKind from our lexer

/// The top-level function that parses a stream of tokens into a Program AST node.
///
/// This function will be the main entry point for the parsing stage.
/// It takes a Vec<Token> (the output from our lexer) and returns either a
/// complete `Program` AST or a vector of parsing errors.
pub fn parse(tokens: Vec<Token>) -> Result<Program, Vec<Simple<TokenKind>>> {
    // A placeholder parser function. In the upcoming tasks, we will build this
    // out to parse the entire SimpliLang grammar.
    fn program_parser() -> impl Parser<TokenKind, Program, Error = Simple<TokenKind>> {
        // For now, we'll use a placeholder parser that does nothing and always fails.
        // `chumsky::primitive::end()` is a parser that expects the end of input.
        // We `map` its output (which is nothing, `()`) to an empty `Program`.
        // This is just to satisfy the type checker for now.
        end().map(|_| Program { functions: vec![] })
    }

    // `chumsky` works with a `Stream` of tokens. We create one from our vector of tokens.
    // The `tokens.len()` is used to create a span for the end-of-input token.
    let stream = Stream::from_iter(tokens.len()..tokens.len() + 1, tokens.into_iter().map(|tok| tok.kind));

    // Try to parse the stream with our (currently placeholder) parser.
    program_parser().parse(stream)
}

Next, open src/parser/mod.rs to declare the parser.rs file as a module and re-export the public parse function.

// src/parser/mod.rs

// Declare the `parser` module, which corresponds to `parser.rs`.
pub mod parser;

// Re-export the public items from the `parser` module, namely our `parse` function.
pub use parser::*;

Dissecting the Boilerplate

This code sets up a lot of important infrastructure. Let’s understand each piece:

• use chumsky::prelude::*;: This line imports the most common and useful items from the chumsky crate, including the Parser trait and many essential combinators.
• The parse Function Signature:
  • pub fn parse(tokens: Vec<Token>) -> Result<Program, Vec<Simple<TokenKind>>>
  • This is our public API. It takes the vector of Tokens from the lexer.
  • It returns a Result. If parsing is successful, it gives us an Ok(Program). If there are errors, it gives us an Err containing a Vec of chumsky’s Simple error type. This error type is a default that’s easy to work with.
• The program_parser Function:
  • This is where we will build our grammar. We’ve defined it as a nested function for now, but we will soon expand it greatly.
  • The Return Type (impl Parser<...>): This is a key chumsky and Rust concept. The function returns “some type that implements the Parser trait”. This is extremely efficient because the compiler can figure out the exact, complex type of our combined parser at compile time without us having to write it out.
    • TokenKind: This is the Input type for our parser. It tells chumsky we are parsing a stream of TokenKind enums.
    • Program: This is the Output type. A successful parse by this parser will produce a Program AST node.
    • Error = Simple<TokenKind>: This specifies the error type the parser will generate.
• Creating the Stream:
  • chumsky doesn’t work on a Vec directly; it needs a Stream. The line Stream::from_iter(...) is the bridge.
  • Crucially, chumsky doesn’t care about our whole Token struct with its span. It only needs the TokenKind to make parsing decisions. So, we use .map(|tok| tok.kind) to transform our stream of Tokens into a stream of TokenKinds. We will re-associate the spans later when we build the AST nodes.
  • The first argument, tokens.len()..tokens.len() + 1, is a range used to create a Span for the end-of-input marker, which is required by chumsky.

You have now successfully set up the entire foundation for the parsing stage. You’ve integrated chumsky, created the module structure, and written the boilerplate that will serve as the entry point for turning a token stream into a meaningful AST.

Next Steps

With our parser module now set up with all the necessary boilerplate, our next step is to write our very first real parser. We will start small and build our way up. In the next task, you will replace the placeholder logic in program_parser with a parser that can recognize the simplest components of our language: literal values like 123, true, and 3.14.

Further Reading

• Chumsky Tutorial: The official chumsky documentation has an excellent tutorial that is highly recommended.
  • https://github.com/zesterer/chumsky/blob/master/tutorial.md
• What are Parser Combinators?: A gentle introduction to the concept.
  • https://bodil.lol/parser-combinators/
• Returning impl Trait in Rust: The official book chapter on this important Rust feature that chumsky uses extensively.
  • https://doc.rust-lang.org/book/ch10-02-traits.html#returning-types-that-implement-traits

Implement a Literal Parser with Chumsky

Mục tiêu: Write a Rust function using the chumsky crate to parse literal values (integers, floats, booleans). Use the select! macro to match literal tokens and transform them into Expr::Literal Abstract Syntax Tree (AST) nodes.

---

You’ve done an excellent job setting up the foundation for the parsing stage! With the chumsky crate integrated and the parser module boilerplate in place, you have a clear entry point (parse function) ready to receive a stream of tokens. That placeholder parser, however, doesn’t do anything useful yet. It’s time to replace it with real logic, starting with the most fundamental building blocks of our language.

Parsing from the Bottom Up: Literals

A parser’s job is to assemble a hierarchical AST from a flat stream of tokens. A great way to approach this is “bottom-up”—we’ll start by writing parsers for the smallest, most atomic parts of our grammar (the “leaves” of the AST) and then combine them to build parsers for larger constructs.

In SimpliLang, the most atomic value-producing expressions are literals: 123, 3.14, true, and false. Our first task is to write a parser that can recognize these literal tokens and transform them into the Expr::Literal AST node we defined in the previous step.

Introducing chumsky::select!

To recognize a specific kind of token, chumsky provides a powerful and intuitive macro: select!. It works almost exactly like Rust’s match statement, but instead of matching on a variable, it matches on the next token in the input stream. If the token matches one of the arms, the parser succeeds, consumes the token, and returns the value produced by the arm’s expression. If the token doesn’t match any arm, the parser fails.

This is the perfect tool for our literal parser. We can create a select! block that has an arm for TokenKind::Int, TokenKind::Float, and TokenKind::Bool.

Implementing the Literal Parser

Let’s modify our src/parser/parser.rs file. We will define our first real parser component inside the main parse function. For now, we are just creating this component; we will assemble all the components into a full program parser in later tasks.

Here are the changes for src/parser/parser.rs. Notice how we are adding a new parser function, literal_parser, and leaving the main program_parser as a placeholder for now.

// src/parser/parser.rs

use chumsky::prelude::*;
use crate::ast::*;
use crate::lexer::{Token, TokenKind};

pub fn parse(tokens: Vec<Token>) -> Result<Program, Vec<Simple<TokenKind>>> {
    /// Parses literal values (integers, floats, booleans) into an Expression AST node.
    /// This is our first and most basic parser building block.
    fn literal_parser() -> impl Parser<TokenKind, Expr, Error = Simple<TokenKind>> {
        // `select!` is chumsky's pattern-matching macro for tokens.
        // It's like a `match` statement for the token stream.
        select! {
            // If the next token is a `TokenKind::Int` containing a value `i`,
            // this arm matches. The `i` is captured...
            TokenKind::Int(i) => Expr::Literal(LiteralValue::Int(i)),
            // ...and we use it to construct our `Expr::Literal` AST node.

            // The same logic applies to floats.
            TokenKind::Float(f) => Expr::Literal(LiteralValue::Float(f)),

            // And to booleans.
            TokenKind::Bool(b) => Expr::Literal(LiteralValue::Bool(b)),
        }
    }

    /// The main parser for the entire program (still a placeholder).
    fn program_parser() -> impl Parser<TokenKind, Program, Error = Simple<TokenKind>> {
        // We've created our first parser component (`literal_parser`), but we haven't
        // used it yet. In the upcoming tasks, we will build more components
        // (for identifiers, let statements, etc.) and combine them here to parse
        // a full program.
        end().map(|_| Program { functions: vec![] })
    }

    let stream = Stream::from_iter(tokens.len()..tokens.len() + 1, tokens.into_iter().map(|tok| tok.kind));
    program_parser().parse(stream)
}

Code Breakdown

This is your first parser, so let’s analyze it carefully.

1. New Function literal_parser: We’ve encapsulated the logic for parsing literals into its own function. This is a core concept of parser-combinators: creating small, focused, and reusable parsers.
2. Parser Signature: The function returns impl Parser<TokenKind, Expr, ...>. This is very important. It declares that this is a parser that consumes TokenKinds and, upon success, produces an Expr AST node. This is exactly what we want—a literal is a type of expression.
3. select! { ... }: This is the heart of the implementation.
   • TokenKind::Int(i) => ...: This arm is a pattern. It tells chumsky, “I am looking for a token that is the Int variant of TokenKind.” The (i) part of the pattern is crucial; it binds the i64 value inside the token to the variable i.
   • Expr::Literal(LiteralValue::Int(i)): This is the expression that gets executed if the arm matches. We take the captured value i, wrap it first in our LiteralValue::Int enum, and then in our Expr::Literal enum variant. This directly transforms a token from the lexer into the corresponding AST node.
   • The arms for Float and Bool follow the exact same pattern, demonstrating how cleanly this approach maps tokens to AST nodes.

You have now successfully written your first parser component! You’ve created a piece of logic that can understand and structurally interpret the literal values in your SimpliLang source code. This literal_parser is a fundamental building block upon which we will construct our entire expression parser.

Next Steps

We’ve handled literals, which are one of the “atomic” types of expressions. The other primary atomic expression is a variable name, represented by an Identifier token. In the next task, you will write a parser for identifiers, which will recognize an identifier token and transform it into an Expr::Variable AST node.

Further Reading

• Chumsky Tutorial - Your First Parser: The official tutorial’s introduction to the select! macro and basic parsing.
  • https://github.com/zesterer/chumsky/blob/master/tutorial.md#your-first-parser
• Rust match Control Flow: Understanding Rust’s match is key to understanding chumsky’s select!. The patterns are very similar.
  • https://doc.rust-lang.org/book/ch06-02-match.html
• Terminal and Non-terminal Symbols: A concept from formal grammar theory. Literals are “terminal symbols”—they are the leaves of the grammar tree. Understanding this helps clarify why we start by parsing them first.
  • https://en.wikipedia.org/wiki/Terminal_and_nonterminal_symbols

Create a Parser for Identifiers

Mục tiêu: Implement a parser function using the Chumsky library in Rust to recognize identifier tokens and transform them into ‘Expr::Variable’ Abstract Syntax Tree (AST) nodes.

---

You have successfully created your first parser component, one that can recognize and structure literal values. This is a fantastic start! In that task, you parsed the “leaves” of our expression tree that are constant, known values. Now, we need to handle the other fundamental building block of expressions: variable names, or identifiers.

From Raw Values to Named References

When the parser sees a token like Identifier("score") in an expression (for instance, score + 10), this identifier doesn’t represent a value in itself. Instead, it’s a reference to a value that will be looked up later during semantic analysis or code generation. The parser’s job is to recognize this reference and create a distinct AST node that represents it.

This is precisely why we created the Expr::Variable(String) variant in our AST definition. It captures the idea of “using a variable’s value” in an expression. Our goal in this task is to create a new parser component, very similar to the literal_parser, that specifically recognizes Identifier tokens and transforms them into these Expr::Variable AST nodes.

Implementing the Identifier Parser

We will again use the powerful chumsky::select! macro. It is perfectly suited for this task, as it allows us to pattern match on the TokenKind and destructure it to extract the variable’s name.

Let’s update src/parser/parser.rs by adding a new identifier_parser function alongside the literal_parser you just created.

// src/parser/parser.rs

use chumsky::prelude::*;
use crate::ast::*;
use crate::lexer::{Token, TokenKind};

pub fn parse(tokens: Vec<Token>) -> Result<Program, Vec<Simple<TokenKind>>> {
    /// Parses literal values (integers, floats, booleans) into an Expression AST node.
    fn literal_parser() -> impl Parser<TokenKind, Expr, Error = Simple<TokenKind>> {
        select! {
            TokenKind::Int(i) => Expr::Literal(LiteralValue::Int(i)),
            TokenKind::Float(f) => Expr::Literal(LiteralValue::Float(f)),
            TokenKind::Bool(b) => Expr::Literal(LiteralValue::Bool(b)),
        }
    }

    /// Parses an identifier token into a variable expression AST node.
    /// This parser recognizes tokens that represent variable names.
    fn identifier_parser() -> impl Parser<TokenKind, Expr, Error = Simple<TokenKind>> {
        // We use `select!` again, but this time we look for the `Identifier` variant.
        select! {
            // The pattern `TokenKind::Identifier(name)` does two things:
            // 1. It ensures the parser only succeeds if the next token is an `Identifier`.
            // 2. It destructures the token, binding the `String` payload inside it to the `name` variable.
            TokenKind::Identifier(name) => Expr::Variable(name),
            // We then take this captured `name` and use it to construct our `Expr::Variable` AST node.
        }
    }

    /// The main parser for the entire program (still a placeholder).
    fn program_parser() -> impl Parser<TokenKind, Program, Error = Simple<TokenKind>> {
        // We now have two fundamental building blocks: `literal_parser` and `identifier_parser`.
        // The next step will be to combine them into a more powerful expression parser.
        end().map(|_| Program { functions: vec![] })
    }

    let stream = Stream::from_iter(tokens.len()..tokens.len() + 1, tokens.into_iter().map(|tok| tok.kind));
    program_parser().parse(stream)
}

Dissecting the New Parser

This new parser is small but mighty, and it perfectly illustrates the power of the parser-combinator approach:

1. A Focused Job: The identifier_parser function has one, and only one, responsibility: to parse an identifier token. This makes it easy to understand, test, and reason about.
2. Signature Consistency: Its signature, impl Parser<TokenKind, Expr, ...>, is identical to that of literal_parser. This is intentional and very important. Since both parsers produce an Expr AST node, they are interchangeable from the perspective of a “higher-level” parser. This allows us to easily combine them later.
3. Destructuring with select!: The pattern TokenKind::Identifier(name) is the key. It doesn’t just check for the right token kind; it also extracts the payload—the variable’s name as a String—and makes it available to us. We then immediately use that captured name to construct the Expr::Variable(name) AST node, completing the transformation from token to AST.

You have now successfully built the two fundamental “atomic” expression parsers. You can parse literals (raw values) and identifiers (references to values). These are the essential leaves of any expression tree.

Next Steps

We have parsers for 123 and for x, but we don’t yet have a way to parse x + 123. Our next major goal is to build a parser that can handle complex binary expressions (+, -, *, /, etc.) and correctly respect the operator precedence rules we designed (* and / bind more tightly than + and -).

To do this, you will learn how to use chumsky’s combinators to chain parsers together and build a sophisticated expression parser using a powerful technique known as Pratt parsing.

Further Reading

• Identifiers in Computer Science: A high-level overview of what identifiers are and their role in programming languages.
  • https://en.wikipedia.org/wiki/Identifier_(computer_languages)
• Chumsky Tutorial - A Choice of Parsers: The official tutorial’s section on the .or() combinator, which is the primary tool for combining parsers like the ones you’ve just built.
  • https://github.com/zesterer/chumsky/blob/master/tutorial.md#a-choice-of-parsers
• Expression Trees: A deeper dive into the concept of representing expressions as trees, which is exactly what our AST does.
  • https://en.wikipedia.org/wiki/Binary_expression_tree

Implement a Precedence-Climbing Expression Parser

Mục tiêu: Build a sophisticated expression parser in Rust using the chumsky library. This task involves implementing a precedence-climbing (Pratt) parser to correctly handle mathematical and comparison operators, respecting the order of operations to construct an accurate Abstract Syntax Tree (AST).

---

You’ve built the essential “atomic” parsers for literals and identifiers, which form the leaves of our Abstract Syntax Tree. This is a crucial foundation. However, a programming language isn’t just a collection of values and names; its power comes from combining them. Our next challenge is to parse complex expressions like score * 2 + 100, and to do so in a way that respects the mathematical order of operations.

The Challenge: Operator Precedence

A simple, left-to-right parser would see 5 + 2 * 10 and incorrectly parse it as (5 + 2) * 10, resulting in 70. Our language design, captured in our EBNF grammar, clearly states that multiplication has a higher precedence than addition. The parser must understand this hierarchy to build the correct AST, which should represent 5 + (2 * 10).

Manually implementing this logic can be complex and error-prone. Fortunately, chumsky provides a powerful, declarative API for parsing expressions that handles precedence elegantly. This is a practical implementation of a technique called Pratt Parsing. We will build our expression parser in layers, where each layer corresponds to a level of operator precedence.

Implementing a Precedence-Climbing Parser

We will create a new, sophisticated parser component called expression_parser. This will be the most complex parser we’ve built so far, but it’s composed of the same simple, combinable pieces you’re already familiar with.

Let’s modify src/parser/parser.rs to add this new, powerful parser. Add the following function alongside your existing literal_parser and identifier_parser.

// src/parser/parser.rs

// Add `Recursive` to our chumsky imports
use chumsky::recursive::Recursive;
use chumsky::prelude::*;
use crate::ast::*;
use crate::lexer::{Token, TokenKind};

// ... (The `parse`, `literal_parser`, and `identifier_parser` functions remain here)

pub fn parse(tokens: Vec<Token>) -> Result<Program, Vec<Simple<TokenKind>>> {
    // ... (`literal_parser` and `identifier_parser` are unchanged)
    fn literal_parser() -> impl Parser<TokenKind, Expr, Error = Simple<TokenKind>> { /* ... */ }
    fn identifier_parser() -> impl Parser<TokenKind, Expr, Error = Simple<TokenKind>> { /* ... */ }

    /// Parses a complete expression, handling operator precedence and associativity.
    fn expression_parser() -> impl Parser<TokenKind, Expr, Error = Simple<TokenKind>> {
        // `Recursive::declare` is used to create a parser that can refer to itself.
        // This is essential for parsing recursive structures like expressions, where
        // an expression can contain other expressions (e.g., in parentheses).
        Recursive::declare(|expr| {
            // "Atoms" are the highest-precedence expressions. These are the fundamental
            // building blocks that don't depend on operators.
            let atom = literal_parser()
                // Or an identifier (variable name).
                .or(identifier_parser())
                // Or a whole new expression enclosed in parentheses.
                // We `clone` the `expr` parser passed to us by `Recursive::declare`
                // to allow it to be used recursively here.
                .or(expr
                    .clone()
                    .delimited_by(just(TokenKind::LParen), just(TokenKind::RParen)));

            // Unary operators have the next highest precedence.
            // We parse one or more minus signs and apply them to the atom on the right.
            // `foldr` is used for right-associative operators like unary minus.
            let op = just(TokenKind::Minus).to(UnaryOp::Negate);
            let unary = op
                .repeated()
                .then(atom)
                .foldr(|op, rhs| Expr::Unary { op, operand: Box::new(rhs) });

            // Next up are multiplicative operators (*, /). They have higher precedence
            // than additive operators.
            let op = just(TokenKind::Star).to(BinaryOp::Multiply)
                .or(just(TokenKind::Slash).to(BinaryOp::Divide));
            // `foldl` is used for left-associative operators. It repeatedly parses
            // an operator and a right-hand-side operand (`unary` in this case) and
            // folds them into the left-hand side.
            let product = unary.clone().foldl(op.then(unary).repeated(), |lhs, (op, rhs)| {
                Expr::Binary {
                    left: Box::new(lhs),
                    op,
                    right: Box::new(rhs),
                }
            });

            // Additive operators (+, -) have lower precedence.
            // Notice that the operand for this layer is `product`, the parser for the
            // layer with higher precedence. This is how precedence is enforced.
            let op = just(TokenKind::Plus).to(BinaryOp::Add)
                .or(just(TokenKind::Minus).to(BinaryOp::Subtract));
            let sum = product.clone().foldl(op.then(product).repeated(), |lhs, (op, rhs)| {
                Expr::Binary {
                    left: Box::new(lhs),
                    op,
                    right: Box::new(rhs),
                }
            });

            // Finally, comparison operators, with the lowest precedence.
            // According to our design, these are non-associative, meaning `a < b < c` is invalid.
            // We handle this by parsing a `sum`, and then optionally parsing ONE operator and another `sum`.
            let op = just(TokenKind::Equal).to(BinaryOp::Equal)
                .or(just(TokenKind::BangEqual).to(BinaryOp::NotEqual))
                .or(just(TokenKind::Less).to(BinaryOp::LessThan))
                .or(just(TokenKind::Greater).to(BinaryOp::GreaterThan));
            sum.clone().then(op.then(sum).or_not()).map(|(lhs, rhs_opt)| {
                if let Some((op, rhs)) = rhs_opt {
                    Expr::Binary {
                        left: Box::new(lhs),
                        op,
                        right: Box::new(rhs),
                    }
                } else {
                    lhs
                }
            })
        })
    }

    /// The main parser for the entire program (still a placeholder).
    fn program_parser() -> impl Parser<TokenKind, Program, Error = Simple<TokenKind>> {
        // Our expression parser is now a powerful building block, ready to be used
        // by statement parsers (like `let` and `return`) in the upcoming tasks.
        end().map(|_| Program { functions: vec![] })
    }

    let stream = Stream::from_iter(tokens.len()..tokens.len() + 1, tokens.into_iter().map(|tok| tok.kind));
    program_parser().parse(stream)
}

Dissecting the Expression Parser

This new function is dense with powerful concepts. Let’s break it down layer by layer.

Recursive::declare(|expr| ...)

An expression is a recursive data structure: an expression can contain other expressions. For example, in (5 + 2) * 10, the parentheses contain the expression 5 + 2. To define a parser for a recursive structure, we need a way for the parser to refer to itself. Recursive::declare is chumsky’s tool for this. It gives us a handle, which we’ve named expr, that represents the entire parser we are in the process of defining. We can then use this handle inside our definition.

atom Parser: The Base Case

This is the foundation of our expression parser, defining the highest-precedence elements that don’t involve operators:

• literal_parser(): Parses 123, true, etc.
• .or(identifier_parser()): We use the .or() combinator to say, “If it’s not a literal, try parsing it as an identifier.”
• .or(expr.clone().delimited_by(...)): This is the recursive part. It says, “Or, try to parse a full expression (expr) that is enclosed by ( and ). This handles parenthesized expressions, allowing us to override the default precedence.

unary Parser: Handling Prefixes

This layer handles the unary negation operator (-).

• just(TokenKind::Minus).to(UnaryOp::Negate): A simple parser that recognizes a - token and converts it into our UnaryOp::Negate AST enum.
• .repeated(): This allows for multiple unary operators, like in let x = --5; (which would be a double negation).
• .then(atom): It looks for these operators before an atom.
• .foldr(...): We use foldr because unary operators are right-associative. In - -5, the rightmost - binds to the 5 first. The r in foldr stands for “right”.

The Precedence Chain: product, sum, and comparison

This is the heart of our precedence logic.

• product (Multiplication/Division): This parser uses the unary parser as its operand. It uses .foldl() because * and / are left-associative. In 10 / 2 * 5, the 10 / 2 is evaluated first. The l in foldl stands for “left”.
• sum (Addition/Subtraction): This parser’s key feature is that it uses the product parser as its operand. This is how precedence is enforced. It will only look for + or - after it has parsed a complete, higher-precedence product expression.
• comparison (Comparisons): This is the final layer with the lowest precedence. It takes a sum as its operand. As our comparisons are non-associative, we can’t use foldl. Instead, the pattern .then(op.then(sum).or_not()) ensures we parse a left-hand side, followed by at most one comparison operator and a right-hand side.

You have just built the most complex and powerful component of our parser. This single function can now take a flat stream of tokens and build a correctly structured AST for any mathematical or comparison expression, perfectly respecting the rules of precedence and associativity you designed for SimpliLang.

Next Steps

With a robust expression parser in hand, you are now ready to parse the constructs that use expressions. The next logical step is to write a parser for let statements. This new parser will combine parsers for keywords and types with the powerful expression_parser you’ve just built to handle the variable’s initializer.

Further Reading

• Pratt Parsing: Expression Parsing Made Easy: A classic and highly recommended article that explains the theory behind the parsing strategy we’ve implemented.
  • https://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/
• Chumsky Tutorial - A Simple Expression Parser: The official tutorial’s section on this exact topic. It’s a great resource to reinforce these concepts.
  • https://github.com/zesterer/chumsky/blob/master/tutorial.md#a-simple-expression-parser
• The Recursive Combinator in Chumsky: The official documentation for chumsky’s recursive parsing utility.
  • https://docs.rs/chumsky/latest/chumsky/recursive/fn.recursive.html (Note: Recursive::declare is a newer, often preferred API).

Implement the Parser for let Statements

Mục tiêu: Create a parser for let statements in a custom programming language using the Rust chumsky library. This task involves combining smaller, simpler parsers to recognize the specific sequence of tokens for a variable declaration (let : = ;) and transform the parsed components into an Abstract Syntax Tree (AST) node.

---

You have accomplished one of the most challenging parts of writing a parser: building a robust, precedence-aware expression parser. With the expression_parser complete, you have a powerful component that can understand any mathematical or comparison expression in SimpliLang. Now, we can leverage this power to parse the larger language constructs that contain expressions. The most fundamental of these is the let statement, used for variable declarations.

From Expressions to Statements: Parsing Sequences

A let statement, as we designed it, has a very specific and rigid structure: let <identifier>: <type> = <expression>;. The parser’s job is to verify that a sequence of tokens follows this exact pattern. This is a perfect demonstration of the “combinator” aspect of parser-combinators. We will combine several small, simple parsers in a specific sequence to create a single, larger parser for the entire let statement.

The sequence we need to parse is:

1. The let keyword.
2. An identifier for the variable’s name.
3. A colon (:).
4. An identifier for the variable’s type (e.g., “int”).
5. An equals sign (=).
6. A complete expression (which we can now parse using expression_parser!).
7. A semicolon (;).

chumsky provides intuitive combinators to chain parsers together. We will use just to match specific keywords and punctuation, select! to extract data from tokens, and combinators like .ignore_then() and .then() to build our sequence.

Implementing the let Statement Parser

Let’s add a new function, let_statement_parser, to src/parser/parser.rs. This new component will be responsible for recognizing the let statement pattern and constructing a Stmt::Let AST node from the parsed pieces.

Here is the updated code for src/parser/parser.rs. We’ll add our new parser function and prepare to integrate it into a larger statement parser later.

// src/parser/parser.rs

// (imports and other parser functions are unchanged)
use chumsky::recursive::Recursive;
use chumsky::prelude::*;
use crate::ast::*;
use crate::lexer::{Token, TokenKind};

pub fn parse(tokens: Vec<Token>) -> Result<Program, Vec<Simple<TokenKind>>> {
    // (literal_parser, identifier_parser, and expression_parser are unchanged)
    fn literal_parser() -> impl Parser<TokenKind, Expr, Error = Simple<TokenKind>> { /* ... */ }
    fn identifier_parser() -> impl Parser<TokenKind, Expr, Error = Simple<TokenKind>> { /* ... */ }
    fn expression_parser() -> impl Parser<TokenKind, Expr, Error = Simple<TokenKind>> { /* ... */ }

    /// Parses a `let` statement, e.g., `let x: int = 5;`
    fn let_statement_parser() -> impl Parser<TokenKind, Stmt, Error = Simple<TokenKind>> {
        // A parser for an identifier string.
        // We use `select!` to pattern match and extract the string from the token.
        let ident = select! { TokenKind::Identifier(s) => s };

        // A parser for a type annotation (e.g., "int", "float").
        // We match on an identifier token but then convert the string to our `PrimitiveType` enum.
        let type_annotation = select! {
            TokenKind::Identifier(s) if s == "int" => PrimitiveType::Int,
            TokenKind::Identifier(s) if s == "float" => PrimitiveType::Float,
            TokenKind::Identifier(s) if s == "bool" => PrimitiveType::Bool,
        };

        // Now, we combine the small parsers into a sequence.
        // `just` is used for matching specific tokens like keywords and punctuation.
        just(TokenKind::Let)
            // `.ignore_then(...)` parses something but discards its result,
            // then continues with the next parser. Perfect for keywords.
            .ignore_then(ident)
            // `.then_ignore(...)` is the reverse: it parses something, keeps its result,
            // and then parses and discards the next part. Perfect for punctuation.
            .then_ignore(just(TokenKind::Colon))
            // `.then(...)` is the core sequencing combinator. It parses the first part,
            // then the second, and returns both as a tuple.
            .then(type_annotation)
            .then_ignore(just(TokenKind::Assign))
            // Here is where we reuse our powerful expression parser!
            .then(expression_parser())
            .then_ignore(just(TokenKind::Semicolon))
            // Finally, we use `.map()` to transform the nested tuple of parsed results
            // into our desired `Stmt::Let` AST node.
            .map(|((var_name, var_type), initializer)| Stmt::Let {
                var_name,
                var_type,
                initializer,
            })
    }

    /// The main parser for the entire program (still a placeholder).
    fn program_parser() -> impl Parser<TokenKind, Program, Error = Simple<TokenKind>> {
        // We now have a statement parser (`let_statement_parser`). We will soon
        // combine it with others to parse a full block of statements.
        end().map(|_| Program { functions: vec![] })
    }

    // (stream creation and final parse call are unchanged)
    let stream = Stream::from_iter(tokens.len()..tokens.len() + 1, tokens.into_iter().map(|tok| tok.kind));
    program_parser().parse(stream)
}

Dissecting the let Parser

This parser is a beautiful example of the declarative nature of parser-combinators. We’ve described the what (the sequence of tokens) and let chumsky handle the how (the underlying state machine).

1. Helper Parsers (ident, type_annotation): We first define two small, reusable parsers. ident simply extracts the String from an Identifier token. type_annotation is smarter; it matches specific identifier strings (“int”, “float”, “bool”) and transforms them into our PrimitiveType enum. If it sees an identifier that is not one of these, the parser will fail, correctly rejecting an invalid type name.

2. The Parser Chain: The core of the function is the chain of combinator calls.

   • just(TokenKind::Let).ignore_then(ident): This says, “Expect a let token, throw it away, then expect an identifier and keep the name.”
   • .then_ignore(just(TokenKind::Colon)): “Then, expect a colon and throw it away.”
   • .then(type_annotation): “Then, expect a type annotation and keep the result.”
   • This pattern continues, perfectly mirroring the grammatical structure. We keep the pieces we need for the AST node (the name, the type, the initializer expression) and discard the syntactic sugar (the keywords and punctuation).
3. The .map() Transformation: After the sequence is successfully parsed, chumsky gives us the results of all the parsers we didn’t ignore, neatly bundled into a nested tuple. The structure of the tuple directly reflects the structure of our .then() calls: ((var_name, var_type), initializer). The .map() combinator allows us to provide a closure that takes this tuple, destructures it into named variables, and uses them to construct our final Stmt::Let AST node. This is the final step that transforms the parsed pieces into a meaningful part of our AST.

You have now successfully created a parser that can understand one of the core statements of SimpliLang. By combining your atomic parsers and your powerful expression parser, you are rapidly building up the capability to parse the entire language.

Next Steps

We’ve parsed expressions and now a let statement. The next logical step, following our language design and task list, is to parse another construct that heavily relies on expressions: the if/else expression. In the next task, you will build a parser that recognizes the if <condition> { ... } else { ... } structure.

Further Reading

• Chumsky Tutorial - A Sequence of Parsers: The official tutorial’s section on sequencing with .then and its variants.
  • https://github.com/zesterer/chumsky/blob/master/tutorial.md#a-sequence-of-parsers
• Tuple Destructuring in Rust: Understanding how to break apart tuples is key to using the .map() combinator effectively.
  • https://doc.rust-lang.org/book/ch03-02-data-types.html#the-tuple-type
• The .map() Combinator: Official documentation for this fundamental combinator.
  • https://docs.rs/chumsky/latest/chumsky/trait.Parser.html#method.map

Implement If/Else Expression Parser

Mục tiêu: Refactor the Rust parser to support if/else expressions. This involves defining parsers for statements and blocks within a mutually recursive structure using the chumsky library and integrating the if expression into the existing precedence-climbing grammar.

---

Fantastic work on building the let statement parser! You’ve mastered the art of sequencing simple parsers to recognize a complete grammatical construct. The logic you used there—combining parsers for keywords, identifiers, and expressions in a specific order—is a fundamental skill that we will now apply to another core feature of SimpliLang: the if/else expression.

In SimpliLang, if is not just a statement that directs control flow; it’s a powerful expression that evaluates to a value. However, an if expression is unique because it contains blocks of statements. This creates a fascinating and common challenge in parsing: mutual recursion.

• An if expression contains a block.
• A block contains statements.
• A statement can be an expression (like a function call), which in turn can be an if expression.

This cycle, expression -> block -> statement -> expression, means these parsers are all interdependent. To solve this elegantly, we will define all of these mutually recursive components together within the Recursive::declare block you’ve already set up for the expression parser. This allows each parser to have access to the others, creating a cohesive and powerful parsing grammar.

Implementing the if/else Expression Parser

We will now refactor your src/parser/parser.rs file. The core logic of your expression parser’s precedence climbing will remain the same, but we will add the definitions for statements, blocks, and the if expression itself inside the Recursive::declare closure, and then integrate the if parser into the atom parser.

This is a larger change, but it results in a very clean and correct structure.

// src/parser/parser.rs

use chumsky::recursive::Recursive;
use chumsky::prelude::*;\nuse crate::ast::*;\nuse crate::lexer::{Token, TokenKind};

pub fn parse(tokens: Vec<Token>) -> Result<Program, Vec<Simple<TokenKind>>> {
    // literal_parser and identifier_parser remain unchanged.
    fn literal_parser() -> impl Parser<TokenKind, Expr, Error = Simple<TokenKind>> { /* ... */ }
    fn identifier_parser() -> impl Parser<TokenKind, Expr, Error = Simple<TokenKind>> { /* ... */ }

    // Our expression parser now becomes the home for all mutually recursive parsing logic.
    fn expression_parser() -> impl Parser<TokenKind, Expr, Error = Simple<TokenKind>> {
        Recursive::declare(|expr| {
            // First, let's define parsers for the different kinds of statements.
            // These will need access to the `expr` parser we are defining.

            let ident = select! { TokenKind::Identifier(s) => s };

            let type_annotation = select! {
                TokenKind::Identifier(s) if s == "int" => PrimitiveType::Int,
                TokenKind::Identifier(s) if s == "float" => PrimitiveType::Float,
                TokenKind::Identifier(s) if s == "bool" => PrimitiveType::Bool,
            };

            let let_stmt = just(TokenKind::Let)
                .ignore_then(ident)
                .then_ignore(just(TokenKind::Colon))
                .then(type_annotation)
                .then_ignore(just(TokenKind::Assign))
                .then(expr.clone()) // Use the recursive `expr` parser here
                .then_ignore(just(TokenKind::Semicolon))
                .map(|((var_name, var_type), initializer)| Stmt::Let {
                    var_name,
                    var_type,
                    initializer,
                });

            let return_stmt = just(TokenKind::Return)
                .ignore_then(expr.clone())
                .then_ignore(just(TokenKind::Semicolon))
                .map(Stmt::Return);

            let expr_stmt = expr.clone()
                .then_ignore(just(TokenKind::Semicolon))
                .map(Stmt::Expression);

            // A statement is either a `let`, a `return`, or an expression statement.
            let statement = let_stmt.or(return_stmt).or(expr_stmt);

            // A block is a sequence of statements enclosed in curly braces.
            let block = statement
                .repeated()
                .delimited_by(just(TokenKind::LBrace), just(TokenKind::RBrace))
                .map(|statements| Block { statements });

            // Now, we can define the `if` expression parser.
            let if_expr = just(TokenKind::If)
                .ignore_then(expr.clone()) // The condition
                .then(block.clone())       // The 'then' block
                // The 'else' block is optional. `.or_not()` handles this perfectly.
                .then(just(TokenKind::Else).ignore_then(block.clone()).or_not())
                .map(|((condition, then_block), else_block)| Expr::If {
                    condition: Box::new(condition),
                    then_block,
                    else_block,
                });

            // "Atoms" are the highest-precedence expressions.
            // We now add the `if_expr` parser to this list.
            let atom = literal_parser()
                .or(identifier_parser())
                .or(if_expr) // NEW: An 'if' expression is a valid atom.
                .or(expr
                    .clone()
                    .delimited_by(just(TokenKind::LParen), just(TokenKind::RParen)));

            // The rest of the precedence-climbing logic remains exactly the same as before.
            // ... (unary, product, sum, comparison layers)
            let op = just(TokenKind::Minus).to(UnaryOp::Negate);
            let unary = op.repeated().then(atom).foldr(|op, rhs| Expr::Unary { op, operand: Box::new(rhs) });

            let op = just(TokenKind::Star).to(BinaryOp::Multiply).or(just(TokenKind::Slash).to(BinaryOp::Divide));
            let product = unary.clone().foldl(op.then(unary).repeated(), |lhs, (op, rhs)| {
                Expr::Binary { left: Box::new(lhs), op, right: Box::new(rhs) }
            });

            let op = just(TokenKind::Plus).to(BinaryOp::Add).or(just(TokenKind::Minus).to(BinaryOp::Subtract));
            let sum = product.clone().foldl(op.then(product).repeated(), |lhs, (op, rhs)| {
                Expr::Binary { left: Box::new(lhs), op, right: Box::new(rhs) }
            });

            let op = just(TokenKind::Equal).to(BinaryOp::Equal)
                .or(just(TokenKind::BangEqual).to(BinaryOp::NotEqual))
                .or(just(TokenKind::Less).to(BinaryOp::LessThan))
                .or(just(TokenKind::Greater).to(BinaryOp::GreaterThan));
            sum.clone().then(op.then(sum).or_not()).map(|(lhs, rhs_opt)| {
                if let Some((op, rhs)) = rhs_opt {
                    Expr::Binary { left: Box::new(lhs), op, right: Box::new(rhs) }
                } else {
                    lhs
                }
            })
        })
    }

    /// The main parser for the entire program (still a placeholder).
    fn program_parser() -> impl Parser<TokenKind, Program, Error = Simple<TokenKind>> {
        end().map(|_| Program { functions: vec![] })
    }

    let stream = Stream::from_iter(tokens.len()..tokens.len() + 1, tokens.into_iter().map(|tok| tok.kind));
    program_parser().parse(stream)
}

Dissecting the New Architecture

Let’s break down the new components you’ve just added inside the expression_parser’s recursive declaration:

1. Statement Parsers:

   • We moved the let_statement_parser logic inside and updated it to use the recursive expr handle for its initializer.
   • We added two new simple statement parsers:
     • return_stmt: Parses a return keyword, followed by an expression, and terminated by a semicolon.
     • expr_stmt: Parses any valid expression that is followed by a semicolon. This is for standalone function calls like print_hello();.
   • statement: This parser uses the .or() combinator to define a statement as “either a let statement, OR a return statement, OR an expression statement.”

2. The block_parser:

   • This is a crucial new component. It takes our statement parser and uses the .repeated() combinator to parse zero or more statements in a row.
   • .delimited_by(just(LBrace), just(RBrace)): This combinator then ensures that this sequence of statements is wrapped in { and }. It consumes the braces and returns the Vec<Stmt> produced by .repeated().
   • Finally, .map() wraps this vector into our Block AST struct.

3. The if_expression_parser:

   • This parser beautifully demonstrates sequential parsing:
   • It starts with just(TokenKind::If).
   • It’s followed by the condition, for which we use expr.clone().
   • Next is the “then” block, which we parse using block.clone().
   • The else part is handled by .then(just(Else).ignore_then(block.clone()).or_not()). The .or_not() combinator is the key; it tries to parse an else and a block, and if it fails, it succeeds with a None value instead of a parsing error. This perfectly models our optional else.
   • The final .map() takes the resulting tuple ((condition, then_block), else_block_option) and neatly constructs the Expr::If AST node.

4. Integration into atom:

   • The final, critical change is adding .or(if_expr) to the atom parser’s chain. This officially registers the if expression as a high-precedence “atomic” unit within our expression grammar. This means you can use an if expression anywhere any other value is expected, for example: let x: int = 5 + if a > b { a } else { b };.

You have now dramatically expanded your parser’s capabilities. It not only understands complex mathematical expressions but can also parse statements and the blocks of code that form the bodies of control-flow constructs.

Next Steps

With expressions, statements, and blocks fully handled, you are ready to tackle the larger structural elements of a SimpliLang program. The next logical tasks are to build parsers for function definitions (fn ...) and function calls (my_func(...)), which will allow you to parse complete, reusable units of code.

Further Reading

• Chumsky Tutorial - Let’s Parse a Language: The official tutorial builds a language with a very similar structure. Its section on parsing statements and blocks is excellent for reinforcement.
  • https://github.com/zesterer/chumsky/blob/master/tutorial.md#lets-parse-a-language
• Statements vs. Expressions in Rust: SimpliLang’s design (where if is an expression) is heavily inspired by Rust. Understanding this distinction in Rust will deepen your understanding of your own language’s design.
  • https://doc.rust-lang.org/reference/statements.html
• The .or_not() Combinator: Official documentation for this useful combinator for parsing optional elements.
  • https://docs.rs/chumsky/latest/chumsky/trait.Parser.html#method.or_not

Extend Parser for Function Definitions and Calls

Mục tiêu: Update the chumsky-based parser in Rust to recognize and parse function definitions as top-level statements and function calls as atomic expressions. This involves handling grammar ambiguity between variable access and function calls using ordered choice, and structuring the top-level program parser to consume a sequence of function definitions.

---

In the previous task, you performed a brilliant and essential refactoring, structuring your parser to handle the mutual recursion between expressions, statements, and blocks. This architecture, with all interdependent parsers defined within a single Recursive::declare block, has set us up perfectly for this next task: parsing the primary units of code organization and reuse in SimpliLang—function definitions and function calls.

A function call is a type of expression, while a function definition is a top-level statement. We will tackle both, leveraging the powerful components you’ve already built.

Parsing Function Calls: An Atomic Expression

A function call, like my_func(arg1, arg2), is an “atomic” unit in our expression grammar. It has very high precedence, just like a literal, a variable, or a parenthesized expression. Therefore, the logical place to add its parser is within our atom parser.

The main challenge here is ambiguity. When the parser sees an identifier like value, it could be a simple variable access, or it could be the start of a function call, value(). The key distinguishing feature is the opening parenthesis (. We will create a parser that recognizes an identifier and then looks ahead for a (. If it finds one, it proceeds to parse the argument list; otherwise, it treats it as a simple variable access.

Parsing Function Definitions: The Top-Level Structure

A function definition, like fn add(...) -> int { ... }, is a top-level item. A SimpliLang program is, at its core, simply a list of these definitions. We will create a new parser that recognizes the fn keyword and all the subsequent parts: the name, the parameter list, the optional return type, and the function body (which we can parse using the block parser you’ve already created!).

Let’s update src/parser/parser.rs with this new logic. The changes are concentrated inside the expression_parser’s recursive block and the final program_parser.

// src/parser/parser.rs

use chumsky::recursive::Recursive;
use chumsky::prelude::*;
use crate::ast::*;
use crate::lexer::{Token, TokenKind};

pub fn parse(tokens: Vec<Token>) -> Result<Program, Vec<Simple<TokenKind>>> {
    // literal_parser is unchanged.
    fn literal_parser() -> impl Parser<TokenKind, Expr, Error = Simple<TokenKind>> {
        select! {
            TokenKind::Int(i) => Expr::Literal(LiteralValue::Int(i)),
            TokenKind::Float(f) => Expr::Literal(LiteralValue::Float(f)),
            TokenKind::Bool(b) => Expr::Literal(LiteralValue::Bool(b)),
        }
    }

    // This large recursive block now defines our entire language grammar, from expressions up to statements.
    fn language_grammar_parser() -> (
        impl Parser<TokenKind, Expr, Error = Simple<TokenKind>>,
        impl Parser<TokenKind, FunctionDefinition, Error = Simple<TokenKind>>
    ) {
        // We use `Recursive::declare` for all mutually recursive parsers.
        let mut expr = Recursive::declare();
        let mut block = Recursive::declare();
        let mut function_def = Recursive::declare();

        // --- Core Building Blocks ---

        let ident = select! { TokenKind::Identifier(s) => s };

        let type_annotation = select! {
            TokenKind::Identifier(s) if s == "int" => PrimitiveType::Int,
            TokenKind::Identifier(s) if s == "float" => PrimitiveType::Float,
            TokenKind::Identifier(s) if s == "bool" => PrimitiveType::Bool,
        };

        // --- Statement Parsers (as before) ---

        let let_stmt = just(TokenKind::Let)
            // ... (rest of let_stmt is unchanged)
            .ignore_then(ident)
            .then_ignore(just(TokenKind::Colon))
            .then(type_annotation.clone())
            .then_ignore(just(TokenKind::Assign))
            .then(expr.clone())
            .then_ignore(just(TokenKind::Semicolon))
            .map(|((var_name, var_type), initializer)| Stmt::Let { var_name, var_type, initializer });

        let return_stmt = just(TokenKind::Return)
            .ignore_then(expr.clone())
            .then_ignore(just(TokenKind::Semicolon))
            .map(Stmt::Return);

        let expr_stmt = expr.clone()
            .then_ignore(just(TokenKind::Semicolon))
            .map(Stmt::Expression);

        let statement = let_stmt.or(return_stmt).or(expr_stmt);

        // --- Block Parser (as before) ---
        // We define the block parser using the `block` recursive handle.
        block.define(
            statement
                .repeated()
                .delimited_by(just(TokenKind::LBrace), just(TokenKind::RBrace))
                .map(|statements| Block { statements })
        );

        // --- Expression Parsers (with Function Calls added) ---

        let if_expr = just(TokenKind::If)
            // ... (rest of if_expr is unchanged)
            .ignore_then(expr.clone())
            .then(block.clone())
            .then(just(TokenKind::Else).ignore_then(block.clone()).or_not())
            .map(|((condition, then_block), else_block)| Expr::If {
                condition: Box::new(condition),
                then_block,
                else_block,
            });

        // NEW: Parser for function calls
        let function_call = ident
            // An argument list is a comma-separated list of expressions, inside parentheses.
            .then(
                expr.clone()
                    .separated_by(just(TokenKind::Comma))
                    .allow_trailing() // Allow an optional trailing comma
                    .delimited_by(just(TokenKind::LParen), just(TokenKind::RParen))
            )
            .map(|(fn_name, arguments)| Expr::FunctionCall { fn_name, arguments });

        let atom = literal_parser()
            // IMPORTANT: A function call must be tried BEFORE a simple identifier,
            // because `function_call` also starts with an identifier. This is called
            // "ordered choice".
            .or(function_call)
            // A simple variable access (identifier).
            .or(ident.map(Expr::Variable))
            .or(if_expr)
            .or(expr.clone().delimited_by(just(TokenKind::LParen), just(TokenKind::RParen)));

        // Precedence climbing logic for operators is unchanged
        let op = just(TokenKind::Minus).to(UnaryOp::Negate);
        let unary = op.repeated().then(atom).foldr(|op, rhs| Expr::Unary { op, operand: Box::new(rhs) });
        // ... (product, sum, comparison layers are the same)
        let op = just(TokenKind::Star).to(BinaryOp::Multiply).or(just(TokenKind::Slash).to(BinaryOp::Divide));
        let product = unary.clone().foldl(op.then(unary).repeated(), |lhs, (op, rhs)| Expr::Binary { left: Box::new(lhs), op, right: Box::new(rhs) });
        let op = just(TokenKind::Plus).to(BinaryOp::Add).or(just(TokenKind::Minus).to(BinaryOp::Subtract));
        let sum = product.clone().foldl(op.then(product).repeated(), |lhs, (op, rhs)| Expr::Binary { left: Box::new(lhs), op, right: Box::new(rhs) });
        let op = just(TokenKind::Equal).to(BinaryOp::Equal).or(just(TokenKind::BangEqual).to(BinaryOp::NotEqual)).or(just(TokenKind::Less).to(BinaryOp::LessThan)).or(just(TokenKind::Greater).to(BinaryOp::GreaterThan));
        let comparison = sum.clone().then(op.then(sum).or_not()).map(|(lhs, rhs_opt)| {
            if let Some((op, rhs)) = rhs_opt { Expr::Binary { left: Box::new(lhs), op, right: Box::new(rhs) } } else { lhs }
        });

        // We define the expression parser using the `expr` recursive handle.
        expr.define(comparison);

        // --- NEW: Function Definition Parser ---

        // A parameter is an `identifier: type` pair.
        let parameter = ident.clone().then_ignore(just(TokenKind::Colon)).then(type_annotation);

        let function_definition_parser = just(TokenKind::Fn)
            .ignore_then(ident) // Function name
            .then( // Parameter list
                parameter
                    .separated_by(just(TokenKind::Comma))
                    .allow_trailing()
                    .delimited_by(just(TokenKind::LParen), just(TokenKind::RParen))
            )
            .then( // Optional return type
                just(TokenKind::Arrow)
                    .ignore_then(type_annotation)
                    .or_not()
            )
            .then(block.clone()) // Function body
            .map(|(((name, parameters), return_type), body)| FunctionDefinition {
                name,
                parameters,
                return_type,
                body,
            });

        // We define the top-level function definition parser using its handle
        function_def.define(function_definition_parser);

        (expr, function_def)
    }

    /// The main parser for the entire program.
    fn program_parser() -> impl Parser<TokenKind, Program, Error = Simple<TokenKind>> {
        // Get the expression and function definition parsers from our grammar definition.
        let (_expr_parser, function_def_parser) = language_grammar_parser();

        // A program is a sequence of zero or more function definitions,
        // followed by the end of the input.
        function_def_parser
            .repeated()
            .then_ignore(end())
            .map(|functions| Program { functions })
    }

    let stream = Stream::from_iter(tokens.len()..tokens.len() + 1, tokens.into_iter().map(|tok| tok.kind));
    program_parser().parse(stream)
}

Dissecting the Architecture

This is a significant update that completes the core of our parser’s grammar.

1. Refactored Recursive Setup: Instead of one large Recursive::declare, we now have a language_grammar_parser function that sets up several recursive handles (expr, block, function_def). This is a cleaner pattern for larger grammars where multiple components might refer to each other. We .define() each parser on its handle after it has been fully built.

2. The function_call Parser:

   • expr.clone().separated_by(just(TokenKind::Comma)): This is a powerful chumsky combinator. It parses one or more expressions, separated by commas, and collects the results into a Vec<Expr>.
   • .allow_trailing(): A quality-of-life feature that allows a comma after the last argument, a common practice in modern languages.
   • .delimited_by(...): This ensures the argument list is enclosed in parentheses.
   • Ordered Choice: The line ...or(function_call).or(ident.map(Expr::Variable))... is critical. Because both a function call and a variable access start with an identifier, we must try to parse the more specific pattern (function_call) first. If that fails, the parser backtracks and tries the simpler identifier parser. This is a fundamental concept called “ordered choice”.

3. The function_definition_parser:

   • This is another beautiful example of a sequential parser built from smaller, reusable pieces (ident, parameter, type_annotation, block).
   • The parameter parser is a small, focused component for name: type pairs.
   • .or_not() is used again to elegantly handle the optional return type (-> <type>).

4. The program_parser (Final Version):

   • This function is no longer a placeholder! It now defines a complete SimpliLang program.
   • It uses our new function_definition_parser with the .repeated() combinator to parse a sequence of functions.
   • .then_ignore(end()) is a crucial final step. It ensures that after parsing all the functions, we have reached the end of the token stream. This would catch syntax errors where there is trailing garbage after the last valid function.
   • The final .map() collects the Vec<FunctionDefinition> and wraps it in our top-level Program AST node.

You have now built a complete and robust parser for the entire core syntax of SimpliLang! Every construct you designed, from the smallest literal to a full function definition, can now be transformed from a flat token stream into a rich, hierarchical Abstract Syntax Tree.

Next Steps

We have successfully built parsers for all the core language constructs, including the block parser needed for if/else expressions and function bodies. The next logical step, according to the project roadmap, is to create a top-level parser that assembles a sequence of definitions into the final Program AST. You have already accomplished this in this task by implementing the program_parser!

This puts you in a great position. The next major task will be to write comprehensive unit tests for the entire parser to ensure it correctly handles valid syntax and, just as importantly, rejects invalid syntax for all the features you’ve implemented.

Further Reading

• Chumsky .separated_by() combinator: The official documentation for this extremely useful list-parsing combinator.
  • https://docs.rs/chumsky/latest/chumsky/trait.Parser.html#method.separated_by
• Ordered Choice in Parsing: An article explaining why the order of .or() calls matters when parsers have a common prefix.
  • https://en.wikipedia.org/wiki/Parsing_expression_grammar#Ordered_choice
• Recursive Descent Parsing: While we are using combinators, the underlying strategy is a form of recursive descent. Understanding the theory can provide deeper insight into what chumsky is doing for you.
  • https://en.wikipedia.org/wiki/Recursive_descent_parser

Implement a Parser for Code Blocks

Mục tiêu: Using the chumsky parser-combinator library in Rust, implement a parser for SimpliLang code blocks. The parser should recognize a sequence of statements enclosed in curly braces ({...}) and transform it into a Block AST node, handling both sequencing and scoping.

---

Of course! Let’s dive deep into parsing code blocks.

You’ve made incredible strides by setting up a sophisticated, recursive parsing architecture to handle function definitions and calls. In that major refactoring, you put a crucial piece of infrastructure in place: the parser for code blocks ({...}). While it was used to parse function bodies, this component is so fundamental to the structure of SimpliLang that it deserves its own detailed focus. Now, we’ll zoom in on that parser, understand its mechanics, and appreciate its role as a cornerstone of our grammar.

The Anatomy of a Block

In SimpliLang, as in many languages, a block is more than just a grouping of code. It serves two primary purposes:

1. Sequencing: It defines a sequence of statements that are executed in order.
2. Scoping: It creates a new, nested scope. Variables declared with let inside a block are local to that block and cease to exist once execution leaves it.

Our AST reflects this perfectly with the Block struct, which contains a Vec<Stmt>. Our goal is to create a parser that recognizes a sequence of statements enclosed in curly braces and transforms it into this Block AST node.

The Parsing Strategy: Combining Repetition and Delimiters

To parse a block, we can break down the problem into three simple steps, which translate directly into chumsky combinators:

1. We need a parser that can recognize a single statement. You’ve already built this by combining your let, return, and expression statement parsers!
2. We need to apply this statement parser repeatedly to consume zero or more statements in a sequence. chumsky’s .repeated() combinator is perfect for this.
3. We need to ensure this entire repeated sequence is enclosed by a TokenKind::LBrace ({) and a TokenKind::RBrace (}). chumsky’s .delimited_by() combinator handles this beautifully.

Implementing the Block Parser

As part of the previous refactoring, you already set up the recursive handles needed for our grammar. The block parser uses its handle, block.define(...), to define its logic. This logic is placed within the language_grammar_parser function, where it has access to the other necessary components like the statement parser.

Let’s look at that specific piece of code again, this time with a focus on how it achieves our goal. The following code is the solution for this task and should be placed within your language_grammar_parser function.

// This logic belongs inside your `language_grammar_parser` function,
// after the `statement` parser has been defined.

// --- Block Parser ---

// We use the `block` recursive handle we declared at the start of the function.
// `define` is used to assign the parsing logic to this handle, allowing other
// parsers (like `if` and `fn`) to refer to it before it's fully defined.
block.define(
    // 1. Start with the parser for a single statement.
    //    This `statement` parser is one you've already built by combining
    //    the parsers for `let`, `return`, and expression statements.
    statement
        // 2. Apply the `.repeated()` combinator. This attempts to run the `statement`
        //    parser over and over, collecting all successful results into a `Vec<Stmt>`.
        //    It gracefully stops when the `statement` parser fails (e.g., when it
        //    sees a `}` token), without generating an error. It correctly handles
        //    empty blocks (zero repetitions).
        .repeated()
        // 3. Apply the `.delimited_by()` combinator. This is a powerful tool that:
        //    a. Expects and consumes the opening delimiter (`{`).
        //    b. Runs the parser it's attached to (our `.repeated()` statements).
        //    c. Expects and consumes the closing delimiter (`}`).
        //    d. Discards the delimiters and returns only the result from the inner parser.
        //    If either delimiter is missing, it produces a parsing error.
        .delimited_by(just(TokenKind::LBrace), just(TokenKind::RBrace))
        // 4. Finally, use the `.map()` combinator to transform the output.
        //    The `.repeated()` combinator produces a `Vec<Stmt>`. We take this vector,
        //    which we name `statements` in the closure, and use it to construct
        //    our `Block` AST struct, completing the transformation.
        .map(|statements| Block { statements }),
);

The Power of Reusability

By defining this block parser, you’ve created a highly reusable component. You have already seen its power in the previous task:

• The if_expr parser uses block.clone() to parse both its “then” and “else” bodies.
• The function_definition_parser uses block.clone() to parse the function’s body.

This is the essence of parser-combinators: building small, robust, and focused parsers that can be composed like Lego bricks to describe an entire language grammar. Your block parser is now a fundamental and reliable brick in your compiler’s foundation.

Next Steps

You have now successfully defined and understood the parsers for every single grammatical construct in the core SimpliLang specification. The entire parser implementation is complete! This is a monumental milestone.

However, an implementation is only as good as its tests. Just as you did for the lexer, the next critical step is to write a comprehensive suite of unit tests for the parser. These tests will verify that your parser correctly builds the AST for valid programs and, just as importantly, correctly rejects programs with syntax errors.

Further Reading

• Chumsky .repeated() combinator: Official documentation for the combinator that parses sequences.
  • https://docs.rs/chumsky/latest/chumsky/trait.Parser.html#method.repeated
• Chumsky .delimited_by() combinator: Official documentation for the combinator that handles enclosed content.
  • https://docs.rs/chumsky/latest/chumsky/trait.Parser.html#method.delimited_by
• Scope in Programming Languages: An article explaining the concept of scope, which is the primary semantic role of a block.
  • https://en.wikipedia.org/wiki/Scope_(computer_science)

Assemble the Top-Level Program Parser

Mục tiêu: Implement the final, top-level program\_parser for the SimpliLang grammar using the chumsky library in Rust. This involves combining the function\_definition\_parser with combinators like .repeated() and .then\_ignore(end()) to parse the entire program structure into a final AST.

---

You have done an absolutely outstanding job building up the components of your parser. You’ve created a sophisticated, precedence-climbing expression parser, parsers for statements and blocks, and most recently, a robust parser for function definitions. You now possess every single building block required to parse the entirety of the SimpliLang grammar.

The final task in implementing our parser’s logic is to assemble these pieces. We need to create the single, top-level entry point that defines what a complete SimpliLang program looks like from the parser’s perspective.

The Blueprint: Revisiting Your EBNF Grammar

Let’s look back at the formal grammar you designed. The very first rule, the “root” of your language’s structure, was simple and elegant:

program = { function_definition };

This rule states that a SimpliLang program is nothing more than a sequence of zero or more function definitions. Our goal is to translate this rule directly into a chumsky parser. Thanks to the powerful function_definition_parser you built in the last task, this is surprisingly straightforward.

Assembling the Final Parser

We will now implement the final logic for our program_parser function. This parser will use the function_definition_parser as its core component and apply combinators to match the “zero or more” rule and ensure the entire input is consumed.

This is the final piece of the puzzle for our parser.rs file, transforming it from a collection of components into a complete, working grammar.

Here is the final implementation of the program_parser within src/parser/parser.rs. The code from the previous steps remains, but this finalizes the main entry point of our grammar.

// src/parser/parser.rs

// ... (imports and the `language_grammar_parser` function remain unchanged)
// ...

pub fn parse(tokens: Vec<Token>) -> Result<Program, Vec<Simple<TokenKind>>> {

    // ... (The entire `language_grammar_parser` function you built previously goes here)
    fn language_grammar_parser() -> (
        impl Parser<TokenKind, Expr, Error = Simple<TokenKind>>,
        impl Parser<TokenKind, FunctionDefinition, Error = Simple<TokenKind>>
    ) {
        // ... all the logic for expressions, statements, blocks, function calls,
        // and function definitions lives inside here.
    }

    /// The main parser for the entire program.
    /// This is the top-level entry point that defines the overall structure of a SimpliLang file.
    fn program_parser() -> impl Parser<TokenKind, Program, Error = Simple<TokenKind>> {
        // 1. Get the function definition parser from our central grammar definition.
        let (_expr_parser, function_def_parser) = language_grammar_parser();

        // 2. Define the program structure.
        function_def_parser
            // The `.repeated()` combinator directly implements the `{...}` part of our EBNF rule.
            // It runs the function definition parser as many times as it can, collecting
            // all successfully parsed functions into a `Vec<FunctionDefinition>`.
            // It handles the "zero or more" case perfectly.
            .repeated()
            // 3. Ensure the entire file is consumed.
            // The `.then_ignore(end())` combinator is a crucial final step for correctness.
            // It asserts that after parsing all the function definitions, we must be at the
            // end of the input stream (represented by `chumsky`'s `end()` parser).
            // This prevents the parser from succeeding if there is invalid "garbage" text
            // after the last valid function.
            .then_ignore(end())
            // 4. Map the result into our final AST node.
            // The output of `.repeated()` is a `Vec<FunctionDefinition>`. The `.map()`
            // combinator takes this vector and wraps it inside our top-level `Program`
            // AST struct, completing the parsing process.
            .map(|functions| Program { functions })
    }

    // This part remains unchanged: create the stream and run our top-level parser.
    let stream = Stream::from_iter(tokens.len()..tokens.len() + 1, tokens.into_iter().map(|tok| tok.kind));
    program_parser().parse(stream)
}

Code Breakdown

You have now officially completed the entire parser implementation. Let’s recap the role of this final program_parser:

1. Entry Point: This is the “root” parser that the public parse function invokes. It orchestrates the entire parsing process.
2. Structural Definition: It defines a SimpliLang program as a sequence of function definitions. This perfectly matches your language design.
3. Correctness and Completeness: The use of .then_ignore(end()) is a critical best practice. A parser should ideally consume all of its input. This combinator ensures that a program is only considered valid if it consists only of function definitions from start to finish, with nothing extra.
4. Final Transformation: The final .map() call is the last step in assembling the AST. It takes the collection of parsed functions and places them into the root Program node, creating the complete, hierarchical tree that represents the user’s source code.

This is a massive milestone. You have successfully translated your formal EBNF grammar into a working, robust parser using modern, declarative techniques. The output of this stage will be a rich AST, ready for the next phase of compilation: semantic analysis.

Next Steps

The implementation of your parser is now complete. However, just as with the lexer, we cannot assume it is correct. We must verify its behavior with a rigorous set of automated tests. In the final task of this step, you will create a comprehensive unit test module for the parser, ensuring it correctly handles all valid SimpliLang constructs and gracefully rejects invalid ones.

Further Reading

• Chumsky’s end() parser: Official documentation for this essential parser that matches the end of the input stream.
  • https://docs.rs/chumsky/latest/chumsky/primitive/fn.end.html
• Top-Down vs. Bottom-Up Parsing: An overview of different parsing strategies. Our parser-combinator approach is a form of top-down, recursive descent parsing.
  • https://en.wikipedia.org/wiki/Top-down_parsing
• Compiler Front-End: An article discussing the role of the lexer and parser, which together form the “front-end” of a compiler.
  • https://www.geeksforgeeks.org/phases-of-a-compiler/

Implement Unit Tests for the SimpliLang Parser

Mục tiêu: Create a comprehensive test suite for the SimpliLang parser in Rust. This involves writing both positive tests to verify the Abstract Syntax Tree (AST) for valid code and negative tests to ensure the parser correctly rejects syntactically invalid code.

---

An outstanding job! You have successfully implemented the entire parsing logic for SimpliLang, from the smallest literal to the top-level program structure. This is the most intellectually demanding part of building a compiler’s front-end, and you have created a robust, declarative grammar using chumsky. This is a massive achievement.

However, as with the lexer, code that hasn’t been tested is code that is presumed broken. To move forward with confidence, we must now rigorously verify that our parser behaves exactly as we designed it to. This means not only checking that it correctly builds an AST for valid programs but also ensuring that it correctly rejects programs with syntactical errors.

In this final task of the parser step, we will build a comprehensive unit test suite that will serve as the definitive proof of your parser’s correctness and a safety net against future bugs.

The Strategy: Testing Both Success and Failure

Our testing strategy will be twofold:

1. Positive Test Cases: We will feed the parser valid SimpliLang code and assert that the generated Abstract Syntax Tree (AST) has the exact structure we expect. This verifies correctness.
2. Negative Test Cases: We will feed the parser syntactically incorrect code and assert that the parser returns an error. This verifies robustness.

We’ll follow the same convention as with the lexer, placing our tests in a #[cfg(test)] module at the bottom of the file containing the code we’re testing: src/parser/parser.rs.

Implementing the Parser Test Suite

Let’s add our test module to the bottom of src/parser/parser.rs. This will involve a helper function to streamline the lexing-and-parsing process and two separate test functions for valid and invalid syntax.

Append the following code to the end of your src/parser/parser.rs file.

// At the bottom of src/parser/parser.rs

#[cfg(test)]
mod tests {
    use super::*; // Import everything from the parent module (our parser code)
    use crate::lexer::Lexer; // Import the Lexer to create a token stream

    /// A helper function that encapsulates the entire lexing and parsing pipeline.
    /// It takes a string of source code, tokenizes it, and then parses it.
    /// This makes our test cases much cleaner and more focused.
    fn parse_test_helper(input: &str) -> Result<Program, Vec<Simple<TokenKind>>> {
        // 1. Lex the input string into a vector of tokens.
        let tokens: Vec<Token> = Lexer::new(input).collect();
        // 2. Call our main `parse` function with the tokens.
        parse(tokens)
    }

    #[test]
    fn test_valid_syntax() {
        // Test case 1: A minimal, valid function definition.
        let input = "fn main() -> int { return 0; }";
        let result = parse_test_helper(input);

        // `assert!(result.is_ok())` checks that parsing succeeded.
        assert!(result.is_ok());
        let program = result.unwrap();

        // We expect the program to have exactly one function.
        assert_eq!(program.functions.len(), 1);
        let main_fn = &program.functions[0];

        // Manually construct the expected AST for deep comparison.
        // This is verbose but provides the strongest possible verification.
        let expected_ast = FunctionDefinition {
            name: "main".to_string(),
            parameters: vec![],
            return_type: Some(PrimitiveType::Int),
            body: Block {
                statements: vec![
                    Stmt::Return(Expr::Literal(LiteralValue::Int(0))),
                ],
            },
        };

        assert_eq!(*main_fn, expected_ast);

        // Test case 2: A program with a `let` statement and a complex expression
        // to verify operator precedence.
        let input = "fn main() -> int { let x: int = 5 + 2 * 10; return x; }";
        let program = parse_test_helper(input).unwrap();
        let main_fn = &program.functions[0];
        let let_stmt = &main_fn.body.statements[0];

        // The expected structure for `5 + (2 * 10)`
        let expected_expr = Expr::Binary {
            op: BinaryOp::Add,
            left: Box::new(Expr::Literal(LiteralValue::Int(5))),
            right: Box::new(Expr::Binary {
                op: BinaryOp::Multiply,
                left: Box::new(Expr::Literal(LiteralValue::Int(2))),
                right: Box::new(Expr::Literal(LiteralValue::Int(10))),
            }),
        };

        if let Stmt::Let { initializer, .. } = let_stmt {
            assert_eq!(*initializer, expected_expr);
        } else {
            // Fails the test if the statement is not a `Stmt::Let`.
            panic!("Expected a let statement!");
        }
    }

    #[test]
    fn test_invalid_syntax() {
        // An array of source code snippets that should FAIL to parse.
        let invalid_inputs = [
            // Case 1: Missing semicolon after a `let` statement.
            "fn main() { let x: int = 5 }", 
            // Case 2: Incomplete expression.
            "fn main() { let x: int = 5 +; }",
            // Case 3: Mismatched parentheses.
            "fn main() { return (5 + 2; }",
            // Case 4: Garbage after the last valid function.
            "fn main() { return 0; } this is not valid",
            // Case 5: Missing return type arrow.
            "fn main() int { return 0; }",
            // Case 6: Invalid type name.
            "fn main() -> integer { return 0; }",
        ];

        for input in invalid_inputs {
            let result = parse_test_helper(input);
            // We assert that the result is an `Err`, meaning the parser
            // correctly identified a syntax error.
            assert!(
                result.is_err(),
                "Parser incorrectly succeeded on input: \"{}\"",
                input
            );
        }
    }
}

Dissecting the Test Suite

• parse_test_helper: This helper is the cornerstone of our testing setup. It abstracts away the lexing step, allowing each test to focus purely on the parser’s input (&str) and output (Result<Program, ...>).
• test_valid_syntax():
  • This function focuses on correctness. For each valid input, we first use assert!(result.is_ok()) to ensure the parser didn’t fail unexpectedly.
  • The core of the test is comparing the resulting Program with a manually constructed, “golden” version of the AST. This is the most rigorous way to test a parser. We check the function name, parameters, return type, and the precise, nested structure of the expressions.
  • The test for operator precedence is crucial. By asserting that the AST for 5 + 2 * 10 is (+ 5 (* 2 10)), we are directly verifying that our precedence-climbing logic works as intended.
• test_invalid_syntax():
  • This function focuses on robustness. We define an array of strings, each containing a distinct and common type of syntax error.
  • We loop through these inputs and call our helper. For each one, we use assert!(result.is_err()) to confirm that our parser correctly failed.
  • The custom message in the assert! macro is a best practice; if a test fails, it will tell us exactly which input string caused the unexpected success.
  • The test for “garbage after the last function” is particularly important, as it verifies that our then_ignore(end()) combinator is working correctly to ensure the entire file is valid.

Running Your Tests

With the test suite in place, head to your terminal in the project’s root directory and run the test command:

cargo test

You should see a successful output, confirming that your parser is both correct and robust.

   Compiling simplilang_compiler v0.1.0 (/path/to/your/simplilang_compiler)
    Finished test [unoptimized + debuginfo] target(s) in ...
     Running unittests (target/debug/deps/simplilang_compiler-...)\

running 3 tests
test lexer::lexer::tests::test_all_tokens ... ok
test parser::parser::tests::test_invalid_syntax ... ok
test parser::parser::tests::test_valid_syntax ... ok

test result: ok. 3 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in ...

Next Steps

This marks the successful completion of the entire parsing step! You have now built the two core components of a compiler’s front-end: a lexer that understands the “words” of your language and a parser that understands its “grammar.” The Abstract Syntax Tree your parser produces is a rich, hierarchical representation of the user’s code, ready for deeper analysis.

The next major step in our journey is Step 5: Semantic Analysis. While the parser has confirmed the code is syntactically correct (the grammar is right), it hasn’t checked if it’s logically correct. For example, the parser would happily accept let x: int = 5 + true;, because it’s grammatically valid. The semantic analyzer’s job is to walk the AST you’ve built and enforce the language’s rules, such as type checking (you can’t add an int to a bool), variable resolution (ensuring every variable is declared before it’s used), and more.

Further Reading

• Snapshot Testing in Rust (insta crate): For very large ASTs, writing them out manually can be tedious. Snapshot testing is an alternative where the testing framework saves the “golden” version of the AST to a file for you.
  • https://insta.rs/
• Compiler Testing Strategies: A high-level overview of different ways to ensure a compiler is correct, including fuzz testing and writing end-to-end tests.
  • https://blog.regehr.org/archives/1453
• The Rust Programming Language - Writing Automated Tests: Revisit the official book’s chapter on testing to solidify your understanding of Rust’s testing features.
  • https://doc.rust-lang.org/book/ch11-00-testing.html