xref: /aosp_15_r20/external/emboss/compiler/front_end/module_ir.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.

"""module_ir contains code for generating module-level IRs from parse trees.

The primary export is build_ir(), which takes a parse tree (as returned by a
parser from lr1.py), and returns a module-level intermediate representation
("module IR").

This module also notably exports PRODUCTIONS and START_SYMBOL, which should be
fed to lr1.Grammar in order to create a parser for the Emboss language.
"""

import re
import sys

from compiler.util import ir_data
from compiler.util import ir_data_utils
from compiler.util import name_conversion
from compiler.util import parser_types


# Intermediate types; should not be found in the final IR.
class _List(object):
  """A list with source location information."""
  __slots__ = ('list', 'source_location')

  def __init__(self, l):
    assert isinstance(l, list), "_List object must wrap list, not '%r'" % l
    self.list = l
    self.source_location = ir_data.Location()


class _ExpressionTail(object):
  """A fragment of an expression with an operator and right-hand side.

  _ExpressionTail is the tail of an expression, consisting of an operator and
  the right-hand argument to the operator; for example, in the expression (6+8),
  the _ExpressionTail would be "+8".

  This is used as a temporary object while converting the right-recursive
  "expression" and "times-expression" productions into left-associative
  Expressions.

  Attributes:
    operator: An ir_data.Word of the operator's name.
    expression: The expression on the right side of the operator.
    source_location: The source location of the operation fragment.
  """
  __slots__ = ('operator', 'expression', 'source_location')

  def __init__(self, operator, expression):
    self.operator = operator
    self.expression = expression
    self.source_location = ir_data.Location()


class _FieldWithType(object):
  """A field with zero or more types defined inline with that field."""
  __slots__ = ('field', 'subtypes', 'source_location')

  def __init__(self, field, subtypes=None):
    self.field = field
    self.subtypes = subtypes or []
    self.source_location = ir_data.Location()


def build_ir(parse_tree, used_productions=None):
  r"""Builds a module-level intermediate representation from a valid parse tree.

  The parse tree is precisely dictated by the exact productions in the grammar
  used by the parser, with no semantic information.  _really_build_ir transforms
  this "raw" form into a stable, cooked representation, thereby isolating
  subsequent steps from the exact details of the grammar.

  (Probably incomplete) list of transformations:

  *   ParseResult and Token nodes are replaced with Module, Attribute, Struct,
      Type, etc. objects.

  *   Purely syntactic tokens ('"["', '"struct"', etc.) are discarded.

  *   Repeated elements are transformed from tree form to list form:

          a*
         / \
        b   a*
           / \
          c   a*
             / \
            d   a*

      (where b, c, and d are nodes of type "a") becomes [b, c, d].

  *   The values of numeric constants (Number, etc. tokens) are parsed.

  *   Different classes of names (snake_names, CamelNames, ShoutyNames) are
      folded into a single "Name" type, since they are guaranteed to appear in
      the correct places in the parse tree.


  Arguments:
    parse_tree: A parse tree.  Each leaf node should be a parser_types.Token
      object, and each non-leaf node should have a 'symbol' attribute specifying
      which grammar symbol it represents, and a 'children' attribute containing
      a list of child nodes.  This is the format returned by the parsers
      produced by the lr1 module, when run against tokens from the tokenizer
      module.
    used_productions: If specified, used_productions.add() will be called with
      each production actually used in parsing.  This can be useful when
      developing the grammar and writing tests; in particular, it can be used to
      figure out which productions are *not* used when parsing a particular
      file.

  Returns:
    A module-level intermediate representation (module IR) for an Emboss module
    (source file).  This IR will not have symbols resolved; that must be done on
    a forest of module IRs so that names from other modules can be resolved.
  """

  # TODO(b/140259131): Refactor _really_build_ir to be less recursive/use an
  # explicit stack.
  old_recursion_limit = sys.getrecursionlimit()
  sys.setrecursionlimit(16 * 1024)  # ~8000 top-level entities in one module.
  try:
    result = _really_build_ir(parse_tree, used_productions)
  finally:
    sys.setrecursionlimit(old_recursion_limit)
  return result


def _really_build_ir(parse_tree, used_productions):
  """Real implementation of build_ir()."""
  if used_productions is None:
    used_productions = set()
  if hasattr(parse_tree, 'children'):
    parsed_children = [_really_build_ir(child, used_productions)
                       for child in parse_tree.children]
    used_productions.add(parse_tree.production)
    result = _handlers[parse_tree.production](*parsed_children)
    if parse_tree.source_location is not None:
      if result.source_location:
        ir_data_utils.update(result.source_location, parse_tree.source_location)
      else:
        result.source_location = ir_data_utils.copy(parse_tree.source_location)
    return result
  else:
    # For leaf nodes, the temporary "IR" is just the token.  Higher-level rules
    # will translate it to a real IR.
    assert isinstance(parse_tree, parser_types.Token), str(parse_tree)
    return parse_tree

# Map of productions to their handlers.
_handlers = {}

_anonymous_name_counter = 0


def _get_anonymous_field_name():
  global _anonymous_name_counter
  _anonymous_name_counter += 1
  return 'emboss_reserved_anonymous_field_{}'.format(_anonymous_name_counter)


def _handles(production_text):
  """_handles marks a function as the handler for a particular production."""
  production = parser_types.Production.parse(production_text)

  def handles(f):
    _handlers[production] = f
    return f

  return handles


def _make_prelude_import(position):
  """Helper function to construct a synthetic ir_data.Import for the prelude."""
  location = parser_types.make_location(position, position)
  return ir_data.Import(
      file_name=ir_data.String(text='', source_location=location),
      local_name=ir_data.Word(text='', source_location=location),
      source_location=location)


def _text_to_operator(text):
  """Converts an operator's textual name to its corresponding enum."""
  operations = {
      '+': ir_data.FunctionMapping.ADDITION,
      '-': ir_data.FunctionMapping.SUBTRACTION,
      '*': ir_data.FunctionMapping.MULTIPLICATION,
      '==': ir_data.FunctionMapping.EQUALITY,
      '!=': ir_data.FunctionMapping.INEQUALITY,
      '&&': ir_data.FunctionMapping.AND,
      '||': ir_data.FunctionMapping.OR,
      '>': ir_data.FunctionMapping.GREATER,
      '>=': ir_data.FunctionMapping.GREATER_OR_EQUAL,
      '<': ir_data.FunctionMapping.LESS,
      '<=': ir_data.FunctionMapping.LESS_OR_EQUAL,
  }
  return operations[text]


def _text_to_function(text):
  """Converts a function's textual name to its corresponding enum."""
  functions = {
      '$max': ir_data.FunctionMapping.MAXIMUM,
      '$present': ir_data.FunctionMapping.PRESENCE,
      '$upper_bound': ir_data.FunctionMapping.UPPER_BOUND,
      '$lower_bound': ir_data.FunctionMapping.LOWER_BOUND,
  }
  return functions[text]


################################################################################
# Grammar & parse tree to IR translation.
#
# From here to (almost) the end of the file are functions which recursively
# build an IR.  The @_handles annotations indicate the exact grammar
# production(s) handled by each function.  The handler function should take
# exactly one argument for each symbol in the production's RHS.
#
# The actual Emboss grammar is extracted directly from the @_handles
# annotations, so this is also the grammar definition.  For convenience, the
# grammar can be viewed separately in g3doc/grammar.md.
#
# At the end, symbols whose names end in "*", "+", or "?" are extracted from the
# grammar, and appropriate productions are added for zero-or-more, one-or-more,
# or zero-or-one lists, respectively.  (This is analogous to the *, +, and ?
# operators in regex.)  It is necessary for this to happen here (and not in
# lr1.py) because the generated productions must be associated with
# IR-generation functions.


# A module file is a list of documentation, then imports, then top-level
# attributes, then type definitions.  Any section may be missing.
# TODO(bolms): Should Emboss disallow completely empty files?
@_handles('module -> comment-line* doc-line* import-line* attribute-line*'
          '          type-definition*')
def _file(leading_newlines, docs, imports, attributes, type_definitions):
  """Assembles the top-level IR for a module."""
  del leading_newlines  # Unused.
  # Figure out the best synthetic source_location for the synthesized prelude
  # import.
  if imports.list:
    position = imports.list[0].source_location.start
  elif docs.list:
    position = docs.list[0].source_location.end
  elif attributes.list:
    position = attributes.list[0].source_location.start
  elif type_definitions.list:
    position = type_definitions.list[0].source_location.start
  else:
    position = 1, 1

  # If the source file is completely empty, build_ir won't automatically
  # populate the source_location attribute for the module.
  if (not docs.list and not imports.list and not attributes.list and
      not type_definitions.list):
    module_source_location = parser_types.make_location((1, 1), (1, 1))
  else:
    module_source_location = None

  return ir_data.Module(
      documentation=docs.list,
      foreign_import=[_make_prelude_import(position)] + imports.list,
      attribute=attributes.list,
      type=type_definitions.list,
      source_location=module_source_location)


@_handles('import-line ->'
          '    "import" string-constant "as" snake-word Comment? eol')
def _import(import_, file_name, as_, local_name, comment, eol):
  del import_, as_, comment, eol  # Unused
  return ir_data.Import(file_name=file_name, local_name=local_name)


@_handles('doc-line -> doc Comment? eol')
def _doc_line(doc, comment, eol):
  del comment, eol  # Unused.
  return doc


@_handles('doc -> Documentation')
def _doc(documentation):
  # As a special case, an empty documentation string may omit the trailing
  # space.
  if documentation.text == '--':
    doc_text = '-- '
  else:
    doc_text = documentation.text
  assert doc_text[0:3] == '-- ', (
      "Documentation token '{}' in unknown format.".format(
          documentation.text))
  return ir_data.Documentation(text=doc_text[3:])


# A attribute-line is just a attribute on its own line.
@_handles('attribute-line -> attribute Comment? eol')
def _attribute_line(attr, comment, eol):
  del comment, eol  # Unused.
  return attr


# A attribute is [name = value].
@_handles('attribute -> "[" attribute-context? "$default"?'
          '             snake-word ":" attribute-value "]"')
def _attribute(open_bracket, context_specifier, default_specifier, name, colon,
               attribute_value, close_bracket):
  del open_bracket, colon, close_bracket  # Unused.
  if context_specifier.list:
    return ir_data.Attribute(name=name,
                            value=attribute_value,
                            is_default=bool(default_specifier.list),
                            back_end=context_specifier.list[0])
  else:
    return ir_data.Attribute(name=name,
                            value=attribute_value,
                            is_default=bool(default_specifier.list))


@_handles('attribute-context -> "(" snake-word ")"')
def _attribute_context(open_paren, context_name, close_paren):
  del open_paren, close_paren  # Unused.
  return context_name


@_handles('attribute-value -> expression')
def _attribute_value_expression(expression):
  return ir_data.AttributeValue(expression=expression)


@_handles('attribute-value -> string-constant')
def _attribute_value_string(string):
  return ir_data.AttributeValue(string_constant=string)


@_handles('boolean-constant -> BooleanConstant')
def _boolean_constant(boolean):
  return ir_data.BooleanConstant(value=(boolean.text == 'true'))


@_handles('string-constant -> String')
def _string_constant(string):
  """Turns a String token into an ir_data.String, with proper unescaping.

  Arguments:
    string: A String token.

  Returns:
    An ir_data.String with the "text" field set to the unescaped value of
    string.text.
  """
  # TODO(bolms): If/when this logic becomes more complex (e.g., to handle \NNN
  # or \xNN escapes), extract this into a separate module with separate tests.
  assert string.text[0] == '"'
  assert string.text[-1] == '"'
  assert len(string.text) >= 2
  result = []
  for substring in re.split(r'(\\.)', string.text[1:-1]):
    if substring and substring[0] == '\\':
      assert len(substring) == 2
      result.append({'\\': '\\', '"': '"', 'n': '\n'}[substring[1]])
    else:
      result.append(substring)
  return ir_data.String(text=''.join(result))


# In Emboss, '&&' and '||' may not be mixed without parentheses.  These are all
# fine:
#
#     x && y && z
#     x || y || z
#     (x || y) && z
#     x || (y && z)
#
# These are syntax errors:
#
#     x || y && z
#     x && y || z
#
# This is accomplished by making && and || separate-but-equal in the precedence
# hierarchy.  Instead of the more traditional:
#
#     logical-expression   -> or-expression
#     or-expression        -> and-expression or-expression-right*
#     or-expression-right  -> '||' and-expression
#     and-expression       -> equality-expression and-expression-right*
#     and-expression-right -> '&&' equality-expression
#
# Or, using yacc-style precedence specifiers:
#
#     %left "||"
#     %left "&&"
#     expression -> expression
#                 | expression '||' expression
#                 | expression '&&' expression
#
# Emboss uses a slightly more complex grammar, in which '&&' and '||' are
# parallel, but unmixable:
#
#     logical-expression   -> and-expression
#                           | or-expression
#                           | equality-expression
#     or-expression        -> equality-expression or-expression-right+
#     or-expression-right  -> '||' equality-expression
#     and-expression       -> equality-expression and-expression-right+
#     and-expression-right -> '&&' equality-expression
#
# In either case, explicit parenthesization is handled elsewhere in the grammar.
@_handles('logical-expression -> and-expression')
@_handles('logical-expression -> or-expression')
@_handles('logical-expression -> comparison-expression')
@_handles('choice-expression -> logical-expression')
@_handles('expression -> choice-expression')
def _expression(expression):
  return expression


# The `logical-expression`s here means that ?: can't be chained without
# parentheses.  `x < 0 ? -1 : (x == 0 ? 0 : 1)` is OK, but `x < 0 ? -1 : x == 0
# ? 0 : 1` is not.  Parentheses are also needed in the middle: `x <= 0 ? x < 0 ?
# -1 : 0 : 1` is not syntactically valid.
@_handles('choice-expression -> logical-expression "?" logical-expression'
          '                                        ":" logical-expression')
def _choice_expression(condition, question, if_true, colon, if_false):
  location = parser_types.make_location(
      condition.source_location.start, if_false.source_location.end)
  operator_location = parser_types.make_location(
      question.source_location.start, colon.source_location.end)
  # The function_name is a bit weird, but should suffice for any error messages
  # that might need it.
  return ir_data.Expression(
      function=ir_data.Function(function=ir_data.FunctionMapping.CHOICE,
                               args=[condition, if_true, if_false],
                               function_name=ir_data.Word(
                                   text='?:',
                                   source_location=operator_location),
                               source_location=location))


@_handles('comparison-expression -> additive-expression')
def _no_op_comparative_expression(expression):
  return expression


@_handles('comparison-expression ->'
          '    additive-expression inequality-operator additive-expression')
def _comparative_expression(left, operator, right):
  location = parser_types.make_location(
      left.source_location.start, right.source_location.end)
  return ir_data.Expression(
      function=ir_data.Function(function=_text_to_operator(operator.text),
                               args=[left, right],
                               function_name=operator,
                               source_location=location))


@_handles('additive-expression -> times-expression additive-expression-right*')
@_handles('times-expression -> negation-expression times-expression-right*')
@_handles('and-expression -> comparison-expression and-expression-right+')
@_handles('or-expression -> comparison-expression or-expression-right+')
def _binary_operator_expression(expression, expression_right):
  """Builds the IR for a chain of equal-precedence left-associative operations.

  _binary_operator_expression transforms a right-recursive list of expression
  tails into a left-associative Expression tree.  For example, given the
  arguments:

      6, (Tail("+", 7), Tail("-", 8), Tail("+", 10))

  _expression produces a structure like:

     Expression(Expression(Expression(6, "+", 7), "-", 8), "+", 10)

  This transformation is necessary because strict LR(1) grammars do not allow
  left recursion.

  Note that this method is used for several productions; each of those
  productions handles a different precedence level, but are identical in form.

  Arguments:
    expression: An ir_data.Expression which is the head of the (expr, operator,
        expr, operator, expr, ...) list.
    expression_right: A list of _ExpressionTails corresponding to the (operator,
        expr, operator, expr, ...) list that comes after expression.

  Returns:
    An ir_data.Expression with the correct recursive structure to represent a
    list of left-associative operations.
  """
  e = expression
  for right in expression_right.list:
    location = parser_types.make_location(
        e.source_location.start, right.source_location.end)
    e = ir_data.Expression(
        function=ir_data.Function(
            function=_text_to_operator(right.operator.text),
            args=[e, right.expression],
            function_name=right.operator,
            source_location=location),
        source_location=location)
  return e


@_handles('comparison-expression ->'
          '    additive-expression equality-expression-right+')
@_handles('comparison-expression ->'
          '    additive-expression less-expression-right-list')
@_handles('comparison-expression ->'
          '    additive-expression greater-expression-right-list')
def _chained_comparison_expression(expression, expression_right):
  """Builds the IR for a chain of comparisons, like a == b == c.

  Like _binary_operator_expression, _chained_comparison_expression transforms a
  right-recursive list of expression tails into a left-associative Expression
  tree.  Unlike _binary_operator_expression, extra AND nodes are added.  For
  example, the following expression:

      0 <= b <= 64

  must be translated to the conceptually-equivalent expression:

      0 <= b && b <= 64

  (The middle subexpression is duplicated -- this would be a problem in a
  programming language like C where expressions like `x++` have side effects,
  but side effects do not make sense in a data definition language like Emboss.)

  _chained_comparison_expression receives a left-hand head expression and a list
  of tails, like:

      6, (Tail("<=", b), Tail("<=", 64))

  which it translates to a structure like:

      Expression(Expression(6, "<=", b), "&&", Expression(b, "<=", 64))

  The Emboss grammar is constructed such that sequences of "<", "<=", and "=="
  comparisons may be chained, and sequences of ">", ">=", and "==" can be
  chained, but greater and less-than comparisons may not; e.g., "b < 64 > a" is
  not allowed.

  Arguments:
    expression: An ir_data.Expression which is the head of the (expr, operator,
        expr, operator, expr, ...) list.
    expression_right: A list of _ExpressionTails corresponding to the (operator,
        expr, operator, expr, ...) list that comes after expression.

  Returns:
    An ir_data.Expression with the correct recursive structure to represent a
    chain of left-associative comparison operations.
  """
  sequence = [expression]
  for right in expression_right.list:
    sequence.append(right.operator)
    sequence.append(right.expression)
  comparisons = []
  for i in range(0, len(sequence) - 1, 2):
    left, operator, right = sequence[i:i+3]
    location = parser_types.make_location(
        left.source_location.start, right.source_location.end)
    comparisons.append(ir_data.Expression(
        function=ir_data.Function(
            function=_text_to_operator(operator.text),
            args=[left, right],
            function_name=operator,
            source_location=location),
        source_location=location))
  e = comparisons[0]
  for comparison in comparisons[1:]:
    location = parser_types.make_location(
        e.source_location.start, comparison.source_location.end)
    e = ir_data.Expression(
        function=ir_data.Function(
            function=ir_data.FunctionMapping.AND,
            args=[e, comparison],
            function_name=ir_data.Word(
                text='&&',
                source_location=comparison.function.args[0].source_location),
            source_location=location),
        source_location=location)
  return e


# _chained_comparison_expression, above, handles three types of chains: `a == b
# == c`, `a < b <= c`, and `a > b >= c`.
#
# This requires a bit of subtlety in the productions for
# `x-expression-right-list`, because the `==` operator may be freely mixed into
# greater-than or less-than chains, like `a < b == c <= d` or `a > b == c >= d`,
# but greater-than and less-than may not be mixed; i.e., `a < b >= c` is
# disallowed.
#
# In order to keep the grammar unambiguous -- that is, in order to ensure that
# every valid input can only be parsed in exactly one way -- the languages
# defined by `equality-expression-right*`, `greater-expression-right-list`, and
# `less-expression-right-list` cannot overlap.
#
# `equality-expression-right*`, by definition, only contains `== n` elements.
# By forcing `greater-expression-right-list` to contain at least one
# `greater-expression-right`, we can ensure that a chain like `== n == m` cannot
# be parsed as a `greater-expression-right-list`.  Similar logic applies in the
# less-than case.
#
# There is another potential source of ambiguity here: if
# `greater-expression-right-list` were
#
#     greater-expression-right-list ->
#         equality-or-greater-expression-right* greater-expression-right
#         equality-or-greater-expression-right*
#
# then a sequence like '> b > c > d' could be parsed as any of:
#
#     () (> b) ((> c) (> d))
#     ((> b)) (> c) ((> d))
#     ((> b) (> c)) (> d) ()
#
# By using `equality-expression-right*` for the first symbol, only the first
# parse is possible.
@_handles('greater-expression-right-list ->'
          '    equality-expression-right* greater-expression-right'
          '    equality-or-greater-expression-right*')
@_handles('less-expression-right-list ->'
          '    equality-expression-right* less-expression-right'
          '    equality-or-less-expression-right*')
def _chained_comparison_tails(start, middle, end):
  return _List(start.list + [middle] + end.list)


@_handles('equality-or-greater-expression-right -> equality-expression-right')
@_handles('equality-or-greater-expression-right -> greater-expression-right')
@_handles('equality-or-less-expression-right -> equality-expression-right')
@_handles('equality-or-less-expression-right -> less-expression-right')
def _equality_or_less_or_greater(right):
  return right


@_handles('and-expression-right -> and-operator comparison-expression')
@_handles('or-expression-right -> or-operator comparison-expression')
@_handles('additive-expression-right -> additive-operator times-expression')
@_handles('equality-expression-right -> equality-operator additive-expression')
@_handles('greater-expression-right -> greater-operator additive-expression')
@_handles('less-expression-right -> less-operator additive-expression')
@_handles('times-expression-right ->'
          '    multiplicative-operator negation-expression')
def _expression_right_production(operator, expression):
  return _ExpressionTail(operator, expression)


# This supports a single layer of unary plus/minus, so "+5" and "-value" are
# allowed, but "+-5" or "-+-something" are not.
@_handles('negation-expression -> additive-operator bottom-expression')
def _negation_expression_with_operator(operator, expression):
  phantom_zero_location = ir_data.Location(start=operator.source_location.start,
                                          end=operator.source_location.start)
  return ir_data.Expression(
      function=ir_data.Function(
          function=_text_to_operator(operator.text),
          args=[ir_data.Expression(
              constant=ir_data.NumericConstant(
                  value='0',
                  source_location=phantom_zero_location),
              source_location=phantom_zero_location), expression],
          function_name=operator,
          source_location=ir_data.Location(
              start=operator.source_location.start,
              end=expression.source_location.end)))


@_handles('negation-expression -> bottom-expression')
def _negation_expression(expression):
  return expression


@_handles('bottom-expression -> "(" expression ")"')
def _bottom_expression_parentheses(open_paren, expression, close_paren):
  del open_paren, close_paren  # Unused.
  return expression


@_handles('bottom-expression -> function-name "(" argument-list ")"')
def _bottom_expression_function(function, open_paren, arguments, close_paren):
  del open_paren  # Unused.
  return ir_data.Expression(
      function=ir_data.Function(
          function=_text_to_function(function.text),
          args=arguments.list,
          function_name=function,
          source_location=ir_data.Location(
              start=function.source_location.start,
              end=close_paren.source_location.end)))


@_handles('comma-then-expression -> "," expression')
def _comma_then_expression(comma, expression):
  del comma  # Unused.
  return expression


@_handles('argument-list -> expression comma-then-expression*')
def _argument_list(head, tail):
  tail.list.insert(0, head)
  return tail


@_handles('argument-list ->')
def _empty_argument_list():
  return _List([])


@_handles('bottom-expression -> numeric-constant')
def _bottom_expression_from_numeric_constant(constant):
  return ir_data.Expression(constant=constant)


@_handles('bottom-expression -> constant-reference')
def _bottom_expression_from_constant_reference(reference):
  return ir_data.Expression(constant_reference=reference)


@_handles('bottom-expression -> builtin-reference')
def _bottom_expression_from_builtin(reference):
  return ir_data.Expression(builtin_reference=reference)


@_handles('bottom-expression -> boolean-constant')
def _bottom_expression_from_boolean_constant(boolean):
  return ir_data.Expression(boolean_constant=boolean)


@_handles('bottom-expression -> field-reference')
def _bottom_expression_from_reference(reference):
  return reference


@_handles('field-reference -> snake-reference field-reference-tail*')
def _indirect_field_reference(field_reference, field_references):
  if field_references.source_location.HasField('end'):
    end_location = field_references.source_location.end
  else:
    end_location = field_reference.source_location.end
  return ir_data.Expression(field_reference=ir_data.FieldReference(
      path=[field_reference] + field_references.list,
      source_location=parser_types.make_location(
          field_reference.source_location.start, end_location)))


# If "Type.field" ever becomes syntactically valid, it will be necessary to
# check that enum values are compile-time constants.
@_handles('field-reference-tail -> "." snake-reference')
def _field_reference_tail(dot, reference):
  del dot  # Unused.
  return reference


@_handles('numeric-constant -> Number')
def _numeric_constant(number):
  # All types of numeric constant tokenize to the same symbol, because they are
  # interchangeable in source code.
  if number.text[0:2] == '0b':
    n = int(number.text.replace('_', '')[2:], 2)
  elif number.text[0:2] == '0x':
    n = int(number.text.replace('_', '')[2:], 16)
  else:
    n = int(number.text.replace('_', ''), 10)
  return ir_data.NumericConstant(value=str(n))


@_handles('type-definition -> struct')
@_handles('type-definition -> bits')
@_handles('type-definition -> enum')
@_handles('type-definition -> external')
def _type_definition(type_definition):
  return type_definition


# struct StructureName:
#   ... fields ...
# bits BitName:
#   ... fields ...
@_handles('struct -> "struct" type-name delimited-parameter-definition-list?'
          '          ":" Comment? eol struct-body')
@_handles('bits -> "bits" type-name delimited-parameter-definition-list? ":"'
          '        Comment? eol bits-body')
def _structure(struct, name, parameters, colon, comment, newline, struct_body):
  """Composes the top-level IR for an Emboss structure."""
  del colon, comment, newline  # Unused.
  ir_data_utils.builder(struct_body.structure).source_location.start.CopyFrom(
      struct.source_location.start)
  ir_data_utils.builder(struct_body.structure).source_location.end.CopyFrom(
      struct_body.source_location.end)
  if struct_body.name:
    ir_data_utils.update(struct_body.name, name)
  else:
    struct_body.name = ir_data_utils.copy(name)
  if parameters.list:
    struct_body.runtime_parameter.extend(parameters.list[0].list)
  return struct_body


@_handles('delimited-parameter-definition-list ->'
          '    "(" parameter-definition-list ")"')
def _delimited_parameter_definition_list(open_paren, parameters, close_paren):
  del open_paren, close_paren  # Unused
  return parameters


@_handles('parameter-definition -> snake-name ":" type')
def _parameter_definition(name, double_colon, parameter_type):
  del double_colon  # Unused
  return ir_data.RuntimeParameter(name=name, physical_type_alias=parameter_type)


@_handles('parameter-definition-list-tail -> "," parameter-definition')
def _parameter_definition_list_tail(comma, parameter):
  del comma  # Unused.
  return parameter


@_handles('parameter-definition-list -> parameter-definition'
          '                             parameter-definition-list-tail*')
def _parameter_definition_list(head, tail):
  tail.list.insert(0, head)
  return tail


@_handles('parameter-definition-list ->')
def _empty_parameter_definition_list():
  return _List([])


# The body of a struct: basically, the part after the first line.
@_handles('struct-body -> Indent doc-line* attribute-line*'
          '               type-definition* struct-field-block Dedent')
def _struct_body(indent, docs, attributes, types, fields, dedent):
  del indent, dedent  # Unused.
  return _structure_body(docs, attributes, types, fields,
                         ir_data.AddressableUnit.BYTE)


def _structure_body(docs, attributes, types, fields, addressable_unit):
  """Constructs the body of a structure (bits or struct) definition."""
  return ir_data.TypeDefinition(
      structure=ir_data.Structure(field=[field.field for field in fields.list]),
      documentation=docs.list,
      attribute=attributes.list,
      subtype=types.list + [subtype for field in fields.list for subtype in
                            field.subtypes],
      addressable_unit=addressable_unit)


@_handles('struct-field-block ->')
@_handles('bits-field-block ->')
@_handles('anonymous-bits-field-block ->')
def _empty_field_block():
  return _List([])


@_handles('struct-field-block ->'
          '    conditional-struct-field-block struct-field-block')
@_handles('bits-field-block ->'
          '    conditional-bits-field-block bits-field-block')
@_handles('anonymous-bits-field-block -> conditional-anonymous-bits-field-block'
          '                              anonymous-bits-field-block')
def _conditional_block_plus_field_block(conditional_block, block):
  return _List(conditional_block.list + block.list)


@_handles('struct-field-block ->'
          '    unconditional-struct-field struct-field-block')
@_handles('bits-field-block ->'
          '    unconditional-bits-field bits-field-block')
@_handles('anonymous-bits-field-block ->'
          '    unconditional-anonymous-bits-field anonymous-bits-field-block')
def _unconditional_block_plus_field_block(field, block):
  """Prepends an unconditional field to block."""
  ir_data_utils.builder(field.field).existence_condition.source_location.CopyFrom(
      field.source_location)
  ir_data_utils.builder(field.field).existence_condition.boolean_constant.source_location.CopyFrom(
      field.source_location)
  ir_data_utils.builder(field.field).existence_condition.boolean_constant.value = True
  return _List([field] + block.list)


# Struct "fields" are regular fields, inline enums, bits, or structs, anonymous
# inline bits, or virtual fields.
@_handles('unconditional-struct-field -> field')
@_handles('unconditional-struct-field -> inline-enum-field-definition')
@_handles('unconditional-struct-field -> inline-bits-field-definition')
@_handles('unconditional-struct-field -> inline-struct-field-definition')
@_handles('unconditional-struct-field -> anonymous-bits-field-definition')
@_handles('unconditional-struct-field -> virtual-field')
# Bits fields are "regular" fields, inline enums or bits, or virtual fields.
#
# Inline structs and anonymous inline bits are not allowed inside of bits:
# anonymous inline bits are pointless, and inline structs do not make sense,
# since a struct cannot be a part of a bits.
#
# Anonymous inline bits may not include virtual fields; instead, the virtual
# field should be a direct part of the enclosing structure.
@_handles('unconditional-anonymous-bits-field -> field')
@_handles('unconditional-anonymous-bits-field -> inline-enum-field-definition')
@_handles('unconditional-anonymous-bits-field -> inline-bits-field-definition')
@_handles('unconditional-bits-field -> unconditional-anonymous-bits-field')
@_handles('unconditional-bits-field -> virtual-field')
def _unconditional_field(field):
  """Handles the unifying grammar production for a struct or bits field."""
  return field


# TODO(bolms): Add 'elif' and 'else' support.
# TODO(bolms): Should nested 'if' blocks be allowed?
@_handles('conditional-struct-field-block ->'
          '    "if" expression ":" Comment? eol'
          '        Indent unconditional-struct-field+ Dedent')
@_handles('conditional-bits-field-block ->'
          '    "if" expression ":" Comment? eol'
          '        Indent unconditional-bits-field+ Dedent')
@_handles('conditional-anonymous-bits-field-block ->'
          '    "if" expression ":" Comment? eol'
          '        Indent unconditional-anonymous-bits-field+ Dedent')
def _conditional_field_block(if_keyword, expression, colon, comment, newline,
                             indent, fields, dedent):
  """Applies an existence_condition to each element of fields."""
  del if_keyword, newline, colon, comment, indent, dedent  # Unused.
  for field in fields.list:
    condition = ir_data_utils.builder(field.field).existence_condition
    condition.CopyFrom(expression)
    condition.source_location.is_disjoint_from_parent = True
  return fields


# The body of a bit field definition: basically, the part after the first line.
@_handles('bits-body -> Indent doc-line* attribute-line*'
          '             type-definition* bits-field-block Dedent')
def _bits_body(indent, docs, attributes, types, fields, dedent):
  del indent, dedent  # Unused.
  return _structure_body(docs, attributes, types, fields,
                         ir_data.AddressableUnit.BIT)


# Inline bits (defined as part of a field) are more restricted than standalone
# bits.
@_handles('anonymous-bits-body ->'
          '    Indent attribute-line* anonymous-bits-field-block Dedent')
def _anonymous_bits_body(indent, attributes, fields, dedent):
  del indent, dedent  # Unused.
  return _structure_body(_List([]), attributes, _List([]), fields,
                         ir_data.AddressableUnit.BIT)


# A field is:
#     range  type  name  (abbr)  [attr: value] [attr2: value] -- doc
#         -- doc
#         -- doc
#         [attr3: value]
#         [attr4: value]
@_handles('field ->'
          '    field-location type snake-name abbreviation? attribute* doc?'
          '    Comment? eol field-body?')
def _field(location, field_type, name, abbreviation, attributes, doc, comment,
           newline, field_body):
  """Constructs an ir_data.Field from the given components."""
  del comment  # Unused
  field_ir = ir_data.Field(location=location,
                       type=field_type,
                       name=name,
                       attribute=attributes.list,
                       documentation=doc.list)
  field = ir_data_utils.builder(field_ir)
  if field_body.list:
    field.attribute.extend(field_body.list[0].attribute)
    field.documentation.extend(field_body.list[0].documentation)
  if abbreviation.list:
    field.abbreviation.CopyFrom(abbreviation.list[0])
  field.source_location.start.CopyFrom(location.source_location.start)
  if field_body.source_location.HasField('end'):
    field.source_location.end.CopyFrom(field_body.source_location.end)
  else:
    field.source_location.end.CopyFrom(newline.source_location.end)
  return _FieldWithType(field=field_ir)


# A "virtual field" is:
#     let name = value
#         -- doc
#         -- doc
#         [attr1: value]
#         [attr2: value]
@_handles('virtual-field ->'
          '    "let" snake-name "=" expression Comment? eol field-body?')
def _virtual_field(let, name, equals, value, comment, newline, field_body):
  """Constructs an ir_data.Field from the given components."""
  del equals, comment  # Unused
  field_ir = ir_data.Field(read_transform=value, name=name)
  field = ir_data_utils.builder(field_ir)
  if field_body.list:
    field.attribute.extend(field_body.list[0].attribute)
    field.documentation.extend(field_body.list[0].documentation)
  field.source_location.start.CopyFrom(let.source_location.start)
  if field_body.source_location.HasField('end'):
    field.source_location.end.CopyFrom(field_body.source_location.end)
  else:
    field.source_location.end.CopyFrom(newline.source_location.end)
  return _FieldWithType(field=field_ir)


# An inline enum is:
#     range  "enum"  name  (abbr):
#         -- doc
#         -- doc
#         [attr3: value]
#         [attr4: value]
#         NAME = 10
#         NAME2 = 20
@_handles('inline-enum-field-definition ->'
          '    field-location "enum" snake-name abbreviation? ":" Comment? eol'
          '    enum-body')
def _inline_enum_field(location, enum, name, abbreviation, colon, comment,
                       newline, enum_body):
  """Constructs an ir_data.Field for an inline enum field."""
  del enum, colon, comment, newline  # Unused.
  return _inline_type_field(location, name, abbreviation, enum_body)


@_handles(
    'inline-struct-field-definition ->'
    '    field-location "struct" snake-name abbreviation? ":" Comment? eol'
    '    struct-body')
def _inline_struct_field(location, struct, name, abbreviation, colon, comment,
                         newline, struct_body):
  del struct, colon, comment, newline  # Unused.
  return _inline_type_field(location, name, abbreviation, struct_body)


@_handles('inline-bits-field-definition ->'
          '    field-location "bits" snake-name abbreviation? ":" Comment? eol'
          '    bits-body')
def _inline_bits_field(location, bits, name, abbreviation, colon, comment,
                       newline, bits_body):
  del bits, colon, comment, newline  # Unused.
  return _inline_type_field(location, name, abbreviation, bits_body)


def _inline_type_field(location, name, abbreviation, body):
  """Shared implementation of _inline_enum_field and _anonymous_bit_field."""
  field_ir = ir_data.Field(location=location,
                       name=name,
                       attribute=body.attribute,
                       documentation=body.documentation)
  field = ir_data_utils.builder(field_ir)
  # All attributes should be attached to the field, not the type definition: if
  # the user wants to use type attributes, they should create a separate type
  # definition and reference it.
  del body.attribute[:]
  type_name = ir_data_utils.copy(name)
  ir_data_utils.builder(type_name).name.text = name_conversion.snake_to_camel(type_name.name.text)
  field.type.atomic_type.reference.source_name.extend([type_name.name])
  field.type.atomic_type.reference.source_location.CopyFrom(
      type_name.source_location)
  field.type.atomic_type.reference.is_local_name = True
  field.type.atomic_type.source_location.CopyFrom(type_name.source_location)
  field.type.source_location.CopyFrom(type_name.source_location)
  if abbreviation.list:
    field.abbreviation.CopyFrom(abbreviation.list[0])
  field.source_location.start.CopyFrom(location.source_location.start)
  ir_data_utils.builder(body.source_location).start.CopyFrom(location.source_location.start)
  if body.HasField('enumeration'):
    ir_data_utils.builder(body.enumeration).source_location.CopyFrom(body.source_location)
  else:
    assert body.HasField('structure')
    ir_data_utils.builder(body.structure).source_location.CopyFrom(body.source_location)
  ir_data_utils.builder(body).name.CopyFrom(type_name)
  field.source_location.end.CopyFrom(body.source_location.end)
  subtypes = [body] + list(body.subtype)
  del body.subtype[:]
  return _FieldWithType(field=field_ir, subtypes=subtypes)


@_handles('anonymous-bits-field-definition ->'
          '    field-location "bits" ":" Comment? eol anonymous-bits-body')
def _anonymous_bit_field(location, bits_keyword, colon, comment, newline,
                         bits_body):
  """Constructs an ir_data.Field for an anonymous bit field."""
  del colon, comment, newline  # Unused.
  name = ir_data.NameDefinition(
      name=ir_data.Word(
          text=_get_anonymous_field_name(),
          source_location=bits_keyword.source_location),
      source_location=bits_keyword.source_location,
      is_anonymous=True)
  return _inline_type_field(location, name, _List([]), bits_body)


@_handles('field-body -> Indent doc-line* attribute-line* Dedent')
def _field_body(indent, docs, attributes, dedent):
  del indent, dedent  # Unused.
  return ir_data.Field(documentation=docs.list, attribute=attributes.list)


# A parenthetically-denoted abbreviation.
@_handles('abbreviation -> "(" snake-word ")"')
def _abbreviation(open_paren, word, close_paren):
  del open_paren, close_paren  # Unused.
  return word


# enum EnumName:
#   ... values ...
@_handles('enum -> "enum" type-name ":" Comment? eol enum-body')
def _enum(enum, name, colon, comment, newline, enum_body):
  del colon, comment, newline  # Unused.
  ir_data_utils.builder(enum_body.enumeration).source_location.start.CopyFrom(
      enum.source_location.start)
  ir_data_utils.builder(enum_body.enumeration).source_location.end.CopyFrom(
      enum_body.source_location.end)
  ir_data_utils.builder(enum_body).name.CopyFrom(name)
  return enum_body


# [enum Foo:]
#   name = value
#   name = value
@_handles('enum-body -> Indent doc-line* attribute-line* enum-value+ Dedent')
def _enum_body(indent, docs, attributes, values, dedent):
  del indent, dedent  # Unused.
  return ir_data.TypeDefinition(
      enumeration=ir_data.Enum(value=values.list),
      documentation=docs.list,
      attribute=attributes.list,
      addressable_unit=ir_data.AddressableUnit.BIT)


# name = value
@_handles('enum-value -> '
          '    constant-name "=" expression attribute* doc? Comment? eol enum-value-body?')
def _enum_value(name, equals, expression, attribute, documentation, comment, newline,
                body):
  del equals, comment, newline  # Unused.
  result = ir_data.EnumValue(name=name,
                            value=expression,
                            documentation=documentation.list,
                            attribute=attribute.list)
  if body.list:
    result.documentation.extend(body.list[0].documentation)
    result.attribute.extend(body.list[0].attribute)
  return result


@_handles('enum-value-body -> Indent doc-line* attribute-line* Dedent')
def _enum_value_body(indent, docs, attributes, dedent):
  del indent, dedent  # Unused.
  return ir_data.EnumValue(documentation=docs.list, attribute=attributes.list)


# An external is just a declaration that a type exists and has certain
# attributes.
@_handles('external -> "external" type-name ":" Comment? eol external-body')
def _external(external, name, colon, comment, newline, external_body):
  del colon, comment, newline  # Unused.
  ir_data_utils.builder(external_body.source_location).start.CopyFrom(external.source_location.start)
  if external_body.name:
    ir_data_utils.update(external_body.name, name)
  else:
    external_body.name = ir_data_utils.copy(name)
  return external_body


# This syntax implicitly requires either a documentation line or a attribute
# line, or it won't parse (because no Indent/Dedent tokens will be emitted).
@_handles('external-body -> Indent doc-line* attribute-line* Dedent')
def _external_body(indent, docs, attributes, dedent):
  return ir_data.TypeDefinition(
      external=ir_data.External(
          # Set source_location here, since it won't be set automatically.
          source_location=ir_data.Location(start=indent.source_location.start,
                                          end=dedent.source_location.end)),
      documentation=docs.list,
      attribute=attributes.list)


@_handles('field-location -> expression "[" "+" expression "]"')
def _field_location(start, open_bracket, plus, size, close_bracket):
  del open_bracket, plus, close_bracket  # Unused.
  return ir_data.FieldLocation(start=start, size=size)


@_handles('delimited-argument-list -> "(" argument-list ")"')
def _type_argument_list(open_paren, arguments, close_paren):
  del open_paren, close_paren  # Unused
  return arguments


# A type is "TypeName" or "TypeName[length]" or "TypeName[length][length]", etc.
# An array type may have an empty length ("Type[]").  This is only valid for the
# outermost length (the last set of brackets), but that must be checked
# elsewhere.
@_handles('type -> type-reference delimited-argument-list? type-size-specifier?'
          '        array-length-specifier*')
def _type(reference, parameters, size, array_spec):
  """Builds the IR for a type specifier."""
  base_type_source_location_end = reference.source_location.end
  atomic_type_source_location_end = reference.source_location.end
  if parameters.list:
    base_type_source_location_end = parameters.source_location.end
    atomic_type_source_location_end = parameters.source_location.end
  if size.list:
    base_type_source_location_end = size.source_location.end
  base_type_location = parser_types.make_location(
      reference.source_location.start,
      base_type_source_location_end)
  atomic_type_location = parser_types.make_location(
      reference.source_location.start,
      atomic_type_source_location_end)
  t = ir_data.Type(
      atomic_type=ir_data.AtomicType(
          reference=ir_data_utils.copy(reference),
          source_location=atomic_type_location,
          runtime_parameter=parameters.list[0].list if parameters.list else []),
      size_in_bits=size.list[0] if size.list else None,
      source_location=base_type_location)
  for length in array_spec.list:
    location = parser_types.make_location(
        t.source_location.start, length.source_location.end)
    if isinstance(length, ir_data.Expression):
      t = ir_data.Type(
          array_type=ir_data.ArrayType(base_type=t,
                                      element_count=length,
                                      source_location=location),
          source_location=location)
    elif isinstance(length, ir_data.Empty):
      t = ir_data.Type(
          array_type=ir_data.ArrayType(base_type=t,
                                      automatic=length,
                                      source_location=location),
          source_location=location)
    else:
      assert False, "Shouldn't be here."
  return t


# TODO(bolms): Should symbolic names or expressions be allowed?  E.g.,
# UInt:FIELD_SIZE or UInt:(16 + 16)?
@_handles('type-size-specifier -> ":" numeric-constant')
def _type_size_specifier(colon, numeric_constant):
  """handles the ":32" part of a type specifier like "UInt:32"."""
  del colon
  return ir_data.Expression(constant=numeric_constant)


# The distinctions between different formats of NameDefinitions, Words, and
# References are enforced during parsing, but not propagated to the IR.
@_handles('type-name -> type-word')
@_handles('snake-name -> snake-word')
@_handles('constant-name -> constant-word')
def _name(word):
  return ir_data.NameDefinition(name=word)


@_handles('type-word -> CamelWord')
@_handles('snake-word -> SnakeWord')
@_handles('builtin-field-word -> "$size_in_bits"')
@_handles('builtin-field-word -> "$size_in_bytes"')
@_handles('builtin-field-word -> "$max_size_in_bits"')
@_handles('builtin-field-word -> "$max_size_in_bytes"')
@_handles('builtin-field-word -> "$min_size_in_bits"')
@_handles('builtin-field-word -> "$min_size_in_bytes"')
@_handles('builtin-word -> "$is_statically_sized"')
@_handles('builtin-word -> "$static_size_in_bits"')
@_handles('builtin-word -> "$next"')
@_handles('constant-word -> ShoutyWord')
@_handles('and-operator -> "&&"')
@_handles('or-operator -> "||"')
@_handles('less-operator -> "<="')
@_handles('less-operator -> "<"')
@_handles('greater-operator -> ">="')
@_handles('greater-operator -> ">"')
@_handles('equality-operator -> "=="')
@_handles('inequality-operator -> "!="')
@_handles('additive-operator -> "+"')
@_handles('additive-operator -> "-"')
@_handles('multiplicative-operator -> "*"')
@_handles('function-name -> "$max"')
@_handles('function-name -> "$present"')
@_handles('function-name -> "$upper_bound"')
@_handles('function-name -> "$lower_bound"')
def _word(word):
  return ir_data.Word(text=word.text)


@_handles('type-reference -> type-reference-tail')
@_handles('constant-reference -> constant-reference-tail')
def _un_module_qualified_type_reference(reference):
  return reference


@_handles('constant-reference-tail -> constant-word')
@_handles('type-reference-tail -> type-word')
@_handles('snake-reference -> snake-word')
@_handles('snake-reference -> builtin-field-word')
def _reference(word):
  return ir_data.Reference(source_name=[word])


@_handles('builtin-reference -> builtin-word')
def _builtin_reference(word):
  return ir_data.Reference(source_name=[word],
                          canonical_name=ir_data.CanonicalName(
                              object_path=[word.text]))


# Because constant-references ("Enum.NAME") are used in the same contexts as
# field-references ("field.subfield"), module-qualified constant references
# ("module.Enum.VALUE") have to take snake-reference, not snake-word, on the
# left side of the dot.  Otherwise, when a "snake_word" is followed by a "." in
# an expression context, the LR(1) parser cannot determine whether to reduce the
# snake-word to snake-reference (to eventually become field-reference), or to
# shift the dot onto the stack (to eventually become constant-reference).  By
# using snake-reference as the head of both, the parser can always reduce, then
# shift the dot, then determine whether to proceed with constant-reference if it
# sees "snake_name.TypeName" or field-reference if it sees
# "snake_name.snake_name".
@_handles('constant-reference -> snake-reference "." constant-reference-tail')
def _module_qualified_constant_reference(new_head, dot, reference):
  del dot  # Unused.
  new_source_name = list(new_head.source_name) + list(reference.source_name)
  del reference.source_name[:]
  reference.source_name.extend(new_source_name)
  return reference


@_handles('constant-reference-tail -> type-word "." constant-reference-tail')
# module.Type.SubType.name is a reference to something that *must* be a
# constant.
@_handles('constant-reference-tail -> type-word "." snake-reference')
@_handles('type-reference-tail -> type-word "." type-reference-tail')
@_handles('type-reference -> snake-word "." type-reference-tail')
def _qualified_reference(word, dot, reference):
  """Adds a name. or Type. qualification to the head of a reference."""
  del dot  # Unused.
  new_source_name = [word] + list(reference.source_name)
  del reference.source_name[:]
  reference.source_name.extend(new_source_name)
  return reference


# Arrays are properly translated to IR in _type().
@_handles('array-length-specifier -> "[" expression "]"')
def _array_length_specifier(open_bracket, length, close_bracket):
  del open_bracket, close_bracket  # Unused.
  return length


# An array specifier can end with empty brackets ("arr[3][]"), in which case the
# array's size is inferred from the size of its enclosing field.
@_handles('array-length-specifier -> "[" "]"')
def _auto_array_length_specifier(open_bracket, close_bracket):
  # Note that the Void's source_location is the space between the brackets (if
  # any).
  return ir_data.Empty(
      source_location=ir_data.Location(start=open_bracket.source_location.end,
                                      end=close_bracket.source_location.start))


@_handles('eol -> "\\n" comment-line*')
def _eol(eol, comments):
  del comments  # Unused
  return eol


@_handles('comment-line -> Comment? "\\n"')
def _comment_line(comment, eol):
  del comment  # Unused
  return eol


def _finalize_grammar():
  """_Finalize adds productions for foo*, foo+, and foo? symbols."""
  star_symbols = set()
  plus_symbols = set()
  option_symbols = set()
  for production in _handlers:
    for symbol in production.rhs:
      if symbol[-1] == '*':
        star_symbols.add(symbol[:-1])
      elif symbol[-1] == '+':
        # symbol+ relies on the rule for symbol*
        star_symbols.add(symbol[:-1])
        plus_symbols.add(symbol[:-1])
      elif symbol[-1] == '?':
        option_symbols.add(symbol[:-1])
  for symbol in star_symbols:
    _handles('{s}* -> {s} {s}*'.format(s=symbol))(
        lambda e, r: _List([e] + r.list))
    _handles('{s}* ->'.format(s=symbol))(lambda: _List([]))
  for symbol in plus_symbols:
    _handles('{s}+ -> {s} {s}*'.format(s=symbol))(
        lambda e, r: _List([e] + r.list))
  for symbol in option_symbols:
    _handles('{s}? -> {s}'.format(s=symbol))(lambda e: _List([e]))
    _handles('{s}? ->'.format(s=symbol))(lambda: _List([]))


_finalize_grammar()

# End of grammar.
################################################################################

# These export the grammar used by module_ir so that parser_generator can build
# a parser for the same language.
START_SYMBOL = 'module'
EXPRESSION_START_SYMBOL = 'expression'
PRODUCTIONS = list(_handlers.keys())