[Ur] Mutually recursive values

Gabriel Riba gabriel at xarxaire.com
Thu Jul 9 10:51:35 EDT 2015


Trying to use mutually recursive values don't compile, giving the error:

syntax error: replacing  AND with  UNDER
Parse failure
----------

Here is a sample to try with:

   val rec even (i:int) = if i = 0 then True
                        else if i > 0 then odd (i -1)
                        else error <xml>error: negative input</xml>

   and val rec odd (i:int) = if i = 0 then False
                           else if i > 0 then even (i -1)
                           else error <xml>error: negative input</xml>

(* --- *)

I have found the syntax problem in urweb.grm in the non-terminal 
production "valis" used in declarations (decl production) and local 
declarations (edecl production).

decl   :...
        | VAL REC valis
        | FUN valis

vali   : SYMBOL eargl2 copt EQ eexp

valis  : vali                           ([vali])
        | vali AND valis                 (vali :: valis)

----------

A simple working patch:

valis  : vali                           ([vali])
        | vali AND VAL REC valis         (vali :: valis)
        | vali AND FUN valis             (vali :: valis)


But it is recommended to avoid right recursion in LR grammars because of 
rightmost derivation [1], so another tested proposal is

valis  : vali                           ([vali])
        | valis AND VAL REC vali         (valis @ [vali])
        | valis AND FUN vali             (valis @ [vali])


-------------
[1] Lex-YACC-HOWTO - 6.2 Recursion: 'right is wrong' 
(http://tldp.org/HOWTO/Lex-YACC-HOWTO-6.html#ss6.2)




More information about the Ur mailing list