blob: 9d096dbd7f79ef506b5e477eb70890e183fdcfa6 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#![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<Self>);
/// The multiplication.
fn mul(&mut self, other: impl AsRef<Self>);
}
// TODO: Implement boolean semiring
// TODO: Implement counting semiring
// TODO: Implement derivation forest semiring
#[cfg(test)]
mod tests {}
|
