bendns' repos / klunk
smol lang
Diffstat
-rw-r--r--Cargo.toml5
-rw-r--r--draft.kl10
-rw-r--r--src/main.rs2
-rw-r--r--src/parser.rs37
-rw-r--r--src/parser/expression.rs195
-rw-r--r--src/parser/types.rs96
-rw-r--r--src/parser/util.rs16
7 files changed, 323 insertions, 38 deletions
diff --git a/Cargo.toml b/Cargo.toml
index 845a3d4..57024fd 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -7,7 +7,10 @@ edition = "2021"
[dependencies]
beef = "0.5.2"
-chumsky = { git = "https://github.com/zesterer/chumsky", version = "1.0.0-alpha.6", features = ["label", "nightly"] }
+chumsky = { git = "https://github.com/zesterer/chumsky", version = "1.0.0-alpha.6", features = ["label", "nightly", "pratt"], default-features = false }
comat = "0.1.3"
lerr = "0.1.5"
logos = "0.13.0"
+match_deref = "0.1.1"
+petgraph = { version = "0.6.4", default-features = false }
+thiserror = "1.0.56"
diff --git a/draft.kl b/draft.kl
index 2f3b5c7..95102d0 100644
--- a/draft.kl
+++ b/draft.kl
@@ -19,10 +19,10 @@ each (x: slice[T] -> for[T]) { idk } [prefix]
each (x: vec[T] -> for[T]) { idk } [prefix]
each (x: array[T, N] -> for[T]) { idk } [prefix, N ∈ ℤ]
-¬ (x: T -> bool) [alias { !, not }, prefix { tighter_than all }]
+¬ (x: T -> bool) [alias { !, not }, prefix { looser_than function }]
- (x: T -> T) [alias neg, prefix { like ¬ }]
-× ((a: T, b: T) -> T) [alias { *, ⋅, mul }, infix { associativity <, looser_than ¬ }]
+× ((a: T, b: T) -> T) [alias { *, ⋅, mul }, infix { associativity <, looser_than top }]
÷ ((a: T, b: T) -> T) [alias { /, div }, infix { like × }]
rem ((a: T, b: T) -> T) [infix { like × }]
mod ((a: T, b: T) -> T) [infix { like × }]
@@ -32,10 +32,10 @@ mod ((a: T, b: T) -> T) [infix { like × }]
+ ((a: T, b: T) -> T) [alias add, infix { associativity <, looser_than × }]
- ((a: T, b: T) -> T) [alias { −, sub }, infix { like + }]
-« ((a: T, b: T) -> T) [alias { <<, shl }, infix { associativity <, looser_than + }]
-» ((a: T, b: T) -> T) [alias { >>, shr }, infix { like « }]
+shl ((a: T, b: T) -> T) [alias { << }, infix { associativity <, looser_than + }]
+shr ((a: T, b: T) -> T) [alias { >> }, infix { like « }]
-∧ ((a: bool, b: bool) -> bool) { a & b } [infix { associativity <, looser_than « }]
+∧ ((a: bool, b: bool) -> bool) { a & b } [infix { associativity <, looser_than shl }]
& ((a: T, b: T) -> T) [alias and, infix { like ∧ }]
impl bool {
∧ ((a, b: λ(() -> me)) -> me) {
diff --git a/src/main.rs b/src/main.rs
index 2ad7194..cfe0523 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -1,4 +1,4 @@
-#![feature(iter_intersperse)]
+#![feature(iter_intersperse, let_chains)]
use chumsky::error::RichReason;
use comat::cformat as cmt;
use std::process::ExitCode;
diff --git a/src/parser.rs b/src/parser.rs
index 18aa536..e071b11 100644
--- a/src/parser.rs
+++ b/src/parser.rs
@@ -4,6 +4,7 @@ use chumsky::{
prelude::*,
Parser,
};
+mod expression;
mod types;
mod util;
use types::*;
@@ -14,11 +15,11 @@ impl<'s> FixMetaData<'s> {
x: &[Spanned<FixMetaPiece<'s>>],
fixness: Fix,
e: Span,
- ) -> Result<Self, Error<'s>> {
+ ) -> Result<Spanned<Self>, Error<'s>> {
let mut looser_than = None;
let mut tighter_than = None;
let mut assoc = None;
- for &(x, span) in x {
+ for &Spanned { inner: x, span } in x {
match x {
FixMetaPiece::A(_) if assoc.is_some() => {
return Err(Rich::custom(span, "duplicate associatity meta elements"))
@@ -29,9 +30,9 @@ impl<'s> FixMetaData<'s> {
FixMetaPiece::T(_) if tighter_than.is_some() => {
return Err(Rich::custom(span, "duplicate tightness meta elements"))
}
- FixMetaPiece::A(x) => assoc = Some(x),
- FixMetaPiece::L(x) => looser_than = Some(x),
- FixMetaPiece::T(x) => tighter_than = Some(x),
+ FixMetaPiece::A(x) => assoc = Some(Spanned::from((x, span))),
+ FixMetaPiece::L(x) => looser_than = Some(Spanned::from((x, span))),
+ FixMetaPiece::T(x) => tighter_than = Some(Spanned::from((x, span))),
}
}
@@ -45,6 +46,7 @@ impl<'s> FixMetaData<'s> {
None => Err(Rich::custom(e, "precedence meta required")),
Some(()) => Ok(x),
})
+ .map(|x| Spanned::from((x, e)))
}
}
@@ -191,9 +193,9 @@ impl<'s> Meta<'s> {
fn pieces() -> parser![Vec<Spanned<FixMetaPiece<'s>>>] {
use FixMetaPiece::*;
choice((
- Meta::associativity().map(|x| x.ml(A)),
- Meta::looser().map(|x| x.ml(L)),
- Meta::tighter().map(|x| x.ml(T)),
+ Meta::associativity().map(|x| x.map(A)),
+ Meta::looser().map(|x| x.map(L)),
+ Meta::tighter().map(|x| x.map(T)),
))
.separated_by(tok![,])
.collect::<Vec<_>>()
@@ -203,7 +205,7 @@ impl<'s> Meta<'s> {
fn prefix() -> parser![Meta<'s>] {
tok![prefix]
.ignore_then(choice((
- Meta::like().map(|x| Meta::Fix(FixMeta::Like(Fix::Pre, x))),
+ Meta::like().map_with(|x, e| Meta::Fix(FixMeta::Like(Fix::Pre, x, e.span()))),
Meta::pieces()
.try_map(|x, e| {
FixMetaData::from_pieces(&x, Fix::Pre, e)
@@ -216,7 +218,7 @@ impl<'s> Meta<'s> {
.map(|x| Meta::Fix(FixMeta::Data(x)))
})
.delimited_by(tok![lbrace], tok![rbrace]),
- empty().map(|()| Meta::Fix(FixMeta::Default(Fix::Pre))),
+ empty().map_with(|(), e| Meta::Fix(FixMeta::Default(e.tspn(Fix::Pre)))),
)))
.labelled("prefix meta")
}
@@ -224,7 +226,7 @@ impl<'s> Meta<'s> {
fn postfix() -> parser![Meta<'s>] {
tok![postfix]
.ignore_then(choice((
- Meta::like().map(|x| Meta::Fix(FixMeta::Like(Fix::Post, x))),
+ Meta::like().map_with(|x, e| Meta::Fix(FixMeta::Like(Fix::Post, x, e.span()))),
Meta::pieces()
.try_map(|x, e| {
FixMetaData::from_pieces(&x, Fix::Post, e)
@@ -237,7 +239,7 @@ impl<'s> Meta<'s> {
.map(|x| Meta::Fix(FixMeta::Data(x)))
})
.delimited_by(tok![lbrace], tok![rbrace]),
- empty().map(|()| Meta::Fix(FixMeta::Default(Fix::Post))),
+ empty().map_with(|(), e| Meta::Fix(FixMeta::Default(e.tspn(Fix::Post)))),
)))
.labelled("postfix meta")
}
@@ -245,7 +247,7 @@ impl<'s> Meta<'s> {
fn infix() -> parser![Meta<'s>] {
tok![infix]
.ignore_then(choice((
- Meta::like().map(|x| Meta::Fix(FixMeta::Like(Fix::In, x))),
+ Meta::like().map_with(|x, e| Meta::Fix(FixMeta::Like(Fix::In, x, e.span()))),
Meta::pieces()
.try_map(|x, e| {
FixMetaData::from_pieces(&x, Fix::In, e)
@@ -256,7 +258,7 @@ impl<'s> Meta<'s> {
.map(|x| Meta::Fix(FixMeta::Data(x)))
})
.delimited_by(tok![lbrace], tok![rbrace]),
- empty().map(|()| Meta::Fix(FixMeta::Default(Fix::In))),
+ empty().map_with(|(), e| Meta::Fix(FixMeta::Default(e.tspn(Fix::In)))),
)))
.labelled("infix meta")
}
@@ -288,9 +290,10 @@ impl<'s> FnDef<'s> {
.labelled("function signature")
}
- fn block() -> parser![Expr<'s>] {
- expr()
- .clone()
+ fn block() -> parser![Vec<Token<'s>>] {
+ any()
+ .repeated()
+ .collect::<Vec<_>>()
.delimited_by(tok![lbrace], tok![rbrace])
.labelled("block")
}
diff --git a/src/parser/expression.rs b/src/parser/expression.rs
new file mode 100644
index 0000000..3973f3c
--- /dev/null
+++ b/src/parser/expression.rs
@@ -0,0 +1,195 @@
+use super::*;
+use chumsky::prelude::*;
+use match_deref::match_deref;
+use std::collections::{hash_map::Entry, HashMap};
+
+#[derive(Eq, Clone, Copy, Debug)]
+pub struct Proto<'s> {
+ name: &'s str,
+ prec: Precedence,
+}
+
+impl<'s> Proto<'s> {
+ pub fn new(name: &'s str) -> Proto<'s> {
+ Proto {
+ name,
+ prec: Precedence::Ambigous,
+ }
+ }
+
+ pub fn then(self, prec: Precedence) -> Proto<'s> {
+ Self { prec, ..self }
+ }
+}
+
+impl std::hash::Hash for Proto<'_> {
+ fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
+ self.name.hash(state);
+ }
+}
+
+impl PartialEq for Proto<'_> {
+ fn eq(&self, other: &Self) -> bool {
+ self.name == other.name
+ }
+}
+
+#[derive(Copy, Clone, Debug, Eq, PartialEq)]
+enum Precedence {
+ Ambigous,
+ Prefix(u16),
+ Postfix(u16),
+ Infix(u16),
+}
+
+#[derive(Debug, Clone)]
+pub struct Context<'s> {
+ precedence: HashMap<Proto<'s>, Vec<&'s str>>,
+}
+
+#[derive(thiserror::Error, Debug, Clone)]
+pub enum Err<'s> {
+ #[error("unable to find function {0}. are you sure it exists?")]
+ CannotFind(Spanned<&'s str>),
+ #[error("problem.")]
+ Mismatch(Spanned<(Precedence, Fix)>),
+ #[error("{0} != 2")]
+ InfixWithNot2(u8),
+ #[error("you cant bind higher than top")]
+ TtTop(Span),
+ #[error("you cant bind lower than bottom")]
+ LtBot(Span),
+}
+
+/// precedence of "function" defined as (infix) tt bottom (postfix) tt bottom (prefix) lt top
+impl<'s> Context<'s> {
+ fn add(&mut self, dat: FixMeta, proto: Proto<'s>) -> Result<(), Err> {
+ use Fix::*;
+ use Precedence::*;
+ if dat.fix() == In && proto.argc != 2 {
+ return Err(Err::InfixWithNot2(*Spanned::from((proto.argc, dat.span()))));
+ }
+ if let Some(n) = match_deref! {
+ match &dat {
+ FixMeta::Data(Deref @ FixMetaData { looser_than: Some(Deref @ &"top"), .. }) =>Some( 0xfffd),
+ FixMeta::Default(Deref @ Pre) =>Some( 0xfffe),
+ _ => None,
+ }
+ } {
+ let value = match dat.fix() {
+ In => Infix(n),
+ Pre => Prefix(n),
+ Post => Postfix(n),
+ };
+ match self.precedence.entry(proto) {
+ Entry::Occupied(x) => {
+ x.into_mut().push(proto.then(value));
+ }
+ Entry::Vacant(x) => {
+ x.insert(vec![]);
+ }
+ };
+ return Ok(());
+ }
+ if let Some(x) = tt
+ && *x == "top"
+ {
+ return Err(Err::TtTop(s));
+ } // TODO graphs
+ if let Some(lt) = lt {
+ let &position = self
+ .precedence
+ .get(&Proto {
+ name: &*lt,
+ argc: 0,
+ })
+ .ok_or(Err::CannotFind(lt))?;
+ let value = match (position, fix) {
+ (Infix(x), In) => Infix(x - 1),
+ (Prefix(x), Pre) => Prefix(x - 1),
+ (Postfix(x), Post) => Postfix(x - 1),
+ (x, y) => return Err(Err::Mismatch(lt.copys((x, y)))),
+ };
+ self.precedence.insert(proto, value);
+ }
+ if let Some(lt) = tt {
+ let &position = self
+ .precedence
+ .get(&Proto {
+ name: &*lt,
+ argc: 0,
+ })
+ .ok_or(Err::CannotFind(lt))?;
+ let value = match (position, fix) {
+ (Infix(x), In) => Infix(x - 1),
+ (Prefix(x), Pre) => Prefix(x - 1),
+ (Postfix(x), Post) => Postfix(x - 1),
+ (x, y) => return Err(Err::Mismatch(lt.copys((x, y)))),
+ };
+ self.precedence.insert(proto, value);
+ }
+ if let Some(gt) = tt {
+ let &position = self
+ .precedence
+ .get(&Proto {
+ name: &*gt,
+ argc: 0,
+ })
+ .ok_or(Err::CannotFind(gt))?;
+ let value = match (position, fix) {
+ (Infix(x), In) => Infix(x + 1),
+ (Prefix(x), Pre) => Prefix(x + 1),
+ (Postfix(x), Post) => Postfix(x + 1),
+ (x, y) => return Err(Err::Mismatch(gt.copys((x, y)))),
+ };
+ self.precedence.insert(proto, value);
+ }
+ Ok(())
+ }
+}
+
+#[test]
+fn hmm() {
+ let mut hm = std::collections::HashMap::new();
+ hm.insert(Proto { name: "*", argc: 2 }, 32768 - 1);
+ hm.insert(Proto { name: "/", argc: 2 }, 32768 - 1);
+ hm.insert(Proto { name: "+", argc: 2 }, 32768 - 2);
+ hm.insert(Proto { name: "-", argc: 2 }, 32768 - 2);
+ let mut c = Context {
+ precedence: HashMap::default(),
+ };
+ c.add(
+ Proto { name: "*", argc: 2 },
+ None,
+ Some(Spanned::dummy("top")),
+ Fix::In,
+ (0..0).into(),
+ )
+ .unwrap();
+ c.add(
+ Proto { name: "/", argc: 2 },
+ None,
+ Some(Spanned::dummy("top")),
+ Fix::In,
+ (0..0).into(),
+ )
+ .unwrap();
+ println!("{c:#?}");
+ c.add(
+ Proto { name: "+", argc: 2 },
+ None,
+ Some(Spanned::dummy("*")),
+ Fix::In,
+ (0..0).into(),
+ )
+ .unwrap();
+ c.add(
+ Proto { name: "-", argc: 2 },
+ None,
+ Some(Spanned::dummy("*")),
+ Fix::In,
+ (0..0).into(),
+ )
+ .unwrap();
+ panic!("{c:#?}");
+}
diff --git a/src/parser/types.rs b/src/parser/types.rs
index f06554a..0857e1c 100644
--- a/src/parser/types.rs
+++ b/src/parser/types.rs
@@ -1,15 +1,22 @@
+use std::ops::Deref;
+
use crate::lexer::Token;
use beef::lean::Cow;
-use chumsky::prelude::*;
+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>>>;
#[derive(Clone)]
pub struct FnDef<'s> {
pub name: &'s str,
pub args: Vec<(Type<'s>, Type<'s>)>,
pub ret: Type<'s>,
- pub block: Option<Expr<'s>>,
+ pub block: Option<Vec<Token<'s>>>,
pub meta: Vec<Meta<'s>>,
}
@@ -59,7 +66,7 @@ pub enum Associativity {
None,
}
-#[derive(Clone, Debug, Copy)]
+#[derive(Clone, Debug, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum Fix {
Pre,
Post,
@@ -68,10 +75,10 @@ pub enum Fix {
#[derive(Clone, Copy)]
pub struct FixMetaData<'s> {
- pub looser_than: Option<&'s str>,
- pub tighter_than: Option<&'s str>,
+ pub looser_than: Option<Spanned<&'s str>>,
+ pub tighter_than: Option<Spanned<&'s str>>,
pub fixness: Fix,
- pub assoc: Option<Associativity>,
+ pub assoc: Option<Spanned<Associativity>>,
}
impl std::fmt::Debug for FixMetaData<'_> {
@@ -92,16 +99,36 @@ impl std::fmt::Debug for FixMetaData<'_> {
#[derive(Clone, Copy)]
pub enum FixMeta<'s> {
- Default(Fix), // function precedence
- Like(Fix, &'s str),
- Data(FixMetaData<'s>),
+ Default(Spanned<Fix>), // function precedence
+ Like(Fix, &'s str, Span),
+ Data(Spanned<FixMetaData<'s>>),
+}
+
+impl<'s> FixMeta<'s> {
+ pub fn span(&self) -> Span {
+ match self {
+ Self::Default(x) => x.span,
+ Self::Like(_, _, x) => x,
+ Self::Data(x) => x.span,
+ }
+ }
+
+ pub fn fix(&self) -> Fix {
+ match_deref! {
+ match self {
+ Self::Default(Deref @ x) => *x,
+ Self::Like(x,..) => *x,
+ Self::Data(Deref @ FixMetaData { fixness, .. }) => *fixness,
+ }
+ }
+ }
}
impl std::fmt::Debug for FixMeta<'_> {
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
match self {
Self::Default(x) => write!(f, "{x:?}"),
- Self::Like(x, y) => write!(f, "{x:?} {{ like {y} }}"),
+ Self::Like(x, y, _) => write!(f, "{x:?} {{ like {y} }}"),
Self::Data(x) => write!(f, "{x:?}"),
}
}
@@ -155,7 +182,54 @@ impl std::fmt::Debug for Expr<'_> {
}
}
-pub type Spanned<T> = (T, Span);
+#[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> {
diff --git a/src/parser/util.rs b/src/parser/util.rs
index 744e202..3526ce5 100644
--- a/src/parser/util.rs
+++ b/src/parser/util.rs
@@ -79,16 +79,26 @@ macro_rules! tok {
}
macro_rules! parser {
($t:ty) => {
- impl Parser<'s, SpannedInput<Token<'s>, SimpleSpan, Stream<Lexer<'s>>>, $t, extra::Err<Error<'s>>> + Clone
+ 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| (a, extra.span())
+ |a, extra| Spanned::from((a, extra.span()))
};
}
+use chumsky::input::MapExtra;
pub(crate) use parser;
pub(crate) use spanned;
pub(crate) use tok;
@@ -108,7 +118,7 @@ pub trait Spanner {
where
Self: Sized,
{
- (self, s)
+ (self, s).into()
}
}
impl<T> Spanner for T {}