exception FAIL;

fun nondet FUNCS ARGS =
    case FUNCS of
	 [] => raise FAIL
     |   only_choice::[] => only_choice ARGS
     |   head::tail => head ARGS
		       handle FAIL => nondet tail ARGS
;


(* Simple example: parsing strings (in regular languages).
   The three rules (S1,S2,S3) below correspond to the grammar
      S --> aS
      S --> abS
      S --> ""     (the empty string)
*)

fun S1 ("a"::x) = nondet [S1,S2,S3] x
 |  S1     _    = raise FAIL

and S2 ("a"::"b"::x) = nondet [S1,S2,S3] x   (* "and" is used for functions that
                                                 are mutually recursive  *)
 |  S2       _       = raise FAIL

and S3 [] = true
 |  S3 _  = raise FAIL
;

fun parse Rules String = nondet Rules (explode String);

val Grammar1 = parse [S1,S2,S3];