Quelle  rewrites.py   Sprache: Python

"""Early-pipeline operations that error-check and lower grammars."""

from __future__ import annotations
# mypy: disallow-untyped-defs, disallow-incomplete-defs, disallow-untyped-calls

import collections
import dataclasses
from dataclasses import dataclass
import typing

from .grammar import (CallMethod, Element, End, ErrorSymbol, Exclude, Grammar,
                      LenientNt, Literal, LookaheadRule, Optional,
                      NoLineTerminatorHere, Nt, NtDef, NtParameter, Production,
                      ReduceExpr, ReduceExprOrAccept, Some, UnicodeCategory,
                      Var, is_concrete_element)
from .ordered import OrderedFrozenSet, OrderedSet
from .runtime import ErrorToken, ErrorTokenClass


# *** Checking for errors *****************************************************

T = typing.TypeVar("T")


def fix(f: typing.Callable[[T], T], start: T) -> T:
    """Compute a fixed point of `f`, the hard way, starting from `start`."""
    prev, current = start, f(start)
    while current != prev:
        prev, current = current, f(current)
    return current


def empty_nt_set(grammar: Grammar) -> typing.Dict[LenientNt, ReduceExprOrAccept]:
    """Determine which nonterminals in `grammar` can produce the empty string.

    Return a dict {nt: expr} that maps each such nonterminal to the expr
    that should be evaluated when reducing the empty string to nt.
    So, for example, if we have a production

        a ::= b? c?  => CallMethod("a", [0, 1])

    then the resulting dictionary will contain the entry
    `("a", CallMethod("a", [None, None]))`.
    """

    empties: typing.Dict[LenientNt, ReduceExprOrAccept] = {}

    def production_is_empty(p: Production) -> bool:
        return all(isinstance(e, LookaheadRule)
                   or isinstance(e, Optional)
                   or (isinstance(e, Nt) and e in empties)
                   or e is NoLineTerminatorHere
                   for e in p.body)

    def evaluate_reducer_with_empty_matches(p: Production) -> ReduceExprOrAccept:
        # partial evaluation of p.reducer
        stack = [e for e in p.body if is_concrete_element(e)]

        Expr = typing.TypeVar("Expr", ReduceExpr, ReduceExprOrAccept)

        def eval(expr: Expr) -> Expr:
            if expr is None:
                return None
            elif isinstance(expr, Some):
                return Some(eval(expr.inner))
            elif isinstance(expr, CallMethod):
                return dataclasses.replace(
                    expr,
                    args=tuple(eval(arg_expr) for arg_expr in expr.args)
                )
            elif isinstance(expr, int):
                e = stack[expr]
                if isinstance(e, Optional):
                    return None
                else:
                    assert isinstance(e, Nt)
                    result = empties[e]
                    assert not isinstance(result, str)
                    return result
            elif expr == 'accept':
                # Hmm, this is not ideal! Maybe 'accept' needs to take an
                # argument so that the normal case is Accept(0) and this case
                # is Accept(eval(expr.args[0])).
                return 'accept'
            else:
                raise TypeError(
                    "internal error: unhandled reduce expression type {!r}"
                    .format(expr))

        return eval(p.reducer)

    done = False
    while not done:
        done = True
        for nt, nt_def in grammar.nonterminals.items():
            if nt not in empties:
                for p in nt_def.rhs_list:
                    if production_is_empty(p):
                        if nt in empties:
                            raise ValueError(
                                "ambiguous grammar: multiple productions for "
                                "{!r} match the empty string"
                                .format(nt))
                        done = False
                        empties[nt] = evaluate_reducer_with_empty_matches(p)
    return empties


def check_cycle_free(grammar: Grammar) -> None:
    """Throw an exception if any nonterminal in `grammar` produces itself
    via a cycle of 1 or more productions.
    """
    empties = empty_nt_set(grammar)

    # OK, first find out which nonterminals directly produce which other
    # nonterminals (after possibly erasing some optional/empty nts).
    direct_produces: typing.Dict[LenientNt, typing.Set[Nt]] = {}
    for orig in grammar.nonterminals:
        direct_produces[orig] = set()
        for source_production in grammar.nonterminals[orig].rhs_list:
            for rhs, _r in expand_optional_symbols_in_rhs(source_production.body, grammar, empties):
                result: typing.List[Nt] = []
                all_possibly_empty_so_far = True
                # If we break out of the following loop, that means it turns
                # out that this production does not produce *any* strings that
                # are just a single nonterminal.
                for e in rhs:
                    if grammar.is_terminal(e):
                        break  # no good, this production contains a terminal
                    elif isinstance(e, Nt):
                        if e in empties:
                            if all_possibly_empty_so_far:
                                result.append(e)
                        else:
                            if not all_possibly_empty_so_far:
                                # Give up - we have 2+ nonterminals that can't
                                # be empty.
                                break
                            all_possibly_empty_so_far = False
                            result = [e]
                    elif isinstance(e, Exclude):
                        if isinstance(e.inner, Nt):
                            result.append(e.inner)
                    elif isinstance(e, LookaheadRule):
                        # Ignore the restriction. We lose a little precision
                        # here, and could report a cycle where there isn't one,
                        # but it's unlikely in real-world grammars.
                        pass
                    elif e is NoLineTerminatorHere:
                        # This doesn't affect the property we're checking.
                        pass
                    elif isinstance(e, Literal):
                        if e.text != "":
                            # This production contains a non-empty character,
                            # therefore it cannot correspond to an empty cycle.
                            break
                    elif isinstance(e, UnicodeCategory):
                        # This production consume a class of character,
                        # therefore it cannot correspond to an empty cycle.
                        break
                    elif isinstance(e, End):
                        # This production consume the End meta-character,
                        # therefore it cannot correspond to an empty cycle,
                        # even if this character is expect to be produced
                        # infinitely once the end is reached.
                        break
                    elif isinstance(e, CallMethod):
                        # This production execute code, but does not consume
                        # any input.
                        pass
                    else:
                        # Optional is not possible because we called
                        # expand_optional_symbols_in_rhs. ErrorSymbol
                        # effectively matches the empty string (though only if
                        # nothing else matches).
                        assert isinstance(e, ErrorSymbol)
                else:
                    # If we get here, we didn't break, so our results are good!
                    # nt can definitely produce all the nonterminals in result.
                    direct_produces[orig] |= set(result)

    def step(
            produces: typing.Dict[LenientNt, typing.Set[Nt]]
    ) -> typing.Dict[LenientNt, typing.Set[Nt]]:
        return {
            orig: dest | set(b for a in dest for b in produces[a])
            for orig, dest in produces.items()
        }
    produces = fix(step, direct_produces)

    for nt in grammar.nonterminals:
        if nt in produces[nt]:
            raise ValueError(
                "invalid grammar: nonterminal {} can produce itself"
                .format(nt))


def check_lookahead_rules(grammar: Grammar) -> None:
    """Check that no LookaheadRule appears at the end of a production (or before
    elements that can produce the empty string).

    If there are any offending lookahead rules, throw a ValueError.
    """

    empties = empty_nt_set(grammar)

    check_cycle_free(grammar)
    for nt in grammar.nonterminals:
        for source_production in grammar.nonterminals[nt].rhs_list:
            body = source_production.body
            for rhs, _r in expand_optional_symbols_in_rhs(body, grammar, empties):
                # XXX BUG: The next if-condition is insufficient, since it
                # fails to detect a lookahead restriction followed by a
                # nonterminal that can match the empty string.
                if rhs and isinstance(rhs[-1], LookaheadRule):
                    raise ValueError(
                        "invalid grammar: lookahead restriction "
                        "at end of production: {}"
                        .format(grammar.production_to_str(nt, body)))


def check_no_line_terminator_here(grammar: Grammar) -> None:
    empties = empty_nt_set(grammar)

    def check(e: Element, nt: LenientNt, body: typing.List[Element]) -> None:
        if grammar.is_terminal(e):
            pass
        elif isinstance(e, Nt):
            if e in empties:
                raise ValueError(
                    "invalid grammar: [no LineTerminator here] cannot appear next to "
                    "a nonterminal that matches the empty string\n"
                    "in production: {}".format(grammar.production_to_str(nt, body)))
        else:
            raise ValueError(
                "invalid grammar: [no LineTerminator here] must appear only "
                "between terminals and/or nonterminals\n"
                "in production: {}".format(grammar.production_to_str(nt, body)))

    for nt in grammar.nonterminals:
        for production in grammar.nonterminals[nt].rhs_list:
            body = production.body
            for i, e in enumerate(body):
                if e is NoLineTerminatorHere:
                    if i == 0 or i == len(body) - 1:
                        raise ValueError(
                            "invalid grammar: [no LineTerminator here] must be between two symbols\n"
                            "in production: {}".format(grammar.production_to_str(nt, body)))
                    check(body[i - 1], nt, body)
                    check(body[i + 1], nt, body)


def expand_parameterized_nonterminals(grammar: Grammar) -> Grammar:
    """Replace parameterized nonterminals with specialized copies.

    For example, a single pair `nt_name: NtDef(params=('A', 'B'), ...)` in
    `grammar.nonterminals` will be replaced with (assuming A and B are boolean
    parameters) up to four pairs, each having an Nt object as the key and an
    NtDef with no parameters as the value.

    `grammar.nonterminals` must have string keys.

    Returns a new copy of `grammar` with Nt keys, whose NtDefs all have
    `nt_def.params == []`.
    """

    todo = collections.deque(grammar.goals())
    new_nonterminals = {}

    def expand(nt: Nt) -> NtDef:
        """Expand grammar.nonterminals[nt](**args).

        Returns the expanded NtDef, which contains no conditional
        productions or Nt objects.
        """

        if nt.args is None:
            args_dict = None
        else:
            args_dict = dict(nt.args)

        def evaluate_arg(arg: NtParameter) -> NtParameter:
            if isinstance(arg, Var):
                return args_dict[arg.name]
            else:
                return arg

        def expand_element(e: Element) -> Element:
            if isinstance(e, Optional):
                return Optional(expand_element(e.inner))
            elif isinstance(e, Exclude):
                return Exclude(expand_element(e.inner), tuple(map(expand_element, e.exclusion_list)))
            elif isinstance(e, Nt):
                args = tuple((name, evaluate_arg(arg))
                             for name, arg in e.args)
                e = Nt(e.name, args)
                if e not in new_nonterminals:
                    todo.append(e)
                return e
            else:
                return e

        def expand_production(p: Production) -> Production:
            return p.copy_with(
                body=[expand_element(e) for e in p.body],
                condition=None)

        def expand_productions(nt_def: NtDef) -> NtDef:
            result = []
            for p in nt_def.rhs_list:
                if p.condition is None:
                    included = True
                else:
                    param, value = p.condition
                    included = (args_dict[param] == value)
                if included:
                    result.append(expand_production(p))
            return NtDef((), result, nt_def.type)

        nt_def = grammar.nonterminals[nt.name]
        assert tuple(name for name, value in nt.args) == nt_def.params
        return expand_productions(nt_def)

    while todo:
        nt = todo.popleft()
        if nt not in new_nonterminals:  # not already expanded
            new_nonterminals[nt] = expand(nt)

    # "type: ignore" because this runs afoul of Python's covariance rules for
    # Mapping; but it conforms to the intended type.
    return grammar.with_nonterminals(new_nonterminals)  # type: ignore


# *** Start sets and follow sets **********************************************

EMPTY = "(empty)"
END = None

TerminalOrEmpty = str
TerminalOrEmptyOrErrorToken = typing.Union[str, ErrorTokenClass]
StartSets = typing.Dict[Nt, OrderedFrozenSet[TerminalOrEmptyOrErrorToken]]


def start_sets(grammar: Grammar) -> StartSets:
    """Compute the start sets for nonterminals in a grammar.

    A nonterminal's start set is the set of tokens that a match for that
    nonterminal may start with, plus EMPTY if it can match the empty string
    and ErrorToken if it can start with an error.
    """

    # How this works: Note that we can replace the words "match" and "start
    # with" in the definition above with more queries about start sets.
    #
    # 1.  A nonterminal's start set contains a terminal `t` if any of its
    #     productions contains either `t` or a nonterminal with `t` in *its*
    #     start set, preceded only by zero or more nonterminals that have EMPTY
    #     in *their* start sets. Plus:
    #
    # 2.  A nonterminal's start set contains EMPTY if any of its productions
    #     consists entirely of nonterminals that have EMPTY in *their* start
    #     sets.
    #
    # This definition is rather circular. We want the smallest collection of
    # start sets satisfying these rules, and we get that by iterating to a
    # fixed point.

    assert all(isinstance(nt, Nt) for nt in grammar.nonterminals)
    start: StartSets
    start = {typing.cast(Nt, nt): OrderedFrozenSet() for nt in grammar.nonterminals}
    done = False
    while not done:
        done = True
        for nt, nt_def in grammar.nonterminals.items():
            assert isinstance(nt, Nt)
            # Compute start set for each `prod` based on `start` so far.
            # Could be incomplete, but we'll ratchet up as we iterate.
            nt_start = OrderedFrozenSet(
                t for p in nt_def.rhs_list for t in seq_start(grammar, start, p.body))
            if nt_start != start[nt]:
                start[nt] = nt_start
                done = False
    return start


def seq_start(
        grammar: Grammar,
        start: StartSets,
        seq: typing.List[Element]
) -> OrderedFrozenSet[TerminalOrEmptyOrErrorToken]:
    """Compute the start set for a sequence of elements."""
    s: OrderedSet[TerminalOrEmptyOrErrorToken] = OrderedSet([EMPTY])
    for i, e in enumerate(seq):
        if EMPTY not in s:  # preceding elements never match the empty string
            break
        s.remove(EMPTY)
        if grammar.is_terminal(e):
            assert isinstance(e, str)
            s.add(e)
        elif isinstance(e, ErrorSymbol):
            s.add(ErrorToken)
        elif isinstance(e, Nt):
            s |= start[e]
        elif e is NoLineTerminatorHere:
            s.add(EMPTY)
        else:
            assert isinstance(e, LookaheadRule)
            future = seq_start(grammar, start, seq[i + 1:])
            if e.positive:
                future &= e.set
            else:
                future -= e.set
            return OrderedFrozenSet(future)
    return OrderedFrozenSet(s)


StartSetCache = typing.List[typing.List[OrderedFrozenSet[TerminalOrEmptyOrErrorToken]]]


def make_start_set_cache(
        grammar: Grammar,
        prods: typing.List[Prod],
        start: StartSets
) -> StartSetCache:
    """Compute start sets for all suffixes of productions in the grammar.

    Returns a list of lists `cache` such that
    `cache[n][i] == seq_start(grammar, start, prods[n][i:])`.

    (The cache is for speed, since seq_start was being called millions of
    times.)
    """

    def suffix_start_list(
            rhs: typing.List[Element]
    ) -> typing.List[OrderedFrozenSet[TerminalOrEmptyOrErrorToken]]:
        sets: typing.List[OrderedFrozenSet[TerminalOrEmptyOrErrorToken]]
        sets = [OrderedFrozenSet([EMPTY])]
        for e in reversed(rhs):
            s: OrderedFrozenSet[TerminalOrEmptyOrErrorToken]
            if grammar.is_terminal(e):
                assert isinstance(e, str)
                s = OrderedFrozenSet([e])
            elif isinstance(e, ErrorSymbol):
                s = OrderedFrozenSet([ErrorToken])
            elif isinstance(e, Nt):
                s = start[e]
                if EMPTY in s:
                    s = OrderedFrozenSet((s - {EMPTY}) | sets[-1])
            elif e is NoLineTerminatorHere:
                s = sets[-1]
            else:
                assert isinstance(e, LookaheadRule)
                if e.positive:
                    s = OrderedFrozenSet(sets[-1] & e.set)
                else:
                    s = OrderedFrozenSet(sets[-1] - e.set)
            assert isinstance(s, OrderedFrozenSet)
            assert s == seq_start(grammar, start, rhs[len(rhs) - len(sets):])
            sets.append(s)
        sets.reverse()
        assert sets == [seq_start(grammar, start, rhs[i:])
                        for i in range(len(rhs) + 1)]
        return sets

    return [suffix_start_list(prod.rhs) for prod in prods]


FollowSet = OrderedSet[typing.Union[TerminalOrEmptyOrErrorToken, None]]
FollowSets = typing.DefaultDict[Nt, FollowSet]


def follow_sets(
        grammar: Grammar,
        prods_with_indexes_by_nt: typing.DefaultDict[
            LenientNt,
            typing.List[typing.Tuple[int, typing.List[Element]]]
        ],
        start_set_cache: StartSetCache
) -> FollowSets:
    """Compute all follow sets for nonterminals in a grammar.

    The follow set for a nonterminal `A`, as defined in the book, is "the set
    of terminals that can appear immediately to the right of `A` in some
    sentential form"; plus, "If `A` can be the rightmost symbol in some
    sentential form, then $ is in FOLLOW(A)."

    Returns a default-dictionary mapping nts to follow sets.
    """

    # Set of nonterminals already seen, including those we are in the middle of
    # analyzing. The algorithm starts at `goal` and walks all reachable
    # nonterminals, recursively.
    visited = set()

    # The results. By definition, nonterminals that are not reachable from the
    # goal nt have empty follow sets.
    follow: FollowSets = collections.defaultdict(OrderedSet)

    # If `(x, y) in subsumes_relation`, then x can appear at the end of a
    # production of y, and therefore follow[x] should be <= follow[y].
    # (We could maintain that invariant throughout, but at present we
    # brute-force iterate to a fixed point at the end.)
    subsumes_relation: OrderedSet[typing.Tuple[Nt, Nt]]
    subsumes_relation = OrderedSet()

    # `END` is $. It is, of course, in follow[each goal nonterminal]. It gets
    # into other nonterminals' follow sets through the subsumes relation.
    for init_nt in grammar.init_nts:
        assert isinstance(init_nt, Nt)
        follow[init_nt].add(END)

    def visit(nt: Nt) -> None:
        if nt in visited:
            return
        visited.add(nt)
        for prod_index, rhs in prods_with_indexes_by_nt[nt]:
            for i, symbol in enumerate(rhs):
                if isinstance(symbol, Nt):
                    visit(symbol)
                    after = start_set_cache[prod_index][i + 1]
                    if EMPTY in after:
                        after -= {EMPTY}
                        subsumes_relation.add((symbol, nt))
                    follow[symbol] |= after

    for nt in grammar.init_nts:
        assert isinstance(nt, Nt)
        visit(nt)

    # Now iterate to a fixed point on the subsumes relation.
    done = False
    while not done:
        done = True  # optimistically
        for target, source in subsumes_relation:
            if follow[source] - follow[target]:
                follow[target] |= follow[source]
                done = False

    return follow


# *** Lowering ****************************************************************

# At this point, lowered productions start getting farther from the original
# source.  We need to associate them with the original grammar in order to
# produce correct output, so we use Prod values to represent productions.
#
# -   `nt` is the name of the nonterminal as it appears in the original
#     grammar.
#
# -   `index` is the index of the source production, within nt's productions,
#     in the original grammar.
#
# -   `rhs` is the fully lowered/expanded right-hand-side of the production.
#
# There may be many productions in a grammar that all have the same `nt` and
# `index` because they were all produced from the same source production.
@dataclass
class Prod:
    nt: Nt
    index: int
    rhs: typing.List
    reducer: ReduceExprOrAccept


def expand_optional_symbols_in_rhs(
        rhs: typing.List[Element],
        grammar: Grammar,
        empties: typing.Dict[LenientNt, ReduceExprOrAccept],
        start_index: int = 0
) -> typing.Iterable[typing.Tuple[typing.List[Element], typing.Dict[int, ReduceExpr]]]:
    """Expand a sequence with optional symbols into sequences that have none.

    rhs is a list of symbols, possibly containing optional elements. This
    yields every list that can be made by replacing each optional element
    either with its .inner value, or with nothing.

    Each list is accompanied by the list of the indices of optional elements in
    `rhs` that were dropped.

    For example, `expand_optional_symbols_in_rhs(["if", Optional("else")])`
    yields the two pairs `(["if"], [1])` and `["if", "else"], []`.
    """

    replacement: ReduceExpr
    for i in range(start_index, len(rhs)):
        e = rhs[i]
        if isinstance(e, Optional):
            if isinstance(e.inner, Nt) and e.inner in empties:
                # If this is already possibly-empty in the input grammar, it's an
                # error! The grammar is ambiguous.
                raise ValueError(
                    "ambiguous grammar: {} is ambiguous because {} can match "
                    "the empty string"
                    .format(grammar.element_to_str(e),
                            grammar.element_to_str(e.inner)))
            replacement = None
            break
        elif isinstance(e, Nt) and e in empties:
            empty_expr = empties[e]
            # The replacement can't be 'accept' because that only happens with
            # InitNt nonterminals, which are never used in productions.
            assert not isinstance(empty_expr, str)
            replacement = empty_expr
            break
    else:
        yield rhs[start_index:], {}
        return

    for expanded, r in expand_optional_symbols_in_rhs(rhs, grammar, empties, i + 1):
        e = rhs[i]
        rhs_inner = e.inner if isinstance(e, Optional) else e
        # without rhs[i]
        r2 = r.copy()
        r2[i] = replacement
        yield rhs[start_index:i] + expanded, r2
        # with rhs[i]
        yield rhs[start_index:i] + [rhs_inner] + expanded, r


def expand_all_optional_elements(grammar: Grammar) -> typing.Tuple[
        Grammar,
        typing.List[Prod],
        typing.DefaultDict[LenientNt, typing.List[typing.Tuple[int, typing.List[Element]]]]
]:
    """Expand optional elements in the grammar.

    We replace each production that contains an optional element with two
    productions: one with and one without. Downstream of this step, we can
    ignore the possibility of optional elements.
    """
    expanded_grammar: typing.Dict[LenientNt, NtDef] = {}

    # This was capturing the set of empty production to simplify the work of
    # the previous algorithm which was trying to determine the lookahead.
    # However, with the LR0Generator this is no longer needed as we are
    # generating deliberatly inconsistent parse table states, which are then
    # properly fixed by adding lookahead information where needed, and without
    # bugs!
    # empties = empty_nt_set(grammar)
    empties: typing.Dict[LenientNt, ReduceExprOrAccept] = {}

    # Put all the productions in one big list, so each one has an index. We
    # will use the indices in the action table (as reduce action payloads).
    prods: typing.List[Prod] = []
    prods_with_indexes_by_nt: \
        typing.DefaultDict[LenientNt, typing.List[typing.Tuple[int, typing.List[Element]]]] = \
        collections.defaultdict(list)

    for nt, nt_def in grammar.nonterminals.items():
        assert isinstance(nt, Nt)
        prods_expanded = []
        for prod_index, p in enumerate(nt_def.rhs_list):
            # Aggravatingly, a reduce-expression that's an int is not
            # simply an offset into p.body. It only counts "concrete"
            # elements. Make a mapping for converting reduce-expressions to
            # offsets.
            reduce_expr_to_offset = [
                i
                for i, e in enumerate(p.body)
                if is_concrete_element(e)
            ]

            for pair in expand_optional_symbols_in_rhs(p.body, grammar, empties):
                expanded_rhs, removals = pair

                Expr = typing.TypeVar("Expr", ReduceExpr, ReduceExprOrAccept)

                def adjust_reduce_expr(expr: Expr) -> Expr:
                    if isinstance(expr, int):
                        i = reduce_expr_to_offset[expr]
                        if i in removals:
                            return removals[i]
                        was_optional = isinstance(p.body[i], Optional)
                        expr -= sum(1 for r in removals if r < i)
                        if was_optional:
                            return Some(expr)
                        else:
                            return expr
                    elif expr is None:
                        return None
                    elif isinstance(expr, Some):
                        return Some(adjust_reduce_expr(expr.inner))
                    elif isinstance(expr, CallMethod):
                        return dataclasses.replace(
                            expr,
                            args=tuple(adjust_reduce_expr(arg)
                                       for arg in expr.args)
                        )
                    elif expr == 'accept':
                        # doesn't need to be adjusted because 'accept' isn't
                        # turned into code downstream.
                        return 'accept'
                    else:
                        raise TypeError(
                            "internal error: unrecognized element {!r}"
                            .format(expr))

                adjusted_reducer = adjust_reduce_expr(p.reducer)
                prods_expanded.append(
                    Production(body=expanded_rhs,
                               reducer=adjusted_reducer))
                prods.append(Prod(nt, prod_index, expanded_rhs,
                                  adjusted_reducer))
                prods_with_indexes_by_nt[nt].append(
                    (len(prods) - 1, expanded_rhs))
        expanded_grammar[nt] = nt_def.with_rhs_list(prods_expanded)

    return (grammar.with_nonterminals(expanded_grammar),
            prods,
            prods_with_indexes_by_nt)


class CanonicalGrammar:
    __slots__ = ["prods", "prods_with_indexes_by_nt", "grammar"]

    prods: typing.List[Prod]
    prods_with_indexes_by_nt: typing.Mapping[
        LenientNt,
        typing.List[typing.Tuple[int, typing.List[Element]]]]
    grammar: Grammar

    def __init__(self, grammar: Grammar) -> None:
        # Step by step, we check the grammar and lower it to a more primitive form.
        grammar = expand_parameterized_nonterminals(grammar)
        check_cycle_free(grammar)
        # check_lookahead_rules(grammar)
        check_no_line_terminator_here(grammar)
        grammar, prods, prods_with_indexes_by_nt = \
            expand_all_optional_elements(grammar)

        self.prods = prods
        self.prods_with_indexes_by_nt = prods_with_indexes_by_nt
        self.grammar = grammar