2 module Ast = Tiger_absyn
3 module Sym = Tiger_symbol
6 Tiger_position.of_lexing_positions
7 ~pos_start:(Parsing.symbol_start_pos ())
8 ~pos_end:(Parsing.symbol_end_pos ())
49 %token <string> STRING
57 /* from lowest precedence */
64 %nonassoc EQ NEQ GT LT GE LE
68 /* to highest precedence */
70 %type <Tiger_absyn.t> program
76 program: exp EOF { $1 };
83 | MINUS exp %prec HIGHEST
92 | lvalue LBRACK exp RBRACK OF exp
95 | Ast.SimpleVar {symbol=typ; _} ->
102 | Ast.SubscriptVar _ | Ast.FieldVar _ ->
105 | ID LBRACE rec_fields_bind RBRACE
109 let typ = Sym.of_string type_id in
111 Ast.RecordExp {fields; typ; pos}
120 Ast.AssignExp {var; exp; pos}
123 { Ast.StringExp {string = $1; pos = pos ()} }
124 | ID LPAREN fun_args RPAREN
127 { func = Sym.of_string $1
163 ; oper = Ast.DivideOp
229 ; else' = Some (Ast.IntExp 0)
239 ; then' = Ast.IntExp 1
244 | IF exp THEN exp ELSE exp
277 | FOR ID ASSIGN exp TO exp DO exp
284 { var = Sym.of_string var
293 { Ast.BreakExp (pos ()) }
296 | LET decs IN exps END
300 Ast.LetExp {decs; body = Ast.SeqExp exps; pos = pos ()}
306 | exp { ($1, pos ()) :: [] }
307 | exp SEMICOLON exps { ($1, pos ()) :: $3 }
311 | ID EQ exp { (Sym.of_string $1, $3, pos ()) :: [] }
312 | ID EQ exp COMMA rec_fields_bind { (Sym.of_string $1, $3, pos ()) :: $5 }
315 /* ------------------------------------------------------------------------- */
316 /* BEGIN unintuitive rules for decs (which avoid shift/reduce conflicts) */
317 /* ------------------------------------------------------------------------- */
319 In order to support mutual recursion, we need to group consecutive
320 type and function declarations (see Tiger-book pages 97-99).
322 Initially, I defined the rules to do so as:
326 | dec decs { $1 :: $2 }
330 | typ_decs { Ast.TypeDecs $1 }
331 | fun_decs { Ast.FunDecs $1 }
334 which, while straightforward (and working, because ocamlyacc defaults to
335 shift in case of a conflict), nonetheless caused a shift/reduce conflict in
336 each of: typ_decs and fun_decs; where the parser did not know whether to
337 shift and stay in (typ|fun_)_dec state or to reduce and get back to dec
340 Sadly, tagging the rules with a lower precedence (to explicitly favor
341 shifting) - does not help :(
347 | typ_decs %prec LOWEST { Ast.TypeDecs $1 }
348 | fun_decs %prec LOWEST { Ast.FunDecs $1 }
351 The difficulty seems to be in the lack of a separator token which would be
352 able to definitively mark the end of each sequence of consecutive
353 (typ_|fun_) declarations.
355 Keeping this in mind, another alternative is to manually capture the possible
356 interspersion patterns in the rules like:
358 (N * foo) followed-by (N * not-foo)
360 for the exception of var_dec, which, since we do not need to group its
361 consecutive sequences, can be reduced upon first sighting.
365 | var_dec decs_any { $1 :: $2 }
366 | fun_decs decs_any_but_fun { (Ast.FunDecs $1) :: $2 }
367 | typ_decs decs_any_but_typ { (Ast.TypeDecs $1) :: $2 }
372 | var_dec decs_any { $1 :: $2 }
373 | fun_decs decs_any_but_fun { (Ast.FunDecs $1) :: $2 }
374 | typ_decs decs_any_but_typ { (Ast.TypeDecs $1) :: $2 }
379 | var_dec decs_any { $1 :: $2 }
380 | typ_decs decs_any_but_typ { (Ast.TypeDecs $1) :: $2 }
385 | var_dec decs_any { $1 :: $2 }
386 | fun_decs decs_any_but_fun { (Ast.FunDecs $1) :: $2 }
389 /*---------------------------------------------------------------------------*/
390 /* END unintuitive rules for decs (which avoid shift/reduce conflicts) */
391 /*---------------------------------------------------------------------------*/
394 | typ_dec { $1 :: [] }
395 | typ_dec typ_decs { $1 :: $2 }
401 let type_id_left = $2 in
402 let type_id_right = $4 in
403 let pos = pos () in (* FIXME: rhs id should have its own pos, no? *)
405 { name = Sym.of_string type_id_left
406 ; ty = Ast.NameTy {symbol = Sym.of_string type_id_right; pos}
410 | TYPE ID EQ LBRACE type_fields RBRACE
413 let type_fields = $5 in
415 { name = Sym.of_string type_id
416 ; ty = Ast.RecordTy type_fields
420 | TYPE ID EQ ARRAY OF ID
422 let type_id = Sym.of_string $2 in
423 let element_type_id = Sym.of_string $6 in
427 ; ty = Ast.ArrayTy {symbol = element_type_id; pos}
434 | VAR ID maybe_type_sig ASSIGN exp
436 let var_id = Sym.of_string $2 in
437 let maybe_type_sig = $3 in
443 ; typ = maybe_type_sig
451 | fun_dec { $1 :: [] }
452 | fun_dec fun_decs { $1 :: $2 }
456 | FUNCTION ID LPAREN type_fields RPAREN maybe_type_sig EQ exp
458 let name = Sym.of_string $2 in
463 Ast.FunDec {name; params; result; body; pos}
469 | COLON ID { Some (Sym.of_string $2, pos ()) }
479 { name = Sym.of_string $1
481 ; typ = Sym.of_string $3
487 | ID COLON ID COMMA type_fields
491 { name = Sym.of_string $1
493 ; typ = Sym.of_string $3
504 | exp COMMA fun_args { $1 :: $3 }
511 { symbol = Sym.of_string $1
515 | lvalue LBRACK exp RBRACK
527 ; symbol = Sym.of_string $3