Following Names Through Scopes
In our sample program from chapter 01, let x: i32 = 5 + 3; declares a variable named x, and the next line uses it in x * 2. Another function or an inner block could declare its own x. The parser records each use of the name in the AST; we now need to work out which declaration it refers to.
Name resolution makes that connection. Looking up x involves checking scopes and distinguishing parameters, local bindings, and functions. A binding associates a name with a declaration; each use needs to refer to the right one.
Why this phase matters
The type checker needs that declaration to find the type of x. Later, code generation needs it to choose the right storage location or function symbol. A spelling alone doesn't give either phase enough information.
An undefined name should produce an error here, before type checking or code generation starts. Rust's resolver has many more places to look: modules, imports, crates, traits, associated items, macros, labels, lifetimes, and multiple namespaces. The meaning of a name such as Result depends on scope and context, including what's been imported.
MicroRust needs only a global function namespace and a stack of local variable scopes.
What we are building here
The next addition to our growing main.rs is an inline semantics module. The driver will pass the parser's Program to semantics::resolve. Scanning and parsing stay in place; the resolver receives the tree they already built.
We are adding a symbol table and a scope stack. Function names live in a global table. Parameters and let bindings live in function-local scopes. When the resolver sees a declaration, it inserts a symbol. When it sees a use, it searches local scopes from the inside out. A named call may reach the global table only if no local binding hides that spelling. Otherwise let add: i32 = 1; add(2, 3); would incorrectly call a function that Rust considers shadowed.
The AST from the parser contains strings. We retain that AST and attach resolution results in a side table keyed by the start of each name's source span. Together they form our resolved program. The identities stored in that table are:
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct SymbolId(pub usize);
#[derive(Debug, Clone)]
pub struct Symbol {
pub name: String,
pub kind: SymbolKind,
pub span: Span,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SymbolKind {
Function,
Local,
Parameter,
}A SymbolId identifies a binding independently of its spelling. Later phases can use SymbolId(7) while keeping the source name for diagnostics.
The resolver owns a stack of scopes:
struct Resolver {
symbols: Vec<Symbol>,
names: HashMap<usize, SymbolId>,
globals: HashMap<String, SymbolId>,
scopes: Vec<HashMap<String, SymbolId>>,
}A scope is a region where a binding is visible. In MicroRust, parameters have a surrounding scope and each block pushes another. A nested block can introduce locals without leaking them back into its parent. Separate scopes also let a body binding shadow a parameter, as Rust permits.
The order of declarations matters even in these two lines:
let x: i32 = 5 + 3;
let y: i32 = x * 2;The first line declares x. The second line uses x and declares y. The resolver must insert x before resolving the initializer for y.
The order matters within let too. In let x: i32 = x + 1;, Rust makes the new binding visible only after the initializer. The expression can use an earlier x, but not the one being declared. We follow that rule in the resolver's Stmt::Let arm:
self.expr(value)?;
let id = self.declare(name, SymbolKind::Local, *span);
self.scopes.last_mut().unwrap().insert(name.clone(), id);We resolve the initializer before inserting the new binding, so the lookup fails unless an earlier x is visible.
Function declarations come first. Before resolving any function body, we make a pass over the program and insert every function name into the global table:
for f in &ast.functions {
if r.globals.contains_key(&f.name) {
return Err(Error::new(
"resolve",
f.span,
format!("duplicate function `{}`", f.name),
));
}
let id = r.declare(&f.name, SymbolKind::Function, f.span);
r.globals.insert(f.name.clone(), id);
}That allows calls to functions declared later in the file. C requires a preceding declaration, which this example omits:
int main(void) {
return add(1, 2);
}
int add(int a, int b) {
return a + b;
}This is an intentional C compile-failure example: C11 requires a declaration before the call. Adding int add(int, int); before main fixes it. Rust, Java, Python, Ruby, and JavaScript all have their own timing rules for when names become available. Python, for instance, resolves many names dynamically at runtime, so this compiles but may fail when executed:
def main():
return add(1, 2)Defining main alone succeeds. If add is never defined before main() is called, Python reports the error at runtime. MicroRust resolves names during compilation. For example, this use has no preceding declaration:
fn main() {
let y: i32 = x * 2;
}The syntax is valid, but resolution fails:
error: cannot find name `x` in this scope
--> example.mrs:2:18
|
2 | let y: i32 = x * 2;
| ^There's no binding for x in the applicable scope. The diagnostic can say that directly.
Rust also allows a new binding to shadow an earlier one:
fn main() {
let x: i32 = 1;
let x: i32 = x + 1;
println!("{}", x);
}MicroRust supports this form of shadowing. We allocate a fresh ID and replace the visible entry after resolving the initializer. Earlier uses retain the old ID. Duplicate function definitions and duplicate parameters are still errors.
Symbol IDs give us a way to distinguish such bindings:
outer x -> SymbolId(3)
inner x -> SymbolId(8)Those distinct IDs let code generation allocate storage for each binding. Keeping their source spans also lets a diagnostic point to both declarations when an inner binding shadows an outer one.
There is also an order-of-declarations question for locals. Rust does not let a local be used before its declaration:
fn main() {
let y: i32 = x;
let x: i32 = 5;
}The later x doesn't make the earlier use valid. Resolving local statements in source order gives us that behavior, while predeclaring functions globally allows forward calls. The two kinds of declaration have different visibility rules.
Local lookup uses the scope stack in reverse order:
fn lookup_local(&self, name: &str) -> Option<SymbolId> {
self.scopes
.iter()
.rev()
.find_map(|scope| scope.get(name).copied())
}The call resolver first uses this lookup to detect a local that hides the function name. It then finds the global function and resolves each argument in the local scopes. println! remains a special node and does not use ordinary function lookup. Rust's method lookup needs more information. Resolving value.to_string() differs from resolving add(x, y) because traits can provide methods. Imports affect paths, and associated functions involve type namespaces. Each kind of use has its own lookup rules.
Java attaches members to classes and packages, which gives tools explicit structure to work with. Its compiler also needs classpaths, visibility rules, inheritance, overload sets, and generics. JavaScript's var, let, and const bring different scope rules, alongside hoisting, closures, and global object behavior. Ruby resolves methods through receivers and classes at runtime. C has block and file scopes, tags, labels, and linkage to account for.
In Rust, a path such as std::mem::take needs different lookup from a local variable. The associated item Vec::new involves type namespaces. Resolving values.len() depends on the receiver type, so name resolution and type checking cooperate. Macro names also have hygiene rules that prevent certain accidental captures. Our resolver is much smaller, but it still has to follow scope and binding rules.
The scope stack records why one declaration takes precedence over another with the same spelling. A search by name alone would lose that information.
After resolution, a piece of the canonical program no longer says this:
Let result: i32
Call add(Name x, Name y)It says something more like:
Let #6 result: i32
Call #0 add(Local #4 x, Local #5 y)Later phases can use those IDs directly while retaining the names for diagnostics.
We can test resolution independently of types by checking that each use points to the nearest legal declaration. For add(x, y), the callee should resolve through globals and the arguments through locals. An unresolved name stops here, keeping a missing declaration distinct from a later error about the call's arguments.
Run this version
Keep working on microrust/main.rs. The scanner and parser stay as they were; this version adds the semantics module and a resolve command. It prints the declarations found while walking the program.
The files used below are:
microrust/
|-- main.rs
`-- example.mrsIf you kept golden.mrs beside these files, leave it there. Replace the contents of main.rs with the listing below. It includes all earlier phases, so don't append the whole listing to your existing file.
main.rs: compiler through name resolution
// Chapter 04: add name resolution.
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")),
}
}
}
}
#[allow(dead_code)]
mod semantics {
use crate::syntax::{Block, Expr, ExprKind, Program, Stmt};
use crate::{Error, Span};
use std::collections::HashMap;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct SymbolId(pub usize);
#[derive(Debug, Clone)]
pub struct Symbol {
pub name: String,
pub kind: SymbolKind,
pub span: Span,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum SymbolKind {
Function,
Local,
Parameter,
}
pub struct ResolvedProgram {
pub ast: Program,
pub symbols: Vec<Symbol>,
pub names: HashMap<usize, SymbolId>,
pub globals: HashMap<String, SymbolId>,
}
struct Resolver {
symbols: Vec<Symbol>,
names: HashMap<usize, SymbolId>,
globals: HashMap<String, SymbolId>,
scopes: Vec<HashMap<String, SymbolId>>,
}
pub fn resolve(ast: Program) -> Result<ResolvedProgram, Error> {
let mut r = Resolver {
symbols: vec![],
names: HashMap::new(),
globals: HashMap::new(),
scopes: vec![],
};
for f in &ast.functions {
if r.globals.contains_key(&f.name) {
return Err(Error::new(
"resolve",
f.span,
format!("duplicate function `{}`", f.name),
));
}
let id = r.declare(&f.name, SymbolKind::Function, f.span);
r.globals.insert(f.name.clone(), id);
}
for f in &ast.functions {
r.scopes.push(HashMap::new());
for p in &f.params {
if r.scopes.last().unwrap().contains_key(&p.name) {
return Err(Error::new("resolve", p.span, "duplicate parameter"));
}
let id = r.declare(&p.name, SymbolKind::Parameter, p.span);
r.scopes.last_mut().unwrap().insert(p.name.clone(), id);
}
r.block(&f.body)?;
r.scopes.pop();
}
Ok(ResolvedProgram {
ast,
symbols: r.symbols,
names: r.names,
globals: r.globals,
})
}
impl Resolver {
fn declare(&mut self, name: &str, kind: SymbolKind, span: Span) -> SymbolId {
let id = SymbolId(self.symbols.len());
self.symbols.push(Symbol {
name: name.into(),
kind,
span,
});
self.names.insert(span.start, id);
id
}
fn lookup_local(&self, name: &str) -> Option<SymbolId> {
self.scopes
.iter()
.rev()
.find_map(|scope| scope.get(name).copied())
}
fn block(&mut self, block: &Block) -> Result<(), Error> {
self.scopes.push(HashMap::new());
for stmt in &block.statements {
match stmt {
Stmt::Let { name, span, value } => {
self.expr(value)?;
let id = self.declare(name, SymbolKind::Local, *span);
self.scopes.last_mut().unwrap().insert(name.clone(), id);
}
Stmt::Return { value, .. } => {
if let Some(value) = value {
self.expr(value)?;
}
}
Stmt::Expr(value) => self.expr(value)?,
}
}
if let Some(tail) = &block.tail {
self.expr(tail)?;
}
self.scopes.pop();
Ok(())
}
fn expr(&mut self, expr: &Expr) -> Result<(), Error> {
match &expr.kind {
ExprKind::Int(_) => {}
ExprKind::Name(name) => {
let id = self.lookup_local(name).ok_or_else(|| {
Error::new(
"resolve",
expr.span,
format!("cannot find local `{name}` in this scope"),
)
})?;
self.names.insert(expr.span.start, id);
}
ExprKind::Binary { left, right, .. } => {
self.expr(left)?;
self.expr(right)?;
}
ExprKind::Call { callee, args } => {
if self.lookup_local(callee).is_some() {
return Err(Error::new(
"resolve",
expr.span,
format!("`{callee}` is a local, not a callable function"),
));
}
let id = self.globals.get(callee).copied().ok_or_else(|| {
Error::new(
"resolve",
expr.span,
format!("cannot find function `{callee}`"),
)
})?;
self.names.insert(expr.span.start, id);
for arg in args {
self.expr(arg)?;
}
}
ExprKind::Println { value } => self.expr(value)?,
ExprKind::Block(block) => self.block(block)?,
}
Ok(())
}
}
}
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|resolve> FILE";
let mut args = std::env::args().skip(1);
let mode = args.next().ok_or(USAGE)?;
let path = args.next().ok_or(USAGE)?;
if !["tokens", "ast", "resolve"].contains(&mode.as_str()) || args.next().is_some() {
return Err(USAGE.into());
}
let source = std::fs::read_to_string(&path).map_err(|error| format!("{path}: {error}"))?;
let render = |error: Error| error.render(&path, &source);
let tokens = syntax::lex(&source).map_err(render)?;
if mode == "tokens" {
print_tokens(&tokens);
return Ok(());
}
let ast = syntax::Parser::new(tokens).parse().map_err(render)?;
if mode == "ast" {
print_tree(&ast);
return Ok(());
}
let resolved = semantics::resolve(ast).map_err(render)?;
print_symbols(&resolved);
Ok(())
}
fn print_tokens(tokens: &[syntax::Token]) {
for token in tokens {
println!(
"{:?} {:?} {}..{}",
token.kind, token.lexeme, token.span.start, token.span.end
);
}
}
fn print_symbols(program: &semantics::ResolvedProgram) {
for (index, symbol) in program.symbols.iter().enumerate() {
println!("#{index} {:?} {}", symbol.kind, symbol.name);
}
}The new driver calls lex, then Parser::parse, then semantics::resolve. Asking for tokens or ast still stops at that earlier phase. print_symbols only displays the resolver's results; it does not perform name lookup itself.
Replace the small arithmetic example in example.mrs with our full program. It gives the resolver two functions, their parameters, and several local bindings to connect:
fn add(a: i32, b: i32) -> i32 {
return a + b;
}
fn main() {
let x: i32 = 5 + 3;
let y: i32 = x * 2;
let result: i32 = add(x, y);
println!("{}", result);
}This remains valid Rust, with .mrs marking it as input to our compiler. From the folder containing microrust, run:
cd microrust
rustc main.rs -o microrustc
./microrustc resolve example.mrsSkip the first command if you're already in microrust. Rebuilding updates the same executable. The output should be:
#0 Function add
#1 Function main
#2 Parameter a
#3 Parameter b
#4 Local x
#5 Local y
#6 Local resultThe function names get IDs first, followed by parameters and locals as their bodies are visited. This agrees with the add, x, and y identities we followed above. The IDs belong to this compilation; changing the declarations can change their numbers.
Try changing add(x, y) to add(missing, y) and run the resolve command again. It should stop with a cannot find local error. Restore x, then try add(x). Resolution accepts that call because add exists. The next chapter will reject its argument count.
You can still run ./microrustc tokens example.mrs and ./microrustc ast example.mrs. To check the input with Rust, use rustc -C overflow-checks=yes --crate-name example example.mrs -o example-rust, then ./example-rust; it prints 24. Our compiler hasn't reached execution yet.
Each name use now points to a declaration, or produces a resolution error. The next phase can use that binding to find its type. We'll put those types to work in semantic analysis and type checking.