carbon-lang/explorer/syntax/parser.ypp

// Part of the Carbon Language project, under the Apache License v2.0 with LLVM
// Exceptions. See /LICENSE for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

// -----------------------------------------------------------------------------
// Bison Configuration
// -----------------------------------------------------------------------------

%require "3.2"
%language "c++"

// We don't need a separate header for Bison locations.
%define api.location.file none

// Use a type-safe C++ variant for semantic values
%define api.value.type variant

// Have Bison generate the functions ‘make_TEXT’ and ‘make_NUMBER’, but also
// ‘make_YYEOF’, for the end of input.
%define api.token.constructor

// Generate the parser as `::Carbon::Parser`.
%define api.namespace { Carbon }
%define api.parser.class { Parser }

// Make parse error messages more detailed
%define parse.error verbose

// Enable support for parser debugging
%define parse.trace true

// Generate location structs.
%locations

// Parameters to the parser and lexer.
//
// Parameters to the parser are stored therein as protected data members, and
// thus available to its methods.

// "inout" parameters passed to both the parser and the lexer.
%param {Nonnull<Arena*> arena}
%param {yyscan_t yyscanner}
%param {ParseAndLexContext& context}

// "out" parameter passed to the parser, where the AST is written.
%parse-param {std::optional<AST>* ast}

// No shift-reduce conflicts are expected.
// See README.md#precedence-and-associativity for a description of how
// operator precedence is expressed.
%expect 0

// -----------------------------------------------------------------------------

%code top {
  #include <algorithm>
  #include <cstdarg>
  #include <cstdio>
  #include <cstdlib>
  #include <vector>

  #include "explorer/syntax/parse_and_lex_context.h"
  #include "llvm/ADT/StringExtras.h"
  #include "llvm/Support/FormatVariadic.h"
  #include "llvm/Support/raw_ostream.h"
}  // %code top

%code requires {
  #include <optional>

  #include "explorer/ast/ast.h"
  #include "explorer/ast/declaration.h"
  #include "explorer/ast/expression.h"
  #include "explorer/ast/expression_category.h"
  #include "explorer/ast/paren_contents.h"
  #include "explorer/ast/pattern.h"
  #include "explorer/common/arena.h"
  #include "explorer/common/nonnull.h"
  #include "explorer/syntax/bison_wrap.h"

  namespace Carbon {
  class ParseAndLexContext;
  }  // namespace Carbon

  typedef void* yyscan_t;
}  // %code requires

%code {
  void Carbon::Parser::error(const location_type&, const std::string& message) {
    context.RecordSyntaxError(message);
  }
}  // %code

%token <int> integer_literal
%token <std::string> identifier
%token <IntrinsicExpression::Intrinsic> intrinsic_identifier
%token <std::string> sized_type_literal
%token <std::string> string_literal
%type <std::string> designator
%type <ImplKind> impl_kind_intro
%type <Nonnull<Expression*>> impl_type
%type <std::pair<LibraryName, bool>> package_directive
%type <LibraryName> import_directive
%type <std::vector<LibraryName>> import_directives
%type <std::string> optional_library_path
%type <bool> api_or_impl
%type <VirtualOverride> fn_virtual_override_intro
%type <VirtualOverride> destructor_virtual_override_intro
%type <ClassExtensibility> class_declaration_extensibility
%type <std::optional<Nonnull<Expression*>>> class_declaration_extends
%type <Nonnull<Declaration*>> declaration
%type <BisonWrap<DeclaredName>> declared_name
%type <Nonnull<FunctionDeclaration*>> function_declaration
%type <Nonnull<DestructorDeclaration*>> destructor_declaration
%type <Nonnull<MixDeclaration*>> mix_declaration
%type <Nonnull<AliasDeclaration*>> alias_declaration
%type <Nonnull<ImplDeclaration*>> impl_declaration
%type <Nonnull<MatchFirstDeclaration*>> match_first_declaration
%type <std::vector<Nonnull<ImplDeclaration*>>> match_first_declaration_list
%type <std::vector<Nonnull<Declaration*>>> declaration_list
%type <std::vector<Nonnull<Declaration*>>> class_body
%type <std::vector<Nonnull<Declaration*>>> mixin_body
%type <std::vector<Nonnull<Declaration*>>> interface_body
%type <std::vector<Nonnull<Declaration*>>> impl_body
%type <Nonnull<Statement*>> statement
%type <Nonnull<Statement*>> assign_statement
%type <AssignOperator> assign_operator
%type <Nonnull<If*>> if_statement
%type <std::optional<Nonnull<Block*>>> optional_else
%type <std::pair<Nonnull<Expression*>, bool>> return_expression
%type <Nonnull<Block*>> block
%type <std::vector<Nonnull<Statement*>>> statement_list
%type <Nonnull<Expression*>> primary_expression
%type <Nonnull<Expression*>> postfix_expression
%type <Nonnull<Expression*>> ref_deref_expression
%type <Nonnull<Expression*>> type_expression
%type <Nonnull<Expression*>> fn_type_expression
%type <Nonnull<Expression*>> minus_expression
%type <Nonnull<Expression*>> complement_expression
%type <Nonnull<Expression*>> unary_expression
%type <Nonnull<Expression*>> simple_binary_operand
%type <Nonnull<Expression*>> multiplicative_lhs
%type <Nonnull<Expression*>> multiplicative_expression
%type <Nonnull<Expression*>> additive_operand
%type <Nonnull<Expression*>> additive_lhs
%type <Nonnull<Expression*>> additive_expression
%type <Nonnull<Expression*>> modulo_expression
%type <Nonnull<Expression*>> bitwise_and_lhs
%type <Nonnull<Expression*>> bitwise_and_expression
%type <Nonnull<Expression*>> bitwise_or_lhs
%type <Nonnull<Expression*>> bitwise_or_expression
%type <Nonnull<Expression*>> bitwise_xor_lhs
%type <Nonnull<Expression*>> bitwise_xor_expression
%type <Nonnull<Expression*>> bitwise_expression
%type <Nonnull<Expression*>> bit_shift_expression
%type <Nonnull<Expression*>> as_expression
%type <Nonnull<Expression*>> unimpl_expression
%type <Nonnull<Expression*>> value_expression
%type <Nonnull<Expression*>> comparison_operand
%type <Nonnull<Expression*>> comparison_expression
%type <Nonnull<Expression*>> not_expression
%type <Nonnull<Expression*>> predicate_expression
%type <Nonnull<Expression*>> and_or_operand
%type <Nonnull<Expression*>> and_lhs
%type <Nonnull<Expression*>> and_expression
%type <Nonnull<Expression*>> or_lhs
%type <Nonnull<Expression*>> or_expression
%type <Nonnull<WhereClause*>> where_clause
%type <std::vector<Nonnull<WhereClause*>>> where_clause_list
%type <Nonnull<Expression*>> where_expression
%type <Nonnull<Expression*>> type_or_where_expression
%type <Nonnull<Expression*>> statement_expression
%type <Nonnull<Expression*>> if_expression
%type <Nonnull<Expression*>> expression
%type <Nonnull<Expression*>> mixin_import
%type <Nonnull<GenericBinding*>> generic_binding
%type <Nonnull<Pattern*>> deduced_param
%type <std::vector<Nonnull<AstNode*>>> deduced_params
%type <std::vector<Nonnull<AstNode*>>> impl_deduced_params
%type <std::vector<Nonnull<AstNode*>>> deduced_param_list
%type <Nonnull<Pattern*>> pattern
%type <Nonnull<Pattern*>> non_expression_pattern
%type <BisonWrap<ReturnTerm>> return_term
%type <Nonnull<Expression*>> paren_expression
%type <Nonnull<StructLiteral*>> struct_literal
%type <std::vector<FieldInitializer>> struct_literal_contents
%type <Nonnull<StructTypeLiteral*>> struct_type_literal
%type <std::vector<FieldInitializer>> struct_type_literal_contents
%type <Nonnull<TupleLiteral*>> tuple
%type <std::string> binding_lhs
%type <Nonnull<BindingPattern*>> variable_declaration
%type <ParenContents<Expression>> paren_expression_base
%type <ParenContents<Expression>> paren_expression_contents
%type <Nonnull<Pattern*>> paren_pattern
%type <Nonnull<TuplePattern*>> tuple_pattern
%type <Nonnull<TuplePattern*>> maybe_empty_tuple_pattern
%type <std::optional<Nonnull<TuplePattern*>>> type_params
%type <ParenContents<Pattern>> paren_pattern_base
%type <ParenContents<Pattern>> paren_pattern_contents
%type <Nonnull<AlternativeSignature*>> alternative
%type <std::vector<Nonnull<AlternativeSignature*>>> alternative_list
%type <std::vector<Nonnull<AlternativeSignature*>>> alternative_list_contents
%type <BisonWrap<Match::Clause>> clause
%type <std::vector<Match::Clause>> clause_list
%type <Operator> comparison_operator;

%token
  // Most tokens have their spelling defined in lexer.lpp.
  // table-begin
  ABSTRACT
  ADDR
  ALIAS
  AMPERSAND
  AMPERSAND_EQUAL
  AND
  API
  ARROW
  AS
  AUTO
  BASE
  BOOL
  BREAK
  CARET
  CARET_EQUAL
  CASE
  CHOICE
  CLASS
  COLON
  COLON_BANG
  COMMA
  CONSTRAINT
  CONTINUE
  DEFAULT
  DESTRUCTOR
  DOUBLE_ARROW
  ELSE
  EQUAL
  EQUAL_EQUAL
  EXTENDS
  EXTERNAL
  FALSE
  FN
  FN_TYPE
  FOR
  FORALL
  GREATER
  GREATER_EQUAL
  GREATER_GREATER
  GREATER_GREATER_EQUAL
  IF
  IMPL
  IMPLS
  IMPORT
  IN
  INTERFACE
  LEFT_CURLY_BRACE
  LEFT_PARENTHESIS
  LEFT_SQUARE_BRACKET
  LESS
  LESS_EQUAL
  LESS_LESS
  LESS_LESS_EQUAL
  LET
  LIBRARY
  MATCH
  MATCH_FIRST
  MINUS
  MINUS_EQUAL
  MINUS_MINUS
  MIX
  MIXIN
  NAMESPACE
  NOT
  NOT_EQUAL
  OR
  OR_EQUAL
  PACKAGE
  PERCENT
  PERCENT_EQUAL
  PERIOD
  PIPE
  PIPE_EQUAL
  PLUS
  PLUS_EQUAL
  PLUS_PLUS
  RETURN
  RETURNED
  RIGHT_CURLY_BRACE
  RIGHT_PARENTHESIS
  RIGHT_SQUARE_BRACKET
  SELF
  SEMICOLON
  SLASH
  SLASH_EQUAL
  STAR_EQUAL
  STRING
  TEMPLATE
  THEN
  TRUE
  TYPE
  UNDERSCORE
  UNIMPL_EXAMPLE
  VAR
  VIRTUAL
  WHERE
  WHILE
  // table-end
  // Used to track EOF.
  END_OF_FILE 0
  // Only used for precedence.
  FNARROW "-> in return type"
  // The lexer determines the arity and fixity of each `*` based on whitespace
  // and adjacent tokens. UNARY_STAR indicates that the operator is unary but
  // could be either prefix or postfix.
  UNARY_STAR "unary *"
  PREFIX_STAR "prefix *"
  POSTFIX_STAR "postfix *"
  BINARY_STAR "binary *"
;

%start input
%%
input: package_directive import_directives declaration_list
    {
      *ast = AST({.package = $[package_directive].first,
                  .is_api = $[package_directive].second,
                  .imports = std::move($[import_directives]),
                  .declarations = std::move($[declaration_list])});
    }
;
package_directive:
  PACKAGE identifier optional_library_path api_or_impl SEMICOLON
    {
      $$ = {LibraryName(
                {.package = $[identifier], .path = $[optional_library_path]}),
            $[api_or_impl]};
    }
;
import_directive:
  IMPORT identifier optional_library_path SEMICOLON
    {
      $$ = LibraryName(
          {.package = $[identifier], .path = $[optional_library_path]});
    }
;
import_directives:
  // Empty
    { $$ = std::vector<LibraryName>(); }
| import_directives[accumulated_import_directives] import_directive
    {
      $$ = std::move($[accumulated_import_directives]);
      $$.push_back($[import_directive]);
    }
;
optional_library_path:
  // Empty
    { $$ = ""; }
| LIBRARY string_literal
    { $$ = $[string_literal]; }
;
api_or_impl:
  API
    { $$ = true; }
| IMPL
    { $$ = false; }
;
primary_expression:
  identifier
    {
      $$ =
          arena->New<IdentifierExpression>(context.source_loc(), $[identifier]);
    }
| designator
    {
      // `.Foo` is rewritten to `.Self.Foo`.
      $$ = arena->New<SimpleMemberAccessExpression>(
          context.source_loc(),
          arena->New<DotSelfExpression>(context.source_loc()), $[designator]);
    }
| PERIOD SELF
    { $$ = arena->New<DotSelfExpression>(context.source_loc()); }
| integer_literal
    { $$ = arena->New<IntLiteral>(context.source_loc(), $[integer_literal]); }
| string_literal
    { $$ = arena->New<StringLiteral>(context.source_loc(), $[string_literal]); }
| TRUE
    { $$ = arena->New<BoolLiteral>(context.source_loc(), true); }
| FALSE
    { $$ = arena->New<BoolLiteral>(context.source_loc(), false); }
| sized_type_literal
    {
      int val = 0;
      if (!llvm::to_integer(llvm::StringRef($[sized_type_literal]).substr(1),
                            val)) {
        context.RecordSyntaxError(
            llvm::formatv("Invalid type literal: {0}", $[sized_type_literal]));
        YYERROR;
      } else if ($[sized_type_literal][0] != 'i' || val != 32) {
        context.RecordSyntaxError(llvm::formatv(
            "Only i32 is supported for now: {0}", $[sized_type_literal]));
        YYERROR;
      } else {
        $$ = arena->New<IntTypeLiteral>(context.source_loc());
      }
    }
| SELF
    // TODO: Should we create a new TypeLiteral for `Self`?
    { $$ = arena->New<IdentifierExpression>(context.source_loc(), "Self"); }
| STRING
    { $$ = arena->New<StringTypeLiteral>(context.source_loc()); }
| BOOL
    { $$ = arena->New<BoolTypeLiteral>(context.source_loc()); }
| TYPE
    { $$ = arena->New<TypeTypeLiteral>(context.source_loc()); }
| paren_expression { $$ = $[paren_expression]; }
| struct_literal { $$ = $[struct_literal]; }
| struct_type_literal { $$ = $[struct_type_literal]; }
| LEFT_SQUARE_BRACKET expression[type_expression] SEMICOLON
  expression[size_expression] RIGHT_SQUARE_BRACKET
    {
      $$ = arena->New<ArrayTypeLiteral>(context.source_loc(),
                                        $[type_expression], $[size_expression]);
    }
| LEFT_SQUARE_BRACKET expression[type_expression] SEMICOLON RIGHT_SQUARE_BRACKET
    {
      $$ = arena->New<ArrayTypeLiteral>(context.source_loc(),
                                        $[type_expression]);
    }
;
postfix_expression:
  primary_expression
| postfix_expression[child_postfix_expression] designator
    {
      $$ = arena->New<SimpleMemberAccessExpression>(
          context.source_loc(), $[child_postfix_expression], $[designator]);
    }
| postfix_expression[child_postfix_expression] ARROW identifier
    {
      auto deref = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Deref,
          std::vector<Nonnull<Expression*>>({$[child_postfix_expression]}));
      $$ = arena->New<SimpleMemberAccessExpression>(context.source_loc(), deref,
                                                    $[identifier]);
    }
| postfix_expression[child_postfix_expression] PERIOD LEFT_PARENTHESIS
  expression RIGHT_PARENTHESIS
    {
      $$ = arena->New<CompoundMemberAccessExpression>(
          context.source_loc(), $[child_postfix_expression], $[expression]);
    }
| postfix_expression[child_postfix_expression] ARROW LEFT_PARENTHESIS expression
  RIGHT_PARENTHESIS
    {
      auto deref = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Deref,
          std::vector<Nonnull<Expression*>>({$[child_postfix_expression]}));
      $$ = arena->New<CompoundMemberAccessExpression>(context.source_loc(),
                                                      deref, $[expression]);
    }
| postfix_expression[child_postfix_expression] LEFT_SQUARE_BRACKET expression
  RIGHT_SQUARE_BRACKET
    {
      $$ = arena->New<IndexExpression>(
          context.source_loc(), $[child_postfix_expression], $[expression]);
    }
| intrinsic_identifier tuple
    {
      $$ = arena->New<IntrinsicExpression>($[intrinsic_identifier], $[tuple],
                                           context.source_loc());
    }
| postfix_expression[child_postfix_expression] tuple
    {
      $$ = arena->New<CallExpression>(context.source_loc(),
                                      $[child_postfix_expression], $[tuple]);
    }
| postfix_expression[child_postfix_expression] POSTFIX_STAR
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Ptr,
          std::vector<Nonnull<Expression*>>({$[child_postfix_expression]}));
    }
| postfix_expression[child_postfix_expression] UNARY_STAR
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Ptr,
          std::vector<Nonnull<Expression*>>({$[child_postfix_expression]}));
    }
;
ref_deref_expression:
  postfix_expression
| PREFIX_STAR ref_deref_expression[child_ref_deref_expression]
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Deref,
          std::vector<Nonnull<Expression*>>({$[child_ref_deref_expression]}));
    }
| UNARY_STAR ref_deref_expression[child_ref_deref_expression]
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Deref,
          std::vector<Nonnull<Expression*>>({$[child_ref_deref_expression]}));
    }
| AMPERSAND ref_deref_expression[child_ref_deref_expression]
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::AddressOf,
          std::vector<Nonnull<Expression*>>({$[child_ref_deref_expression]}));
    }
;
fn_type_expression:
  FN_TYPE tuple ARROW type_expression
    {
      $$ = arena->New<FunctionTypeLiteral>(context.source_loc(), $[tuple],
                                           $[type_expression]);
    }
;
type_expression:
  ref_deref_expression
| bitwise_and_expression
| fn_type_expression
;
minus_expression:
  // ref_deref_expression excluded due to precedence diamond.
  MINUS ref_deref_expression
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Neg,
          std::vector<Nonnull<Expression*>>({$[ref_deref_expression]}));
    }
;
complement_expression:
  // ref_deref_expression excluded due to precedence diamond.
  CARET ref_deref_expression
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Complement,
          std::vector<Nonnull<Expression*>>({$[ref_deref_expression]}));
    }
;
unary_expression:
  // ref_deref_expression excluded due to precedence diamond.
  minus_expression
| complement_expression
;
// A simple_binary_operand is an operand of a binary operator
// that is not itself a binary operator expression.
simple_binary_operand:
  ref_deref_expression
| unary_expression
;
multiplicative_lhs:
  simple_binary_operand
| multiplicative_expression
;
multiplicative_expression:
  multiplicative_lhs BINARY_STAR simple_binary_operand
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Mul,
          std::vector<Nonnull<Expression*>>(
              {$[multiplicative_lhs], $[simple_binary_operand]}));
    }
| multiplicative_lhs SLASH simple_binary_operand
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Div,
          std::vector<Nonnull<Expression*>>(
              {$[multiplicative_lhs], $[simple_binary_operand]}));
    }
;
additive_operand:
  simple_binary_operand
| multiplicative_expression
;
additive_lhs:
  simple_binary_operand
| additive_expression
;
additive_expression:
  multiplicative_expression
| additive_lhs PLUS additive_operand
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Add,
          std::vector<Nonnull<Expression*>>(
              {$[additive_lhs], $[additive_operand]}));
    }
| additive_lhs MINUS additive_operand
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Sub,
          std::vector<Nonnull<Expression*>>(
              {$[additive_lhs], $[additive_operand]}));
    }
;
modulo_expression:
  simple_binary_operand[lhs_simple_binary_operand] PERCENT
  simple_binary_operand[rhs_simple_binary_operand]
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Mod,
          std::vector<Nonnull<Expression*>>(
              {$[lhs_simple_binary_operand], $[rhs_simple_binary_operand]}));
    }
;
bitwise_and_lhs:
  simple_binary_operand
| bitwise_and_expression
;
bitwise_and_expression:
  bitwise_and_lhs AMPERSAND simple_binary_operand
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::BitwiseAnd,
          std::vector<Nonnull<Expression*>>(
              {$[bitwise_and_lhs], $[simple_binary_operand]}));
    }
;
bitwise_or_lhs:
  simple_binary_operand
| bitwise_or_expression
;
bitwise_or_expression:
  bitwise_or_lhs PIPE simple_binary_operand
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::BitwiseOr,
          std::vector<Nonnull<Expression*>>(
              {$[bitwise_or_lhs], $[simple_binary_operand]}));
    }
;
bitwise_xor_lhs:
  simple_binary_operand
| bitwise_xor_expression
;
bitwise_xor_expression:
  bitwise_xor_lhs CARET simple_binary_operand
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::BitwiseXor,
          std::vector<Nonnull<Expression*>>(
              {$[bitwise_xor_lhs], $[simple_binary_operand]}));
    }
;
bitwise_expression:
  bitwise_and_expression
| bitwise_or_expression
| bitwise_xor_expression
;
bit_shift_expression:
  simple_binary_operand[lhs_simple_binary_operand] LESS_LESS
  simple_binary_operand[rhs_simple_binary_operand]
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::BitShiftLeft,
          std::vector<Nonnull<Expression*>>(
              {$[lhs_simple_binary_operand], $[rhs_simple_binary_operand]}));
    }
| simple_binary_operand[lhs_simple_binary_operand] GREATER_GREATER
  simple_binary_operand[rhs_simple_binary_operand]
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::BitShiftRight,
          std::vector<Nonnull<Expression*>>(
              {$[lhs_simple_binary_operand], $[rhs_simple_binary_operand]}));
    }
;
as_expression:
  simple_binary_operand[lhs_simple_binary_operand] AS
  simple_binary_operand[rhs_simple_binary_operand]
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::As,
          std::vector<Nonnull<Expression*>>{$[lhs_simple_binary_operand],
                                            $[rhs_simple_binary_operand]});
    }
;
unimpl_expression:
  // ref_deref_expression excluded due to precedence diamond.
  ref_deref_expression[lhs_ref_deref_expression] UNIMPL_EXAMPLE
  ref_deref_expression[rhs_ref_deref_expression]
    {
      $$ = arena->New<UnimplementedExpression>(
          context.source_loc(), "ExampleInfix", $[lhs_ref_deref_expression],
          $[rhs_ref_deref_expression]);
    }
;
value_expression:
  // ref_deref_expression excluded due to precedence diamond.
  additive_expression
| as_expression
| bitwise_expression
| bit_shift_expression
| fn_type_expression
| modulo_expression
| unary_expression
| unimpl_expression
;
comparison_operand:
  ref_deref_expression
| value_expression
;
comparison_operator:
  EQUAL_EQUAL
    { $$ = Operator::Eq; }
| LESS
    { $$ = Operator::Less; }
| LESS_EQUAL
    { $$ = Operator::LessEq; }
|  GREATER
    { $$ = Operator::Greater; }
| GREATER_EQUAL
    { $$ = Operator::GreaterEq; }
| NOT_EQUAL
    { $$ = Operator::NotEq; }
;
comparison_expression:
  value_expression
| comparison_operand[lhs_simple_binary_operand] comparison_operator
  comparison_operand[rhs_simple_binary_operand]
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), $[comparison_operator],
          std::vector<Nonnull<Expression*>>(
              {$[lhs_simple_binary_operand], $[rhs_simple_binary_operand]}));
    }
;
not_expression:
  NOT ref_deref_expression
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Not,
          std::vector<Nonnull<Expression*>>({$[ref_deref_expression]}));
    }
;
predicate_expression:
  // ref_deref_expression excluded due to precedence diamond.
  not_expression
| comparison_expression
;
and_or_operand:
  ref_deref_expression
| predicate_expression
;
and_lhs:
  and_or_operand
| and_expression
;
and_expression:
  // predicate_expression excluded due to precedence diamond.
  and_lhs AND and_or_operand
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::And,
          std::vector<Nonnull<Expression*>>({$[and_lhs], $[and_or_operand]}));
    }
;
or_lhs:
  and_or_operand
| or_expression
;
or_expression:
  // predicate_expression excluded due to precedence diamond.
  or_lhs OR and_or_operand
    {
      $$ = arena->New<OperatorExpression>(
          context.source_loc(), Operator::Or,
          std::vector<Nonnull<Expression*>>({$[or_lhs], $[and_or_operand]}));
    }
;
where_clause:
  comparison_operand[lhs_simple_binary_operand] IMPLS
  comparison_operand[rhs_simple_binary_operand]
    {
      $$ = arena->New<ImplsWhereClause>(context.source_loc(),
                                        $[lhs_simple_binary_operand],
                                        $[rhs_simple_binary_operand]);
    }
| comparison_operand[lhs_simple_binary_operand] EQUAL_EQUAL
  comparison_operand[rhs_simple_binary_operand]
    {
      $$ = arena->New<EqualsWhereClause>(context.source_loc(),
                                         $[lhs_simple_binary_operand],
                                         $[rhs_simple_binary_operand]);
    }
// TODO: .(expression) = expression
| designator EQUAL comparison_operand
    {
      $$ = arena->New<RewriteWhereClause>(context.source_loc(), $[designator],
                                          $[comparison_operand]);
    }
;
where_clause_list:
  where_clause
    { $$ = {$[where_clause]}; }
| where_clause_list[accumulated_where_clause_list] AND where_clause
    {
      $$ = std::move($[accumulated_where_clause_list]);
      $$.push_back($[where_clause]);
    }
;
where_expression:
  type_expression WHERE where_clause_list
    {
      auto* self = arena->New<GenericBinding>(
          context.source_loc(), ".Self", $[type_expression],
          GenericBinding::BindingKind::Checked);
      $$ = arena->New<WhereExpression>(context.source_loc(), self,
                                       $[where_clause_list]);
    }
;
type_or_where_expression:
  type_expression
| where_expression
;
statement_expression:
  ref_deref_expression
| predicate_expression
| and_expression
| or_expression
| where_expression
;
if_expression:
  statement_expression
| IF expression THEN if_expression[then_if_expression] ELSE
  if_expression[else_if_expression]
    {
      $$ = arena->New<IfExpression>(context.source_loc(), $[expression],
                                    $[then_if_expression],
                                    $[else_if_expression]);
    }
;
expression:
  if_expression
;
designator:
  PERIOD identifier { $$ = $[identifier]; }
| PERIOD BASE { $$ = "base"; }
;
paren_expression: paren_expression_base
    {
      $$ = ExpressionFromParenContents(arena, context.source_loc(),
                                       $[paren_expression_base]);
    }
;
tuple: paren_expression_base
    {
      $$ = TupleExpressionFromParenContents(arena, context.source_loc(),
                                            $[paren_expression_base]);
    }
;
paren_expression_base:
  LEFT_PARENTHESIS RIGHT_PARENTHESIS
    { $$ = {.elements = {}, .has_trailing_comma = false}; }
| LEFT_PARENTHESIS paren_expression_contents RIGHT_PARENTHESIS
    { $$ = $[paren_expression_contents]; }
| LEFT_PARENTHESIS paren_expression_contents COMMA RIGHT_PARENTHESIS
    {
      $$ = $[paren_expression_contents];
      $$.has_trailing_comma = true;
    }
;
paren_expression_contents:
  expression
    { $$ = {.elements = {$[expression]}, .has_trailing_comma = false}; }
| paren_expression_contents[accumulated_paren_expression_contents] COMMA
  expression
    {
      $$ = std::move($[accumulated_paren_expression_contents]);
      $$.elements.push_back($[expression]);
    }
;

struct_literal:
  LEFT_CURLY_BRACE RIGHT_CURLY_BRACE
    { $$ = arena->New<StructLiteral>(context.source_loc()); }
| LEFT_CURLY_BRACE struct_literal_contents RIGHT_CURLY_BRACE
    {
      $$ = arena->New<StructLiteral>(context.source_loc(),
                                     $[struct_literal_contents]);
    }
| LEFT_CURLY_BRACE struct_literal_contents COMMA RIGHT_CURLY_BRACE
    {
      $$ = arena->New<StructLiteral>(context.source_loc(),
                                     $[struct_literal_contents]);
    }
;
struct_literal_contents:
  designator EQUAL expression
    { $$ = {FieldInitializer($[designator], $[expression])}; }
| struct_literal_contents[accumulated_struct_literal_contents] COMMA designator
  EQUAL expression
    {
      $$ = std::move($[accumulated_struct_literal_contents]);
      $$.push_back(FieldInitializer($[designator], $[expression]));
    }
;

struct_type_literal:
  LEFT_CURLY_BRACE struct_type_literal_contents RIGHT_CURLY_BRACE
    {
      $$ = arena->New<StructTypeLiteral>(context.source_loc(),
                                         $[struct_type_literal_contents]);
    }
| LEFT_CURLY_BRACE struct_type_literal_contents COMMA RIGHT_CURLY_BRACE
    {
      $$ = arena->New<StructTypeLiteral>(context.source_loc(),
                                         $[struct_type_literal_contents]);
    }
;
struct_type_literal_contents:
  designator COLON expression
    { $$ = {FieldInitializer($[designator], $[expression])}; }
| struct_type_literal_contents[accumulated_struct_type_literal_contents] COMMA
  designator COLON expression
  {
    $$ = std::move($[accumulated_struct_type_literal_contents]);
    $$.push_back(FieldInitializer($[designator], $[expression]));
  }
;

// In many cases, using `pattern` recursively will result in ambiguities.
// When that happens, it's necessary to factor out two separate productions,
// one for when the sub-pattern is an expression, and one for when it is not.
// To facilitate this, non-terminals besides `pattern` whose names contain
// `pattern` are structured to be disjoint from `expression`, unless otherwise
// specified.
pattern:
  non_expression_pattern
    { $$ = $[non_expression_pattern]; }
| expression
    { $$ = arena->New<ExpressionPattern>($[expression]); }
;
non_expression_pattern:
  AUTO
    { $$ = arena->New<AutoPattern>(context.source_loc()); }
| binding_lhs COLON pattern
    {
      $$ = arena->New<BindingPattern>(context.source_loc(), $[binding_lhs],
                                      $[pattern], std::nullopt);
    }
| binding_lhs COLON_BANG expression
    {
      $$ = arena->New<GenericBinding>(context.source_loc(), $[binding_lhs],
                                      $[expression],
                                      GenericBinding::BindingKind::Checked);
    }
| TEMPLATE binding_lhs COLON_BANG expression
    {
      $$ = arena->New<GenericBinding>(context.source_loc(), $[binding_lhs],
                                      $[expression],
                                      GenericBinding::BindingKind::Template);
    }
| paren_pattern
    { $$ = $[paren_pattern]; }
| postfix_expression tuple_pattern
    {
      ErrorOr<Nonnull<AlternativePattern*>> alternative_pattern =
          AlternativePattern::Create(arena, context.source_loc(),
                                     $[postfix_expression], $[tuple_pattern]);
      if (alternative_pattern.ok()) {
        $$ = *alternative_pattern;
      } else {
        context.RecordSyntaxError(std::move(alternative_pattern).error());
        YYERROR;
      }
    }
| VAR non_expression_pattern[child_non_expression_pattern]
    {
      $$ = arena->New<VarPattern>(context.source_loc(),
                                  $[child_non_expression_pattern]);
    }
;
binding_lhs:
  identifier { $$ = $[identifier]; }
| UNDERSCORE { $$ = AnonymousName; }
;
paren_pattern: paren_pattern_base
    {
      $$ = PatternFromParenContents(arena, context.source_loc(),
                                    $[paren_pattern_base]);
    }
;
paren_pattern_base:
  LEFT_PARENTHESIS paren_pattern_contents RIGHT_PARENTHESIS
    { $$ = $[paren_pattern_contents]; }
| LEFT_PARENTHESIS paren_pattern_contents COMMA RIGHT_PARENTHESIS
    {
      $$ = $[paren_pattern_contents];
      $$.has_trailing_comma = true;
    }
;
// paren_pattern is analogous to paren_expression, but in order to avoid
// ambiguities, it must be disjoint from paren_expression, meaning it must
// contain at least one non_expression_pattern. The structure of this rule
// is very different from the corresponding expression rule because is has to
// enforce that requirement.
paren_pattern_contents:
  non_expression_pattern
    {
      $$ = {.elements = {$[non_expression_pattern]},
            .has_trailing_comma = false};
    }
| paren_expression_contents[accumulated_paren_pattern_contents] COMMA
  non_expression_pattern
    {
      $$ = ParenExpressionToParenPattern(arena,
                                         $[accumulated_paren_pattern_contents]);
      $$.elements.push_back($[non_expression_pattern]);
    }
| paren_pattern_contents[accumulated_paren_pattern_contents] COMMA expression
    {
      $$ = std::move($[accumulated_paren_pattern_contents]);
      $$.elements.push_back(arena->New<ExpressionPattern>($[expression]));
    }
| paren_pattern_contents[accumulated_paren_pattern_contents] COMMA
  non_expression_pattern
    {
      $$ = std::move($[accumulated_paren_pattern_contents]);
      $$.elements.push_back($[non_expression_pattern]);
    }
;
tuple_pattern: paren_pattern_base
    {
      $$ = TuplePatternFromParenContents(arena, context.source_loc(),
                                         $[paren_pattern_base]);
    }
;
// Unlike most `pattern` nonterminals, this one overlaps with `expression`,
// so it should be used only when prior context (such as an introducer)
// rules out the possibility of an `expression` at this point.
maybe_empty_tuple_pattern:
  LEFT_PARENTHESIS RIGHT_PARENTHESIS
    {
      $$ = arena->New<TuplePattern>(context.source_loc(),
                                    std::vector<Nonnull<Pattern*>>());
    }
| tuple_pattern
    { $$ = $[tuple_pattern]; }
;

clause:
  CASE pattern DOUBLE_ARROW block
    { $$ = Match::Clause($[pattern], $[block]); }
| DEFAULT DOUBLE_ARROW block
    {
      $$ = Match::Clause(arena->New<BindingPattern>(
                             context.source_loc(), std::string(AnonymousName),
                             arena->New<AutoPattern>(context.source_loc()),
                             ExpressionCategory::Value),
                         $[block]);
    }
;
clause_list:
  // Empty
    { $$ = {}; }
| clause_list[accumulated_clause_list] clause
    {
      $$ = std::move($[accumulated_clause_list]);
      $$.push_back($[clause]);
    }
;
statement:
  assign_statement
| VAR pattern SEMICOLON
    {
      $$ = arena->New<VariableDefinition>(
          context.source_loc(), $[pattern], std::nullopt,
          ExpressionCategory::Reference,
          VariableDefinition::DefinitionType::Var);
    }
| VAR pattern EQUAL expression SEMICOLON
    {
      $$ = arena->New<VariableDefinition>(
          context.source_loc(), $[pattern], $[expression],
          ExpressionCategory::Reference,
          VariableDefinition::DefinitionType::Var);
    }
| RETURNED VAR variable_declaration SEMICOLON
    {
      $$ = arena->New<VariableDefinition>(
          context.source_loc(), $[variable_declaration], std::nullopt,
          ExpressionCategory::Reference,
          VariableDefinition::DefinitionType::Returned);
    }
| RETURNED VAR variable_declaration EQUAL expression SEMICOLON
    {
      $$ = arena->New<VariableDefinition>(
          context.source_loc(), $[variable_declaration], $[expression],
          ExpressionCategory::Reference,
          VariableDefinition::DefinitionType::Returned);
    }
| LET pattern EQUAL expression SEMICOLON
    {
      $$ = arena->New<VariableDefinition>(
          context.source_loc(), $[pattern], $[expression],
          ExpressionCategory::Value, VariableDefinition::DefinitionType::Var);
    }
| statement_expression SEMICOLON
    {
      $$ = arena->New<ExpressionStatement>(context.source_loc(),
                                           $[statement_expression]);
    }
| if_statement
    { $$ = $[if_statement]; }
| WHILE LEFT_PARENTHESIS expression RIGHT_PARENTHESIS block
    { $$ = arena->New<While>(context.source_loc(), $[expression], $[block]); }
| BREAK SEMICOLON
    { $$ = arena->New<Break>(context.source_loc()); }
| CONTINUE SEMICOLON
    { $$ = arena->New<Continue>(context.source_loc()); }
| RETURN return_expression SEMICOLON
    {
      auto [return_exp, is_omitted_exp] = $[return_expression];
      $$ = arena->New<ReturnExpression>(context.source_loc(), return_exp,
                                        is_omitted_exp);
    }
| RETURN VAR SEMICOLON
    { $$ = arena->New<ReturnVar>(context.source_loc()); }
| MATCH LEFT_PARENTHESIS expression RIGHT_PARENTHESIS LEFT_CURLY_BRACE
  clause_list RIGHT_CURLY_BRACE
    {
      $$ = arena->New<Match>(context.source_loc(), $[expression],
                             $[clause_list]);
    }
| FOR LEFT_PARENTHESIS variable_declaration IN type_expression RIGHT_PARENTHESIS
  block
    {
      $$ = arena->New<For>(context.source_loc(), $[variable_declaration],
                           $[type_expression], $[block]);
    }
;
assign_statement:
  statement_expression assign_operator expression SEMICOLON
    {
      $$ = arena->New<Assign>(context.source_loc(), $[statement_expression],
                              $[assign_operator], $[expression]);
    }
| PLUS_PLUS expression SEMICOLON
    {
      $$ = arena->New<IncrementDecrement>(context.source_loc(), $[expression],
                                          true);
    }
| MINUS_MINUS expression SEMICOLON
    {
      $$ = arena->New<IncrementDecrement>(context.source_loc(), $[expression],
                                          false);
    }
;
assign_operator:
  EQUAL
    { $$ = AssignOperator::Plain; }
| PLUS_EQUAL
    { $$ = AssignOperator::Add; }
| SLASH_EQUAL
    { $$ = AssignOperator::Div; }
| STAR_EQUAL
    { $$ = AssignOperator::Mul; }
| PERCENT_EQUAL
    { $$ = AssignOperator::Mod; }
| MINUS_EQUAL
    { $$ = AssignOperator::Sub; }
| AMPERSAND_EQUAL
    { $$ = AssignOperator::And; }
| PIPE_EQUAL
    { $$ = AssignOperator::Or; }
| CARET_EQUAL
    { $$ = AssignOperator::Xor; }
| LESS_LESS_EQUAL
    { $$ = AssignOperator::ShiftLeft; }
| GREATER_GREATER_EQUAL
    { $$ = AssignOperator::ShiftRight; }
;
if_statement:
  IF LEFT_PARENTHESIS expression RIGHT_PARENTHESIS block optional_else
    {
      $$ = arena->New<If>(context.source_loc(), $[expression], $[block],
                          $[optional_else]);
    }
;
optional_else:
  // Empty
    { $$ = std::nullopt; }
| ELSE if_statement
    {
      $$ = arena->New<Block>(
          context.source_loc(),
          std::vector<Nonnull<Statement*>>({$[if_statement]}));
    }
| ELSE block
    { $$ = $[block]; }
;
return_expression:
  // Empty
    { $$ = {arena->New<TupleLiteral>(context.source_loc()), true}; }
| expression
    { $$ = {$[expression], false}; }
;
statement_list:
  // Empty
    { $$ = {}; }
| statement_list[accumulated_statement_list] statement
    {
      $$ = std::move($[accumulated_statement_list]);
      $$.push_back($[statement]);
    }
;
block:
  LEFT_CURLY_BRACE statement_list RIGHT_CURLY_BRACE
    {
      $$ =
          arena->New<Block>(context.source_loc(), std::move($[statement_list]));
    }
;
return_term:
  // Empty
    { $$ = ReturnTerm::Omitted(context.source_loc()); }
| ARROW AUTO
    { $$ = ReturnTerm::Auto(context.source_loc()); }
| ARROW expression
    { $$ = ReturnTerm::Explicit($[expression]); }
;
generic_binding:
  identifier COLON_BANG expression
    {
      $$ = arena->New<GenericBinding>(context.source_loc(),
                                      std::move($[identifier]), $[expression],
                                      GenericBinding::BindingKind::Checked);
    }
| TEMPLATE identifier COLON_BANG expression
    {
      $$ = arena->New<GenericBinding>(context.source_loc(),
                                      std::move($[identifier]), $[expression],
                                      GenericBinding::BindingKind::Template);
    }
;
deduced_param:
  generic_binding
    { $$ = $[generic_binding]; }
| variable_declaration
    { $$ = $[variable_declaration]; }
| ADDR variable_declaration
    {
      $$ = arena->New<AddrPattern>(context.source_loc(),
                                   $[variable_declaration]);
    }
;
deduced_param_list:
  // Empty
    { $$ = {}; }
| deduced_param
    { $$ = {$[deduced_param]}; }
| deduced_param_list[accumulated_deduced_param_list] COMMA deduced_param
    {
      $$ = std::move($[accumulated_deduced_param_list]);
      $$.push_back($[deduced_param]);
    }
;
deduced_params:
  // Empty
    { $$ = std::vector<Nonnull<AstNode*>>(); }
| LEFT_SQUARE_BRACKET deduced_param_list RIGHT_SQUARE_BRACKET
    { $$ = $[deduced_param_list]; }
;
impl_deduced_params:
  // Empty
    { $$ = std::vector<Nonnull<AstNode*>>(); }
| FORALL LEFT_SQUARE_BRACKET deduced_param_list RIGHT_SQUARE_BRACKET
    { $$ = $[deduced_param_list]; }
;
declared_name:
  identifier
    { $$ = DeclaredName(context.source_loc(), $[identifier]); }
| declared_name[child_declared_name] PERIOD identifier
    {
      $$ = std::move($[child_declared_name]);
      $$.Unwrap().Append(context.source_loc(), $[identifier]);
    }
| LEFT_PARENTHESIS declared_name[child_declared_name] RIGHT_PARENTHESIS
    { $$ = $[child_declared_name]; }
;
// This includes the FN keyword to work around a shift-reduce conflict between
// virtual function's `IMPL FN` and interfaces `IMPL`.
fn_virtual_override_intro:
  FN
    { $$ = VirtualOverride::None; }
| ABSTRACT FN
    { $$ = VirtualOverride::Abstract; }
| VIRTUAL FN
    { $$ = VirtualOverride::Virtual; }
| IMPL FN
    { $$ = VirtualOverride::Impl; }
;
function_declaration:
  fn_virtual_override_intro declared_name deduced_params
  maybe_empty_tuple_pattern return_term block
    {
      ErrorOr<FunctionDeclaration*> fn = FunctionDeclaration::Create(
          arena, context.source_loc(), std::move($[declared_name]),
          $[deduced_params], $[maybe_empty_tuple_pattern], $[return_term],
          $[block], $[fn_virtual_override_intro]);
      if (fn.ok()) {
        $$ = *fn;
      } else {
        context.RecordSyntaxError(std::move(fn).error());
        YYERROR;
      }
    }
| fn_virtual_override_intro declared_name deduced_params
  maybe_empty_tuple_pattern return_term SEMICOLON
    {
      ErrorOr<FunctionDeclaration*> fn = FunctionDeclaration::Create(
          arena, context.source_loc(), std::move($[declared_name]),
          $[deduced_params], $[maybe_empty_tuple_pattern], $[return_term],
          std::nullopt, $[fn_virtual_override_intro]);
      if (fn.ok()) {
        $$ = *fn;
      } else {
        context.RecordSyntaxError(std::move(fn).error());
        YYERROR;
      }
    }
;
variable_declaration: identifier COLON pattern
    {
      $$ = arena->New<BindingPattern>(context.source_loc(), $[identifier],
                                      $[pattern], std::nullopt);
    }
;
alias_declaration: ALIAS declared_name EQUAL expression SEMICOLON
    {
      $$ = arena->New<AliasDeclaration>(context.source_loc(), $[declared_name],
                                        $[expression]);
    }
;
// EXPERIMENTAL MIXIN FEATURE
mix_declaration: MIX expression SEMICOLON
    { $$ = arena->New<MixDeclaration>(context.source_loc(), $[expression]); }
;
alternative:
  identifier tuple
    {
      $$ = arena->New<AlternativeSignature>(context.source_loc(), $[identifier],
                                            $[tuple]);
    }
| identifier
    {
      $$ = arena->New<AlternativeSignature>(context.source_loc(), $[identifier],
                                            std::nullopt);
    }
;
alternative_list:
  // Empty
    { $$ = {}; }
| alternative_list_contents[accumulated_alternative_list_contents]
| alternative_list_contents[accumulated_alternative_list_contents] COMMA
;
alternative_list_contents:
  alternative
    { $$ = {std::move($[alternative])}; }
| alternative_list_contents[accumulated_alternative_list_contents] COMMA
  alternative
    {
      $$ = std::move($[accumulated_alternative_list_contents]);
      $$.push_back(std::move($[alternative]));
    }
;
type_params:
  // Empty
    { $$ = std::nullopt; }
| tuple_pattern
    { $$ = $[tuple_pattern]; }
;
// EXPERIMENTAL MIXIN FEATURE
mixin_import:
  // Empty
    { $$ = arena->New<TypeTypeLiteral>(context.source_loc()); }
| FOR expression
    {
      context.RecordSyntaxError("'for' not supported currently");
      YYERROR;
      // $$ = $[expression];
    }
;
class_declaration_extensibility:
  // Empty
    { $$ = Carbon::ClassExtensibility::None; }
| ABSTRACT
    { $$ = Carbon::ClassExtensibility::Abstract; }
| BASE
    { $$ = Carbon::ClassExtensibility::Base; }
;
class_declaration_extends:
  // Empty
    { $$ = std::nullopt; }
| EXTENDS expression
    { $$ = $[expression]; }
;
declaration:
  NAMESPACE declared_name SEMICOLON
    {
      $$ = arena->New<NamespaceDeclaration>(context.source_loc(),
                                            std::move($[declared_name]));
    }
| function_declaration
    { $$ = $[function_declaration]; }
| destructor_declaration
    { $$ = $[destructor_declaration]; }
| class_declaration_extensibility CLASS declared_name type_params
  class_declaration_extends LEFT_CURLY_BRACE class_body RIGHT_CURLY_BRACE
    {
      $$ = arena->New<ClassDeclaration>(
          context.source_loc(), std::move($[declared_name]),
          arena->New<SelfDeclaration>(context.source_loc()),
          $[class_declaration_extensibility], $[type_params],
          $[class_declaration_extends], $[class_body]);
    }
| MIXIN declared_name type_params mixin_import LEFT_CURLY_BRACE mixin_body
  RIGHT_CURLY_BRACE
    {
      // EXPERIMENTAL MIXN FEATURE
      auto self = arena->New<GenericBinding>(
          context.source_loc(), "Self", $[mixin_import],
          GenericBinding::BindingKind::Checked);
      $$ = arena->New<MixinDeclaration>(context.source_loc(),
                                        std::move($[declared_name]),
                                        $[type_params], self, $[mixin_body]);
    }
| CHOICE declared_name type_params LEFT_CURLY_BRACE alternative_list
  RIGHT_CURLY_BRACE
    {
      $$ = arena->New<ChoiceDeclaration>(context.source_loc(), $[declared_name],
                                         $[type_params], $[alternative_list]);
    }
| VAR variable_declaration SEMICOLON
    {
      $$ = arena->New<VariableDeclaration>(
          context.source_loc(), $[variable_declaration], std::nullopt,
          ExpressionCategory::Reference);
    }
| VAR variable_declaration EQUAL expression SEMICOLON
    {
      $$ = arena->New<VariableDeclaration>(
          context.source_loc(), $[variable_declaration], $[expression],
          ExpressionCategory::Reference);
    }
| LET variable_declaration EQUAL expression SEMICOLON
    {
      $$ = arena->New<VariableDeclaration>(
          context.source_loc(), $[variable_declaration], $[expression],
          ExpressionCategory::Value);
    }
| INTERFACE declared_name type_params LEFT_CURLY_BRACE interface_body
  RIGHT_CURLY_BRACE
    {
      $$ = arena->New<InterfaceDeclaration>(arena, context.source_loc(),
                                            std::move($[declared_name]),
                                            $[type_params], $[interface_body]);
    }
| CONSTRAINT declared_name type_params LEFT_CURLY_BRACE interface_body
  RIGHT_CURLY_BRACE
    {
      $$ = arena->New<ConstraintDeclaration>(arena, context.source_loc(),
                                             std::move($[declared_name]),
                                             $[type_params], $[interface_body]);
    }
| impl_declaration
    { $$ = $[impl_declaration]; }
| match_first_declaration
    { $$ = $[match_first_declaration]; }
| alias_declaration
    { $$ = $[alias_declaration]; }
;
impl_declaration:
  impl_kind_intro impl_deduced_params impl_type AS type_or_where_expression
  LEFT_CURLY_BRACE impl_body RIGHT_CURLY_BRACE
    {
      ErrorOr<ImplDeclaration*> impl = ImplDeclaration::Create(
          arena, context.source_loc(), $[impl_kind_intro], $[impl_type],
          $[type_or_where_expression], $[impl_deduced_params], $[impl_body]);
      if (impl.ok()) {
        $$ = *impl;
      } else {
        context.RecordSyntaxError(std::move(impl).error());
        YYERROR;
      }
    }
impl_kind_intro:
  IMPL // Internal
    { $$ = Carbon::ImplKind::InternalImpl; }
| EXTERNAL IMPL
    { $$ = Carbon::ImplKind::ExternalImpl; }
;
impl_type:
  // Self
    { $$ = arena->New<IdentifierExpression>(context.source_loc(), "Self"); }
| type_expression
;
match_first_declaration:
  MATCH_FIRST LEFT_CURLY_BRACE match_first_declaration_list RIGHT_CURLY_BRACE
    {
      $$ = arena->New<MatchFirstDeclaration>(
          context.source_loc(), std::move($[match_first_declaration_list]));
    }
;
match_first_declaration_list:
  // Empty
    { $$ = {}; }
| match_first_declaration_list[accumulated_match_first_declaration_list]
  impl_declaration
    {
      $$ = std::move($[accumulated_match_first_declaration_list]);
      $$.push_back($[impl_declaration]);
    }
destructor_virtual_override_intro:
  DESTRUCTOR
  { $$ = VirtualOverride::None; }
| VIRTUAL DESTRUCTOR
  { $$ = VirtualOverride::Virtual; }
| IMPL DESTRUCTOR
  { $$ = VirtualOverride::Impl; }
;
destructor_declaration:
  destructor_virtual_override_intro deduced_params block
  {
    ErrorOr<DestructorDeclaration*> fn =
        DestructorDeclaration::CreateDestructor(
            arena, context.source_loc(), $[deduced_params],
            arena->New<TuplePattern>(context.source_loc(),
                                     std::vector<Nonnull<Pattern*>>()),
            ReturnTerm::Omitted(context.source_loc()), $[block],
            $[destructor_virtual_override_intro]);
    if (fn.ok()) {
      $$ = *fn;
    } else {
      context.RecordSyntaxError(std::move(fn).error());
      YYERROR;
    }
  }
;
declaration_list:
  // Empty
    { $$ = {}; }
| declaration_list[accumulated_declaration_list] declaration
    {
      $$ = std::move($[accumulated_declaration_list]);
      $$.push_back(Nonnull<Declaration*>($[declaration]));
    }
;
class_body:
  // Empty
    { $$ = {}; }
| class_body[accumulated_class_body] declaration
    {
      $$ = std::move($[accumulated_class_body]);
      $$.push_back(Nonnull<Declaration*>($[declaration]));
    }
| class_body[accumulated_class_body] mix_declaration
    {
      $$ = std::move($[accumulated_class_body]);
      $$.push_back(Nonnull<Declaration*>($[mix_declaration]));
    }
;
// EXPERIMENTAL MIXIN FEATURE
mixin_body:
  // Empty
    { $$ = {}; }
| mixin_body[accumulated_mixin_body] function_declaration
    {
      $$ = std::move($[accumulated_mixin_body]);
      $$.push_back(Nonnull<Declaration*>($[function_declaration]));
    }
| mixin_body[accumulated_mixin_body] mix_declaration
    {
      $$ = std::move($[accumulated_mixin_body]);
      $$.push_back(Nonnull<Declaration*>($[mix_declaration]));
    }
;
interface_body:
  // Empty
    { $$ = {}; }
| interface_body[accumulated_interface_body] function_declaration
    {
      $$ = std::move($[accumulated_interface_body]);
      $$.push_back($[function_declaration]);
    }
| interface_body[accumulated_interface_body] LET generic_binding SEMICOLON
    {
      $$ = std::move($[accumulated_interface_body]);
      $$.push_back(arena->New<AssociatedConstantDeclaration>(
          context.source_loc(), $[generic_binding]));
    }
| interface_body[accumulated_interface_body] EXTENDS expression SEMICOLON
    {
      $$ = std::move($[accumulated_interface_body]);
      $$.push_back(arena->New<InterfaceExtendsDeclaration>(context.source_loc(),
                                                           $[expression]));
    }
| interface_body[accumulated_interface_body] IMPL impl_type AS
  type_or_where_expression SEMICOLON
    {
      $$ = std::move($[accumulated_interface_body]);
      $$.push_back(arena->New<InterfaceImplDeclaration>(
          context.source_loc(), $[impl_type], $[type_or_where_expression]));
    }
;
impl_body:
  // Empty
    { $$ = {}; }
| impl_body[accumulated_impl_body] function_declaration
    {
      $$ = std::move($[accumulated_impl_body]);
      $$.push_back($[function_declaration]);
    }
| impl_body[accumulated_impl_body] alias_declaration
    {
      $$ = std::move($[accumulated_impl_body]);
      $$.push_back($[alias_declaration]);
    }
;
%%