From f28155105134b90fd86049c65478d307e0d8dbbc Mon Sep 17 00:00:00 2001 From: JSDurand Date: Sat, 28 Jan 2023 10:17:24 +0800 Subject: a prototype of an item derivation forest It seems to be complete now, but still awaits more tests to see where the errors are, which should be plenty, haha. --- semiring/src/lib.rs | 51 ++++++++++++++++++++++++++++++++++++++++----------- 1 file changed, 40 insertions(+), 11 deletions(-) (limited to 'semiring') diff --git a/semiring/src/lib.rs b/semiring/src/lib.rs index 7d12d9a..9d096db 100644 --- a/semiring/src/lib.rs +++ b/semiring/src/lib.rs @@ -1,14 +1,43 @@ -pub fn add(left: usize, right: usize) -> usize { - left + right +#![warn(missing_docs)] +//! This crate defines the expected behaviours of semirings and +//! semiring parsers. Some standard semirings are also implemented, +//! such as the boolean, the counting, and the derivation forest +//! semirings. Moreover, this crate also defines the behaviours of a +//! parser, with the formalism of an "item-based description". See +//! the paper [Parsing +//! inside-out](https://arxiv.org/abs/cmp-lg/9805007) by Joshua +//! Goodman. To be more precise, it defines the behaviours of an +//! "item interpreter" that executes "items" in a chosen semiring. +//! Finally, it provides a default implementation of an item +//! interpreter. +//! +//! The crate *chain* will implement a parser using the item-based +//! description. Specifically, it will produce items as it parses the +//! input string. Then we can execute these items by any interpreter. + +/// A semiring is equipped with two operations: the addition and the +/// multiplication. It also has additive and multiplicative +/// identities. Also the two operations are supposed to be +/// associative, and the multiplication is supposed to be distributive +/// over the addition. But the addition is not required to be +/// commutative, and is usually not indeed commutative. +pub trait Semiring { + /// The additive identity. + fn zero() -> Self; + + /// The multiplicative identity. + fn one() -> Self; + + /// The addition. + fn add(&mut self, other: impl AsRef); + + /// The multiplication. + fn mul(&mut self, other: impl AsRef); } +// TODO: Implement boolean semiring +// TODO: Implement counting semiring +// TODO: Implement derivation forest semiring + #[cfg(test)] -mod tests { - use super::*; - - #[test] - fn it_works() { - let result = add(2, 2); - assert_eq!(result, 4); - } -} +mod tests {} -- cgit v1.2.3-18-g5258