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
78 | error {Tiger_error.exn ~pos:(pos ()) ~msg:"invalid syntax"}
86 | MINUS exp %prec HIGHEST
95 | lvalue LBRACK exp RBRACK OF exp
98 | Ast.SimpleVar {symbol=typ; _} ->
105 | Ast.SubscriptVar _ | Ast.FieldVar _ ->
108 | ID LBRACE rec_fields_bind RBRACE
112 let typ = Sym.of_string type_id in
114 Ast.RecordExp {fields; typ; pos}
123 Ast.AssignExp {var; exp; pos}
126 { Ast.StringExp {string = $1; pos = pos ()} }
127 | ID LPAREN fun_args RPAREN
130 { func = Sym.of_string $1
166 ; oper = Ast.DivideOp
232 ; else' = Some (Ast.IntExp 0)
242 ; then' = Ast.IntExp 1
247 | IF exp THEN exp ELSE exp
280 | FOR ID ASSIGN exp TO exp DO exp
287 { var = Sym.of_string var
296 { Ast.BreakExp (pos ()) }
299 | LET decs IN exps END
303 Ast.LetExp {decs; body = Ast.SeqExp exps; pos = pos ()}
309 | exp { ($1, pos ()) :: [] }
310 | exp SEMICOLON exps { ($1, pos ()) :: $3 }
314 | ID EQ exp { (Sym.of_string $1, $3, pos ()) :: [] }
315 | ID EQ exp COMMA rec_fields_bind { (Sym.of_string $1, $3, pos ()) :: $5 }
318 /* ------------------------------------------------------------------------- */
319 /* BEGIN unintuitive rules for decs (which avoid shift/reduce conflicts) */
320 /* ------------------------------------------------------------------------- */
322 In order to support mutual recursion, we need to group consecutive
323 type and function declarations (see Tiger-book pages 97-99).
325 Initially, I defined the rules to do so as:
329 | dec decs { $1 :: $2 }
333 | typ_decs { Ast.TypeDecs $1 }
334 | fun_decs { Ast.FunDecs $1 }
337 which, while straightforward (and working, because ocamlyacc defaults to
338 shift in case of a conflict), nonetheless caused a shift/reduce conflict in
339 each of: typ_decs and fun_decs; where the parser did not know whether to
340 shift and stay in (typ|fun_)_dec state or to reduce and get back to dec
343 Sadly, tagging the rules with a lower precedence (to explicitly favor
344 shifting) - does not help :(
350 | typ_decs %prec LOWEST { Ast.TypeDecs $1 }
351 | fun_decs %prec LOWEST { Ast.FunDecs $1 }
354 The difficulty seems to be in the lack of a separator token which would be
355 able to definitively mark the end of each sequence of consecutive
356 (typ_|fun_) declarations.
358 Keeping this in mind, another alternative is to manually capture the possible
359 interspersion patterns in the rules like:
361 (N * foo) followed-by (N * not-foo)
363 for the exception of var_dec, which, since we do not need to group its
364 consecutive sequences, can be reduced upon first sighting.
368 | var_dec decs_any { $1 :: $2 }
369 | fun_decs decs_any_but_fun { (Ast.FunDecs $1) :: $2 }
370 | typ_decs decs_any_but_typ { (Ast.TypeDecs $1) :: $2 }
375 | var_dec decs_any { $1 :: $2 }
376 | fun_decs decs_any_but_fun { (Ast.FunDecs $1) :: $2 }
377 | typ_decs decs_any_but_typ { (Ast.TypeDecs $1) :: $2 }
382 | var_dec decs_any { $1 :: $2 }
383 | typ_decs decs_any_but_typ { (Ast.TypeDecs $1) :: $2 }
388 | var_dec decs_any { $1 :: $2 }
389 | fun_decs decs_any_but_fun { (Ast.FunDecs $1) :: $2 }
392 /*---------------------------------------------------------------------------*/
393 /* END unintuitive rules for decs (which avoid shift/reduce conflicts) */
394 /*---------------------------------------------------------------------------*/
397 | typ_dec { $1 :: [] }
398 | typ_dec typ_decs { $1 :: $2 }
404 let type_id_left = $2 in
405 let type_id_right = $4 in
406 let pos = pos () in (* FIXME: rhs id should have its own pos, no? *)
408 { name = Sym.of_string type_id_left
409 ; ty = Ast.NameTy {symbol = Sym.of_string type_id_right; pos}
413 | TYPE ID EQ LBRACE type_fields RBRACE
416 let type_fields = $5 in
418 { name = Sym.of_string type_id
419 ; ty = Ast.RecordTy type_fields
423 | TYPE ID EQ ARRAY OF ID
425 let type_id = Sym.of_string $2 in
426 let element_type_id = Sym.of_string $6 in
430 ; ty = Ast.ArrayTy {symbol = element_type_id; pos}
437 | VAR ID maybe_type_sig ASSIGN exp
439 let var_id = Sym.of_string $2 in
440 let maybe_type_sig = $3 in
446 ; typ = maybe_type_sig
454 | fun_dec { $1 :: [] }
455 | fun_dec fun_decs { $1 :: $2 }
459 | FUNCTION ID LPAREN type_fields RPAREN maybe_type_sig EQ exp
461 let name = Sym.of_string $2 in
466 Ast.FunDec {name; params; result; body; pos}
472 | COLON ID { Some (Sym.of_string $2, pos ()) }
482 { name = Sym.of_string $1
484 ; typ = Sym.of_string $3
490 | ID COLON ID COMMA type_fields
494 { name = Sym.of_string $1
496 ; typ = Sym.of_string $3
507 | exp COMMA fun_args { $1 :: $3 }
514 { symbol = Sym.of_string $1
518 | lvalue LBRACK exp RBRACK
530 ; symbol = Sym.of_string $3