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

/*
 * Copyright 2022 Arnaud Golfouse
 *
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */

//! Structures outputed by [`compute_table`](crate::compute_table).

pub mod error;
/// Contains [`Lookahead`].
mod lookahead;
/// Contains things related to [`State`], [`Item`] and [`Action`].
mod state;
mod statistics;

pub use self::{
    error::Error,
    lookahead::Lookahead,
    state::{Action, ActionTable, GotoTable, Item, State, StateIdx},
    statistics::Statistics,
};

use crate::{grammar_data::GrammarData, indices::StateIdxRaw, input::Node, structures::Map};
use std::collections::BTreeMap;

/// The parsing table generated by the [`IELR`](crate::compute_table) algorithm.
#[derive(Debug, Clone)]
pub struct Table {
    /// States of the parsing table.
    pub states: Vec<State>,
    /// For a node `n`, gives the index of the state on which to start to parse `n`.
    pub(crate) starting_states: BTreeMap<Node, StateIdx>,
}

impl Table {
    /// Get the starting state for `node` if the table can start here.
    pub fn get_starting_state(&self, node: Node) -> Option<StateIdx> {
        self.starting_states.get(&node).copied()
    }

    /// Get all possible starting nodes of this table, and their associated state.
    pub fn get_all_starts(&self) -> impl Iterator<Item = (Node, StateIdx)> + '_ {
        self.starting_states
            .iter()
            .map(|(node, state)| (*node, *state))
    }

    /// Fill all reduction information, based on items lookaheads.
    // TODO: merge the items that only differ by precedence annotations
    pub(crate) fn finish(&mut self, grammar_data: &GrammarData) {
        let end_states = {
            let mut end_states = Map::default();
            for (node, &state) in &self.starting_states {
                let state = &self.states[state];
                let end_state = state.goto_table[node];
                end_states.insert(end_state, *node);
            }
            end_states
        };
        for (state_idx, state) in self.states.iter_mut().enumerate() {
            let state_idx = StateIdx(state_idx as StateIdxRaw);
            let mut has_reduce_on_eof = false;
            for item in &mut state.items {
                let rhs = grammar_data.get_rhs(item.production).unwrap_or_default();
                if item.index as usize != rhs.len() {
                    continue;
                }
                for &lookahead in &item.lookaheads {
                    has_reduce_on_eof |= lookahead == Lookahead::Eof;
                    state
                        .action_table
                        .insert(lookahead, Action::Reduce(item.production));
                }
            }
            if let Some(&node) = end_states.get(&state_idx) {
                if has_reduce_on_eof {
                    todo!("handle reduce/accept conflicts")
                } else {
                    state
                        .action_table
                        .insert(Lookahead::Eof, Action::Accept(node));
                }
            }
        }
    }
}