Basic hand written lambda calculus parser.

lcparser.rs

use std::{iter::Peekable, str::Chars};

struct Parser<'a> {
    chars: Peekable<Chars<'a>>,
    input: &'a str,
    index: usize,
}

#[derive(Debug, Clone)]
pub enum Expr {
    Var(String),
    Abs(String, Box<Expr>),
    App(Box<Expr>, Box<Expr>),
}

impl<'a> Parser<'a> {
    pub fn new(input: &'a str) -> Parser<'a> {
        Parser {
            chars: input.chars().peekable(),
            input,
            index: 0,
        }
    }

    pub fn accumulate(&mut self, predicate: impl Fn(char) -> bool) -> &str {
        let start = self.index;

        while self.chars.peek().map_or(false, |&c| predicate(c)) {
            self.next();
        }

        &self.input[start..self.index]
    }

    pub fn next(&mut self) -> Option<()> {
        let res = self.chars.next()?;
        self.index += res.len_utf8();
        Some(())
    }

    pub fn expect(&mut self, expected_char: char) -> Result<(), String> {
        match self.chars.peek() {
            Some(&c) if c == expected_char => {
                self.next();
                Ok(())
            }
            Some(&c) => Err(format!("Unexpected character '{}', expected '{}'", c, expected_char)),
            None => Err("Unexpected EOF".to_owned()),
        }
    }

    pub fn parse_var(&mut self) -> Result<Expr, String> {
        let name = self.accumulate(char::is_alphanumeric);
        if name.is_empty() {
            return Err("Expected a variable name".to_owned());
        }
        Ok(Expr::Var(name.to_owned()))
    }

    pub fn parse_lambda(&mut self) -> Result<Expr, String> {
        self.next();

        let param = self.accumulate(char::is_alphanumeric).to_owned();
        if param.is_empty() {
            return Err("Expected parameter name after 'λ'".to_owned());
        }

        self.expect('.')?;
        let body = self.parse()?;

        Ok(Expr::Abs(param, Box::new(body)))
    }

    pub fn parse(&mut self) -> Result<Expr, String> {
        let mut func = self.parse_single()?;

        while self.chars.peek().map_or(false, |&c| c != ')') {
            self.accumulate(char::is_whitespace);
            let arg = self.parse_single()?;
            func = Expr::App(Box::new(func), Box::new(arg));
        }

        Ok(func)
    }

    pub fn parse_single(&mut self) -> Result<Expr, String> {
        self.accumulate(char::is_whitespace);

        let Some(&char) = self.chars.peek() else {
            return Err("Unexpected EOF".to_owned());
        };

        match char {
            '(' => {
                self.next();
                let res = self.parse()?;
                self.accumulate(char::is_whitespace);
                self.expect(')')?;
                Ok(res)
            }
            'λ' => self.parse_lambda(),
            c if c.is_alphabetic() => self.parse_var(),
            _ => Err(format!("Unexpected character '{}'", char)),
        }
    }
}

// Exemplo disso funcionando \/
fn main() {
    let res = Parser::new("λf.λx.f (f (f x))").parse();
    println!("{:?}", res);
}