Struct liblet::derivation::Derivation

pub struct Derivation { /* fields omitted */ }

The main type of this module.

It allows derivations on a specified grammar. Every derivation step modify the current derivation state. A derivation can be created from scratch with the initial sentential form based on the grammar start symbol or a custom sentential form can be used to initialize the derivation from there (in the latter case, no previous steps are automatically calculated, so the history can't be reproduced using the derivation).

At any time, you can query the sentential form and the applied steps of the derivation.

For more information about derivation steps, check out their documentation.

Notice

A derivation needs to borrow a grammar, in order for it to work even if the grammar is then left. So if the original grammar is then modified, it doesn't affect the derivation of the original one.

Implementations

impl Derivation

pub fn new(g: Grammar) -> Derivation

Return a new derivation based on the given grammar. The initial sentential form is supposed to be the start symbol of the grammar.

Examples

use liblet::derivation::Derivation;
use liblet::grammar::grammar;
use liblet::symbol::symbol;

let g = grammar("A -> a");
let d = Derivation::new(g);

assert_eq!(d.sentential_form(), vec![symbol("A")]);

pub fn new_from<I>(g: Grammar, sentential_form: I) -> Derivation where
    I: IntoIterator<Item = Symbol>, 

Return a new derivation based on the given grammar. The initial sentential form is the collection of symbols passed as input, ordered as it's passed.

Notice

It allows you to create derivation based on sentential forms with any symbols, even the ones not in the grammar.

Examples

use liblet::derivation::Derivation;
use liblet::grammar::grammar;
use liblet::symbol::symbol;

let g = grammar("A -> a");
let d = Derivation::new_from(g, vec![symbol("Custom")]);

assert_eq!(d.sentential_form(), vec![symbol("Custom")]);

pub fn steps(&self) -> Vec<DerivationStep>

Return the steps done from the derivation until now.

Return an empy collection if no steps have been done.

Examples

use liblet::derivation::Derivation;
use liblet::grammar::grammar;

let g = grammar("A -> a");
let d = Derivation::new(g);

assert!(d.steps().is_empty());

pub fn sentential_form(&self) -> Vec<Symbol>

Return the current sentential form of the derivation, that is, the sentential form obtained by applying the derivation steps on the initial sentential form of the derivation.

Return the initial sentential form if no steps have been done.

Examples

use liblet::derivation::Derivation;
use liblet::grammar::grammar;
use liblet::symbol::symbol;

let g = grammar("A -> a");
let d = Derivation::new(g);

assert_eq!(d.sentential_form(), vec![symbol("A")]);

pub fn step(
    self,
    p_index: usize,
    index: usize
) -> Result<Derivation, DerivationError>

Apply the given step (production index and sentential form index) to the derivation. Return the modified derivation for writing things like d.step(0,0).step(1,2) etc.

Return the initial sentential form if no steps have been done.

Errors

For more info about the errors returned, check the DerivationError documentation.

• WrongProductionIndex error if the production index targets a nonexistent grammar production
• WrongIndex error if the index target an impossible index of the current derivation sentential form
• ImpossibleStep error if the step to be applied can't be applied to the current derivation sentential form (but the steps indexes were correct)

Examples

use liblet::derivation::Derivation;
use liblet::grammar::grammar;
use liblet::symbol::symbol;

let g = grammar("A -> a");
let d = Derivation::new(g);

assert_eq!(d.sentential_form(), vec![symbol("A")]);

pub fn step_from_iter<I>(self, steps: I) -> Result<Derivation, DerivationError> where
    I: IntoIterator<Item = DerivationStep>, 

Apply the given ordered collection of steps.

It works just like the step method, but it receives a collection of steps instead of a single one. For clarity reason, a colleciton of formal DerivationSteps is required here.

Errors

Return an error if any of the given steps return an error when applied. For more info about the errors returned, check the DerivationError documentation.

• WrongProductionIndex error if the production index target a nonexistent grammar production
• WrongIndex error if the index target an impossible index of the current derivation sentential form
• ImpossibleStep error if the step to be applied can't be applied to the current derivation sentential form (but the steps indexes were correct)

Examples

use liblet::derivation::Derivation;
use liblet::grammar::grammar;
use liblet::symbol::symbol;

let g = grammar("A -> a");
let d = Derivation::new(g);

assert_eq!(d.sentential_form(), vec![symbol("A")]);

pub fn leftmost(self, p_index: usize) -> Result<Derivation, DerivationError>

Apply a step on the leftmost symbol of the current sentential form, using the production specified as input with the production index.

It works just like the step method, using the index of the first non terminal symbol within the current sentential form as the sentential form symbol index.

Errors

Return an error according to the step method.

Moreover, it can return a NoNSymbol error if there are no non terminal symbols in the current sentential form

Examples

use liblet::derivation::Derivation;
use liblet::grammar::grammar;
use liblet::symbol::symbol;

let g = grammar("A -> a");
let d = Derivation::new(g);

assert!(d.leftmost(0).is_ok()); // applied "A -> a" on "A"

pub fn leftmost_from_iter<I>(
    self,
    p_indexes: I
) -> Result<Derivation, DerivationError> where
    I: IntoIterator<Item = usize>, 

Repeated leftmost for each production index in an ordered collection of productions passed as input

pub fn rightmost(self, p_index: usize) -> Result<Derivation, DerivationError>

Apply a step on the rightmost symbol of the current sentential form, using the production specified as input with the production index.

It works just like the step method, using as the index of the sentential form symbol to derive from the index of rightmost non terminal symbol within the sentential form

Errors

Return an error according to the step method.

Moreover, it can return a NoNSymbol error if there are no non terminal symbols in the current sentential form.

Examples

use liblet::derivation::Derivation;
use liblet::grammar::grammar;
use liblet::symbol::symbol;

let g = grammar("A -> a");
let d = Derivation::new(g);

assert!(d.rightmost(0).is_ok()); // applied "A -> a" on "A"

pub fn rightmost_from_iter<I>(
    self,
    p_indexes: I
) -> Result<Derivation, DerivationError> where
    I: IntoIterator<Item = usize>, 

Repeated rightmost for each production index in an ordered collection of productions passed as input

pub fn is_possible_step(self, p_index: usize, index: usize) -> bool

Check if a given step is appliable to the current sentential form.

Return true if the given step is appliable, false otherwise.

Examples

use liblet::derivation::Derivation;
use liblet::grammar::grammar;
use liblet::symbol::symbol;

let g = grammar("A -> a");
let d = Derivation::new(g);

// check if step "A -> a" on "A" is appliable
assert!(d.is_possible_step(0,0));

pub fn possible_steps_by_prod(
    self,
    p_index: usize
) -> Result<Vec<DerivationStep>, DerivationError>

Return a collection of steps, representing the possible steps from the current derivation state, based on trying to derive using the production whose production index is given as argument with each possible sentential form symbol index.

Can return an empty collection if no steps are possible.

Errors

Return a WrongProductionIndex error if the production index targets a nonexistent grammar production

Examples

use liblet::derivation::Derivation;
use liblet::grammar::grammar;
use liblet::symbol::symbol;

let g = grammar("A -> a");
let d = Derivation::new(g);

// get all possible steps for applying "A -> a"
// on the current sentential form (which is only 1),
// the step (0,0)
let possible_steps = d.possible_steps_by_prod(0)?;
assert_eq!(possible_steps.len(), 1);

pub fn possible_steps_by_index(
    self,
    index: usize
) -> Result<Vec<DerivationStep>, DerivationError>

Return a collection of steps, representing the possible steps from the current derivation state, based on trying to derive using the sentential form symbol index given as argument with each possible production of the grammar.

Can return an empty collection if no steps are possible.

Errors

Return a WrongIndex error if the sentential form symbol index is not in range of the sentential form symbol indexes.

Examples

use liblet::derivation::Derivation;
use liblet::grammar::grammar;
use liblet::symbol::symbol;

let g = grammar("A -> a");
let d = Derivation::new(g);

// get all possible steps starting from the 0°
// symbol of the sentential form ("A"), which is
// only 1, the step (0,0)
let possible_steps = d.possible_steps_by_index(0)?;
assert_eq!(possible_steps.len(), 1);

Trait Implementations

impl Clone for Derivation

fn clone(&self) -> Derivation

Returns a copy of the value.

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

Performs copy-assignment from source.

impl Debug for Derivation

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

Formats the value using the given formatter.

impl Display for Derivation

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

Formats the value using the given formatter.

impl Eq for Derivation

impl PartialEq<Derivation> for Derivation

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

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

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

This method tests for !=.

impl StructuralEq for Derivation

impl StructuralPartialEq for Derivation