Skip to content

parsing_table

LR0ParsingTable

Table that contains all the transitions from state to state with a symbol.

Source code in src/syntactes/parsing_table/table.py 
 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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
class LR0ParsingTable:
    """
    Table that contains all the transitions from state to state with a symbol.
    """

    def __init__(self, grammar: Grammar) -> None:
        self.rows: dict[LR0State, Row] = {}
        self._grammar = grammar
        self._initial_state: LR0State | None = None

    @classmethod
    def from_entries(cls, entries: Iterable[Entry], grammar: Grammar) -> Self:
        """
        Create a parsing table from the given entries.
        """
        table = cls(grammar)
        for entry in entries:
            table.add_entry(entry)
        return table

    @property
    def grammar(self) -> Grammar:
        """
        The grammar the table was created for.
        """
        return self._grammar

    @property
    def initial_state(self) -> LR0State:
        """
        The state the parser starts from, i.e. the state with number 1.
        Raises `ValueError` if the table has no entries from that state.
        """
        if self._initial_state is None:
            raise ValueError("parsing table has no initial state")

        return self._initial_state

    def get_actions(self, state: LR0State, token: Token) -> list[Action] | None:
        """
        Get the actions from state with given number with `token`.
        If there are no actions, returns None.
        """
        return self.rows.get(state, {}).get(token, None)

    def get(self, state: LR0State) -> Row | None:
        """
        Get the mapping of tokens to actions for the given state number.
        Returns None if the state is not found.
        """
        return self.rows.get(state, None)

    def add_entry(self, entry: Entry) -> None:
        """
        Adds an entry to the parsing table.
        """
        if entry.from_state.number == 1:
            self._initial_state = entry.from_state

        row = self.rows.setdefault(entry.from_state, {})
        actions = row.setdefault(entry.token, [])
        actions.append(entry.action)

    def pretty_str(self) -> str:
        """
        Returns a pretty-formatted string representation of the table.
        """
        return self._rules_pretty_str() + "\n\n" + self._table_pretty_str()

    def conflicts(self) -> list[Conflict]:
        """
        Retuns a list with all the conflicts in the parsing table.
        """
        conflicts = []
        for state, row in self.rows.items():
            for token, actions in row.items():
                if len(actions) > 1:
                    conflicts.append(Conflict(state, token, actions))

        return conflicts

    def _rules_pretty_str(self) -> str:
        rules = [f"{rule.number}. {rule}" for rule in self._grammar.rules]
        line = "-" * max(map(len, rules))

        return "\n".join(["GRAMMAR RULES", line, *rules, line])

    def _table_pretty_str(self) -> str:
        # ε is never an input token, so its column would always be empty.
        tokens = sorted(t for t in self._grammar.tokens if t != Token.null())

        header = ["", *map(str, tokens)]
        rows = [header]
        for state, row in sorted(self.rows.items(), key=lambda r: r[0].number or 0):
            cells = [str(state.number)]
            for token in tokens:
                actions = row.get(token, [])
                cells.append(",".join(map(str, actions)) if actions else "--")

            rows.append(cells)

        widths = [max(len(row[i]) for row in rows) for i in range(len(header))]
        lines = [
            "|" + "|".join(f"  {cell:<{w}}  " for cell, w in zip(row, widths)) + "|"
            for row in rows
        ]
        separator = "-" * len(lines[0])

        table = [self._header_str(), separator]
        for line in lines:
            table += [line, separator]

        return "\n".join(table) + "\n"

    def _header_str(self) -> str:
        return "LR0 PARSING TABLE"

grammar property

The grammar the table was created for.

initial_state property

The state the parser starts from, i.e. the state with number 1. Raises ValueError if the table has no entries from that state.

add_entry(entry)

Adds an entry to the parsing table.

Source code in src/syntactes/parsing_table/table.py 
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
def add_entry(self, entry: Entry) -> None:
    """
    Adds an entry to the parsing table.
    """
    if entry.from_state.number == 1:
        self._initial_state = entry.from_state

    row = self.rows.setdefault(entry.from_state, {})
    actions = row.setdefault(entry.token, [])
    actions.append(entry.action)

conflicts()

Retuns a list with all the conflicts in the parsing table.

Source code in src/syntactes/parsing_table/table.py 
108
109
110
111
112
113
114
115
116
117
118
def conflicts(self) -> list[Conflict]:
    """
    Retuns a list with all the conflicts in the parsing table.
    """
    conflicts = []
    for state, row in self.rows.items():
        for token, actions in row.items():
            if len(actions) > 1:
                conflicts.append(Conflict(state, token, actions))

    return conflicts

from_entries(entries, grammar) classmethod

Create a parsing table from the given entries.

Source code in src/syntactes/parsing_table/table.py 
49
50
51
52
53
54
55
56
57
@classmethod
def from_entries(cls, entries: Iterable[Entry], grammar: Grammar) -> Self:
    """
    Create a parsing table from the given entries.
    """
    table = cls(grammar)
    for entry in entries:
        table.add_entry(entry)
    return table

get(state)

Get the mapping of tokens to actions for the given state number. Returns None if the state is not found.

Source code in src/syntactes/parsing_table/table.py 
84
85
86
87
88
89
def get(self, state: LR0State) -> Row | None:
    """
    Get the mapping of tokens to actions for the given state number.
    Returns None if the state is not found.
    """
    return self.rows.get(state, None)

get_actions(state, token)

Get the actions from state with given number with token. If there are no actions, returns None.

Source code in src/syntactes/parsing_table/table.py 
77
78
79
80
81
82
def get_actions(self, state: LR0State, token: Token) -> list[Action] | None:
    """
    Get the actions from state with given number with `token`.
    If there are no actions, returns None.
    """
    return self.rows.get(state, {}).get(token, None)

pretty_str()

Returns a pretty-formatted string representation of the table.

Source code in src/syntactes/parsing_table/table.py 
102
103
104
105
106
def pretty_str(self) -> str:
    """
    Returns a pretty-formatted string representation of the table.
    """
    return self._rules_pretty_str() + "\n\n" + self._table_pretty_str()

LR1ParsingTable

Bases: LR0ParsingTable

Table that contains all the transitions from state to state with a symbol.

Source code in src/syntactes/parsing_table/table.py 
166
167
168
169
170
171
172
class LR1ParsingTable(LR0ParsingTable):
    """
    Table that contains all the transitions from state to state with a symbol.
    """

    def _header_str(self) -> str:
        return "LR1 PARSING TABLE"

ParsingTable

Bases: Protocol

The interface of the parsing tables that generators create and parsers use.

Source code in src/syntactes/parsing_table/table.py 
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
class ParsingTable(Protocol):
    """
    The interface of the parsing tables that generators create and parsers use.
    """

    rows: dict[LR0State, Row]

    @property
    def grammar(self) -> Grammar: ...

    @property
    def initial_state(self) -> LR0State: ...

    @classmethod
    def from_entries(
        cls, entries: Iterable[Entry], grammar: Grammar
    ) -> "ParsingTable": ...

    def get(self, state: LR0State) -> Row | None: ...

    def get_actions(self, state: LR0State, token: Token) -> list[Action] | None: ...

    def pretty_str(self) -> str: ...

    def conflicts(self) -> list[Conflict]: ...

SLRParsingTable

Bases: LR0ParsingTable

Table that contains all the transitions from state to state with a symbol.

Source code in src/syntactes/parsing_table/table.py 
157
158
159
160
161
162
163
class SLRParsingTable(LR0ParsingTable):
    """
    Table that contains all the transitions from state to state with a symbol.
    """

    def _header_str(self) -> str:
        return "SLR PARSING TABLE"

Entry

An entry of the parsing table. Holds the information of a transition from a state to another state via a symbol.

Source code in src/syntactes/parsing_table/entry.py 
 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
class Entry:
    """
    An entry of the parsing table. Holds the information of a transition from
    a state to another state via a symbol.
    """

    def __init__(self, from_state: LR0State, token: Token, action: Action) -> None:
        self.from_state = from_state
        self.token = token
        self.action = action

    def __repr__(self) -> str:
        return f"<Entry: {self!s}>"

    def __str__(self) -> str:
        return f"{self.from_state.number}, {self.action}, {self.token}"

    def __hash__(self) -> int:
        return hash((self.from_state, self.token, self.action))

    def __eq__(self, other) -> bool:
        if not isinstance(other, Entry):
            return False

        return (
            self.from_state == other.from_state
            and self.token == other.token
            and self.action == other.action
        )

Conflict

A cell of a parsing table with more than one action: the actions for token in state.

Source code in src/syntactes/parsing_table/conflict.py 
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
class Conflict:
    """
    A cell of a parsing table with more than one action: the `actions` for
    `token` in `state`.
    """

    def __init__(self, state: LR0State, token: Token, actions: list[Action]) -> None:
        self.state = state
        self.token = token
        self.actions = actions
        self._conflict_type = None

    def pretty_str(self) -> str:
        """
        Returns a pretty-formatted string with conflict details.
        """
        string = f"{self.conflict_type.value} conflict in state {self.state}\n"
        string += f"Available actions on input token '{self.token}':\n"
        for action in self.actions:
            if action.action_type == ActionType.SHIFT:
                string += f"shift to {action.actionable}\n"
            elif action.action_type == ActionType.REDUCE:
                string += f"reduce by {action.actionable}\n"
            else:
                string += f"{action.action_type}, {action.actionable}\n"

        return string

    @property
    def conflict_type(self) -> ConflictType:
        """
        The kind of the conflict, from the types of its actions.
        """
        if self._conflict_type is None:
            self._conflict_type = self._create_type()

        return self._conflict_type

    def _create_type(self) -> ConflictType:
        if not len(self.actions) > 1:
            return ConflictType.NO_CONFLICT

        action_types = {a.action_type for a in self.actions}

        if ActionType.SHIFT not in action_types:
            if ActionType.REDUCE not in action_types:
                return ConflictType.NO_CONFLICT

            return ConflictType.REDUCE_REDUCE

        if ActionType.REDUCE not in action_types:
            return ConflictType.SHIFT_SHIFT

        return ConflictType.SHIFT_REDUCE

    def __repr__(self) -> str:
        return f"<Conflict: {self!s}>"

    def __str__(self) -> str:
        return f"{self.state}, {self.token}, {self.actions}"

conflict_type property

The kind of the conflict, from the types of its actions.

pretty_str()

Returns a pretty-formatted string with conflict details.

Source code in src/syntactes/parsing_table/conflict.py 
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def pretty_str(self) -> str:
    """
    Returns a pretty-formatted string with conflict details.
    """
    string = f"{self.conflict_type.value} conflict in state {self.state}\n"
    string += f"Available actions on input token '{self.token}':\n"
    for action in self.actions:
        if action.action_type == ActionType.SHIFT:
            string += f"shift to {action.actionable}\n"
        elif action.action_type == ActionType.REDUCE:
            string += f"reduce by {action.actionable}\n"
        else:
            string += f"{action.action_type}, {action.actionable}\n"

    return string

ConflictType

Bases: Enum

The kinds of actions that conflict in a cell of a parsing table.

Source code in src/syntactes/parsing_table/conflict.py 
 8
 9
10
11
12
13
14
15
16
class ConflictType(Enum):
    """
    The kinds of actions that conflict in a cell of a parsing table.
    """

    SHIFT_SHIFT = "shift/shift"
    SHIFT_REDUCE = "shift/reduce"
    REDUCE_REDUCE = "reduce/reduce"
    NO_CONFLICT = "NO_CONFLICT"