ielr 0.1.1

Table generation backend for LR parser generators
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

/*
 * 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/.
 */

//! Errors while generating the LR table.

use super::{Lookahead, StateIdx};
use crate::input::{Node, ProdIdx};

/// An error occured while generating the LR table.
#[derive(Clone, Debug)]
pub enum Error {
    /// The algorithm  generated too many states.
    StatesOverflow,
    /// The grammar derives `node ⇒+ node` for some `node`.
    CycleError(CycleError),
    /// There is at least one LR conflict in the grammar.
    Conflict {
        /// LALR tables.
        ///
        /// Those can be used to gather context about the conflict.
        lalr_tables: super::Table,
        /// State in which the conflict occured.
        ///
        /// Used to access a [`State`](super::State) in the
        /// [LALR tables](Self::Conflict::lalr_tables).
        state: StateIdx,
        /// Conflict in [state](Self::Conflict::state) between multiple possible
        /// [`Action`](super::Action).
        conflict: Conflict,
    },
}

impl From<crate::lr::StatesOverflow> for Error {
    fn from(_: crate::lr::StatesOverflow) -> Self {
        Self::StatesOverflow
    }
}

/// The grammar derives `node ⇒+ node` for some `node`.
///
/// Note that this is only one example of such a derivation in the grammar: other may
/// exist.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct CycleError {
    /// The node that can derive itself.
    pub node: Node,
    /// The productions to follow in order to derive `node ⇒+ node`.
    ///
    /// This does not contains the productions necessary to nullate some nodes.
    pub path: Vec<ProdIdx>,
}

impl From<CycleError> for Error {
    fn from(err: CycleError) -> Self {
        Self::CycleError(err)
    }
}

/// The table contains a conflict between various possible actions.
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct Conflict {
    /// The lookahead on which the conflict occurs.
    pub lookahead: Lookahead,
    /// The various possible actions on `lookahead`, that conflict with one another.
    pub contributions: ConflictContributions,
}

/// Possible actions in a [`Conflict`].
#[derive(Clone, Debug, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub struct ConflictContributions {
    /// `true` if the conflict has a 'shift' contributions.
    ///
    /// Else, the conflict only has 'reduce' contributions.
    pub has_shift: bool,
    /// Reduce contributions of the conflict, in the form of the associated production
    /// to reduce.
    ///
    /// Contains at least one element.
    // NOTE: since those come from a state, the length of this Vec is bounded by both
    // `ProdIdxRaw` and `ItemIdx`
    pub reduces: Vec<ProdIdx>,
}

impl ConflictContributions {
    /// Get the number of contributions to the conflict.
    ///
    /// This is `self.reduces.len()` if `self.has_shift` is false, and
    /// `self.reduces.len() + 1` else.
    #[allow(clippy::len_without_is_empty)]
    pub fn len(&self) -> usize {
        let mut len = self.reduces.len();
        if self.has_shift {
            len += 1;
        }
        len
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn conflict_contributions_len() {
        let conflict_contributions = ConflictContributions {
            has_shift: true,
            reduces: vec![
                ProdIdx {
                    lhs: Node(0),
                    index: 0,
                },
                ProdIdx {
                    lhs: Node(0),
                    index: 1,
                },
            ],
        };
        assert_eq!(conflict_contributions.len(), 3);
        let conflict_contributions = ConflictContributions {
            has_shift: false,
            reduces: vec![
                ProdIdx {
                    lhs: Node(0),
                    index: 0,
                },
                ProdIdx {
                    lhs: Node(0),
                    index: 1,
                },
            ],
        };
        assert_eq!(conflict_contributions.len(), 2);
    }
}