bundles/menhirLib/menhir-20120123/src/parser.mly

   1 /**************************************************************************/
   2 /*                                                                        */
   3 /*  Menhir                                                                */
   4 /*                                                                        */
   5 /*  François Pottier, INRIA Rocquencourt                                  */
   6 /*  Yann Régis-Gianas, PPS, Université Paris Diderot                      */
   7 /*                                                                        */
   8 /*  Copyright 2005-2008 Institut National de Recherche en Informatique    */
   9 /*  et en Automatique. All rights reserved. This file is distributed      */
  10 /*  under the terms of the Q Public License version 1.0, with the change  */
  11 /*  described in file LICENSE.                                            */
  12 /*                                                                        */
  13 /**************************************************************************/
  14
  15 /* This is the crude version of the parser. It is meant to be processed
  16    by ocamlyacc. Its existence is necessary for bootstrapping. It is kept
  17    in sync with [fancy-parser]. The two parsers accept the same language,
  18    but [fancy-parser] performs more refined error recovery. */
  19
  20 %{
  21
  22 open Keyword
  23 open ConcreteSyntax
  24 open Syntax
  25 open Positions
  26
  27 %}
  28
  29 %token TOKEN TYPE LEFT RIGHT NONASSOC START PREC PUBLIC COLON BAR EOF EQUAL
  30 %token INLINE LPAREN RPAREN COMMA QUESTION STAR PLUS PARAMETER
  31 %token <string Positions.located> LID UID
  32 %token <Stretch.t> HEADER
  33 %token <Stretch.ocamltype> OCAMLTYPE
  34 %token <string Lazy.t> PERCENTPERCENT
  35 %token <Syntax.action> ACTION
  36 %start grammar
  37 %type <ConcreteSyntax.grammar> grammar
  38
  39 /* These declarations solve a shift-reduce conflict in favor of
  40    shifting: when the declaration of a non-terminal symbol begins with
  41    a leading bar, it is understood as an (insignificant) leading
  42    optional bar, *not* as an empty right-hand side followed by a bar.
  43    This ambiguity arises due to the existence of a new notation for
  44    letting several productions share a single semantic action. */
  45
  46 %nonassoc no_optional_bar
  47 %nonassoc BAR
  48
  49 %%
  50
  51 /* ------------------------------------------------------------------------- */
  52 /* A grammar consists of declarations and rules, followed by an optional
  53    trailer, which we do not parse. */
  54
  55 grammar:
  56   declarations PERCENTPERCENT rules trailer
  57     {
  58       {
  59         pg_filename          = ""; (* filled in by the caller *)
  60         pg_declarations      = List.rev $1;
  61         pg_rules             = $3;
  62         pg_trailer           = $4
  63       }
  64     }
  65
  66 trailer:
  67   EOF
  68     { None }
  69 | PERCENTPERCENT /* followed by actual trailer */
  70     { Some (Lazy.force $1) }
  71
  72 /* ------------------------------------------------------------------------- */
  73 /* A declaration is an %{ Objective Caml header %}, or a %token, %start,
  74    %type, %left, %right, or %nonassoc declaration. */
  75
  76 declarations:
  77   /* epsilon */
  78     { [] }
  79 | declarations declaration
  80     { $2 @ $1 }
  81
  82 declaration:
  83 | HEADER /* lexically delimited by %{ ... %} */
  84     { [ unknown_pos (DCode $1) ] }
  85
  86 | TOKEN optional_ocamltype terminals
  87     { List.map (Positions.map (fun terminal -> DToken ($2, terminal))) $3 }
  88
  89 | START nonterminals
  90     { List.map (Positions.map (fun nonterminal -> DStart nonterminal)) $2 }
  91
  92 | TYPE OCAMLTYPE actual_parameters
  93     { List.map (Positions.map (fun nt -> DType ($2, nt)))
  94         (List.map Parameters.with_pos $3) }
  95
  96 | START OCAMLTYPE nonterminals
  97     /* %start <ocamltype> foo is syntactic sugar for %start foo %type <ocamltype> foo */
  98     { Misc.mapd (fun ntloc ->
  99         Positions.mapd (fun nt -> DStart nt, DType ($2, ParameterVar ntloc)) ntloc) $3 }
 100
 101 | priority_keyword symbols
 102     { let prec = ParserAux.current_token_precedence (rhs_start_pos 1) (rhs_end_pos 1) in
 103       List.map (Positions.map (fun symbol -> DTokenProperties (symbol, $1, prec))) $2 }
 104
 105 | PARAMETER OCAMLTYPE
 106     { [ unknown_pos (DParameter $2) ] }
 107
 108 optional_ocamltype:
 109   /* epsilon */
 110     { None }
 111 | OCAMLTYPE /* lexically delimited by angle brackets */
 112     { Some $1 }
 113
 114 priority_keyword:
 115   LEFT
 116     { LeftAssoc }
 117 | RIGHT
 118     { RightAssoc }
 119 | NONASSOC
 120     { NonAssoc }
 121
 122 /* ------------------------------------------------------------------------- */
 123 /* A symbol is a terminal or nonterminal symbol. One would like to
 124    require nonterminal symbols to begin with a lowercase letter, so as
 125    to lexically distinguish them from terminal symbols, which must
 126    begin with an uppercase letter. However, for compatibility with
 127    ocamlyacc, this is impossible. It can be required only for
 128    nonterminal symbols that are also start symbols. */
 129
 130 symbols:
 131   /* epsilon */
 132     { [] }
 133 | symbols optional_comma symbol
 134     { $3 :: $1 }
 135
 136 symbol:
 137   LID
 138     { $1 }
 139 | UID
 140     { $1 }
 141
 142 optional_comma:
 143   /* epsilon */
 144     { () }
 145 | COMMA
 146     { () }
 147
 148 /* ------------------------------------------------------------------------- */
 149 /* Terminals must begin with an uppercase letter. Nonterminals that are
 150    declared to be start symbols must begin with a lowercase letter. */
 151
 152 terminals:
 153   /* epsilon */
 154     { [] }
 155 | terminals optional_comma UID
 156     { $3 :: $1 }
 157
 158 nonterminals:
 159   /* epsilon */
 160     { [] }
 161 | nonterminals LID
 162     { $2 :: $1 }
 163
 164 /* ------------------------------------------------------------------------- */
 165 /* A rule defines a symbol. It is optionally declared %public, and optionally
 166    carries a number of formal parameters. The right-hand side of the definition
 167    consists of a list of production groups. */
 168
 169 rules:
 170   /* epsilon */
 171     { [] }
 172 | rules rule
 173     { $2 :: $1 }
 174
 175 rule:
 176   flags
 177   symbol
 178   optional_formal_parameters
 179   COLON optional_bar
 180   production_group production_groups
 181     {
 182       let public, inline = $1 in
 183       { pr_public_flag = public;
 184         pr_inline_flag = inline;
 185         pr_nt          = Positions.value $2;
 186         pr_positions   = [ Positions.position $2 ];
 187         pr_parameters  = $3;
 188         pr_branches    = List.flatten ($6 :: List.rev $7)
 189       }
 190     }
 191
 192 flags:
 193   /* epsilon */
 194     { false, false }
 195 | PUBLIC
 196     { true, false }
 197 | INLINE
 198     { false, true }
 199 | PUBLIC INLINE
 200     { true, true }
 201 | INLINE PUBLIC
 202     { true, true }
 203
 204 /* ------------------------------------------------------------------------- */
 205 /* Parameters are surroundered with parentheses and delimited by commas.
 206    The syntax of actual parameters allows applications, whereas the syntax
 207    of formal parameters does not. It also allows use of the "?", "+", and
 208    "*" shortcuts. */
 209
 210 optional_formal_parameters:
 211   /* epsilon */
 212     { [] }
 213 | LPAREN formal_parameters RPAREN
 214     { $2 }
 215
 216 formal_parameters:
 217   symbol
 218     { [ Positions.value $1 ] }
 219 | symbol COMMA formal_parameters
 220     { Positions.value $1 :: $3 }
 221
 222 optional_actual_parameters:
 223   /* epsilon */
 224     { [] }
 225 | LPAREN actual_parameters_comma RPAREN
 226     { $2 }
 227
 228 actual_parameters_comma:
 229   actual_parameter
 230     { [ $1 ] }
 231 | actual_parameter COMMA actual_parameters_comma
 232     { $1 :: $3 }
 233
 234 actual_parameter:
 235   symbol optional_actual_parameters optional_modifier
 236     { Parameters.oapp1 $3 (Parameters.app $1 $2) }
 237
 238 actual_parameters:
 239   /* epsilon */
 240     { [] }
 241 | actual_parameters optional_comma actual_parameter
 242     { $3::$1 }
 243
 244 optional_bar:
 245   /* epsilon */ %prec no_optional_bar
 246     { () }
 247 | BAR
 248     { () }
 249
 250 /* ------------------------------------------------------------------------- */
 251 /* The "?", "+", and "*" modifiers are short-hands for applications of
 252    certain parameterized nonterminals, defined in the standard library. */
 253
 254 optional_modifier:
 255   /* epsilon */
 256     { None }
 257 | modifier
 258     { Some $1 }
 259
 260 modifier:
 261   QUESTION
 262     { unknown_pos "option" }
 263 | PLUS
 264     { unknown_pos "nonempty_list" }
 265 | STAR
 266     { unknown_pos "list" }
 267
 268 /* ------------------------------------------------------------------------- */
 269 /* A production group consists of a list of productions, followed by a
 270    semantic action and an optional precedence specification. */
 271
 272 production_groups:
 273   /* epsilon */
 274     { [] }
 275 | production_groups BAR production_group
 276     { $3 :: $1 }
 277
 278 production_group:
 279   productions ACTION /* action is lexically delimited by braces */ optional_precedence
 280     {
 281       let productions, action, oprec2 = $1, $2, $3 in
 282
 283       ParserAux.check_production_group
 284         productions
 285         (rhs_start_pos 2) (rhs_end_pos 2) action;
 286
 287       List.map (fun (producers, oprec1, rprec, pos) -> {
 288         pr_producers                = producers;
 289         pr_action                   = action;
 290         pr_branch_shift_precedence  = ParserAux.override pos oprec1 oprec2;
 291         pr_branch_reduce_precedence = rprec;
 292         pr_branch_position          = pos
 293       }) productions
 294     }
 295
 296 optional_precedence:
 297   /* epsilon */
 298     { None }
 299 | PREC symbol
 300     { Some $2 }
 301
 302 /* ------------------------------------------------------------------------- */
 303 /* A production is a list of producers, optionally followed by a
 304    precedence declaration. Lists of productions are nonempty and
 305    separated with bars. */
 306
 307 productions:
 308   production
 309     { [ $1 ] }
 310 | production bar_productions
 311     { $1 :: $2 }
 312
 313 bar_productions:
 314   BAR production
 315     { [ $2 ] }
 316 | BAR production bar_productions
 317     { $2 :: $3 }
 318
 319 production:
 320   producers optional_precedence
 321     { List.rev $1,
 322       $2,
 323       ParserAux.current_reduce_precedence(),
 324       Positions.lex_join (symbol_start_pos()) (symbol_end_pos())
 325     }
 326
 327 producers:
 328   /* epsilon */
 329     { [] }
 330 | producers producer
 331     { $2 :: $1 }
 332
 333 /* ------------------------------------------------------------------------- */
 334 /* A producer is an actual parameter, possibly preceded by a
 335    binding. */
 336
 337 producer:
 338 | actual_parameter
 339     { None, $1 }
 340 | LID EQUAL actual_parameter
 341     { Some $1, $3 }
 342
 343 %%
 344