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
44
45
46
47
48
49
50
51
52
53
|
#![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.
use grammar::Grammar;
/// 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: &Self);
// FIXME: The multiplication needs another information: the parent
// of the other value in the item derivation tree.
/// The multiplication.
fn mul(&mut self, other: &Self);
/// A valuation associates a semiring value from a rule position.
///
/// Since a position is not complete without a grammar, we also
/// give it a grammar.
fn valuation(pos: usize, grammar: &Grammar) -> Self;
}
pub mod counting;
// TODO: Implement derivation forest semiring
#[cfg(test)]
mod tests {}
|
