lalr 0.0.2

a library for creating LALR(1) parsers from context-free grammars
Documentation 
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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

use super::*;
use std::collections::BTreeMap;

macro_rules! map {
    ($($l: expr => $r: expr),*) => ({
        let mut r = BTreeMap::new();
        $(r.insert($l, $r);)*
        r
    });
}

macro_rules! coll {
    ($($x: expr),*) => (vec!($($x),*).into_iter().collect());
    () => (None.into_iter().collect());
}

fn rhs<T, N, A>(syms: Vec<Symbol<T, N>>, act: A) -> Rhs<T, N, A> {
    Rhs {
        syms: syms,
        act: act,
    }
}

fn grammar() -> Grammar<&'static str, &'static str, ()> {
    Grammar {
        rules: map![
            "S" => vec![
                rhs(vec![Nonterminal("N")], ()),
            ],
            "N" => vec![
                rhs(vec![Nonterminal("V"), Terminal("="), Nonterminal("E")], ()),
                rhs(vec![Nonterminal("E")], ()),
            ],
            "E" => vec![
                rhs(vec![Nonterminal("V")], ()),
            ],
            "V" => vec![
                rhs(vec![Terminal("x")], ()),
                rhs(vec![Terminal("*"), Nonterminal("E")], ()),
            ]
        ],
        start: "S"
    }
}

static S: &'static &'static str = &"S";
static N: &'static &'static str = &"N";
static E: &'static &'static str = &"E";
static V: &'static &'static str = &"V";
static X: &'static &'static str = &"x";
static STAR: &'static &'static str = &"*";
static EQ: &'static &'static str = &"=";

#[test]
fn test_first_sets() {
    let g = grammar();
    assert_eq!(g.first_sets(), map! {
        S => (coll![X, STAR], false),
        N => (coll![X, STAR], false),
        E => (coll![X, STAR], false),
        V => (coll![X, STAR], false)
    });
}

#[test]
fn test_follow_sets() {
    let g = grammar();
    assert_eq!(g.follow_sets(g.first_sets()), map! {
        S => (coll![], true),
        N => (coll![], true),
        E => (coll![EQ], true),
        V => (coll![EQ], true)
    });
}

#[test]
fn test_extended_grammar() {
    let g = grammar();
    let state_machine = g.lr0_state_machine();
    let extended = state_machine.extended_grammar();
    assert_eq!(extended.start.1, S);
    // Too difficult to test the actual output so just do a sanity check
    assert_eq!(extended.rules.len(), 8);
    let total: usize = extended.rules.values().map(|rhss| rhss.len()).fold(0, |x, y| x + y);
    assert_eq!(total, 12);
}

#[test]
fn test_lalr1() {
    let g = grammar();
    // FIXME: write a test
    assert!(g.lalr1(|_, _| true, |_, _| 0).is_ok());
}