Skip to content
TheChatArchiveThe Chat Archive
Qwenqwen3-235b-a22b-instruct-2507· Alibaba (Qwen)Hugging Face LMArena Human Preference 140K

create a minimal lexer + parser (of AST) in Rust

From a Chatbot Arena battleThe same person sent this prompt to two anonymous models at once. Compare it with grok-4-0709’s answer.
  1. User

    create a minimal lexer + parser (of AST) in Rust

  2. Qwen 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 Number and BinaryOp nodes.

    🧱 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 Result or 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.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.