carbon-lang/executable_semantics/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.

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

// "inout" parameters passed to both the parser and the lexer.
%param {yyscan_t yyscanner}
%param {ParseAndLexContext& context}

// No shift-reduce conflicts are expected.
%expect 0

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

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

  #include "common/check.h"
  #include "executable_semantics/syntax/parse_and_lex_context.h"
  #include "executable_semantics/syntax/syntax_helpers.h"
  #include "llvm/ADT/StringExtras.h"
}  // %code top

%code requires {
  #include <optional>

  #include "executable_semantics/ast/abstract_syntax_tree.h"
  #include "executable_semantics/ast/declaration.h"
  #include "executable_semantics/ast/expression.h"
  #include "executable_semantics/ast/function_definition.h"
  #include "executable_semantics/ast/paren_contents.h"
  #include "executable_semantics/ast/pattern.h"
  #include "executable_semantics/common/arena.h"
  #include "executable_semantics/common/ptr.h"
  #include "executable_semantics/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.PrintDiagnostic(message);
  }
}  // %code

%token <int> integer_literal
%token <std::string> identifier
%token <std::string> sized_type_literal
%token <std::string> string_literal
%type <std::string> designator
%type <BisonWrap<Ptr<const Declaration>>> declaration
%type <BisonWrap<Ptr<const FunctionDefinition>>> function_declaration
%type <BisonWrap<Ptr<const FunctionDefinition>>> function_definition
%type <std::list<Ptr<const Declaration>>> declaration_list
%type <BisonWrap<Ptr<const Statement>>> statement
%type <BisonWrap<Ptr<const Statement>>> if_statement
%type <std::optional<Ptr<const Statement>>> optional_else
%type <BisonWrap<std::pair<Ptr<const Expression>, bool>>> return_expression
%type <BisonWrap<Ptr<const Statement>>> block
%type <std::optional<Ptr<const Statement>>> statement_list
%type <BisonWrap<Ptr<const Expression>>> expression
%type <BisonWrap<GenericBinding>> generic_binding
%type <std::vector<GenericBinding>> deduced_params
%type <std::vector<GenericBinding>> deduced_param_list
%type <BisonWrap<Ptr<const Pattern>>> pattern
%type <BisonWrap<Ptr<const Pattern>>> non_expression_pattern
%type <BisonWrap<std::pair<Ptr<const Expression>, bool>>> return_type
%type <BisonWrap<Ptr<const Expression>>> paren_expression
%type <BisonWrap<Ptr<const Expression>>> tuple
%type <std::optional<std::string>> binding_lhs
%type <BisonWrap<Ptr<const BindingPattern>>> variable_declaration
%type <BisonWrap<Ptr<Member>>> member
%type <std::list<Ptr<Member>>> member_list
%type <BisonWrap<ParenContents<Expression>::Element>> paren_expression_element
%type <ParenContents<Expression>> paren_expression_base
%type <ParenContents<Expression>> paren_expression_contents
%type <BisonWrap<Ptr<const Pattern>>> paren_pattern
%type <BisonWrap<Ptr<const TuplePattern>>> tuple_pattern
%type <BisonWrap<Ptr<const TuplePattern>>> maybe_empty_tuple_pattern
%type <ParenContents<Pattern>> paren_pattern_base
%type <BisonWrap<ParenContents<Pattern>::Element>> paren_pattern_element
%type <ParenContents<Pattern>> paren_pattern_contents
%type <BisonWrap<std::pair<std::string, Ptr<const Expression>>>> alternative
%type <std::list<std::pair<std::string, Ptr<const Expression>>>> alternative_list
%type <std::pair<Ptr<const Pattern>, Ptr<const Statement>>*> clause
%type <std::list<std::pair<Ptr<const Pattern>, Ptr<const Statement>>>*> clause_list

%token
  // Most tokens have their spelling defined in lexer.lpp.
  AND
  ARROW
  AUTO
  AWAIT
  BOOL
  BREAK
  CASE
  CHOICE
  CLASS
  COLON
  COLON_BANG
  COMMA
  CONTINUATION
  CONTINUATION_TYPE
  CONTINUE
  DEFAULT
  DOUBLE_ARROW
  ELSE
  EQUAL
  EQUAL_EQUAL
  FALSE
  FN
  FNTY
  IF
  LEFT_CURLY_BRACE
  LEFT_PARENTHESIS
  LEFT_SQUARE_BRACKET
  MATCH
  MINUS
  NOT
  OR
  PERIOD
  PLUS
  RETURN
  RIGHT_CURLY_BRACE
  RIGHT_PARENTHESIS
  RIGHT_SQUARE_BRACKET
  RUN
  SEMICOLON
  SLASH
  STRING
  TRUE
  TYPE
  UNDERSCORE
  VAR
  WHILE
  // 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 *"
;

%precedence FNARROW
%precedence LEFT_CURLY_BRACE RIGHT_CURLY_BRACE
%precedence COLON_BANG COLON COMMA DOUBLE_ARROW
%left OR AND
%nonassoc EQUAL_EQUAL
%left PLUS MINUS
%left BINARY_STAR
%precedence NOT UNARY_MINUS PREFIX_STAR
// We need to give the `UNARY_STAR` token a precedence, rather than overriding
// the precedence of the `expression UNARY_STAR` rule below, because bison
// compares the precedence of the final token (for a shift) to the precedence
// of the other rule (for a reduce) when attempting to resolve a shift-reduce
// conflict. See https://stackoverflow.com/a/26188429/1041090. When UNARY_STAR
// is the final token of a rule, it must be a postfix usage, so we give it the
// same precedence as POSTFIX_STAR.
%precedence POSTFIX_STAR UNARY_STAR
%left PERIOD ARROW
%precedence
  LEFT_PARENTHESIS
  RIGHT_PARENTHESIS
  LEFT_SQUARE_BRACKET
  RIGHT_SQUARE_BRACKET
;

%start input
%%
input: declaration_list
    { parsed_program = $1; }
;
expression:
  identifier
    { $$ = global_arena->New<IdentifierExpression>(context.SourceLoc(), $1); }
| expression designator
    {
      $$ =
          global_arena->New<FieldAccessExpression>(context.SourceLoc(), $1, $2);
    }
| expression LEFT_SQUARE_BRACKET expression RIGHT_SQUARE_BRACKET
    { $$ = global_arena->New<IndexExpression>(context.SourceLoc(), $1, $3); }
| integer_literal
    { $$ = global_arena->New<IntLiteral>(context.SourceLoc(), $1); }
| string_literal
    { $$ = global_arena->New<StringLiteral>(context.SourceLoc(), $1); }
| TRUE
    { $$ = global_arena->New<BoolLiteral>(context.SourceLoc(), true); }
| FALSE
    { $$ = global_arena->New<BoolLiteral>(context.SourceLoc(), false); }
| sized_type_literal
    {
      int val;
      CHECK(llvm::to_integer(llvm::StringRef($1).substr(1), val));
      CHECK($1[0] == 'i' && val == 32)
          << "Only i32 is supported for now: " << $1;
      $$ = global_arena->New<IntTypeLiteral>(context.SourceLoc());
    }
| STRING
    { $$ = global_arena->New<StringTypeLiteral>(context.SourceLoc()); }
| BOOL
    { $$ = global_arena->New<BoolTypeLiteral>(context.SourceLoc()); }
| TYPE
    { $$ = global_arena->New<TypeTypeLiteral>(context.SourceLoc()); }
| CONTINUATION_TYPE
    { $$ = global_arena->New<ContinuationTypeLiteral>(context.SourceLoc()); }
| paren_expression { $$ = $1; }
| expression EQUAL_EQUAL expression
    {
      $$ = global_arena->New<PrimitiveOperatorExpression>(
          context.SourceLoc(), Operator::Eq,
          std::vector<Ptr<const Expression>>({$1, $3}));
    }
| expression PLUS expression
    {
      $$ = global_arena->New<PrimitiveOperatorExpression>(
          context.SourceLoc(), Operator::Add,
          std::vector<Ptr<const Expression>>({$1, $3}));
    }
| expression MINUS expression
    {
      $$ = global_arena->New<PrimitiveOperatorExpression>(
          context.SourceLoc(), Operator::Sub,
          std::vector<Ptr<const Expression>>({$1, $3}));
    }
| expression BINARY_STAR expression
    {
      $$ = global_arena->New<PrimitiveOperatorExpression>(
          context.SourceLoc(), Operator::Mul,
          std::vector<Ptr<const Expression>>({$1, $3}));
    }
| expression AND expression
    {
      $$ = global_arena->New<PrimitiveOperatorExpression>(
          context.SourceLoc(), Operator::And,
          std::vector<Ptr<const Expression>>({$1, $3}));
    }
| expression OR expression
    {
      $$ = global_arena->New<PrimitiveOperatorExpression>(
          context.SourceLoc(), Operator::Or,
          std::vector<Ptr<const Expression>>({$1, $3}));
    }
| NOT expression
    {
      $$ = global_arena->New<PrimitiveOperatorExpression>(
          context.SourceLoc(), Operator::Not,
          std::vector<Ptr<const Expression>>({$2}));
    }
| MINUS expression %prec UNARY_MINUS
    {
      $$ = global_arena->New<PrimitiveOperatorExpression>(
          context.SourceLoc(), Operator::Neg,
          std::vector<Ptr<const Expression>>({$2}));
    }
| PREFIX_STAR expression
    {
      $$ = global_arena->New<PrimitiveOperatorExpression>(
          context.SourceLoc(), Operator::Deref,
          std::vector<Ptr<const Expression>>({$2}));
    }
| UNARY_STAR expression %prec PREFIX_STAR
    {
      $$ = global_arena->New<PrimitiveOperatorExpression>(
          context.SourceLoc(), Operator::Deref,
          std::vector<Ptr<const Expression>>({$2}));
    }
| expression tuple
    { $$ = global_arena->New<CallExpression>(context.SourceLoc(), $1, $2); }
| expression POSTFIX_STAR
    {
      $$ = global_arena->New<PrimitiveOperatorExpression>(
          context.SourceLoc(), Operator::Ptr,
          std::vector<Ptr<const Expression>>({$1}));
    }
| expression UNARY_STAR
    {
      $$ = global_arena->New<PrimitiveOperatorExpression>(
          context.SourceLoc(), Operator::Ptr,
          std::vector<Ptr<const Expression>>({$1}));
    }
| FNTY tuple return_type
    {
      auto [return_exp, is_omitted_exp] = $3.Release();
      $$ = global_arena->New<FunctionTypeLiteral>(context.SourceLoc(), $2,
                                                  return_exp, is_omitted_exp);
    }
;
designator: PERIOD identifier { $$ = $2; }
;
paren_expression: paren_expression_base
    { $$ = ExpressionFromParenContents(context.SourceLoc(), $1); }
;
tuple: paren_expression_base
    { $$ = TupleExpressionFromParenContents(context.SourceLoc(), $1); }
;
paren_expression_element:
  expression
    { $$ = {.name = std::nullopt, .term = $1}; }
| designator EQUAL expression
    { $$ = {.name = $1, .term = $3}; }
;
paren_expression_base:
  LEFT_PARENTHESIS RIGHT_PARENTHESIS
    { $$ = {.elements = {}, .has_trailing_comma = false}; }
| LEFT_PARENTHESIS paren_expression_contents RIGHT_PARENTHESIS
    { $$ = $2; }
| LEFT_PARENTHESIS paren_expression_contents COMMA RIGHT_PARENTHESIS
    {
      $$ = $2;
      $$.has_trailing_comma = true;
    }
;
paren_expression_contents:
  paren_expression_element
    { $$ = {.elements = {$1}, .has_trailing_comma = false}; }
| paren_expression_contents COMMA paren_expression_element
    {
      $$ = $1;
      $$.elements.push_back($3);
    }
;

// 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
    { $$ = $1; }
| expression
    { $$ = global_arena->New<ExpressionPattern>($1); }
;
non_expression_pattern:
  AUTO
    { $$ = global_arena->New<AutoPattern>(context.SourceLoc()); }
| binding_lhs COLON pattern
    { $$ = global_arena->New<BindingPattern>(context.SourceLoc(), $1, $3); }
| paren_pattern
    { $$ = $1; }
| expression tuple_pattern
    { $$ = global_arena->New<AlternativePattern>(context.SourceLoc(), $1, $2); }
;
binding_lhs:
  identifier { $$ = $1; }
| UNDERSCORE { $$ = std::nullopt; }
;
paren_pattern: paren_pattern_base
    { $$ = PatternFromParenContents(context.SourceLoc(), $1); }
;
paren_pattern_base:
  LEFT_PARENTHESIS paren_pattern_contents RIGHT_PARENTHESIS
    { $$ = $2; }
| LEFT_PARENTHESIS paren_pattern_contents COMMA RIGHT_PARENTHESIS
    {
      $$ = $2;
      $$.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:
  paren_pattern_element
    { $$ = {.elements = {$1}, .has_trailing_comma = false}; }
| paren_expression_contents COMMA paren_pattern_element
    {
      $$ = ParenExpressionToParenPattern($1);
      $$.elements.push_back($3);
    }
| paren_pattern_contents COMMA paren_expression_element
    {
      $$ = $1;
      auto el = $3.Release();
      $$.elements.push_back(
          {.name = el.name,
           .term = global_arena->New<ExpressionPattern>(el.term)});
    }
| paren_pattern_contents COMMA paren_pattern_element
    {
      $$ = $1;
      $$.elements.push_back($3);
    }
;
paren_pattern_element:
  non_expression_pattern
    { $$ = {.name = std::nullopt, .term = $1}; }
| designator EQUAL non_expression_pattern
    { $$ = {.name = $1, .term = $3}; }
;
tuple_pattern: paren_pattern_base
    { $$ = TuplePatternFromParenContents(context.SourceLoc(), $1); }
;
// 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
    {
      $$ = global_arena->New<TuplePattern>(context.SourceLoc(),
                                           std::vector<TuplePattern::Field>());
    }
| tuple_pattern
    { $$ = $1; }
;
clause:
  CASE pattern DOUBLE_ARROW statement
    {
      $$ = global_arena
               ->RawNew<std::pair<Ptr<const Pattern>, Ptr<const Statement>>>(
                   $2, $4);
    }
| DEFAULT DOUBLE_ARROW statement
    {
      auto vp = global_arena -> New<BindingPattern>(
                    context.SourceLoc(), std::nullopt,
                    global_arena->New<AutoPattern>(context.SourceLoc()));
      $$ = global_arena
               ->RawNew<std::pair<Ptr<const Pattern>, Ptr<const Statement>>>(
                   vp, $3);
    }
;
clause_list:
  // Empty
    {
      $$ = global_arena->RawNew<
          std::list<std::pair<Ptr<const Pattern>, Ptr<const Statement>>>>();
    }
| clause clause_list
    {
      $$ = $2;
      $$->push_front(*$1);
    }
;
statement:
  expression EQUAL expression SEMICOLON
    { $$ = global_arena->New<Assign>(context.SourceLoc(), $1, $3); }
| VAR pattern EQUAL expression SEMICOLON
    { $$ = global_arena->New<VariableDefinition>(context.SourceLoc(), $2, $4); }
| expression SEMICOLON
    { $$ = global_arena->New<ExpressionStatement>(context.SourceLoc(), $1); }
| if_statement
    { $$ = $1; }
| WHILE LEFT_PARENTHESIS expression RIGHT_PARENTHESIS block
    { $$ = global_arena->New<While>(context.SourceLoc(), $3, $5); }
| BREAK SEMICOLON
    { $$ = global_arena->New<Break>(context.SourceLoc()); }
| CONTINUE SEMICOLON
    { $$ = global_arena->New<Continue>(context.SourceLoc()); }
| RETURN return_expression SEMICOLON
    {
      auto [return_exp, is_omitted_exp] = $2.Release();
      $$ = global_arena->New<Return>(context.SourceLoc(), return_exp,
                                     is_omitted_exp);
    }
| block
    { $$ = $1; }
| MATCH LEFT_PARENTHESIS expression RIGHT_PARENTHESIS LEFT_CURLY_BRACE
  clause_list RIGHT_CURLY_BRACE
    { $$ = global_arena->New<Match>(context.SourceLoc(), $3, $6); }
| CONTINUATION identifier statement
    { $$ = global_arena->New<Continuation>(context.SourceLoc(), $2, $3); }
| RUN expression SEMICOLON
    { $$ = global_arena->New<Run>(context.SourceLoc(), $2); }
| AWAIT SEMICOLON
    { $$ = global_arena->New<Await>(context.SourceLoc()); }
;
if_statement:
  IF LEFT_PARENTHESIS expression RIGHT_PARENTHESIS block optional_else
    { $$ = global_arena->New<If>(context.SourceLoc(), $3, $5, $6); }
;
optional_else:
  // Empty
    { $$ = std::nullopt; }
| ELSE if_statement
    { $$ = $2; }
| ELSE block
    { $$ = $2; }
;
return_expression:
  // Empty
    { $$ = {global_arena->New<TupleLiteral>(context.SourceLoc()), true}; }
| expression
    { $$ = {$1, false}; }
;
statement_list:
  // Empty
    { $$ = std::nullopt; }
| statement statement_list
    { $$ = global_arena->New<Sequence>(context.SourceLoc(), $1, $2); }
;
block:
  LEFT_CURLY_BRACE statement_list RIGHT_CURLY_BRACE
    { $$ = global_arena->New<Block>(context.SourceLoc(), $2); }
;
return_type:
  // Empty
    { $$ = {global_arena->New<TupleLiteral>(context.SourceLoc()), true}; }
| ARROW expression %prec FNARROW
    { $$ = {$2, false}; }
;
generic_binding:
  identifier COLON_BANG expression
    { $$ = GenericBinding({.name = std::move($1), .type = $3}); }
;
deduced_param_list:
  // Empty
    { $$ = std::vector<GenericBinding>(); }
| generic_binding
    {
      $$ = std::vector<GenericBinding>();
      $$.push_back($1);
    }
| generic_binding COMMA deduced_param_list
    {
      $$ = $3;
      $$.push_back($1);
    }
;
deduced_params:
  // Empty
    { $$ = std::vector<GenericBinding>(); }
| LEFT_SQUARE_BRACKET deduced_param_list RIGHT_SQUARE_BRACKET
    { $$ = $2; }
;
function_definition:
  FN identifier deduced_params maybe_empty_tuple_pattern return_type block
    {
      auto [return_exp, is_omitted_exp] = $5.Release();
      $$ = global_arena->New<FunctionDefinition>(
          context.SourceLoc(), $2, $3, $4,
          global_arena->New<ExpressionPattern>(return_exp), is_omitted_exp, $6);
    }
| FN identifier deduced_params maybe_empty_tuple_pattern DOUBLE_ARROW expression
  SEMICOLON
    {
      // The return type is not considered "omitted" because it's automatic from
      // the expression.
      $$ = global_arena->New<FunctionDefinition>(
          context.SourceLoc(), $2, $3, $4,
          global_arena->New<AutoPattern>(context.SourceLoc()), true,
          global_arena->New<Return>(context.SourceLoc(), $6, true));
    }
;
function_declaration:
  FN identifier deduced_params maybe_empty_tuple_pattern return_type SEMICOLON
    {
      auto [return_exp, is_omitted_exp] = $5.Release();
      $$ = global_arena->New<FunctionDefinition>(
          context.SourceLoc(), $2, $3, $4,
          global_arena->New<ExpressionPattern>(return_exp), is_omitted_exp,
          std::nullopt);
    }
;
variable_declaration: identifier COLON pattern
    { $$ = global_arena->New<BindingPattern>(context.SourceLoc(), $1, $3); }
;
member: VAR variable_declaration SEMICOLON
    { $$ = global_arena->New<FieldMember>(context.SourceLoc(), $2); }
;
member_list:
  // Empty
    { $$ = std::list<Ptr<Member>>(); }
| member member_list
    {
      $$ = $2;
      $$.push_front($1);
    }
;
alternative:
  identifier tuple
    { $$ = std::pair<std::string, Ptr<const Expression>>($1, $2); }
| identifier
    {
      $$ = std::pair<std::string, Ptr<const Expression>>(
          $1, global_arena->New<TupleLiteral>(context.SourceLoc()));
    }
;
alternative_list:
  // Empty
    { $$ = std::list<std::pair<std::string, Ptr<const Expression>>>(); }
| alternative
    {
      $$ = std::list<std::pair<std::string, Ptr<const Expression>>>();
      $$.push_front($1);
    }
| alternative COMMA alternative_list
    {
      $$ = std::move($3);
      $$.push_front($1);
    }
;
declaration:
  function_definition
    { $$ = global_arena->New<FunctionDeclaration>($1); }
| function_declaration
    { $$ = global_arena->New<FunctionDeclaration>($1); }
| CLASS identifier LEFT_CURLY_BRACE member_list RIGHT_CURLY_BRACE
    { $$ = global_arena->New<ClassDeclaration>(context.SourceLoc(), $2, $4); }
| CHOICE identifier LEFT_CURLY_BRACE alternative_list RIGHT_CURLY_BRACE
    { $$ = global_arena->New<ChoiceDeclaration>(context.SourceLoc(), $2, $4); }
| VAR variable_declaration EQUAL expression SEMICOLON
    {
      $$ = global_arena->New<VariableDeclaration>(context.SourceLoc(), $2, $4);
    }
;
declaration_list:
  // Empty
    { $$ = std::list<Ptr<const Declaration>>(); }
| declaration declaration_list
    {
      $$ = $2;
      $$.push_front(Ptr<const Declaration>($1));
    }
;
%%