Project Setup

This guide demonstrates how to create a complete Rust application that combines logos for lexical analysis and lalrpop for parsing with abstract syntax tree (AST) generation. We'll build a mathematical expression processor with the following components:

Dependency Configuration

Begin by updating your Cargo.toml with the required dependencies:

[dependencies]
lalrpop = "0.20"
logos = "0.13"

Defining the Grammar

Create a src/expression.lalrpop file to specify the parsing rules for our mathematical expressions that handle addition and multiplication operations:

// src/expression.lalrpop
grammar;

use crate::scanner::Token;

Expression: i64 = {
    Term "+" Expression => |left, _, right| left + right,
    Term => |value| value,
};

Term: i64 = {
    Factor "*" Term => |left, _, right| left * right,
    Factor => |value| value,
};

Factor: i64 = {
    Number => |num| num,
};

Number: i64 = r"[0-9]+" => |text: &str| text.parse::<i64>().unwrap();

Lexical Analysis Implementation

In src/scanner.rs, implement the lexical analyzer using logos to tokenize input text:

// src/scanner.rs
use logos::Logos;

#[derive(Debug, Logos, PartialEq, Clone)]
pub enum Token {
    #[regex(r"[0-9]+")]  
    Number,
    
    #[token("+")]  
    Addition,
    
    #[token("*")]  
    Multiplication,
    
    #[error]  
    Invalid,
}

pub struct Tokenizer<'a> {
    scanner: logos::Lexer<'a, Token>,
}

impl<'a> Tokenizer<'a> {
    pub fn create(input: &'a str) -> Self {
        Tokenizer {
            scanner: Token::lexer(input),
        }
    }
}

impl<'a> Iterator for Tokenizer<'a> {
    type Item = Token;
    
    fn next(&mut self) -> Option {
        self.scanner.next()
    }
}

AST Structure Definition

Define the abstract syntax tree in src/syntax.rs to represent parsed expressions:

// src/syntax.rs
#[derive(Debug)]
pub enum ExpressionNode {
    Constant(i64),
    Sum(Box<ExpressionNode>, Box<ExpressionNode>),
    Product(Box<ExpressionNode>, Box<ExpressionNode>),
}

Parser Integration

Create src/parser.rs to bridge the lexical analyzer and grammar parser:

// src/parser.rs
use lalrpop_util::lalrpop_mod;
use crate::scanner::Token;
use crate::syntax::ExpressionNode;

lalrpop_mod!(pub grammar); // Generates parser module

pub struct ExpressionParser;

impl ExpressionParser {
    pub fn initialize() -> Self {
        ExpressionParser {}
    }
    
    pub fn process_tokens<'a>(&self, tokens: &mut impl Iterator<Item = Token>) -> Result<ExpressionNode, String> {
        let token_sequence: Vec<_> = tokens.collect();
        let mut token_stream = token_sequence.into_iter();
        
        grammar::ExpressionParser::new()
            .parse(&mut token_stream)
            .map_err(|_| "Parsing failed".to_string())
    }
}

Main Application Logic

In src/main.rs, integrate all components to process mathematical expressions:

// src/main.rs
mod scanner;
mod parser;
mod syntax;

use scanner::Tokenizer;
use parser::ExpressionParser;
use syntax::ExpressionNode;

fn main() {
    let input_expression = "5 + 2 * 3 + 1";
    let mut tokenizer = Tokenizer::create(input_expression);
    let parser = ExpressionParser::initialize();
    
    match parser.process_tokens(&mut tokenizer) {
        Ok(ast) => {
            println!("Generated AST: {:?}", ast);
        }
        Err(error_message) => {
            println!("Processing error: {}", error_message);
        }
    }
}

Project Structure

Ensure your project follows this directory structure:

src/
├── main.rs
├── scanner.rs
├── parser.rs
├── syntax.rs
└── expression.lalrpop

Execution and Output

Build and run the application with:

cargo run

For the input "5 + 2 * 3 + 1", the output will be:

Generated AST: Sum(
    Box::new(Constant(5)),
    Box::new(Sum(
        Box::new(Product(
            Box::new(Constant(2)),
            Box::new(Constant(3)),
        )),
        Box::new(Constant(1)),
    )),
)

This represents the expression tree structure: 5 + (2 * 3) + 1.