create a minimal lexer + parser (of AST) in Rust
- User
create a minimal lexer + parser (of AST) in Rust
Assistant
Here's a minimal implementation of a lexer and parser in Rust that generates an Abstract Syntax Tree (AST) from a simple arithmetic expression.
This implementation is designed to be simple and self-contained, focusing on parsing expressions with numbers, basic arithmetic operators (
+,-,*,/), and parentheses.
📦 Overview
- Lexer: Converts the input string into a list of
Tokens. - Parser: Builds an AST from the tokens using a recursive descent parser.
- AST: A tree structure representing the expression with
NumberandBinaryOpnodes.
🧱 1. Token Definitions
#[derive(Debug, PartialEq, Clone, Copy)] pub enum Token { Number(f64), Plus, Minus, Multiply, Divide, LParen, RParen, }
🔍 2. Lexer
pub struct Lexer<'a> { source: &'a str, position: usize, } impl<'a> Lexer<'a> { pub fn new(source: &'a str) -> Self { Lexer { source, position: 0 } } pub fn lex(&mut self) -> Vec<Token> { let mut tokens = Vec::new(); while self.position < self.source.len() { let c = self.source.chars().nth(self.position).unwrap(); match c { ' ' => self.position += 1, '+' => { tokens.push(Token::Plus); self.position += 1; } '-' => { tokens.push(Token::Minus); self.position += 1; } '*' => { tokens.push(Token::Multiply); self.position += 1; } '/' => { tokens.push(Token::Divide); self.position += 1; } '(' => { tokens.push(Token::LParen); self.position += 1; } ')' => { tokens.push(Token::RParen); self.position += 1; } _ => { if c.is_digit(10) || c == '.' { let number = self.read_number(); tokens.push(Token::Number(number)); } else { panic!("Unexpected character: {}", c); } } } } tokens } fn read_number(&mut self) -> f64 { let start = self.position; while self.position < self.source.len() { let c = self.source.chars().nth(self.position).unwrap(); if c.is_digit(10) || c == '.' { self.position += 1; } else { break; } } let number_str = &self.source[start..self.position]; number_str.parse().unwrap() } }
🌳 3. Abstract Syntax Tree (AST)
#[derive(Debug)] pub enum Expr { Number(f64), BinaryOp { left: Box<Expr>, op: BinaryOp, right: Box<Expr>, }, } #[derive(Debug)] pub enum BinaryOp { Add, Subtract, Multiply, Divide, }
🧮 4. Parser
pub struct Parser { tokens: Vec<Token>, current: usize, } impl Parser { pub fn new(tokens: Vec<Token>) -> Self { Parser { tokens, current: 0 } } pub fn parse(&mut self) -> Result<Expr, String> { self.parse_expr() } fn parse_expr(&mut self) -> Result<Expr, String> { let mut left = self.parse_term()?; while let Some(op) = self.match_binary_op() { let right = self.parse_term()?; left = Expr::BinaryOp { left: Box::new(left), op, right: Box::new(right), }; } Ok(left) } fn parse_term(&mut self) -> Result<Expr, String> { let mut left = self.parse_factor()?; while let Some(op) = self.match_binary_op() { let right = self.parse_factor()?; left = Expr::BinaryOp { left: Box::new(left), op, right: Box::new(right), }; } Ok(left) } fn parse_factor(&mut self) -> Result<Expr, String> { match self.current_token() { Some(Token::Number(n)) => { self.advance(); Ok(Expr::Number(n)) } Some(Token::LParen) => { self.advance(); let expr = self.parse_expr()?; if self.current_token() == Some(Token::RParen) { self.advance(); Ok(expr) } else { Err("Expected closing parenthesis".to_string()) } } _ => Err("Expected number or parenthesis".to_string()), } } fn match_binary_op(&mut self) -> Option<BinaryOp> { match self.current_token() { Some(Token::Plus) => { self.advance(); Some(BinaryOp::Add) } Some(Token::Minus) => { self.advance(); Some(BinaryOp::Subtract) } Some(Token::Multiply) => { self.advance(); Some(BinaryOp::Multiply) } Some(Token::Divide) => { self.advance(); Some(BinaryOp::Divide) } _ => None, } } fn current_token(&self) -> Option<Token> { self.tokens.get(self.current).copied() } fn advance(&mut self) { self.current += 1; } }
🧪 5. Main Function
fn main() { let input = "3 + 4 * (2 - 1)"; let mut lexer = Lexer::new(input); let tokens = lexer.lex(); let mut parser = Parser::new(tokens); match parser.parse() { Ok(ast) => println!("{:#?}", ast), Err(e) => println!("Error: {}", e), } }
✅ Example Output
For input
"3 + 4 * (2 - 1)", the output will be:BinaryOp { left: Number(3.0), op: Add, right: BinaryOp { left: Number(4.0), op: Multiply, right: BinaryOp { left: Number(2.0), op: Subtract, right: Number(1.0), }, }, }
🧠 Notes
- This is a minimal implementation, suitable for educational purposes or simple DSLs.
- It assumes valid input and uses
panic!()for invalid characters. - Operator precedence is respected:
*and/bind tighter than+and-. - Parentheses allow grouping and override precedence.
📌 Future Improvements
- Add support for unary operators (
-,+) - Implement better error handling with
Resultor custom error types - Add support for variables or functions
- Optimize the lexer to avoid repeated
chars().nth()
This code provides a solid foundation for building more complex parsers and interpreters in Rust.
- Lexer: Converts the input string into a list of
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.