Building MicroRust's Parser and AST
The lexer has given us tokens in source order. We'll organise them into an abstract syntax tree, or AST, which records how the parts of a program fit together. It shows, for example, which statements belong to a function's body and which expressions make up a statement.
The parser builds this tree. A function gets a name, parameters, an optional return type, and a body. The tokens in x * 2 become an expression, and precedence determines why 5 + 3 * 2 groups differently from (5 + 3) * 2. We can check this grouping before evaluating the expression.
Later phases use this tree in different ways. Name resolution walks scopes; type checking inspects expressions; lowering translates statements in order. Building the tree once saves each phase from having to reconstruct it from tokens.
Parsing gives us more context for errors too. Where the lexer reports an unsupported @, the parser can report a missing ; after a let binding or a parameter type without a name.
rustc also parses macro invocations, attributes, visibility, patterns, generics, lifetimes, modules, and expressions with many precedence levels, while preserving compatibility across editions. MicroRust's subset is small enough that we can follow most parsing decisions directly in the code.
What we are building here
A grammar describes how smaller pieces combine into valid syntax. In recursive descent, our functions follow those rules: parse_function handles an item, and parse_block handles its statements and final expression. This is top-down parsing: we start with an expected structure and parse its smaller parts.
For expressions, a Pratt parser, also called top-down operator precedence parsing, handles precedence and associativity without a separate parsing function for each precedence level. Either style would work for our arithmetic subset. Pratt parsing is also convenient if we later extend expressions with unary operators or field access.
The LL and LR names describe two approaches. Both read left to right. LL works top-down, predicting grammar rules and constructing a leftmost derivation; LR works bottom-up, reconstructing a rightmost derivation in reverse. A derivation is the sequence of grammar-rule choices that accounts for the input. LR parsers are often generated from grammars. LALR merges some LR states to reduce table size, sometimes introducing conflicts; yacc and Bison's traditional mode use this approach.
Those generators work well for many languages. Here I prefer to follow the parser's control flow in ordinary functions. Our item and statement parser is predictive recursive descent, broadly LL-style, with limited lookahead. Expressions use Pratt parsing. Neither part uses LR or LALR tables.
A context-free grammar lets a rule expand a syntactic category without consulting the surrounding declarations. It can describe nested blocks and expressions. Whether a name has been declared is a separate question for resolution. That distinction gives us a useful boundary for this implementation.
The parser consumes tokens from the lexer and produces the AST. A parse tree represents every grammar rule and punctuation mark; an AST retains the structure needed by later phases. We need to check the semicolon when parsing a let statement, but keeping a SemicolonNode afterward wouldn't help the type checker.
The top-level AST begins with functions:
#[derive(Debug, Clone)]
pub struct Program {
pub functions: Vec<Function>,
}
#[derive(Debug, Clone)]
pub struct Function {
pub name: String,
pub span: Span,
pub params: Vec<Param>,
pub return_type: Type,
pub body: Block,
}
#[derive(Debug, Clone)]
pub struct Param {
pub name: String,
pub span: Span,
}The source text fn add(a: i32, b: i32) -> i32 { ... } becomes a Function node. Its fields retain the name, signature, and body without separate nodes for punctuation.
Statements and expressions stay separate:
#[derive(Debug, Clone)]
pub struct Block {
pub statements: Vec<Stmt>,
pub tail: Option<Box<Expr>>,
pub span: Span,
}
#[derive(Debug, Clone)]
pub enum Stmt {
Let {
name: String,
span: Span,
value: Expr,
},
Return {
value: Option<Expr>,
span: Span,
},
Expr(Expr),
}Rust has expression-oriented blocks where the final expression can become the block value. MicroRust keeps that behaviour: Block::tail holds an optional final expression, and a missing tail means unit. A semicolon places an expression in statements instead. return; has no expression, while return value; does. The parser requires i32 annotations on parameters and locals, so it does not retain a choice of local type that our grammar cannot make.
The function parser consumes those parts in source order:
fn parse_function(&mut self) -> Result<Function, Error> {
self.expect(TokenKind::Fn)?;
let name = self.ident()?;
self.expect(TokenKind::LParen)?;
let mut params = Vec::new();
while self.peek().kind != TokenKind::RParen {
let param = self.ident()?;
self.expect(TokenKind::Colon)?;
self.expect(TokenKind::I32)?;
params.push(Param {
name: param.lexeme,
span: param.span,
});
if !self.eat(TokenKind::Comma) {
break;
}
}
self.expect(TokenKind::RParen)?;
let return_type = if self.eat(TokenKind::Arrow) {
self.expect(TokenKind::I32)?;
Type::I32
} else {
Type::Unit
};
let body = self.parse_block()?;
Ok(Function {
name: name.lexeme,
span: name.span,
params,
return_type,
body,
})
}I find it helpful to read this beside a function declaration: the tokens appear in source order, with the parameters and return annotation checked before the body.
After consuming let, the corresponding branch in parse_block reads:
let name = self.ident()?;
self.expect(TokenKind::Colon)?;
self.expect(TokenKind::I32)?;
self.expect(TokenKind::Eq)?;
let value = self.parse_expr(0)?;
self.expect(TokenKind::Semicolon)?;
statements.push(Stmt::Let {
name: name.lexeme,
span: name.span,
value,
});The call to parse_expr(0) needs more explanation. It has to account for operator precedence in an initializer such as this one:
let x: i32 = 5 + 3 * 2;The AST we want is:
Let x: i32 =
Add
Int 5
Mul
Int 3
Int 2Here is the initializer drawn as a tree. The arrows point from an expression to its operands; the enclosing let statement would hold the top node in its value field.
The multiplication is the right operand of the addition. We haven't evaluated either operation. The tree records how they group, which is what later phases need to preserve.
Multiplication has higher precedence than addition, so it binds first. Our four arithmetic operators are left-associative, so a - b - c means (a - b) - c, not a - (b - c).
Adding parentheses to make (5 + 3) * 2 changes the tree:
Now multiplication is at the root, and addition is its left operand. The parser checks the parentheses while reading the source, but the AST doesn't need nodes for them. The changed shape already carries their meaning.
A Pratt parser expresses that with binding power:
fn parse_expr(&mut self, min_bp: u8) -> Result<Expr, Error> {
let mut left = self.parse_prefix()?;
while let Some((op, left_bp, right_bp)) = self.current_infix() {
if left_bp < min_bp {
break;
}
self.advance();
let right = self.parse_expr(right_bp)?;
let span = Span {
start: left.span.start,
end: right.span.end,
};
left = Expr {
kind: ExprKind::Binary {
op,
left: Box::new(left),
right: Box::new(right),
},
span,
};
}
Ok(left)
}The parser reads a left expression, then accepts operators whose binding power meets the current minimum. Giving the right side of + a slightly higher minimum makes a + b + c group left. The next + is handled by the outer call rather than absorbed into the right operand.
We'll use these binding powers:
operator left bp right bp
* / 30 31
+ - 20 21Named calls are parsed as complete primary expressions before the infix loop. That makes add(x, y) * 2 a completed call followed by multiplication by 2. An expression such as y * 2 stays outside the call unless the parentheses place it inside an argument. We don't support first-class functions; the parser still needs to establish the grouping before semantic checks begin.
Adding an infix operator usually means choosing its binding powers and mapping its token to an AST operator. A form such as if needs its own parsing rules. Separating those cases keeps the infix loop short as the surrounding grammar grows.
Parentheses are handled in parse_prefix. This match arm parses their contents, then checks for the closing delimiter:
TokenKind::LParen => {
self.advance();
let expr = self.parse_expr(0)?;
self.expect(TokenKind::RParen)?;
Ok(expr)
}An identifier alone is a variable use. Looking at the next token distinguishes it from a named call. Once parse_prefix has consumed the opening (, the call branch reads the arguments:
let mut args = Vec::new();
while self.peek().kind != TokenKind::RParen {
args.push(self.parse_expr(0)?);
if !self.eat(TokenKind::Comma) {
break;
}
}
self.expect(TokenKind::RParen)?;
ExprKind::Call {
callee: name.lexeme,
args,
}println! needs one extra token, Bang, because the Rust syntax is a macro invocation. MicroRust does not expand macros. The parser still checks the parentheses, exact format string, comma, and value. Its special macro branch ends by constructing this node:
ExprKind::Println {
value: Box::new(value),
}Here value is the parsed expression. Boxing it gives the recursive node a fixed size. Rust macros can produce more syntax, so expansion interacts with parsing. Recognizing this one form directly keeps our example valid Rust without implementing that machinery.
A missing operand gives us a parser error:
fn main() {
let x: i32 = 5 + ;
}The lexer accepts every character. The parser fails when parse_prefix sees a semicolon where an expression should begin:
parse error: expected expression
--> example.mrs:2:22
2 | let x: i32 = 5 + ;
| ^This is MicroRust's own diagnostic. It points to the semicolon where the parser expected an expression; the driver prints it and exits with status 1.
The difficulty of parsing depends heavily on the language. Java's grammar is large but relatively explicit. C has the typedef-name ambiguity, where parsing can depend on name resolution, while Python makes indentation part of syntax. Ruby and JavaScript have flexible call forms to account for. Rust adds a broad expression grammar, macro syntax, patterns, and edition compatibility. Our explicit, restricted syntax avoids most of that work.
Our first parser can stop at an error. rustc tries to recover so it can report several useful errors in one run. Recovery needs synchronization points: after a statement fails to parse, we might skip to a semicolon or closing brace and continue. The risk is choosing the wrong boundary and producing a stream of misleading errors about otherwise valid code.
A possible later recovery strategy would look like this:
on statement error:
report it
skip until ';' or '}'
resume at the next statement boundaryThe companion stops at the first error and does not implement this sketch. We can keep recovery in mind when designing AST nodes and spans. It's easier to preserve the needed source information now than recover it later.
When our parser processes the canonical program, we get a tree shaped roughly like this:
Program
Function add(a: i32, b: i32) -> i32
Return
Binary +
Name a
Name b
Function main() -> unit
Let x: i32
Binary +
Int 5
Int 3
Let y: i32
Binary *
Name x
Int 2
Let result: i32
Call add(Name x, Name y)
Println(Name result)The tree still contains unresolved questions. Name x records a use without proving that x was declared. Whether add expects two arguments, or main should return nothing, belongs to later checks.
The AST now records our functions, blocks, statements, calls, and arithmetic. Later phases can walk that structure without parsing the tokens again.
Run this version
Open the same microrust/main.rs you built in the lexer chapter. We are adding the AST types and parser to its syntax module, then extending the driver with an ast command. The scanner and its tokens command stay available.
The two files used for this example stay in the same places. You can leave golden.mrs beside them:
microrust/
|-- main.rs
`-- example.mrsThe complete listing below includes the earlier code, so replace the contents of main.rs rather than appending the whole block. If you've been adding the pieces as you read, compare your file with this one. The new pieces are the AST types, Parser, and the functions that print its tree; run now passes the scanner's tokens to the parser when we ask for ast.
main.rs: compiler through the parser stage
// Chapter 03: the lexer, AST, and parser.
use std::fmt;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct Span {
pub start: usize,
pub end: usize,
}
#[derive(Debug, Clone)]
pub struct Error {
pub phase: &'static str,
pub span: Span,
pub message: String,
}
impl Error {
pub fn new(phase: &'static str, span: Span, message: impl Into<String>) -> Self {
Self {
phase,
span,
message: message.into(),
}
}
pub fn render(&self, path: &str, source: &str) -> String {
let start = self.span.start.min(source.len());
let prefix = &source[..start];
let line = prefix.bytes().filter(|b| *b == b'\n').count() + 1;
let column = prefix.rsplit('\n').next().unwrap_or("").chars().count() + 1;
let text = source.lines().nth(line - 1).unwrap_or("");
format!(
"{}\n --> {path}:{line}:{column}\n{line} | {text}\n | {}^",
self,
" ".repeat(column - 1)
)
}
}
impl fmt::Display for Error {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{} error: {}", self.phase, self.message)
}
}
impl std::error::Error for Error {}
// Later phases will use the source spans retained in the AST.
#[allow(dead_code)]
mod syntax {
use crate::{Error, Span};
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum TokenKind {
Fn,
Let,
Return,
Ident,
Int,
String,
I32,
Plus,
Minus,
Star,
Slash,
Colon,
Semicolon,
Comma,
LParen,
RParen,
LBrace,
RBrace,
Arrow,
Eq,
Bang,
Eof,
}
#[derive(Debug, Clone)]
pub struct Token {
pub kind: TokenKind,
pub lexeme: String,
pub span: Span,
}
pub fn ident_or_keyword(text: &str) -> TokenKind {
match text {
"fn" => TokenKind::Fn,
"let" => TokenKind::Let,
"return" => TokenKind::Return,
"i32" => TokenKind::I32,
_ => TokenKind::Ident,
}
}
pub fn lex(source: &str) -> Result<Vec<Token>, Error> {
let bytes = source.as_bytes();
let mut pos = 0;
let mut tokens = Vec::new();
while pos < bytes.len() {
if bytes[pos].is_ascii_whitespace() {
pos += 1;
continue;
}
if source[pos..].starts_with("//!")
|| (source[pos..].starts_with("///") && !source[pos..].starts_with("////"))
{
return Err(Error::new(
"lex",
Span {
start: pos,
end: pos + 3,
},
"doc comments are outside MicroRust",
));
}
if source[pos..].starts_with("//") {
while pos < bytes.len() && bytes[pos] != b'\n' {
pos += 1;
}
continue;
}
let start = pos;
let c = bytes[pos];
pos += 1;
let kind = if c.is_ascii_alphabetic() || c == b'_' {
while pos < bytes.len()
&& (bytes[pos].is_ascii_alphanumeric() || bytes[pos] == b'_')
{
pos += 1;
}
ident_or_keyword(&source[start..pos])
} else if c.is_ascii_digit() {
while pos < bytes.len() && bytes[pos].is_ascii_digit() {
pos += 1;
}
TokenKind::Int
} else {
match c {
b'+' => TokenKind::Plus,
b'-' if bytes.get(pos) == Some(&b'>') => {
pos += 1;
TokenKind::Arrow
}
b'-' => TokenKind::Minus,
b'*' => TokenKind::Star,
b'/' if bytes.get(pos) == Some(&b'*') => {
return Err(Error::new(
"lex",
Span {
start,
end: pos + 1,
},
"block comments are outside MicroRust; use //",
))
}
b'/' => TokenKind::Slash,
b':' => TokenKind::Colon,
b';' => TokenKind::Semicolon,
b',' => TokenKind::Comma,
b'(' => TokenKind::LParen,
b')' => TokenKind::RParen,
b'{' => TokenKind::LBrace,
b'}' => TokenKind::RBrace,
b'=' => TokenKind::Eq,
b'!' => TokenKind::Bang,
b'"' => {
while pos < bytes.len() && bytes[pos] != b'"' {
if !bytes[pos].is_ascii() || matches!(bytes[pos], b'\\' | b'\n' | b'\r')
{
return Err(Error::new(
"lex",
Span { start, end: pos },
"only the unescaped format string \"{}\" is supported",
));
}
pos += 1;
}
if pos == bytes.len() {
return Err(Error::new(
"lex",
Span { start, end: pos },
"unterminated string",
));
}
pos += 1;
TokenKind::String
}
_ => {
let ch = source[start..].chars().next().unwrap();
return Err(Error::new(
"lex",
Span {
start,
end: start + ch.len_utf8(),
},
format!("unexpected character '{ch}'"),
));
}
}
};
tokens.push(Token {
kind,
lexeme: source[start..pos].into(),
span: Span { start, end: pos },
});
}
tokens.push(Token {
kind: TokenKind::Eof,
lexeme: String::new(),
span: Span {
start: pos,
end: pos,
},
});
Ok(tokens)
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Type {
I32,
Unit,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BinOp {
Add,
Sub,
Mul,
Div,
}
#[derive(Debug, Clone)]
pub struct Program {
pub functions: Vec<Function>,
}
#[derive(Debug, Clone)]
pub struct Function {
pub name: String,
pub span: Span,
pub params: Vec<Param>,
pub return_type: Type,
pub body: Block,
}
#[derive(Debug, Clone)]
pub struct Param {
pub name: String,
pub span: Span,
}
#[derive(Debug, Clone)]
pub struct Block {
pub statements: Vec<Stmt>,
pub tail: Option<Box<Expr>>,
pub span: Span,
}
#[derive(Debug, Clone)]
pub enum Stmt {
Let {
name: String,
span: Span,
value: Expr,
},
Return {
value: Option<Expr>,
span: Span,
},
Expr(Expr),
}
#[derive(Debug, Clone)]
pub struct Expr {
pub kind: ExprKind,
pub span: Span,
}
#[derive(Debug, Clone)]
pub enum ExprKind {
Int(i32),
Name(String),
Binary {
op: BinOp,
left: Box<Expr>,
right: Box<Expr>,
},
Call {
callee: String,
args: Vec<Expr>,
},
Println {
value: Box<Expr>,
},
Block(Block),
}
pub struct Parser {
tokens: Vec<Token>,
pos: usize,
}
impl Parser {
pub fn new(tokens: Vec<Token>) -> Self {
Self { tokens, pos: 0 }
}
fn peek(&self) -> &Token {
&self.tokens[self.pos]
}
fn advance(&mut self) -> Token {
let t = self.peek().clone();
if t.kind != TokenKind::Eof {
self.pos += 1;
}
t
}
fn error(&self, message: &str) -> Error {
Error::new("parse", self.peek().span, message)
}
fn eat(&mut self, kind: TokenKind) -> bool {
if self.peek().kind == kind {
self.advance();
true
} else {
false
}
}
fn expect(&mut self, kind: TokenKind) -> Result<Token, Error> {
if self.peek().kind == kind {
Ok(self.advance())
} else {
Err(self.error(&format!("expected {kind:?}, found {:?}", self.peek().kind)))
}
}
fn ident(&mut self) -> Result<Token, Error> {
let token = self.expect(TokenKind::Ident)?;
// A restricted scanner must not turn Rust keywords into valid user names.
const RESERVED: &[&str] = &[
"_", "as", "async", "await", "break", "const", "continue", "crate", "dyn", "else",
"enum", "extern", "false", "for", "if", "impl", "in", "loop", "match", "mod",
"move", "mut", "pub", "ref", "self", "Self", "static", "struct", "super", "trait",
"true", "type", "unsafe", "use", "where", "while", "abstract", "become", "box",
"do", "final", "macro", "override", "priv", "typeof", "unsized", "virtual",
"yield", "try", "gen",
];
if RESERVED.contains(&token.lexeme.as_str()) {
return Err(Error::new(
"parse",
token.span,
"reserved Rust word is not an identifier",
));
}
Ok(token)
}
pub fn parse(mut self) -> Result<Program, Error> {
let mut functions = Vec::new();
while self.peek().kind != TokenKind::Eof {
functions.push(self.parse_function()?);
}
Ok(Program { functions })
}
fn parse_function(&mut self) -> Result<Function, Error> {
self.expect(TokenKind::Fn)?;
let name = self.ident()?;
self.expect(TokenKind::LParen)?;
let mut params = Vec::new();
while self.peek().kind != TokenKind::RParen {
let param = self.ident()?;
self.expect(TokenKind::Colon)?;
self.expect(TokenKind::I32)?;
params.push(Param {
name: param.lexeme,
span: param.span,
});
if !self.eat(TokenKind::Comma) {
break;
}
}
self.expect(TokenKind::RParen)?;
let return_type = if self.eat(TokenKind::Arrow) {
self.expect(TokenKind::I32)?;
Type::I32
} else {
Type::Unit
};
let body = self.parse_block()?;
Ok(Function {
name: name.lexeme,
span: name.span,
params,
return_type,
body,
})
}
fn parse_block(&mut self) -> Result<Block, Error> {
let start = self.expect(TokenKind::LBrace)?.span.start;
let mut statements = Vec::new();
let mut tail = None;
while self.peek().kind != TokenKind::RBrace {
if self.peek().kind == TokenKind::Eof {
return Err(self.error("unclosed block"));
}
if self.eat(TokenKind::Let) {
let name = self.ident()?;
self.expect(TokenKind::Colon)?;
self.expect(TokenKind::I32)?;
self.expect(TokenKind::Eq)?;
let value = self.parse_expr(0)?;
self.expect(TokenKind::Semicolon)?;
statements.push(Stmt::Let {
name: name.lexeme,
span: name.span,
value,
});
} else if self.peek().kind == TokenKind::Return {
let span = self.advance().span;
let value = if self.peek().kind == TokenKind::Semicolon {
None
} else {
Some(self.parse_expr(0)?)
};
self.expect(TokenKind::Semicolon)?;
statements.push(Stmt::Return { value, span });
} else {
let value = self.parse_expr(0)?;
if self.eat(TokenKind::Semicolon) {
statements.push(Stmt::Expr(value));
} else {
tail = Some(Box::new(value));
break;
}
}
}
let end = self.expect(TokenKind::RBrace)?.span.end;
Ok(Block {
statements,
tail,
span: Span { start, end },
})
}
fn current_infix(&self) -> Option<(BinOp, u8, u8)> {
match self.peek().kind {
TokenKind::Plus => Some((BinOp::Add, 20, 21)),
TokenKind::Minus => Some((BinOp::Sub, 20, 21)),
TokenKind::Star => Some((BinOp::Mul, 30, 31)),
TokenKind::Slash => Some((BinOp::Div, 30, 31)),
_ => None,
}
}
fn parse_expr(&mut self, min_bp: u8) -> Result<Expr, Error> {
let mut left = self.parse_prefix()?;
while let Some((op, left_bp, right_bp)) = self.current_infix() {
if left_bp < min_bp {
break;
}
self.advance();
let right = self.parse_expr(right_bp)?;
let span = Span {
start: left.span.start,
end: right.span.end,
};
left = Expr {
kind: ExprKind::Binary {
op,
left: Box::new(left),
right: Box::new(right),
},
span,
};
}
Ok(left)
}
fn parse_prefix(&mut self) -> Result<Expr, Error> {
match self.peek().kind {
TokenKind::Int => {
let t = self.advance();
let n = t.lexeme.parse::<i32>().map_err(|_| {
Error::new("parse", t.span, "integer literal is outside 0..=2147483647")
})?;
Ok(Expr {
kind: ExprKind::Int(n),
span: t.span,
})
}
TokenKind::Ident => {
let name = self.ident()?;
let kind = if self.eat(TokenKind::Bang) {
if name.lexeme != "println" {
return Err(Error::new(
"parse",
name.span,
"only println! is supported",
));
}
self.expect(TokenKind::LParen)?;
let format = self.expect(TokenKind::String)?;
if format.lexeme != "\"{}\"" {
return Err(Error::new(
"parse",
format.span,
"expected format string \"{}\"",
));
}
self.expect(TokenKind::Comma)?;
let value = self.parse_expr(0)?;
self.expect(TokenKind::RParen)?;
ExprKind::Println {
value: Box::new(value),
}
} else if self.eat(TokenKind::LParen) {
let mut args = Vec::new();
while self.peek().kind != TokenKind::RParen {
args.push(self.parse_expr(0)?);
if !self.eat(TokenKind::Comma) {
break;
}
}
self.expect(TokenKind::RParen)?;
ExprKind::Call {
callee: name.lexeme,
args,
}
} else {
ExprKind::Name(name.lexeme)
};
let end = self.tokens[self.pos - 1].span.end;
Ok(Expr {
kind,
span: Span {
start: name.span.start,
end,
},
})
}
TokenKind::LParen => {
self.advance();
let expr = self.parse_expr(0)?;
self.expect(TokenKind::RParen)?;
Ok(expr)
}
TokenKind::LBrace => {
let block = self.parse_block()?;
let span = block.span;
Ok(Expr {
kind: ExprKind::Block(block),
span,
})
}
_ => Err(self.error("expected expression")),
}
}
}
}
fn expression(expr: &syntax::Expr) -> String {
use syntax::ExprKind;
match &expr.kind {
ExprKind::Int(value) => value.to_string(),
ExprKind::Name(name) => name.clone(),
ExprKind::Binary { op, left, right } => {
let symbol = match op {
syntax::BinOp::Add => "+",
syntax::BinOp::Sub => "-",
syntax::BinOp::Mul => "*",
syntax::BinOp::Div => "/",
};
format!("({} {symbol} {})", expression(left), expression(right))
}
ExprKind::Call { callee, args } => {
let args = args.iter().map(expression).collect::<Vec<_>>().join(", ");
format!("{callee}({args})")
}
ExprKind::Println { value } => format!("println({})", expression(value)),
ExprKind::Block(block) => format!("{{ {} }}", statements(block).join(" ")),
}
}
fn statements(block: &syntax::Block) -> Vec<String> {
let mut lines = Vec::new();
for statement in &block.statements {
let line = match statement {
syntax::Stmt::Let { name, value, .. } => {
format!("let {name}: i32 = {};", expression(value))
}
syntax::Stmt::Return { value, .. } => match value {
Some(value) => format!("return {};", expression(value)),
None => "return;".into(),
},
syntax::Stmt::Expr(value) => format!("{};", expression(value)),
};
lines.push(line);
}
if let Some(tail) = &block.tail {
lines.push(format!("tail {}", expression(tail)));
}
lines
}
fn print_tree(program: &syntax::Program) {
for function in &program.functions {
let params = function
.params
.iter()
.map(|param| format!("{}: i32", param.name))
.collect::<Vec<_>>()
.join(", ");
println!(
"fn {}({params}) -> {:?}",
function.name, function.return_type
);
for line in statements(&function.body) {
println!(" {line}");
}
}
}
fn main() {
if let Err(error) = run() {
eprintln!("{error}");
std::process::exit(1);
}
}
fn run() -> Result<(), String> {
const USAGE: &str = "usage: microrustc <tokens|ast> FILE";
let mut args = std::env::args().skip(1);
let mode = args.next().ok_or(USAGE)?;
let path = args.next().ok_or(USAGE)?;
if !matches!(mode.as_str(), "tokens" | "ast") || args.next().is_some() {
return Err(USAGE.into());
}
let source = std::fs::read_to_string(&path).map_err(|error| format!("{path}: {error}"))?;
let tokens = syntax::lex(&source).map_err(|error| error.render(&path, &source))?;
if mode == "tokens" {
print_tokens(&tokens);
return Ok(());
}
let program = syntax::Parser::new(tokens)
.parse()
.map_err(|error| error.render(&path, &source))?;
print_tree(&program);
Ok(())
}
fn print_tokens(tokens: &[syntax::Token]) {
for token in tokens {
println!(
"{:?} {:?} {}..{}",
token.kind, token.lexeme, token.span.start, token.span.end
);
}
}The parser follows the same steps as the excerpts in this chapter. The printer adds parentheses around each binary expression so its grouping is easy to see. It doesn't evaluate the expression. The AST also keeps spans for later phases; the allow(dead_code) attribute avoids warnings about fields this version doesn't read yet.
Keep the same example.mrs as before. Here it is again if you're starting with this chapter:
fn main() {
let x: i32 = 5 + 3 * 2;
}Keeping the input unchanged lets us compare the lexer output with the parser's view of it.
With Rust installed, run these commands from the folder that contains microrust. They use a macOS or Linux terminal:
cd microrust
rustc main.rs -o microrustc
./microrustc ast example.mrsSkip cd microrust if you're already in that folder. Rebuilding replaces the earlier executable with one that includes parsing. The ast command prints a short rendering of the tree:
fn main() -> Unit
let x: i32 = (5 + (3 * 2));Unit records that main has no return type annotation. The parentheses show multiplication grouped inside addition; the parser hasn't evaluated it to 11.
Run ./microrustc tokens example.mrs too. It should print the same token list as the previous chapter, because ast uses that lexer before parsing. We can still inspect the earlier stage when something goes wrong later.
Change the input to (5 + 3) * 2 and run the last command again. The printed initializer should become ((5 + 3) * 2). Removing the 2 instead should produce a parse error, since ; cannot finish a multiplication without its right operand.
This version can also parse the full add and main example from the first chapter. It still won't tell us whether a name exists or whether a call has the right arguments. Those checks need the next phases.
The tree records a use of result, but doesn't yet connect it to a declaration. We'll add that connection in symbol tables and name resolution.