Crate glr

Expand description

Right nulled GLR (RNGLR) parser.

§Example

This example shows building a parser for the grammar

S → S S
S → a
S → ε

and using it to parse the input string a:

use glr::{lalr, Grammar, Parser};
let grammar = Grammar {
    num_symbols: 2,
    nonterminals: &[vec![vec![0, 0], vec![1], Vec::new()]],
};
let table = lalr::Table::new(&grammar);
let (sppf, root) = Parser::new(&grammar, &table)
    .parse([1])
    .ok_or("Failed to parse")?;

// The family of the root node is three alternative lists of children
let family: Vec<_> = root.family(&sppf).collect();
// Either a single `a`;
assert_eq!(family[0][0].symbol(&sppf), Ok(1));
// left-recursion; or
assert_eq!(family[1][0], root);
assert_eq!(family[1][1].symbol(&sppf), Err(&[0][..]));
// right recursion.
assert_eq!(family[2][0].symbol(&sppf), Ok(0));
assert_eq!(family[2][1], root);

Any one of the infinitely many derivation trees can be recovered by unwinding the cycles the right number of times.

See: SCOTT, Elizabeth; JOHNSTONE, Adrian. Right nulled GLR parsers. ACM Transactions on Programming Languages and Systems (TOPLAS), 2006, 28.4: 577-618.

Modules§

lalr: LALR(1) parser generator.

Structs§

Grammar: Context-free grammar.
Parser: GLR parser.
Production
Sppf: Shared packed parse forest.

Enums§

SppfNode: A sub-tree in the SPPF.

Type Aliases§