Skip to content

parser

LR0Parser

Bases: Parser

Parser that uses an LR0 parsing table.

Source code in src/syntactes/parser/parser.py 
206
207
208
209
210
211
class LR0Parser(Parser):
    """
    Parser that uses an LR0 parsing table.
    """

    generator_cls = LR0Generator

LR1Parser

Bases: Parser

Parser that uses an LR1 parsing table.

Source code in src/syntactes/parser/parser.py 
222
223
224
225
226
227
class LR1Parser(Parser):
    """
    Parser that uses an LR1 parsing table.
    """

    generator_cls = LR1Generator

Parser

Bases: ABC

Base class of the LR parsers. Parses a stream of tokens with a parsing table, and on each reduction computes the rule's value: with the callback registered with execute_on, else with the rule's primitive from the grammar.

Source code in src/syntactes/parser/parser.py 
 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
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
class Parser(ABC):
    """
    Base class of the LR parsers. Parses a stream of tokens with a parsing table,
    and on each reduction computes the rule's value: with the callback registered
    with `execute_on`, else with the rule's primitive from the grammar.
    """

    generator_cls: type

    def __init__(self, table: ParsingTable) -> None:
        self._table = table
        self._executables: dict[Rule, Executable] = {}

    @classmethod
    def from_grammar(cls, grammar: Grammar) -> "Parser":
        """
        Create a parser for the given grammar.
        """
        generator = cls.generator_cls(grammar)
        parsing_table = generator.generate()
        parser = cls(parsing_table)
        return parser

    def execute_on[F: Executable](self, rule: Rule) -> Callable[[F], F]:
        """
        Decorate a function to be executed when this parser reduces by `rule`.

        The function is called with one token per right-hand side symbol of the
        rule, and returns the value of the left-hand side token. The decorated
        function is returned unchanged.

        Raises `ValueError` if `rule` is not a rule of the parser's grammar.
        """
        if rule not in self._table.grammar.rules:
            raise ValueError(f"Rule '{rule}' is not in the parser's grammar.")

        def executable_decorator(executable_fn: F) -> F:
            self._executables[rule] = executable_fn
            return executable_fn

        return executable_decorator

    def parse(self, stream: Iterable[Token]) -> object:
        """
        Parses the given stream of tokens. Expects the EOF token as the last one.

        On each reduction the rule's value becomes the `value` of the token
        pushed for the left-hand side. The value is, in order of precedence:

        - what the callback registered for the rule returns, called with one
          token per right-hand side symbol, in order;
        - the result of the rule's primitive (`Grammar.primitives`): a binary
          operation gets the values of the tokens at `Grammar.operands`, `None`
          gives None, and any other primitive converts its single token's value;
        - the value of the rule's token, if it has exactly one;
        - None.

        On accept the starting rule's value is computed the same way, from its
        right-hand side tokens except the trailing EOF, and returned. So a
        starting rule with neither a callback nor a primitive returns the start
        symbol's value.

        Raises `syntactes.parser.PrimitiveError` if a primitive raises, with the
        original exception as its cause. Exceptions raised by callbacks
        propagate unchanged.

        Raises `syntactes.parser.UnexpectedTokenError` if an unexpected token is
        received.

        Raises `syntactes.parser.NotAcceptedError` if the stream of tokens ends
        before the parser receives an accept action.
        """
        states: list[LR0State] = [self._table.initial_state]
        tokens: list[Token] = []

        tokens_in = iter(stream)
        token = next(tokens_in, None)

        while token is not None:
            action = self._get_action(states[-1], token)

            if action.action_type == ActionType.SHIFT:
                tokens.append(token)
                states.append(cast(LR0State, action.actionable))
                token = next(tokens_in, None)
            elif action.action_type == ActionType.REDUCE:
                # Reduce actions do not consume the token.
                rule = cast(Rule, action.actionable)
                rhs_len = 0 if rule.is_empty() else rule.rhs_len
                args = self._pop(tokens, rhs_len)
                self._pop(states, rhs_len)

                value = self._value(rule, args)

                tokens.append(Token(rule.lhs.symbol, False, value))
                shift = self._get_action(states[-1], rule.lhs)
                states.append(cast(LR0State, shift.actionable))
            elif action.action_type == ActionType.ACCEPT:
                extra = next(tokens_in, None)
                if extra is not None:
                    raise UnexpectedTokenError(extra, [])

                starting_rule = self._table.grammar.starting_rule
                args = self._pop(tokens, starting_rule.rhs_len - 1)
                return self._value(starting_rule, args)

        raise NotAcceptedError("Expected EOF token. ")

    def _value(self, rule: Rule, tokens: list[Token]) -> object:
        """
        Computes the value of `rule` from its right-hand side tokens: with its
        callback, else its primitive, else its single token's value, else None.
        """
        executable = self._executables.get(rule)
        if executable is not None:
            return executable(*tokens)

        primitive = self._table.grammar.primitives.get(rule)
        if primitive is not None:
            return self._apply(rule, primitive, tokens)

        if len(tokens) == 1:
            return tokens[0].value

        return None

    def _apply(self, rule: Rule, primitive: Primitive, tokens: list[Token]) -> object:
        try:
            if _is_binary(primitive):
                left, right = self._table.grammar.operands[rule]
                return primitive(tokens[left - 1].value, tokens[right - 1].value)

            if primitive is NoneType:
                return None

            return primitive(tokens[0].value)
        except Exception as e:
            raise PrimitiveError(rule, primitive) from e

    @staticmethod
    def _pop[T](stack: list[T], count: int) -> list[T]:
        """
        Pops the top `count` elements of the stack and returns them in stack order.
        """
        popped = stack[len(stack) - count :]
        del stack[len(stack) - count :]
        return popped

    def _get_action(self, state: LR0State, token: Token) -> Action:
        actions = self._table.get_actions(state, token)
        if actions is None:
            raise UnexpectedTokenError(token, self._expected_tokens(state))

        return self._resolve_conflict(actions)

    def _expected_tokens(self, state: LR0State) -> list[Token]:
        """
        Returns the terminals that have an action in the given state, sorted.
        """
        row = self._table.get(state) or {}
        return sorted(token for token in row if token.is_terminal)

    def _resolve_conflict(self, actions: list[Action]) -> Action:
        """
        Picks one of the actions of a table cell. Accept wins over shift, shift
        wins over reduce, and among reduces the lowest rule number wins.
        """
        return min(actions, key=self._action_priority)

    @staticmethod
    def _action_priority(action: Action) -> tuple[int, int]:
        if action.action_type == ActionType.ACCEPT:
            return (0, 0)

        if action.action_type == ActionType.SHIFT:
            return (1, 0)

        return (2, cast(Rule, action.actionable).number)

execute_on(rule)

Decorate a function to be executed when this parser reduces by rule.

The function is called with one token per right-hand side symbol of the rule, and returns the value of the left-hand side token. The decorated function is returned unchanged.

Raises ValueError if rule is not a rule of the parser's grammar.

Source code in src/syntactes/parser/parser.py 
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
def execute_on[F: Executable](self, rule: Rule) -> Callable[[F], F]:
    """
    Decorate a function to be executed when this parser reduces by `rule`.

    The function is called with one token per right-hand side symbol of the
    rule, and returns the value of the left-hand side token. The decorated
    function is returned unchanged.

    Raises `ValueError` if `rule` is not a rule of the parser's grammar.
    """
    if rule not in self._table.grammar.rules:
        raise ValueError(f"Rule '{rule}' is not in the parser's grammar.")

    def executable_decorator(executable_fn: F) -> F:
        self._executables[rule] = executable_fn
        return executable_fn

    return executable_decorator

from_grammar(grammar) classmethod

Create a parser for the given grammar.

Source code in src/syntactes/parser/parser.py 
39
40
41
42
43
44
45
46
47
@classmethod
def from_grammar(cls, grammar: Grammar) -> "Parser":
    """
    Create a parser for the given grammar.
    """
    generator = cls.generator_cls(grammar)
    parsing_table = generator.generate()
    parser = cls(parsing_table)
    return parser

parse(stream)

Parses the given stream of tokens. Expects the EOF token as the last one.

On each reduction the rule's value becomes the value of the token pushed for the left-hand side. The value is, in order of precedence:

  • what the callback registered for the rule returns, called with one token per right-hand side symbol, in order;
  • the result of the rule's primitive (Grammar.primitives): a binary operation gets the values of the tokens at Grammar.operands, None gives None, and any other primitive converts its single token's value;
  • the value of the rule's token, if it has exactly one;
  • None.

On accept the starting rule's value is computed the same way, from its right-hand side tokens except the trailing EOF, and returned. So a starting rule with neither a callback nor a primitive returns the start symbol's value.

Raises syntactes.parser.PrimitiveError if a primitive raises, with the original exception as its cause. Exceptions raised by callbacks propagate unchanged.

Raises syntactes.parser.UnexpectedTokenError if an unexpected token is received.

Raises syntactes.parser.NotAcceptedError if the stream of tokens ends before the parser receives an accept action.

Source code in src/syntactes/parser/parser.py 
 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
def parse(self, stream: Iterable[Token]) -> object:
    """
    Parses the given stream of tokens. Expects the EOF token as the last one.

    On each reduction the rule's value becomes the `value` of the token
    pushed for the left-hand side. The value is, in order of precedence:

    - what the callback registered for the rule returns, called with one
      token per right-hand side symbol, in order;
    - the result of the rule's primitive (`Grammar.primitives`): a binary
      operation gets the values of the tokens at `Grammar.operands`, `None`
      gives None, and any other primitive converts its single token's value;
    - the value of the rule's token, if it has exactly one;
    - None.

    On accept the starting rule's value is computed the same way, from its
    right-hand side tokens except the trailing EOF, and returned. So a
    starting rule with neither a callback nor a primitive returns the start
    symbol's value.

    Raises `syntactes.parser.PrimitiveError` if a primitive raises, with the
    original exception as its cause. Exceptions raised by callbacks
    propagate unchanged.

    Raises `syntactes.parser.UnexpectedTokenError` if an unexpected token is
    received.

    Raises `syntactes.parser.NotAcceptedError` if the stream of tokens ends
    before the parser receives an accept action.
    """
    states: list[LR0State] = [self._table.initial_state]
    tokens: list[Token] = []

    tokens_in = iter(stream)
    token = next(tokens_in, None)

    while token is not None:
        action = self._get_action(states[-1], token)

        if action.action_type == ActionType.SHIFT:
            tokens.append(token)
            states.append(cast(LR0State, action.actionable))
            token = next(tokens_in, None)
        elif action.action_type == ActionType.REDUCE:
            # Reduce actions do not consume the token.
            rule = cast(Rule, action.actionable)
            rhs_len = 0 if rule.is_empty() else rule.rhs_len
            args = self._pop(tokens, rhs_len)
            self._pop(states, rhs_len)

            value = self._value(rule, args)

            tokens.append(Token(rule.lhs.symbol, False, value))
            shift = self._get_action(states[-1], rule.lhs)
            states.append(cast(LR0State, shift.actionable))
        elif action.action_type == ActionType.ACCEPT:
            extra = next(tokens_in, None)
            if extra is not None:
                raise UnexpectedTokenError(extra, [])

            starting_rule = self._table.grammar.starting_rule
            args = self._pop(tokens, starting_rule.rhs_len - 1)
            return self._value(starting_rule, args)

    raise NotAcceptedError("Expected EOF token. ")

SLRParser

Bases: Parser

Parser that uses an SLR parsing table.

Source code in src/syntactes/parser/parser.py 
214
215
216
217
218
219
class SLRParser(Parser):
    """
    Parser that uses an SLR parsing table.
    """

    generator_cls = SLRGenerator

NotAcceptedError

Bases: ParserError

The parser did not receive an accept action. The stream of tokens is syntactically invalid.

Source code in src/syntactes/parser/exception.py 
24
25
26
27
28
class NotAcceptedError(ParserError):
    """
    The parser did not receive an accept action. The stream of tokens is
    syntactically invalid.
    """

ParserError

Bases: Exception

Base class of the errors raised by parse().

Source code in src/syntactes/parser/exception.py 
5
6
7
8
class ParserError(Exception):
    """
    Base class of the errors raised by `parse()`.
    """

PrimitiveError

Bases: ParserError

A rule's primitive raised while the parser applied it, e.g. int on a token whose value isn't a number. The rule and primitive are available as rule and primitive, and the original exception as __cause__.

Source code in src/syntactes/parser/exception.py 
31
32
33
34
35
36
37
38
39
40
41
class PrimitiveError(ParserError):
    """
    A rule's primitive raised while the parser applied it, e.g. `int` on a
    token whose value isn't a number. The rule and primitive are available as
    `rule` and `primitive`, and the original exception as `__cause__`.
    """

    def __init__(self, rule: Rule, primitive: Primitive) -> None:
        self.rule = rule
        self.primitive = primitive
        super().__init__(f"Primitive {primitive.string()} of rule '{rule}' failed.")

UnexpectedTokenError

Bases: ParserError

A token was received that does not map to an action. The stream of tokens is syntactically invalid.

Source code in src/syntactes/parser/exception.py 
11
12
13
14
15
16
17
18
19
20
21
class UnexpectedTokenError(ParserError):
    """
    A token was received that does not map to an action. The stream of tokens
    is syntactically invalid.
    """

    def __init__(self, received_token, expected_tokens):
        self.received_token = received_token
        self.expected_tokens = expected_tokens
        msg = f"Received token: {received_token}; expected one of: {[str(e) for e in expected_tokens]}"
        super().__init__(msg)