| -rw-r--r-- | Cargo.lock | 89 | ||||
| -rw-r--r-- | Cargo.toml | 8 | ||||
| -rw-r--r-- | src/lexer.rs | 27 | ||||
| -rw-r--r-- | src/main.rs | 2 | ||||
| -rw-r--r-- | src/parser.rs | 81 | ||||
| -rw-r--r-- | src/parser/types.rs | 124 | ||||
| -rw-r--r-- | src/parser/util.rs | 107 | ||||
| -rw-r--r-- | src/stackd | 15 | ||||
| -rw-r--r-- | stackd | 5 |
9 files changed, 451 insertions, 7 deletions
@@ -21,6 +21,32 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "0942ffc6dcaadf03badf6e6a2d0228460359d5e34b57ccdc720b7382dfbd5ec5" [[package]] +name = "anstream" +version = "0.5.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "b1f58811cfac344940f1a400b6e6231ce35171f614f26439e80f8c1465c5cc0c" +dependencies = [ + "anstyle", + "anstyle-parse", + "utf8parse", +] + +[[package]] +name = "anstyle" +version = "1.0.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "2faccea4cc4ab4a667ce676a30e8ec13922a692c99bb8f5b11f1502c72e04220" + +[[package]] +name = "anstyle-parse" +version = "0.2.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "c75ac65da39e5fe5ab759307499ddad880d724eed2f6ce5b5e8a26f4f387928c" +dependencies = [ + "utf8parse", +] + +[[package]] name = "beef" version = "0.5.2" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -42,6 +68,17 @@ dependencies = [ ] [[package]] +name = "comat" +version = "0.1.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "f24f01cb5d7f027b65718cfab34b16ae783a3290d9b16e15d7e4310e0c24c173" +dependencies = [ + "proc-macro2", + "quote", + "syn 2.0.48", +] + +[[package]] name = "fnv" version = "1.0.7" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -63,11 +100,25 @@ version = "0.1.0" dependencies = [ "beef", "chumsky", + "comat", + "lerr", "logos", + "match_deref", "tinyvec", ] [[package]] +name = "lerr" +version = "0.1.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "318b7599710150e42b2d34f3582d047d3896de30c5d74c197d9b88a185a042b4" +dependencies = [ + "anstream", + "comat", + "unicode-width", +] + +[[package]] name = "logos" version = "0.13.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -87,7 +138,7 @@ dependencies = [ "proc-macro2", "quote", "regex-syntax", - "syn", + "syn 2.0.48", ] [[package]] @@ -100,6 +151,17 @@ dependencies = [ ] [[package]] +name = "match_deref" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "30dd27efba9ccf9069f76ff0b7b65eb293a844d9918e15a36098de609c9aacd7" +dependencies = [ + "proc-macro2", + "quote", + "syn 1.0.109", +] + +[[package]] name = "once_cell" version = "1.19.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -131,6 +193,17 @@ checksum = "f162c6dd7b008981e4d40210aca20b4bd0f9b60ca9271061b07f78537722f2e1" [[package]] name = "syn" +version = "1.0.109" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "72b64191b275b66ffe2469e8af2c1cfe3bafa67b529ead792a6d0160888b4237" +dependencies = [ + "proc-macro2", + "quote", + "unicode-ident", +] + +[[package]] +name = "syn" version = "2.0.48" source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "0f3531638e407dfc0814761abb7c00a5b54992b849452a0646b7f65c9f770f3f" @@ -162,6 +235,18 @@ source = "registry+https://github.com/rust-lang/crates.io-index" checksum = "3354b9ac3fae1ff6755cb6db53683adb661634f67557942dea4facebec0fee4b" [[package]] +name = "unicode-width" +version = "0.1.11" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "e51733f11c9c4f72aa0c160008246859e340b00807569a0da0e7a1079b27ba85" + +[[package]] +name = "utf8parse" +version = "0.2.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "711b9620af191e0cdc7468a8d14e709c3dcdb115b36f838e601583af800a370a" + +[[package]] name = "version_check" version = "0.9.4" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -184,5 +269,5 @@ checksum = "9ce1b18ccd8e73a9321186f97e46f9f04b778851177567b1975109d26a08d2a6" dependencies = [ "proc-macro2", "quote", - "syn", + "syn 2.0.48", ] @@ -6,7 +6,13 @@ edition = "2021" # See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html [dependencies] +chumsky = { git = "https://github.com/zesterer/chumsky", version = "1.0.0-alpha.6", features = [ + "label", + "nightly", +], default-features = false } beef = "0.5.2" -chumsky = { git = "https://github.com/zesterer/chumsky", version = "1.0.0-alpha.6", default-features = false, features = ["label", "nightly"] } logos = "0.13.0" tinyvec = { version = "1.6.0", features = ["alloc"] } +comat = "0.1.3" +lerr = "0.1.5" +match_deref = "0.1.1" diff --git a/src/lexer.rs b/src/lexer.rs index faacab6..241a007 100644 --- a/src/lexer.rs +++ b/src/lexer.rs @@ -52,7 +52,7 @@ macro_rules! tokens { } tokens! { - "λ" => Lamba, + "λ" => Lambda, "←" => Place, "→" => Ret, "=" => Eq, @@ -86,6 +86,8 @@ tokens! { "⏭️" => Each, "➡️" => Reduce, "↘️" => ReduceStack, + "🐋" => If, + "🐳" => Else, } @@ -115,8 +117,27 @@ impl<'s> Iterator for Lexer<'s> { #[test] fn lexer() { - let mut lex = lex(r#""#); - // while let Some(x) = lex.next() { print!("{x} "); } + let mut lex = lex(r#""1abc25hriwm4" + / { str → int } / + line ← λ ( + '0'>🔎'9'<🔎 + '9'- + / modifiers are placed in front / + 🐘⬅➡ + 10×+ + ) + + 🐢≠'\n'🚧 + / run function on all values, pushing to the stack / + ⏭️line + / reduce the stack / + ↘️+ + + true 🐋 (+ 🐳 -) + / if true { + } else { - } /"#); + while let Some((x, _)) = lex.next() { + print!("{x:?} "); + } macro_rules! test { ($($tok:ident$(($var:literal))?)+) => {{ $(assert_eq!(lex.next().map(|(x,_)|x), Some(Token::$tok$(($var.into()))?));)+ diff --git a/src/main.rs b/src/main.rs index 77ae04f..18bd388 100644 --- a/src/main.rs +++ b/src/main.rs @@ -1,5 +1,7 @@ +#![feature(iter_intersperse)] mod array; mod lexer; +mod parser; fn main() { println!("Hello, world!"); } diff --git a/src/parser.rs b/src/parser.rs new file mode 100644 index 0000000..df5af22 --- /dev/null +++ b/src/parser.rs @@ -0,0 +1,81 @@ +mod types; +use crate::lexer::{Lexer, Token}; +use chumsky::{ + input::{SpannedInput, Stream}, + prelude::*, + Parser, +}; +mod util; +use types::*; +use util::*; + +impl<'s> Value<'s> { + pub fn parse() -> parser![Self] { + select! { + Token::Int(x) => Value::Int(x), + Token::Float(x) => Value::Float(x), + Token::String(s) => Value::String(s), + } + .labelled("value") + } +} + +impl<'s> Expr<'s> { + pub fn parse() -> parser![Self] { + recursive::<_, Expr, _, _, _>(|expr| { + let inline_expr = recursive(|inline_expr| { + let val = select! { + Token::Int(x) => Expr::Value(Value::Int(x)), + Token::Float(x) => Expr::Value(Value::Float(x)), + Token::String(s) => Expr::Value(Value::String(s)), + } + .labelled("value"); + + choice((t![ident].map(Expr::Ident), val)).boxed() + }); + + let λ = t![λ].ignore_then(expr.clone().delimited_by(t!['('], t![')'])); + + let decl = t![ident] + .then_ignore(t![<-]) + .then(inline_expr.clone().or(λ.clone())) + .map(|(name, body)| Expr::Let { + name, + rhs: Box::new(body), + }) + .labelled("declare") + .boxed(); + + let r#if = t![if] + .ignore_then( + expr.clone() + .then(t![else].or_not().ignore_then(expr.or_not())) + .delimited_by(t!['('], t![')']), + ) + .map(|(a, b)| Expr::If { + then: Box::new(a), + or: Box::new(b.unwrap_or_else(|| Expr::Value(Value::Unit))), + }) + .labelled("if") + .boxed(); + choice((decl, r#if, inline_expr, λ)) + }) + } +} + +pub fn stream(lexer: Lexer<'_>, len: usize) -> SpannedInput<Token<'_>, Span, Stream<Lexer<'_>>> { + Stream::from_iter(lexer).spanned((len..len).into()) +} + +#[cfg(test)] +pub fn code<'s>(x: &'s str) -> SpannedInput<Token<'s>, Span, Stream<Lexer<'s>>> { + stream(crate::lexer::lex(x), x.len()) +} + +pub fn parse(tokens: Lexer<'_>, len: usize) -> Result<Ast<'_>, Vec<Error<'_>>> { + parser().parse(stream(tokens, len)).into_result() +} + +fn parser<'s>() -> parser![Ast<'s>] { + Expr::parse().repeated().collect().map(Ast::Module) +} diff --git a/src/parser/types.rs b/src/parser/types.rs new file mode 100644 index 0000000..298b573 --- /dev/null +++ b/src/parser/types.rs @@ -0,0 +1,124 @@ +use std::ops::Deref; + +use crate::lexer::Token; +use beef::lean::Cow; +use chumsky::{ + input::{SpannedInput, Stream}, + prelude::*, +}; +use match_deref::match_deref; +pub type Span = SimpleSpan<usize>; +pub type Error<'s> = Rich<'s, Token<'s>, Span>; +pub type Input<'s> = SpannedInput<Token<'s>, SimpleSpan, Stream<crate::lexer::Lexer<'s>>>; + +pub enum Ast<'s> { + Module(Vec<Expr<'s>>), +} + +#[derive(Clone)] +pub enum Value<'s> { + Float(f64), + Int(u64), + String(Cow<'s, str>), + Unit, +} + +impl std::fmt::Debug for Value<'_> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Self::Float(x) => write!(f, "{x}f"), + Self::Int(x) => write!(f, "{x}i"), + Self::String(x) => write!(f, "\"{x}\""), + Self::Unit => write!(f, "()"), + } + } +} + +#[derive(Clone)] +pub enum Expr<'s> { + NoOp, + Value(Value<'s>), + Ident(&'s str), + Let { + name: &'s str, + rhs: Box<Expr<'s>>, + }, + If { + then: Box<Expr<'s>>, + or: Box<Expr<'s>>, + }, +} + +#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] +pub struct Spanned<T> { + pub inner: T, + pub span: Span, +} + +impl<T> Deref for Spanned<T> { + type Target = T; + + fn deref(&self) -> &Self::Target { + &self.inner + } +} + +impl<T> Spanned<T> { + pub fn map<U>(self, f: impl FnOnce(T) -> U) -> Spanned<U> { + Spanned { + inner: f(self.inner), + span: self.span, + } + } + + pub fn dummy(inner: T) -> Spanned<T> { + Spanned { + inner, + span: SimpleSpan::new(0, 0), + } + } + + pub fn copys<U>(&self, with: U) -> Spanned<U> { + Spanned { + inner: with, + span: self.span, + } + } +} + +impl<T> From<(T, Span)> for Spanned<T> { + fn from((inner, span): (T, Span)) -> Self { + Self { inner, span } + } +} + +impl<T: std::fmt::Display> std::fmt::Display for Spanned<T> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + write!(f, "{}", self.inner) + } +} + +#[derive(Clone)] +pub enum Type<'s> { + Tuple(Box<[Type<'s>]>), + Path(&'s str), + Unit, +} + +impl std::fmt::Debug for Type<'_> { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Self::Tuple(x) => write!( + f, + "{}", + std::iter::once("(".to_string()) + .chain(x.iter().map(|x| format!("{x:?}")).intersperse(", ".into()),) + .chain([")".to_string()]) + .reduce(|acc, x| acc + &x) + .unwrap() + ), + Self::Path(x) => write!(f, "{x}"), + Self::Unit => write!(f, "()"), + } + } +} diff --git a/src/parser/util.rs b/src/parser/util.rs new file mode 100644 index 0000000..a4f1c71 --- /dev/null +++ b/src/parser/util.rs @@ -0,0 +1,107 @@ +use super::types::*; + +macro_rules! t { + (ident) => { + select! { Token::Ident(ident) => ident }.labelled("ident") + }; + (if) => { + just(Token::If) + }; + (else) => { + just(Token::Else) + }; + (=) => { + just(Token::Equal) + }; + (λ) => { + just(Token::Lambda) + }; + (<-) => { + just(Token::Place) + }; + (,) => { + just(Token::Comma) + }; + (:) => { + just(Token::Colon) + }; + (->) => { + just(Token::ThinArrow) + }; + (()) => { + just(Token::Unit) + }; + ('(') => { + just(Token::OpeningBracket('(')) + }; + (')') => { + just(Token::ClosingBracket(')')) + }; + ('[') => { + just(Token::OpeningBracket('[')) + }; + (']') => { + just(Token::ClosingBracket(']')) + }; + ('{') => { + just(Token::OpeningBracket('{')) + }; + ('}') => { + just(Token::ClosingBracket('}')) + }; +} +macro_rules! parser { + ($t:ty) => { + impl Parser<'s, crate::parser::types::Input<'s>, $t, extra::Err<Error<'s>>> + Clone + } +} + +pub trait TakeSpan { + fn tspn<T>(&mut self, x: T) -> Spanned<T>; +} + +impl<'a, 'b> TakeSpan for MapExtra<'a, 'b, Input<'a>, chumsky::extra::Err<Error<'a>>> { + fn tspn<T>(&mut self, x: T) -> Spanned<T> { + Spanned::from((x, self.span())) + } +} +macro_rules! spanned { + () => { + |a, extra| Spanned::from((a, extra.span())) + }; +} + +use chumsky::input::MapExtra; +pub(crate) use parser; +pub(crate) use spanned; +pub(crate) use t; + +pub trait Unit<T> { + fn empty(&self) -> T; +} + +impl<T> Unit<Option<()>> for Option<T> { + fn empty(&self) -> Option<()> { + self.as_ref().map(|_| ()) + } +} + +pub trait Spanner { + fn spun(self, s: Span) -> Spanned<Self> + where + Self: Sized, + { + (self, s).into() + } +} +impl<T> Spanner for T {} + +pub trait MapLeft<T, V> { + fn ml<U>(self, f: impl Fn(T) -> U) -> (U, V); +} + +impl<T, V> MapLeft<T, V> for (T, V) { + fn ml<U>(self, f: impl Fn(T) -> U) -> (U, V) { + (f(self.0), self.1) + } +} diff --git a/src/stackd b/src/stackd new file mode 100644 index 0000000..8c48039 --- /dev/null +++ b/src/stackd @@ -0,0 +1,15 @@ +"1abc25hriwm4" +// { str → int } +line ← λ ( + '0'>🔎'9'<🔎 + '9'- + // modifiers are placed in front + 🐘⬅➡ + 10×+ +) + +🐢≠'\n'🚧 +// run function on all values, pushing to the stack +⏭️line +// reduce the stack +↘️+
\ No newline at end of file @@ -12,4 +12,7 @@ line ← λ ( // run function on all values, pushing to the stack ⏭️line // reduce the stack -↘️+
\ No newline at end of file +↘️+ + +// true 🐋 (+ 🐳 -) +// if true { + } else { - }
\ No newline at end of file |