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

//! Naive LR(1) generation algorithm.

use crate::grammar::repr::*;

mod build;
mod build_lalr;
pub mod codegen;
mod core;
mod error;
mod example;
mod first;
mod lane_table;
mod lookahead;
mod report;
mod state_graph;
mod tls;
mod trace;
use std::io::{self, Write};

#[cfg(test)]
mod interpret;

pub use self::core::{Lr1Result, Lr1TableConstructionError};
pub use self::error::report_error;
pub use self::tls::Lr1Tls;

pub fn build_states(grammar: &Grammar, start: NonterminalString) -> Lr1Result<'_> {
    let mut lr1_states = if !grammar.algorithm.lalr {
        build::build_lr1_states(grammar, start)?
    } else {
        build_lalr::build_lalr_states(grammar, start)?
    };

    rewrite_state_indices(grammar, &mut lr1_states);

    Ok(lr1_states)
}

pub fn generate_report<'grammar, W: Write + 'grammar>(
    out: &'grammar mut W,
    lr1result: &Lr1Result<'grammar>,
) -> io::Result<()> {
    report::generate_report(out, lr1result)
}

/// By packing all states which start a reduction we can generate a smaller goto table as any
/// states not starting a reduction will not need a row
fn rewrite_state_indices(grammar: &Grammar, states: &mut [core::Lr1State]) {
    let mut start_states = vec![false; states.len()];
    for (index, state) in states.iter_mut().enumerate() {
        debug_assert!(state.index.0 == index);
        if grammar
            .nonterminals
            .keys()
            .any(|nonterminal| state.gotos.get(nonterminal).is_some())
        {
            start_states[index] = true;
        }
    }

    // Since the sort is stable and we put starting states first, the initial state is still 0
    states.sort_by_key(|state| !start_states[state.index.0]);

    let mut state_rewrite = vec![0; states.len()];
    for (new_index, state) in states.iter_mut().enumerate() {
        state_rewrite[state.index.0] = new_index;
        state.index.0 = new_index;
    }

    for state in states {
        for goto in state.gotos.values_mut() {
            goto.0 = state_rewrite[goto.0];
        }
        for shift in state.shifts.values_mut() {
            shift.0 = state_rewrite[shift.0];
        }
    }
}