Syntax Parsing

Status: Complete (Phase 1) Crate: compiler/syntax-parsing Entry Point: pub fn parse(source: &str) -> Result<Vec<Item>, ParseError>

Overview

The syntax parsing feature slice transforms a token stream from the lexer into an Abstract Syntax Tree (AST). It implements a Pratt parser for expressions with correct operator precedence, and a recursive descent parser for statements and declarations.

Architecture

This slice follows the Vertical Slice Architecture pattern:

• Dependencies: lexical-analysis (tokenization), ast-types (AST definitions), shared-types (common values)
• Public API: Single entry point (parse)
• Internal implementation: All parser internals are pub(crate)
• AST exports: AST types (Expr, Stmt, Item) are public for downstream consumers

Features

AST Node Types

The node set itself lives in the ast-types infrastructure crate, not here: that is what lets semantic analysis, module resolution, and HIR lowering read the tree without depending on this slice. Reproducing the definitions in prose only guarantees they drift, so this section describes the shape and points at the source: compiler/infrastructure/ast-types/src/.

Items (Item), the top level of a file: Function, Struct, Enum, Trait, Impl, Const, Newtype, Import, Module (an inline module { } block), and NoPrelude (the file-scope @no_prelude marker, consumed by module resolution). A function or struct carries its generic parameters and lifetimes; an impl carries an optional trait name, so the inherent and trait forms are one node. A method's receiver is Option<SelfParam>, absent for an associated function, otherwise &self, &mut self, or owned self.

Statements (Stmt), bindings (val / mut), assignment and compound assignment, field and index assignment, dereference assignment, return, break, continue, if, while, for, loop, match, destructuring bindings, val-else, and a bare expression. An if in statement position always parses to Stmt::If, never Stmt::Expr(Expr::If), which is why the type checker and HIR lowering each recognise a trailing Stmt::If as a block's value.

Expressions (Expr), literals, identifiers, unary and binary operators, calls (with optional turbofish type arguments), index, field access, Type::member paths, struct and enum literals, tuples and arrays, ranges, casts, closures, blocks, unsafe blocks, if, match, loop, the ? propagation operator, and Paren grouping (dropped during lowering).

Operator Precedence

The parser is a Pratt parser (precedence climbing). The ladder, loosest first:

There is no >> operator: right shift is the .shr(n) method, because >> is reserved for function composition. ?? associates right-to-left so a ?? b ?? c evaluates each fallback only when every left-hand side before it was absent.

1a + b * c       // a + (b * c)2a < b == c < d  // (a < b) == (c < d)3!a && b         // (!a) && b4f(x)? + 1       // (f(x)?) + 1

Statement boundaries. A newline ends a statement unless the line that just ended asks to continue, it ends with a binary operator, a comma, or an opening delimiter, or the expression is inside an unclosed (, [, or {. The decision belongs to the line that ended, so a line starting with (, [, or * opens a new statement rather than continuing the one above as a call, an index, or a multiplication.

Usage

Basic Parsing

1use syntax_parsing::parse;2 3let source = r#"4    func add(a: i32, b: i32) -> i32 {5        return a + b6    }7"#;8 9let ast = parse(source)?;10for item in ast {11    match item {12        Item::Function(func_def) => {13            println!("Function: {}", func_def.name.name);14            println!("  Parameters: {}", func_def.params.len());15            println!("  Body statements: {}", func_def.body.len());16        }17        Item::Struct(struct_def) => {18            println!("Struct: {}", struct_def.name.name);19            println!("  Fields: {}", struct_def.fields.len());20        }21        Item::Impl(impl_def) => {22            println!("Impl for: {}", impl_def.type_name.name);23            println!("  Methods: {}", impl_def.methods.len());24        }25    }26}

Expression Parsing

1let source = "func test() -> i32 { return (a + b) * c }";2let ast = parse(source)?;3 4// AST structure:5// Binary {6//     left: Paren(Binary { left: "a", op: Add, right: "b" }),7//     op: Multiply,8//     right: "c"9// }

Statement Parsing

1let source = r#"2    func example() -> i32 {3        val x: i32 = 104        if x > 5 {5            return x * 26        } else {7            return 08        }9    }10"#;11 12let ast = parse(source)?;13// Parses variable declarations, if/else, and return statements

Parsing Algorithm

Expression Parsing: Pratt Parser

The Pratt parser algorithm:

1. Parse prefix: Handle unary operators and atoms (literals, identifiers, parentheses)
2. Parse infix: Loop while next operator has higher precedence
3. Recursively parse right side with adjusted precedence
4. Build binary expression node

Key advantages:

• Correct operator precedence without separate grammar rules
• Simple to implement and maintain
• Efficient (single-pass, no backtracking)

Statement Parsing: Recursive Descent

Statements are parsed using traditional recursive descent:

1. Look ahead at current token
2. Dispatch to appropriate statement parser
3. Recursively parse nested structures
4. Validate syntax and build AST nodes

Error Handling

Error Types

ParseError (see errors.rs) covers the token-level failures, UnexpectedToken, UnexpectedEof, a wrapped LexError, and MaxDepthExceeded, which stops runaway nesting rather than overflowing the stack, plus the grammar rules that are cheapest to enforce while parsing: DuplicateParameter, DuplicateTypeAlias, TypeAliasShadowsBuiltin, CyclicTypeAlias, EnumLifetimeParam, ExportNotAllowed, and MisplacedNoPrelude. Each carries the span of the offending token, not the start of the enclosing construct.

Error Recovery

• Fail-fast: parsing stops at the first error. Multiple-error reporting is the type checker's job; it collects diagnostics and keeps going.
• Precise error messages: each names what was expected
• Span information: the exact location of the offending token

Example error:

Planned:

• Error recovery to report multiple errors
• Suggestion system for common mistakes
• Better recovery from missing delimiters

Implementation Details

Technology

• Parser type: Pratt parser (expressions) + Recursive descent (statements)
• Dependencies:
  • lexical-analysis - Token stream
  • shared-types - Common types (Span, Identifier, Literal)

Design Patterns

Visitor Pattern (for future AST traversal):

1impl Expr {2    pub fn span(&self) -> Span {3        // Every expression knows its span4    }5}

Builder Pattern (for complex AST nodes):

1let binary_expr = Expr::Binary {2    left: Box::new(left_expr),3    op: BinaryOp::Add,4    right: Box::new(right_expr),5    span: left_span.merge(right_span),6};

Testing

Test categories:

• Expression parsing (all operators, precedence)
• Statement parsing (var decl, return, if/else)
• Function definitions
• Error cases (syntax errors, unexpected tokens)
• Edge cases (nested expressions, complex control flow)

Example test:

1#[test]2fn test_operator_precedence() {3    let source = "func test() -> i32 { return a + b * c }";4    let ast = parse(source).unwrap();5 6    // Verify that multiplication binds tighter than addition7    let Item::Function(func) = &ast[0];8    let Stmt::Return { value: Some(expr), .. } = &func.body[0];9 10    match expr {11        Expr::Binary { op: BinaryOp::Add, right, .. } => {12            // Right side should be b * c13            assert!(matches!(**right, Expr::Binary { op: BinaryOp::Multiply, .. }));14        }15        _ => panic!("Expected addition at top level"),16    }17}

Design Decisions

Why Pratt Parsing for Expressions?

Alternatives considered:

• Precedence climbing
• Operator precedence parser
• PEG parser (chumsky, nom)

Why Pratt:

• Simple to implement and understand
• Straightforward to extend with new operators
• Correct precedence handling
• Efficient (single pass)
• Less composable than PEG parsers (accepted trade-off for this phase)

Why Recursive Descent for Statements?

• Natural fit for statement grammar
• Easy to add error recovery
• Clear mapping from grammar to code
• Debuggable and maintainable

AST Design Choices

Boxed sub-expressions:

• Reduces enum size
• Prevents recursive type definition
• Slight heap allocation cost (acceptable for Phase 1)

Span on every node:

• Enables precise error reporting
• Supports IDE features (go-to-definition, hover)
• Required for debugging information

Separate Paren node:

• Preserves source formatting information
• Helps with error messages
• Can be eliminated in later passes if needed

API Reference

Public Functions

1/// Parse Neuro source code into an AST2pub fn parse(source: &str) -> Result<Vec<Item>, ParseError>3 4/// Parse a single expression, used by tests and tooling, not by the driver5pub fn parse_expr(source: &str) -> Result<Expr, ParseError>

Public Types

1// AST node types2pub enum Item { ... }3pub enum Stmt { ... }4pub enum Expr { ... }5pub enum Type { ... }6 7// Operators8pub enum BinaryOp { Add, Subtract, Multiply, ... }9pub enum UnaryOp { Negate, Not }10 11// Supporting types12pub struct FunctionDef { ... }13pub struct Parameter { ... }

Integration Points

Upstream Dependencies

• lexical-analysis: Token stream generation
• shared-types: Common types (Span, Identifier, Literal)

Downstream Consumers

• module-resolution: expands the parsed root file into a whole program (the driver injects parse into it, so that slice does not depend on this one)
• semantic-analysis: type checking the AST
• hir-lowering: AST → typed HIR, which is what the backends consume
• LSP server (Phase 8): AST-based features

Grammar Reference

Grammar

The language surface is documented feature by feature in the language reference, where every construct is shown in a program that compiles. That is the grammar's source of truth; a second copy here would only drift from it.

What belongs in this document is the mapping from grammar to code:

Examples

Function with If/Else

1func max(a: i32, b: i32) -> i32 {2    if a > b {3        return a4    } else {5        return b6    }7}

AST:

1Item::Function(FunctionDef {2    name: Identifier { name: "max", span: ... },3    params: [4        Parameter { name: "a", ty: Type::Named("i32"), ... },5        Parameter { name: "b", ty: Type::Named("i32"), ... },6    ],7    return_type: Some(Type::Named("i32")),8    body: [9        Stmt::If {10            condition: Expr::Binary {11                left: Expr::Identifier("a"),12                op: BinaryOp::Greater,13                right: Expr::Identifier("b"),14                ...15            },16            then_block: [Stmt::Return { value: Some(Expr::Identifier("a")) }],17            else_block: Some([Stmt::Return { value: Some(Expr::Identifier("b")) }]),18            ...19        }20    ],21    ...22})

Complex Expression

1func calculate() -> i32 {2    val result = (a + b) * c - d / 23    return result4}

AST (simplified):

Future Enhancements

• Error recovery: continue parsing after an error so a run can report more than one
• Suggestions: "did you mean?" for near-miss identifiers and keywords
• Triple-quoted strings: the """...""" block form (1H)
• Named arguments: the external internal: T parameter form (1H)
• Macros: procedural and declarative (Phase 7)

Troubleshooting

"Unexpected token" errors

Problem: Parser expected different token

Solution:

• Check syntax matches Neuro grammar
• Ensure all delimiters are balanced ({, }, (, ))
• Verify operator precedence expectations

"Unexpected EOF" errors

Problem: Parser reached end of file unexpectedly

Solution:

• Check for missing closing braces
• Ensure all statements are properly terminated
• Verify function definitions are complete

Performance

• Parsing speed: ~1ms for small programs (<100 LOC)
• Memory: Minimal allocations (boxed expressions only)
• Single-pass: No backtracking or re-parsing

References

• Pratt Parsing
• Recursive Descent Parsing
• Source: compiler/syntax-parsing/src/lib.rs