lalrpop 0.12.2

convenient LR(1) parser generator
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124

//! The "Lane Table". In the paper, this is depicted like so:
//!
//! ```
//! +-------+----+-----+----+------------+
//! + State | C1 | ... | Cn | Successors |
//! +-------+----+-----+----+------------+
//! ```
//!
//! where each row summarizes some state that potentially contributes
//! lookahead to the conflict. The columns `Ci` represent each of the
//! conflicts we are trying to disentangle; their values are each
//! `TokenSet` indicating the lookahead contributing by this state.
//! The Successors is a vector of further successors. For simplicity
//! though we store this using maps, at least for now.

use collections::{Map, Multimap, Set};
use grammar::repr::*;
use lr1::core::*;
use lr1::lookahead::*;
use std::default::Default;
use std::fmt::{Debug, Error, Formatter};
use std::iter;

#[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq)]
pub struct ConflictIndex {
    index: usize,
}

impl ConflictIndex {
    pub fn new(index: usize) -> ConflictIndex {
        ConflictIndex { index: index }
    }
}

pub struct LaneTable<'grammar> {
    _grammar: &'grammar Grammar,
    conflicts: usize,
    lookaheads: Map<(StateIndex, ConflictIndex), TokenSet>,
    successors: Multimap<StateIndex, Set<StateIndex>>,
}

impl<'grammar> LaneTable<'grammar> {
    pub fn new(grammar: &'grammar Grammar, conflicts: usize) -> LaneTable {
        LaneTable {
            _grammar: grammar,
            conflicts: conflicts,
            lookaheads: Map::default(),
            successors: Multimap::default(),
        }
    }

    pub fn add_lookahead(&mut self,
                         state: StateIndex,
                         conflict: ConflictIndex,
                         tokens: &TokenSet) {
        self.lookaheads
            .entry((state, conflict))
            .or_insert_with(|| TokenSet::new())
            .union_with(&tokens);
    }

    pub fn add_successor(&mut self, state: StateIndex, succ: StateIndex) {
        self.successors.push(state, succ);
    }
}

impl<'grammar> Debug for LaneTable<'grammar> {
    fn fmt(&self, fmt: &mut Formatter) -> Result<(), Error> {
        let indices: Set<StateIndex> = self.lookaheads
                                           .keys()
                                           .map(|&(state, _)| state)
                                           .chain(self.successors
                                                      .iter()
                                                      .map(|(key, _)| key.clone()))
                                           .collect();

        let header = iter::once(format!("State"))
                         .chain((0..self.conflicts).map(|i| format!("C{}", i)))
                         .chain(Some(format!("Successors")))
                         .collect();

        let rows = indices.iter().map(|&index| {
            iter::once(format!("{:?}", index))
                .chain((0..self.conflicts).map(|i| {
                    self.lookaheads
                        .get(&(index, ConflictIndex::new(i)))
                        .map(|token_set| format!("{:?}", token_set))
                        .unwrap_or(String::new())
                }))
                .chain(Some(self.successors
                                .get(&index)
                                .map(|c| format!("{:?}", c))
                                .unwrap_or(String::new())))
                .collect()
        });

        let table: Vec<Vec<_>> = iter::once(header).chain(rows).collect();

        let columns = 2 + self.conflicts;

        let widths: Vec<_> = (0..columns)
                                 .map(|c| {
                                     // find the max width of any row at this column
                                     table.iter()
                                          .map(|r| r[c].len())
                                          .max()
                                          .unwrap()
                                 })
                                 .collect();

        for row in &table {
            try!(write!(fmt, "| "));
            for (i, column) in row.iter().enumerate() {
                if i > 0 {
                    try!(write!(fmt, " | "));
                }
                try!(write!(fmt, "{0:1$}", column, widths[i]));
            }
            try!(write!(fmt, " |\n"));
        }

        Ok(())
    }
}