Skip to content

Instantly share code, notes, and snippets.

@Shika-B
Created October 6, 2022 17:25
Show Gist options
  • Save Shika-B/08b999ba030aada52764459f6338d0dd to your computer and use it in GitHub Desktop.
Save Shika-B/08b999ba030aada52764459f6338d0dd to your computer and use it in GitHub Desktop.
Small lambda-calculus parser using nom
use nom::{
branch::alt,
bytes::complete::{tag, take_while},
character::complete::satisfy,
combinator::map,
IResult,
};
#[derive(Debug)]
pub enum Term {
Var(char),
App(Box<Term>, Box<Term>),
Abs(char, Box<Term>),
}
fn whitespaces(input: &str) -> IResult<&str, &str> {
take_while(|c: char| c.is_whitespace())(input)
}
fn var(input: &str) -> IResult<&str, char> {
satisfy(|c| char::is_ascii_alphabetic(&c))(input)
}
fn var_term<'a>(input: &'a str) -> IResult<&'a str, Term> {
// println!("{}, var", input);
map(var, |c| Term::Var(c))(input)
}
fn abs<'a>(input: &'a str) -> IResult<&'a str, Term> {
// println!("{}, abs", input);
let (input, _) = tag(r"\")(input)?;
let (input, var_name) = var(input)?;
let (input, _) = whitespaces(input)?;
let (input, _) = tag(".")(input)?;
let (input, _) = whitespaces(input)?;
let (input, body) = term(input)?;
Ok((input, Term::Abs(var_name, Box::new(body))))
}
fn app<'a>(input: &'a str) -> IResult<&'a str, Term> {
// println!("{}, app", input);
let (input, _) = tag("(")(input)?;
let (input, _) = whitespaces(input)?;
let (input, fun) = term(input)?;
let (input, _) = whitespaces(input)?;
let (input, param) = term(input)?;
let (input, _) = whitespaces(input)?;
let (input, _) = tag(")")(input)?;
Ok((input, Term::App(Box::new(fun), Box::new(param))))
}
fn term<'a>(input: &'a str) -> IResult<&'a str, Term> {
let (input, _) = whitespaces(input)?;
alt((var_term, abs, app))(input)
}
fn main() {
println!("{:#?}", abs(r"\x . ( x y )"))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment