2018-09-18
https://github.com/xandkar/tiger.ml
In order to support mutual recursion, we need to group consecutive type and function declarations (see Tiger-book pages 97-99).
Initially, I defined the rules to do so as:
decs: | dec { $1 :: [] } | dec decs { $1 :: $2 } ; dec: | var_dec { $1 } | typ_decs { Ast.TypeDecs $1 } | fun_decs { Ast.FunDecs $1 } ;
which, while straightforward (and working, because
ocamlyacc
defaults to shift in case of a conflict),
nonetheless caused a shift/reduce conflict in each of:
typ_decs
and fun_decs
; where the parser did
not know whether to shift and stay in (typ|fun_)_dec
state
or to reduce and get back to dec
state.
Sadly, tagging the rules with a lower precedence (to explicitly favor shifting) - does not help :(
%nonassoc LOWEST ... dec: | var_dec { $1 } | typ_decs %prec LOWEST { Ast.TypeDecs $1 } | fun_decs %prec LOWEST { Ast.FunDecs $1 } ;
The difficulty seems to be in the lack of a
separator token which would be able to definitively mark the end
of each sequence of consecutive
(typ_|fun_)
declarations.
Keeping this in mind, another alternative is to manually capture the possible interspersion patterns in the rules like:
(N * foo) followed-by (N * not-foo)
for the exception of var_dec
, which, since we do not need to group its
consecutive sequences, can be reduced upon first sighting.
The final rules I ended-up with are:
decs: | var_dec decs_any { $1 :: $2 } | fun_decs decs_any_but_fun { (Ast.FunDecs $1) :: $2 } | typ_decs decs_any_but_typ { (Ast.TypeDecs $1) :: $2 } ; decs_any: | { [] } | var_dec decs_any { $1 :: $2 } | fun_decs decs_any_but_fun { (Ast.FunDecs $1) :: $2 } | typ_decs decs_any_but_typ { (Ast.TypeDecs $1) :: $2 } ; decs_any_but_fun: | { [] } | var_dec decs_any { $1 :: $2 } | typ_decs decs_any_but_typ { (Ast.TypeDecs $1) :: $2 } ; decs_any_but_typ: | { [] } | var_dec decs_any { $1 :: $2 } | fun_decs decs_any_but_fun { (Ast.FunDecs $1) :: $2 } ;