xref: /aosp_15_r20/external/emboss/compiler/front_end/lr1.py (revision 99e0aae7469b87d12f0ad23e61142c2d74c1ef70)

# Copyright 2019 Google LLC
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     https://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.

"""LR(1) parser generator.

The primary class in this module, Grammar, takes a list of context-free grammar
productions, and produces the corresponding LR(1) shift-reduce parser.  This is
an implementation of the algorithm on pages 221 and 261-265 of "Compilers:
Principles, Techniques, & Tools" (Second Edition) by Aho, Lam, Sethi, and
Ullman, also known as "The Dragon Book," hereafter referred to as "ALSU."

This module only implements the LR(1) algorithms; unlike tools such as yacc, it
does not implement the various bits of glue necessary to actually use a parser.
Clients are expected to provide their own tokenizers and handle turning a raw
parse tree into an intermediate representation on their own.
"""

import collections

from compiler.util import parser_types


class Item(collections.namedtuple("Item", ["production", "dot", "terminal",
                                           "next_symbol"])):
  """An Item is an LR(1) Item: a production, a cursor location, and a terminal.

  An Item represents a partially-parsed production, and a lookahead symbol.  The
  position of the dot indicates what portion of the production has been parsed.
  Generally, Items are an internal implementation detail, but they can be useful
  elsewhere, particularly for debugging.

  Attributes:
    production: The Production this Item covers.
    dot: The index of the "dot" in production's rhs.
    terminal: The terminal lookahead symbol that follows the production in the
        input stream.
  """

  def __str__(self):
    """__str__ generates ASLU notation."""
    return (str(self.production.lhs) + " -> " + " ".join(
        [str(r) for r in self.production.rhs[0:self.dot] + (".",) +
         self.production.rhs[self.dot:]]) + ", " + str(self.terminal))

  @staticmethod
  def parse(text):
    """Parses an Item in ALSU notation.

    Parses an Item from notation like:

       symbol -> foo . bar baz, qux

    where "symbol -> foo bar baz" will be taken as the production, the position
    of the "." is taken as "dot" (in this case 1), and the symbol after "," is
    taken as the "terminal".  The following are also valid items:

       sym -> ., foo
       sym -> . foo bar, baz
       sym -> foo bar ., baz

    Symbols on the right-hand side of the production should be separated by
    whitespace.

    Arguments:
      text: The text to parse into an Item.

    Returns:
      An Item.
    """
    production, terminal = text.split(",")
    terminal = terminal.strip()
    if terminal == "$":
      terminal = END_OF_INPUT
    lhs, rhs = production.split("->")
    lhs = lhs.strip()
    if lhs == "S'":
      lhs = START_PRIME
    before_dot, after_dot = rhs.split(".")
    handle = before_dot.split()
    tail = after_dot.split()
    return make_item(parser_types.Production(lhs, tuple(handle + tail)),
                     len(handle), terminal)


def make_item(production, dot, symbol):
  return Item(production, dot, symbol,
              None if dot >= len(production.rhs) else production.rhs[dot])


class Conflict(
    collections.namedtuple("Conflict", ["state", "symbol", "actions"])
):
  """Conflict represents a parse conflict."""

  def __str__(self):
    return "Conflict for {} in state {}: ".format(
        self.symbol, self.state) + " vs ".join([str(a) for a in self.actions])


Shift = collections.namedtuple("Shift", ["state", "items"])
Reduce = collections.namedtuple("Reduce", ["rule"])
Accept = collections.namedtuple("Accept", [])
Error = collections.namedtuple("Error", ["code"])

Symbol = collections.namedtuple("Symbol", ["symbol"])

# START_PRIME is the implicit 'real' root symbol for the grammar.
START_PRIME = "S'"

# END_OF_INPUT is the implicit symbol at the end of input.
END_OF_INPUT = "$"

# ANY_TOKEN is used by mark_error as a "wildcard" token that should be replaced
# by every other token.
ANY_TOKEN = parser_types.Token(object(), "*",
                               parser_types.parse_location("0:0-0:0"))


class Reduction(collections.namedtuple("Reduction",
                                       ["symbol", "children", "production",
                                        "source_location"])):
  """A Reduction is a non-leaf node in a parse tree.

  Attributes:
    symbol: The name of this element in the parse.
    children: The child elements of this parse.
    production: The grammar production to which this reduction corresponds.
    source_location: If known, the range in the source text corresponding to the
      tokens from which this reduction was parsed.  May be 'None' if this
      reduction was produced from no symbols, or if the tokens fed to `parse`
      did not include source_location.
  """
  pass


class Grammar(object):
  """Grammar is an LR(1) context-free grammar.

  Attributes:
    start: The start symbol for the grammar.
    productions: A list of productions in the grammar, including the S' -> start
      production.
    symbols: A set of all symbols in the grammar, including $ and S'.
    nonterminals: A set of all nonterminal symbols in the grammar, including S'.
    terminals: A set of all terminal symbols in the grammar, including $.
  """

  def __init__(self, start_symbol, productions):
    """Constructs a Grammar object.

    Arguments:
      start_symbol: The start symbol for the grammar.
      productions: A list of productions (not including the "S' -> start_symbol"
          production).
    """
    object.__init__(self)
    self.start = start_symbol
    self._seed_production = parser_types.Production(START_PRIME, (self.start,))
    self.productions = productions + [self._seed_production]

    self._single_level_closure_of_item_cache = {}
    self._closure_of_item_cache = {}
    self._compute_symbols()
    self._compute_seed_firsts()
    self._set_productions_by_lhs()
    self._populate_item_cache()

  def _set_productions_by_lhs(self):
    # Prepopulating _productions_by_lhs speeds up _closure_of_item by about 30%,
    # which is significant on medium-to-large grammars.
    self._productions_by_lhs = {}
    for production in self.productions:
      self._productions_by_lhs.setdefault(production.lhs, list()).append(
          production)

  def _populate_item_cache(self):
    # There are a relatively small number of possible Items for a grammar, and
    # the algorithm needs to get Items from their constituent components very
    # frequently.  As it turns out, pre-caching all possible Items results in a
    # ~35% overall speedup to Grammar.parser().
    self._item_cache = {}
    for symbol in self.terminals:
      for production in self.productions:
        for dot in range(len(production.rhs) + 1):
          self._item_cache[production, dot, symbol] = make_item(
              production, dot, symbol)

  def _compute_symbols(self):
    """Finds all grammar symbols, and sorts them into terminal and non-terminal.

    Nonterminal symbols are those which appear on the left side of any
    production.  Terminal symbols are those which do not.

    _compute_symbols is used during __init__.
    """
    self.symbols = {END_OF_INPUT}
    self.nonterminals = set()
    for production in self.productions:
      self.symbols.add(production.lhs)
      self.nonterminals.add(production.lhs)
      for symbol in production.rhs:
        self.symbols.add(symbol)
    self.terminals = self.symbols - self.nonterminals

  def _compute_seed_firsts(self):
    """Computes FIRST (ALSU p221) for all terminal and nonterminal symbols.

    The algorithm for computing FIRST is an iterative one that terminates when
    it reaches a fixed point (that is, when further iterations stop changing
    state).  _compute_seed_firsts computes the fixed point for all single-symbol
    strings, by repeatedly calling _first and updating the internal _firsts
    table with the results.

    Once _compute_seed_firsts has completed, _first will return correct results
    for both single- and multi-symbol strings.

    _compute_seed_firsts is used during __init__.
    """
    self.firsts = {}
    # FIRST for a terminal symbol is always just that terminal symbol.
    for terminal in self.terminals:
      self.firsts[terminal] = set([terminal])
    for nonterminal in self.nonterminals:
      self.firsts[nonterminal] = set()
    while True:
      # The first iteration picks up all the productions that start with
      # terminal symbols.  The second iteration picks up productions that start
      # with nonterminals that the first iteration picked up.  The third
      # iteration picks up nonterminals that the first and second picked up, and
      # so on.
      #
      # This is guaranteed to end, in the worst case, when every terminal
      # symbol and epsilon has been added to the _firsts set for every
      # nonterminal symbol.  This would be slow, but requires a pathological
      # grammar; useful grammars should complete in only a few iterations.
      firsts_to_add = {}
      for production in self.productions:
        for first in self._first(production.rhs):
          if first not in self.firsts[production.lhs]:
            if production.lhs not in firsts_to_add:
              firsts_to_add[production.lhs] = set()
            firsts_to_add[production.lhs].add(first)
      if not firsts_to_add:
        break
      for symbol in firsts_to_add:
        self.firsts[symbol].update(firsts_to_add[symbol])

  def _first(self, symbols):
    """The FIRST function from ALSU p221.

    _first takes a string of symbols (both terminals and nonterminals) and
    returns the set of terminal symbols which could be the first terminal symbol
    of a string produced by the given list of symbols.

    _first will not give fully-correct results until _compute_seed_firsts
    finishes, but is called by _compute_seed_firsts, and must provide partial
    results during that method's execution.

    Args:
      symbols: A list of symbols.

    Returns:
      A set of terminals which could be the first terminal in "symbols."
    """
    result = set()
    all_contain_epsilon = True
    for symbol in symbols:
      for first in self.firsts[symbol]:
        if first:
          result.add(first)
      if None not in self.firsts[symbol]:
        all_contain_epsilon = False
        break
    if all_contain_epsilon:
      # "None" seems like a Pythonic way of representing epsilon (no symbol).
      result.add(None)
    return result

  def _closure_of_item(self, root_item):
    """Modified implementation of CLOSURE from ALSU p261.

    _closure_of_item performs the CLOSURE function with a single seed item, with
    memoization.  In the algorithm as presented in ALSU, CLOSURE is called with
    a different set of items every time, which is unhelpful for memoization.
    Instead, we let _parallel_goto merge the sets returned by _closure_of_item,
    which results in a ~40% speedup.

    CLOSURE, roughly, computes the set of LR(1) Items which might be active when
    a "seed" set of Items is active.

    Technically, it is the epsilon-closure of the NFA states represented by
    "items," where an epsilon transition (a transition that does not consume any
    symbols) occurs from a->Z.bY,q to b->.X,p when p is in FIRST(Yq).  (a and b
    are nonterminals, X, Y, and Z are arbitrary strings of symbols, and p and q
    are terminals.)  That is, it is the set of all NFA states which can be
    reached from "items" without consuming any input.  This set corresponds to a
    single DFA state.

    Args:
      root_item: The initial LR(1) Item.

    Returns:
      A set of LR(1) items which may be active at the time when the provided
      item is active.
    """
    if root_item in self._closure_of_item_cache:
      return self._closure_of_item_cache[root_item]
    item_set = set([root_item])
    item_list = [root_item]
    i = 0
    # Each newly-added Item may trigger the addition of further Items, so
    # iterate until no new Items are added.  In the worst case, a new Item will
    # be added for each production.
    #
    # This algorithm is really looking for "next" nonterminals in the existing
    # items, and adding new items corresponding to their productions.
    while i < len(item_list):
      item = item_list[i]
      i += 1
      if not item.next_symbol:
        continue
      # If _closure_of_item_cache contains the full closure of item, then we can
      # add its full closure to the result set, and skip checking any of its
      # items: any item that would be added by any item in the cached result
      # will already be in the _closure_of_item_cache entry.
      if item in self._closure_of_item_cache:
        item_set |= self._closure_of_item_cache[item]
        continue
      # Even if we don't have the full closure of item, we may have the
      # immediate closure of item.  It turns out that memoizing just this step
      # speeds up this function by about 50%, even after the
      # _closure_of_item_cache check.
      if item not in self._single_level_closure_of_item_cache:
        new_items = set()
        for production in self._productions_by_lhs.get(item.next_symbol, []):
          for terminal in self._first(item.production.rhs[item.dot + 1:] +
                                      (item.terminal,)):
            new_items.add(self._item_cache[production, 0, terminal])
        self._single_level_closure_of_item_cache[item] = new_items
      for new_item in self._single_level_closure_of_item_cache[item]:
        if new_item not in item_set:
          item_set.add(new_item)
          item_list.append(new_item)
    self._closure_of_item_cache[root_item] = item_set
    # Typically, _closure_of_item() will be called on items whose closures
    # bring in the greatest number of additional items, then on items which
    # close over fewer and fewer other items.  Since items are not added to
    # _closure_of_item_cache unless _closure_of_item() is called directly on
    # them, this means that it is unlikely that items brought in will (without
    # intervention) have entries in _closure_of_item_cache, which slows down the
    # computation of the larger closures.
    #
    # Although it is not guaranteed, items added to item_list last will tend to
    # close over fewer items, and therefore be easier to compute.  By forcibly
    # re-calculating closures from last to first, and adding the results to
    # _closure_of_item_cache at each step, we get a modest performance
    # improvement: roughly 50% less time spent in _closure_of_item, which
    # translates to about 5% less time in parser().
    for item in item_list[::-1]:
      self._closure_of_item(item)
    return item_set

  def _parallel_goto(self, items):
    """The GOTO function from ALSU p261, executed on all symbols.

    _parallel_goto takes a set of Items, and returns a dict from every symbol in
    self.symbols to the set of Items that would be active after a shift
    operation (if symbol is a terminal) or after a reduction operation (if
    symbol is a nonterminal).

    _parallel_goto is used in lieu of the single-symbol GOTO from ALSU because
    it eliminates the outer loop over self.terminals, and thereby reduces the
    number of next_symbol calls by a factor of len(self.terminals).

    Args:
      items: The set of items representing the initial DFA state.

    Returns:
      A dict from symbols to sets of items representing the new DFA states.
    """
    results = collections.defaultdict(set)
    for item in items:
      next_symbol = item.next_symbol
      if next_symbol is None:
        continue
      item = self._item_cache[item.production, item.dot + 1, item.terminal]
      # Inlining the cache check results in a ~25% speedup in this function, and
      # about 10% overall speedup to parser().
      if item in self._closure_of_item_cache:
        closure = self._closure_of_item_cache[item]
      else:
        closure = self._closure_of_item(item)
      # _closure will add newly-started Items (Items with dot=0) to the result
      # set.  After this operation, the result set will correspond to the new
      # state.
      results[next_symbol].update(closure)
    return results

  def _items(self):
    """The items function from ALSU p261.

    _items computes the set of sets of LR(1) items for a shift-reduce parser
    that matches the grammar.  Each set of LR(1) items corresponds to a single
    DFA state.

    Returns:
      A tuple.

      The first element of the tuple is a list of sets of LR(1) items (each set
      corresponding to a DFA state).

      The second element of the tuple is a dictionary from (int, symbol) pairs
      to ints, where all the ints are indexes into the list of sets of LR(1)
      items.  This dictionary is based on the results of the _Goto function,
      where item_sets[dict[i, sym]] == self._Goto(item_sets[i], sym).
    """
    # The list of states is seeded with the marker S' production.
    item_list = [
        frozenset(self._closure_of_item(
            self._item_cache[self._seed_production, 0, END_OF_INPUT]))
    ]
    items = {item_list[0]: 0}
    goto_table = {}
    i = 0
    # For each state, figure out what the new state when each symbol is added to
    # the top of the parsing stack (see the comments in parser._parse).  See
    # _Goto for an explanation of how that is actually computed.
    while i < len(item_list):
      item_set = item_list[i]
      gotos = self._parallel_goto(item_set)
      for symbol, goto in gotos.items():
        goto = frozenset(goto)
        if goto not in items:
          items[goto] = len(item_list)
          item_list.append(goto)
        goto_table[i, symbol] = items[goto]
      i += 1
    return item_list, goto_table

  def parser(self):
    """parser returns an LR(1) parser for the Grammar.

    This implements the Canonical LR(1) ("LR(1)") parser algorithm ("Algorithm
    4.56", ALSU p265), rather than the more common Lookahead LR(1) ("LALR(1)")
    algorithm.  LALR(1) produces smaller tables, but is more complex and does
    not cover all LR(1) grammars.  When the LR(1) and LALR(1) algorithms were
    invented, table sizes were an important consideration; now, the difference
    between a few hundred and a few thousand entries is unlikely to matter.

    At this time, Grammar does not handle ambiguous grammars, which are commonly
    used to handle precedence, associativity, and the "dangling else" problem.
    Formally, these can always be handled by an unambiguous grammar, though
    doing so can be cumbersome, particularly for expression languages with many
    levels of precedence.  ALSU section 4.8 (pp278-287) contains some techniques
    for handling these kinds of ambiguity.

    Returns:
      A Parser.
    """
    item_sets, goto = self._items()
    action = {}
    conflicts = set()
    end_item = self._item_cache[self._seed_production, 1, END_OF_INPUT]
    for i in range(len(item_sets)):
      for item in item_sets[i]:
        new_action = None
        if (item.next_symbol is None and
            item.production != self._seed_production):
          terminal = item.terminal
          new_action = Reduce(item.production)
        elif item.next_symbol in self.terminals:
          terminal = item.next_symbol
          assert goto[i, terminal] is not None
          new_action = Shift(goto[i, terminal], item_sets[goto[i, terminal]])
        if new_action:
          if (i, terminal) in action and action[i, terminal] != new_action:
            conflicts.add(
                Conflict(i, terminal,
                         frozenset([action[i, terminal], new_action])))
          action[i, terminal] = new_action
        if item == end_item:
          new_action = Accept()
          assert (i, END_OF_INPUT
                 ) not in action or action[i, END_OF_INPUT] == new_action
          action[i, END_OF_INPUT] = new_action
    trimmed_goto = {}
    for k in goto:
      if k[1] in self.nonterminals:
        trimmed_goto[k] = goto[k]
    expected = {}
    for state, terminal in action:
      if state not in expected:
        expected[state] = set()
      expected[state].add(terminal)
    return Parser(item_sets, trimmed_goto, action, expected, conflicts,
                  self.terminals, self.nonterminals, self.productions)


ParseError = collections.namedtuple("ParseError", ["code", "index", "token",
                                                   "state", "expected_tokens"])
ParseResult = collections.namedtuple("ParseResult", ["parse_tree", "error"])


class Parser(object):
  """Parser is a shift-reduce LR(1) parser.

  Generally, clients will want to get a Parser from a Grammar, rather than
  directly instantiating one.

  Parser exposes the raw tables needed to feed into a Shift-Reduce parser,
  but can also be used directly for parsing.

  Attributes:
    item_sets: A list of item sets which correspond to the state numbers in
      the action and goto tables.  This is not necessary for parsing, but is
      useful for debugging parsers.
    goto: The GOTO table for this parser.
    action: The ACTION table for this parser.
    expected: A table of terminal symbols that are expected (that is, that
      have a non-Error action) for each state.  This can be used to provide
      more helpful error messages for parse errors.
    conflicts: A set of unresolved conflicts found during table generation.
    terminals: A set of terminal symbols in the grammar.
    nonterminals: A set of nonterminal symbols in the grammar.
    productions: A list of productions in the grammar.
    default_errors: A dict of states to default error codes to use when
      encountering an error in that state, when a more-specific Error for the
      state/terminal pair has not been set.
  """

  def __init__(self, item_sets, goto, action, expected, conflicts, terminals,
               nonterminals, productions):
    super(Parser, self).__init__()
    self.item_sets = item_sets
    self.goto = goto
    self.action = action
    self.expected = expected
    self.conflicts = conflicts
    self.terminals = terminals
    self.nonterminals = nonterminals
    self.productions = productions
    self.default_errors = {}

  def _parse(self, tokens):
    """_parse implements Shift-Reduce parsing algorithm.

    _parse implements the standard shift-reduce algorithm outlined on ASLU
    pp236-237.

    Arguments:
      tokens: the list of token objects to parse.

    Returns:
      A ParseResult.
    """
    # The END_OF_INPUT token is explicitly added to avoid explicit "cursor <
    # len(tokens)" checks.
    tokens = list(tokens) + [Symbol(END_OF_INPUT)]

    # Each element of stack is a parse state and a (possibly partial) parse
    # tree.  The state at the top of the stack encodes which productions are
    # "active" (that is, which ones the parser has seen partial input which
    # matches some prefix of the production, in a place where that production
    # might be valid), and, for each active production, how much of the
    # production has been completed.
    stack = [(0, None)]

    def state():
      return stack[-1][0]

    cursor = 0

    # On each iteration, look at the next symbol and the current state, and
    # perform the corresponding action.
    while True:
      if (state(), tokens[cursor].symbol) not in self.action:
        # Most state/symbol entries would be Errors, so rather than exhaustively
        # adding error entries, we just check here.
        if state() in self.default_errors:
          next_action = Error(self.default_errors[state()])
        else:
          next_action = Error(None)
      else:
        next_action = self.action[state(), tokens[cursor].symbol]

      if isinstance(next_action, Shift):
        # Shift means that there are no "complete" productions on the stack,
        # and so the current token should be shifted onto the stack, with a new
        # state indicating the new set of "active" productions.
        stack.append((next_action.state, tokens[cursor]))
        cursor += 1
      elif isinstance(next_action, Accept):
        # Accept means that parsing is over, successfully.
        assert len(stack) == 2, "Accepted incompletely-reduced input."
        assert tokens[cursor].symbol == END_OF_INPUT, ("Accepted parse before "
                                                       "end of input.")
        return ParseResult(stack[-1][1], None)
      elif isinstance(next_action, Reduce):
        # Reduce means that there is a complete production on the stack, and
        # that the next symbol implies that the completed production is the
        # correct production.
        #
        # Per ALSU, we would simply pop an element off the state stack for each
        # symbol on the rhs of the production, and then push a new state by
        # looking up the (post-pop) current state and the lhs of the production
        # in GOTO.  The GOTO table, in some sense, is equivalent to shift
        # actions for nonterminal symbols.
        #
        # Here, we attach a new partial parse tree, with the production lhs as
        # the "name" of the tree, and the popped trees as the "children" of the
        # new tree.
        children = [
            item[1] for item in stack[len(stack) - len(next_action.rule.rhs):]
        ]
        # Attach source_location, if known.  The source location will not be
        # known if the reduction consumes no symbols (empty rhs) or if the
        # client did not specify source_locations for tokens.
        #
        # It is necessary to loop in order to handle cases like:
        #
        # C -> c D
        # D ->
        #
        # The D child of the C reduction will not have a source location
        # (because it is not produced from any source), so it is necessary to
        # scan backwards through C's children to find the end position.  The
        # opposite is required in the case where initial children have no
        # source.
        #
        # These loops implicitly handle the case where the reduction has no
        # children, setting the source_location to None in that case.
        start_position = None
        end_position = None
        for child in children:
          if hasattr(child,
                     "source_location") and child.source_location is not None:
            start_position = child.source_location.start
            break
        for child in reversed(children):
          if hasattr(child,
                     "source_location") and child.source_location is not None:
            end_position = child.source_location.end
            break
        if start_position is None:
          source_location = None
        else:
          source_location = parser_types.make_location(start_position,
                                                       end_position)
        reduction = Reduction(next_action.rule.lhs, children, next_action.rule,
                              source_location)
        del stack[len(stack) - len(next_action.rule.rhs):]
        stack.append((self.goto[state(), next_action.rule.lhs], reduction))
      elif isinstance(next_action, Error):
        # Error means that the parse is impossible.  For typical grammars and
        # texts, this usually happens within a few tokens after the mistake in
        # the input stream, which is convenient (though imperfect) for error
        # reporting.
        return ParseResult(None,
                           ParseError(next_action.code, cursor, tokens[cursor],
                                      state(), self.expected[state()]))
      else:
        assert False, "Shouldn't be here."

  def mark_error(self, tokens, error_token, error_code):
    """Marks an error state with the given error code.

    mark_error implements the equivalent of the "Merr" system presented in
    "Generating LR Syntax error Messages from Examples" (Jeffery, 2003).
    This system has limitations, but has the primary advantage that error
    messages can be specified by giving an example of the error and the
    message itself.

    Arguments:
      tokens: a list of tokens to parse.
      error_token: the token where the parse should fail, or None if the parse
        should fail at the implicit end-of-input token.

        If the error_token is the special ANY_TOKEN, then the error will be
        recorded as the default error for the error state.
      error_code: a value to record for the error state reached by parsing
        tokens.

    Returns:
      None if error_code was successfully recorded, or an error message if there
      was a problem.
    """
    result = self._parse(tokens)

    # There is no error state to mark on a successful parse.
    if not result.error:
      return "Input successfully parsed."

    # Check if the error occurred at the specified token; if not, then this was
    # not the expected error.
    if error_token is None:
      error_symbol = END_OF_INPUT
      if result.error.token.symbol != END_OF_INPUT:
        return "error occurred on {} token, not end of input.".format(
            result.error.token.symbol)
    else:
      error_symbol = error_token.symbol
      if result.error.token != error_token:
        return "error occurred on {} token, not {} token.".format(
            result.error.token.symbol, error_token.symbol)

    # If the expected error was found, attempt to mark it.  It is acceptable if
    # the given error_code is already set as the error code for the given parse,
    # but not if a different code is set.
    if result.error.token == ANY_TOKEN:
      # For ANY_TOKEN, mark it as a default error.
      if result.error.state in self.default_errors:
        if self.default_errors[result.error.state] == error_code:
          return None
        else:
          return ("Attempted to overwrite existing default error code {!r} "
                  "with new error code {!r} for state {}".format(
                      self.default_errors[result.error.state], error_code,
                      result.error.state))
      else:
        self.default_errors[result.error.state] = error_code
        return None
    else:
      if (result.error.state, error_symbol) in self.action:
        existing_error = self.action[result.error.state, error_symbol]
        assert isinstance(existing_error, Error), "Bug"
        if existing_error.code == error_code:
          return None
        else:
          return ("Attempted to overwrite existing error code {!r} with new "
                  "error code {!r} for state {}, terminal {}".format(
                      existing_error.code, error_code, result.error.state,
                      error_symbol))
      else:
        self.action[result.error.state, error_symbol] = Error(error_code)
        return None
    assert False, "All other paths should lead to return."

  def parse(self, tokens):
    """Parses a list of tokens.

    Arguments:
      tokens: a list of tokens to parse.

    Returns:
      A ParseResult.
    """
    result = self._parse(tokens)
    return result