Re: [Caml-list] Parser combinators

[Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>]

From: Alex Baretta <alex@barettadeit.com>
> > Interestingly, your example corresponds exactly to the one in the
> > ocaml tutorial, where it is solved using stream parsers.
> > Stream parsers are a bit more involved than just writing yacc rules,
> > but they give you more control on how to combine rules (you can write
> > parser combinators.) And they are completely integrated in the
> > language using camlp4.
> 
> Er.. Excuse me for sticking my nose into this, but I think I read 
> something interesting. Parser combinators? What do you mean? I'm quite 
> sure I have not seen any operators acting on stream parsers, at least if 
> by stream parsers you mean the LL1 based on pa_op.cmo camlp4 module.

The point is that you can define them yourself.
For instance here is the star operator.

let rec star ?(acc=[]) p = parser
    [< x = p ; s >] -> star ~acc:(x::acc) p s
  | [< >] -> List.rev acc

More concretely, here is another version of expression parsing, using
functionals. 

type expr =
    Num of int
  | Var of string
  | Plus of expr * expr
  | Mult of expr * expr

open Genlex

let rec accumulate parse accu = parser
  | [< e = parse accu; s >] -> accumulate parse e s
  | [< >] -> accu
(* val accumulate : ('a -> Genlex.token Stream.t -> 'a) ->
                    'a -> Genlex.token Stream.t -> 'a *)
let left_assoc parse op wrap =
  let parse' accu =
    parser [< 'Kwd k when k = op; s >] -> wrap accu (parse s) in
  parser [< e1 = parse; e2 = accumulate parse' e1 >] -> e2
(* val left_assoc : (Genlex.token Stream.t -> 'a) ->
       string -> ('a -> 'a -> 'a) -> Genlex.token Stream.t -> 'a *)
let rec parse_simple = parser
  | [< 'Int n >] -> Num n
  | [< 'Ident x >] -> Var x
  | [< 'Kwd"("; e = parse_expr; 'Kwd")" >] -> e
and parse_mult s =
  left_assoc parse_simple "*" (fun e1 e2 -> Mult(e1,e2)) s
and parse_expr s =
  left_assoc parse_mult "+" (fun e1 e2 -> Plus(e1,e2)) s
(* val parse_simple : Genlex.token Stream.t -> expr
   val parse_mult : Genlex.token Stream.t -> expr
   val parse_expr : Genlex.token Stream.t -> expr *)

let lexer = Genlex.make_lexer ["+";"*";"(";")"]
let parse_string s =
  match lexer (Stream.of_string s) with parser
    [< e = parse_expr; _ = Stream.empty >] -> e
(* val parse_string : string -> expr *)

I leave as exercise how to extend it to handle "-" and "/" in a
generic way.

Jacques Garrigue