Parsing

[Jon Harrop <jon@ffconsultancy.com>]

I'm not a parser junkie, so please bear with me if this is silly...

The camlp4 stream parsing syntax extension is a very cool way to write 
efficient parsers for simple grammars:

  http://www.ffconsultancy.com/ocaml/benefits/parsing.html

# let rec parse_atom = parser
    | [< 'Int n >] -> Num n
    | [< 'Kwd "("; e=parse_expr; 'Kwd ")" >] -> e

  and parse_factor = parser
    | [< e1=parse_atom; stream >] ->
        (parser
         | [< 'Kwd "*"; e2=parse_factor >] -> e1 *: e2
         | [< >] -> e1) stream

  and parse_expr = parser
    | [< e1=parse_factor; stream >] ->
        (parser
         | [< 'Kwd "+"; e2=parse_expr >] -> e1 +: e2
         | [< 'Kwd "-"; e2=parse_expr >] -> e1 -: e2
         | [< >] -> e1) stream;;
val parse_atom : Genlex.token Stream.t -> expr = <fun>
val parse_factor : Genlex.token Stream.t -> expr = <fun>
val parse_expr : Genlex.token Stream.t -> expr = <fun>

However, you must factor heads in the pattern matches. So instead of:

  and parse_expr = parser
    | [< e1=parse_factor; 'Kwd "+"; e2=parse_expr >] -> e1 +: e2
    | [< e1=parse_factor; 'Kwd "-"; e2=parse_expr >] -> e1 -: e2
    | [< e1=parse_factor  >] -> e1

you must write:

  and parse_expr = parser
    | [< e1=parse_factor; stream >] ->
        (parser
         | [< 'Kwd "+"; e2=parse_expr >] -> e1 +: e2
         | [< 'Kwd "-"; e2=parse_expr >] -> e1 -: e2
         | [< >] -> e1) stream

Why is this? Is it because the streams are destructive? Could the camlp4 macro 
not factor the pattern match for me?

Are there other parser tools that integrate into the language and do a better 
job?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e