[Self-Hosting] Phase 2: Implement Complete Parser in Gradient

[graydeon]

Summary

Implement a complete recursive descent parser in Gradient that converts tokens into an AST.

Background

With a working lexer (Phase 1), we can now build the parser. Currently compiler/parser.gr has AST type definitions and stub parsing functions (~706 lines). Expand to ~2,000 lines with actual parsing logic.

Current State

File: compiler/parser.gr

• ✅ AST type definitions (ExprKind, StmtKind, etc.)
• ✅ Parser state types
• ❌ Actual parsing logic (stubs return empty)

Target State

Full recursive descent parser with:

• Expression parsing with precedence
• Statement parsing
• Module/item parsing
• Error recovery
• Complete AST construction

Implementation Requirements

Core Functions

1. parse_module(tokens: TokenList) -> (AstModule, ParseErrors)

   • Parse entire module
   • Handle all item types

2. parse_function(tokens: TokenList) -> (AstFunction, TokenList)

   • Parse function definitions
   • Handle parameters, return type, effects, body

3. parse_expression(tokens: TokenList, min_precedence: Int) -> (AstExpr, TokenList)

   • Pratt parser for expressions
   • Handle precedence and associativity
   • Binary, unary, call, field access, etc.

4. parse_statement(tokens: TokenList) -> (AstStmt, TokenList)

   • Let, if, while, for, return, expression statements

5. parse_type(tokens: TokenList) -> (AstType, TokenList)

   • Parse type annotations
   • Handle generics, effects, function types

Precedence Levels (High to Low)

1. Field access, indexing (left)
2. Function calls (left)
3. Unary operators (right)
4. Multiplicative (*, /, %) (left)
5. Additive (+, -) (left)
6. Comparison (<, >, ==, etc.) (left)
7. Logical AND (left)
8. Logical OR (left)
9. Assignment (right)

Error Recovery

• Synchronize on statement boundaries
• Report errors but continue parsing
• Collect all errors, not just first

Acceptance Criteria

• Can parse complete Gradient programs
• Correct AST construction for all constructs
• Proper precedence handling
• Error recovery (continue after errors)
• Position information in AST nodes
• Type-checks successfully
• Tests for all parsing paths

Testing

Test parsing of:

• All expression types
• All statement types
• Module structure
• Error cases

Part Of

• Epic: Full Self-Hosting with Rust Kernel
• Phase: 2 of 7
• Blocks: Phase 3 (Type Checker)

Effort

~5 days, ~1,300 new lines of Gradient

Dependencies

• Phase 1 complete (Lexer)