Struct liblet::grammar::Grammar

pub struct Grammar { /* fields omitted */ }

A grammar is the main type of this module

It allows to work on grammar over an easy abstraction. A grammar is a quadruple of:

• n, a set of non terminal symbols
• t, a set of terminal symbols
• p, an ordered collection of productions
• s, a start symbol

You can easily create a grammar from a raw string by specifing the productions involved. The remaining n, t and s elements of the quadruple will be automatically extracted from the productions. The s (start symbol) element will be the left hand side of the first production encountered, which has to be a 1 symbol long length. For further details about the formatting of the raw string, you can have a look at how to specify productions from a raw string in the Production documentation.

Methods

impl Grammar

pub fn new<S, P>(n: S, t: S, p: P, s: Symbol) -> Result<Grammar, GrammarError> where
    S: IntoIterator<Item = Symbol>,
    P: IntoIterator<Item = Production>, 

Return a new grammar based on the quadruple elements passed as arguments.

Errors

Returns an error if any of the strings from n, t collections or s are not valid symbols, specifically:

• WrongNonTerminals if any of the n symbols aren't non terminals
• WrongTerminals if any of the t symbols aren't terminals
• SymbolError if the s symbol is not a non terminal

Examples

use liblet::grammar::Grammar;
use liblet::production::production;
use liblet::symbol::symbol;

// create a grammar
let g = Grammar::new(
    vec![symbol("A")], // one non terminal "A"
    vec![symbol("a")], // one terminal, "a"
    vec![production("A","a")], // only one production, A -> a
    symbol("A") // the start symbol "A"
);

assert!(g.is_ok());

pub fn new_from_string<'a, I>(
    n: I,
    t: I,
    p: I,
    s: &str
) -> Result<Grammar, GrammarError> where
    I: IntoIterator<Item = &'a str>, 

Return a new grammar based on the quadruple elements passed as arguments. This differ from the new constructor because it allows you to use plain string instead of already built Symbols.

Errors

Returns an error if any of the strings from n, t collections or s can't be transformed into Symbol, specifically:

• WrongNonTerminals if an error occurred in the n collection
• WrongTerminals if an error occurred in the t collection
• SymbolError if an error occurred in the s

Returns a ProductionError if any of the strings from the productions collection can't be transformed into Production.

Examples

use liblet::grammar::Grammar;

// create a grammar (same as new constructor)
let g = Grammar::new_from_string(
    vec!["A"],
    vec!["a"],
    vec!["A -> a"],
    "A"
);

assert!(g.is_ok());

pub fn n(&self) -> HashSet<Symbol>

Return the set of non terminal symbols representing the n of the grammar quadruple.

Examples

use liblet::grammar::Grammar;
use liblet::production::production;
use liblet::symbol::{Symbol,symbol};
use std::collections::HashSet;

// create a grammar
let g = Grammar::new_from_string(
    vec!["A"],
    vec!["a"],
    vec!["A -> a"],
    "A"
)?;
let n: HashSet<Symbol> = vec![symbol("A")].into_iter().collect();

assert_eq!(g.n(), n);

pub fn t(&self) -> HashSet<Symbol>

Return the set of terminal symbols representing the t of the grammar quadruple.

Examples

use liblet::grammar::Grammar;
use liblet::production::production;
use liblet::symbol::{Symbol,symbol};
use std::collections::HashSet;

// create a grammar
let g = Grammar::new_from_string(
    vec!["A"],
    vec!["a"],
    vec!["A -> a"],
    "A"
)?;
let t: HashSet<Symbol> = vec![symbol("a")].into_iter().collect();

assert_eq!(g.t(), t);

pub fn p(&self) -> Vec<Production>

Return the ordered collection of productions representing the p of the grammar quadruple.

Examples

use liblet::grammar::Grammar;
use liblet::production::{Production,production};

// create a grammar
let g = Grammar::new_from_string(
    vec!["A"],
    vec!["a"],
    vec!["A -> a"],
    "A"
)?;
let p: Vec<Production> = vec![production("A","a")];

assert_eq!(g.p(), p);

pub fn s(&self) -> Symbol

Return the start symbol, that is the s of the grammar quadruple.

Examples

use liblet::grammar::Grammar;
use liblet::symbol::{Symbol,symbol};

// create a grammar
let g = Grammar::new_from_string(
    vec!["A"],
    vec!["a"],
    vec!["A -> a"],
    "A"
)?;
let s: Symbol = symbol("A");

assert_eq!(g.s(), s);

pub fn from_string(string: &str) -> Result<Grammar, GrammarError>

Return a new grammar constructed from the raw string passed as argument.

The process of converting from a raw string to a grammar is defined at the grammar struct documentation level.

Errors

• Returns a NoStartSymbol error if there are no productions in the raw string (since it can not derive a valid start symbol automatically) or if the first production doesn't have a left hand side
• Returns a MultipleStartSymbols error if there are multiple symbols in the first production left hand side

Examples

use liblet::grammar::Grammar;

// create a grammar
let g = Grammar::from_string("A -> a");
// n = {A}
// t = {a}
// p = [A -> a]
// s = {A}

assert!(g.is_ok());

pub fn alternatives<I>(&self, symbols: I) -> Vec<Vec<Symbol>> where
    I: IntoIterator<Item = Symbol>, 

Return a collection of productions right hand side for each production which left hand side matches the given ordered collection of symbols.

Examples

use liblet::grammar::Grammar;
use liblet::symbol::{Symbol,symbol};

// create a grammar
let g = Grammar::from_string("A -> a | b")?;
// find alternatives for left hand side "A"
let alternatives = g.alternatives(vec![symbol("A")]);

assert_eq!(alternatives.len(), 2);
assert_eq!(alternatives[0], vec![symbol("a")]);
assert_eq!(alternatives[1], vec![symbol("b")]);

pub fn restrict_to<I>(&self, symbols: I) -> Result<Grammar, GrammarError> where
    I: IntoIterator<Item = Symbol>, 

Return a new grammar restricted to have only the symbols in the collection passed as argument.

So every element in the new grammar quadruple can only have the passed symbols inside, everything else is deleted. This does not affect the original grammar.

Errors

Returns a NoStartSymbol error if the restrict operation would delete the start symbol from the original grammar, since it can't automatically choose another start symbol.

Examples

use liblet::grammar::Grammar;
use liblet::production::production;
use liblet::symbol::{Symbol,symbol};
use std::collections::HashSet;

// create a grammar
let g = Grammar::from_string("A -> a | b")?;
// restrict the grammar to a new one with only the "A" and "a" symbols
let g_restricted = g.restrict_to(vec![symbol("A"),symbol("a")])?;
// we except a single non terminal symbol "A"
let expected_n: HashSet<Symbol> = vec![symbol("A")].into_iter().collect();
// we except the terminal symbols "A" and "a", but not "b"
let expected_t: HashSet<Symbol> = vec![symbol("a")].into_iter().collect();
// we except the only production "A -> a", but not "A -> b"
let expected_p = vec![production("A","a")];

assert_eq!(g_restricted.n(), expected_n);
assert_eq!(g_restricted.t(), expected_t);
assert_eq!(g_restricted.p(), expected_p);
assert_eq!(g_restricted.s(), symbol("A")); // the start symbol is still the same

pub fn productives(&self) -> HashSet<Symbol>

Return a set of symbols (from the grammar symbols) which are productives.

That is, only the symbols that have some production rule (or production rule chains) that transform that symbol to a non terminal one. The set of productives symbols contains the terminal ones, since they are the products themself.

Examples

use liblet::grammar::Grammar;
use liblet::symbol::{Symbol,symbol};
use std::collections::HashSet;

// create a grammar
let g = Grammar::from_string("
    A -> a | C
    B -> b
")?;
// let's define the expected productives, "C" should not be productive
let expected: HashSet<Symbol> = vec![
    symbol("A"),
    symbol("B"),
    symbol("a"),
    symbol("b"),
].into_iter().collect();

assert_eq!(g.productives(), expected);

pub fn reachable(&self) -> HashSet<Symbol>

Return a set of symbols (from the grammar symbols) which are reachable from the start symbol of the grammar.

That is, only symbols that can be reached by some production rule (or production rule chains).

Examples

use liblet::grammar::Grammar;
use liblet::symbol::{Symbol,symbol};
use std::collections::HashSet;

// create a grammar
let g = Grammar::from_string("
    A -> a | b
    B -> b
")?;
// let's define the expected rachable, "B" should not be reachable
let expected: HashSet<Symbol> = vec![
    symbol("A"),
    symbol("a"),
    symbol("b"),
].into_iter().collect();

assert_eq!(g.reachable(), expected);

pub fn reachable_from<I>(&self, reached: I) -> HashSet<Symbol> where
    I: IntoIterator<Item = Symbol>, 

Return a set of symbols (from the grammar symbols) which are reachable from the set of symbols passed as arguments.

It has the same behaviour of the reachable method but the symbols to search from are here passed as input.

Examples

use liblet::grammar::Grammar;
use liblet::symbol::{Symbol,symbol};
use std::collections::HashSet;

// create a grammar
let g = Grammar::from_string("
    A -> a | b
    B -> b
")?;
// let's define the expected rachable, "A" and "a" should not be reachable
// if we start from "B"
let expected: HashSet<Symbol> = vec![
    symbol("B"),
    symbol("b"),
].into_iter().collect();

assert_eq!(g.reachable_from(vec![symbol("B")]), expected);

Trait Implementations

impl Clone for Grammar

fn clone(&self) -> Grammar

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Grammar

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for Grammar

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error> where
    __D: Deserializer<'de>, 

Deserialize this value from the given Serde deserializer.

impl Display for Grammar

fn fmt(&self, f: &mut Formatter) -> Result

Formats the value using the given formatter.

impl Eq for Grammar

impl PartialEq<Grammar> for Grammar

fn eq(&self, other: &Grammar) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Grammar) -> bool

This method tests for !=.

impl Serialize for Grammar

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error> where
    __S: Serializer, 

Serialize this value into the given Serde serializer.

impl StructuralEq for Grammar

impl StructuralPartialEq for Grammar

impl<'_> TryFrom<&'_ str> for Grammar

type Error = GrammarError

The type returned in the event of a conversion error.

fn try_from(value: &str) -> Result<Self, Self::Error>

Performs the conversion.