Recursive Descent Parser (sploosh-parser)
Relevant source files
The following files were used as context for generating this wiki page:
The sploosh-parser is a core component of the Sploosh compiler frontend, implemented as a recursive-descent parser in Rust. It is responsible for transforming a stream of tokens provided by the sploosh-lexer into a typed Abstract Syntax Tree (AST) defined in sploosh-ast. The parser targets Section 16 of the Sploosh language specification and is designed to be "spec-first," meaning the implementation must strictly adhere to the documented grammar and behavior.
Sources: crates/sploosh-parser/src/lib.rs:1-15, crates/AGENTS.md:1-10, README.md:105-110
Architecture and Design
The parser is structured around a Parser struct that maintains a list of tokens, the original source text for span-to-text resolution, and the current position in the token stream. It utilizes a recursive-descent approach where different language constructs (items, statements, expressions) are parsed by dedicated methods.
Parser State and Components
| Component | Description |
|---|---|
tokens | A Vec<Token> containing the output from the lexer. |
pos | Current index in the token stream. |
errors | A collection of ParseError objects encountered during parsing. |
no_struct_literal | A boolean flag used to enforce the block-head restriction (§5.1, §5.2). |
Sources: crates/sploosh-parser/src/lib.rs:37-46, crates/sploosh-lexer/src/lib.rs:8-13
Parsing Flow
The high-level flow begins with the parse_program function, which first invokes the lexer and then initializes the Parser to process the resulting tokens into a Program AST node.
This diagram illustrates the top-level execution loop of the parser.
Sources: crates/sploosh-parser/src/lib.rs:14-17, crates/sploosh-parser/src/lib.rs:61-75
Core Language Constructs
Item Parsing
The parser identifies top-level items such as functions, structs, actors, and modules. It enforces specific rules regarding modifiers like pub, async, and offchain. For example, offchain and async are only permitted on fn items.
Sequence of operations for identifying and parsing a top-level language item.
Sources: crates/sploosh-parser/src/lib.rs:77-133, crates/AGENTS.md:15-25
Expression Parsing and Precedence
Expression parsing uses a Pratt-style precedence climbing algorithm. The infix_binding_power method determines the precedence and associativity of operators.
| Operators | Precedence (Left/Right) | Associativity |
|---|---|---|
=, +=, etc. | 2 / 1 | Right |
|> | 8 / 9 | Left |
+, - | 9 / 10 | Left |
*, /, % | 10 / 11 | Left |
.., ..= | 3 / 4 | Non-associative |
Sources: crates/sploosh-parser/src/lib.rs:556-613, crates/sploosh-parser/src/lib.rs:1004-1025
The Block-Head Restriction
To resolve syntactic ambiguity (specifically regarding struct literals vs blocks in if conditions or match scrutinees), the parser implements a "block-head restriction." When no_struct_literal is true, the parser will not allow a struct literal to be parsed as the outermost expression.
Sources: crates/sploosh-parser/src/lib.rs:43-46, crates/sploosh-parser/src/lib.rs:615-632
Parser Implementation Details
Statement Handling
Statements are handled within the block_inner method. The parser recognizes several specific statement types:
- Let Bindings:
let [mut] name [: ty] = expr; - Returns:
return [expr]; - Control Flow:
break;,continue; - Send Statements:
send handle.method(args);- The operand must be a method call.
Sources: crates/sploosh-parser/src/lib.rs:504-554, crates/AGENTS.md:32-35
Error Recovery
The parser includes basic error recovery mechanisms to continue parsing after encountering a syntax error. Methods like recover_item and recover_until allow the parser to skip tokens until it finds a reliable synchronization point, such as a semicolon or a closing brace.
Sources: crates/sploosh-parser/src/lib.rs:1027-1040
Integration with Lexer
The parser relies on the sploosh-lexer to provide tokens. Tokens carry a Span (start and end offsets), but not the text itself. The parser uses Parser::text(&token) to retrieve the actual string content from the original source file.
// From crates/sploosh-parser/src/lib.rs
fn text(&self, token: &Token) -> &'src str {
token.text(self.source)
}
Sources: crates/sploosh-parser/src/lib.rs:56-58, crates/sploosh-lexer/src/lib.rs:17-20
Testing and Quality Assurance
The parser is extensively tested using a corpus of .sp files. The tests/corpus.rs file dynamically discovers and attempts to parse all files in the tests/corpus/ directory, ensuring that any change in grammar or implementation is validated against existing language fixtures.
Sources: crates/sploosh-parser/tests/corpus.rs:1-25, crates/AGENTS.md:43-46
Conclusion
The sploosh-parser is a foundational part of the Sploosh bootstrap compiler. By implementing a strict recursive-descent strategy and adhering to the "spec-first" philosophy, it ensures that the language implementation remains consistent with the technical specification. Its design prioritizes clear error reporting and accurate AST generation to support downstream compiler phases like name resolution and type checking.