Version française
Home     About     Download     Resources     Contact us    
Browse thread
How can I have a string matched my custom type?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Jean-Christophe Filliatre <filliatr@l...>
Subject: Re: [Caml-list] How can I have a string matched my custom type?

 >     I want to parse an expression string from the command line arguments, and have written some codes like below:
 >     
 >     type expr =      
 >           Plus        of expr * expr
 >         | Minus     of expr * expr
 >         | Times     of expr * expr            
 >         | Divide    of expr * expr
 >         | Value     of string
 > 
 >     let rec to_string e =
 >         match e with
 >               Plus      (left, right)   -> "(" ^ (to_string left) ^ "+" ^ (to_string right) ^ ")"
 >             | Minus     (left, right)   -> "(" ^ (to_string left) ^ "-" ^ (to_string right) ^ ")"
 >             | Times     (left, right)   -> "(" ^ (to_string left) ^ "*" ^ (to_string right) ^ ")"
 >             | Divide    (left, right)   -> "(" ^ (to_string left) ^ "/" ^ (to_string right) ^ ")"
 >             | Value     v               -> v
 > 
 >     let _ =
 >          print_endline (to_string Sys.argv.(1))

As you say, you want to _parse_ an expression from a string, which
means a function of type string->expr, but your code only contains a
_pretty-printer_, that is the opposite operation, which has type
expr->string. 

There are several ways to build such a parser. A simple way is to
write a recursive descending parser using Genlex and Stream from
ocaml's standard library, as follows:

======================================================================
open Genlex

let lex = make_lexer ["+"; "-"; "*"; "/"; "("; ")"];;

let rec expr s = 
  let t = term s in
  match Stream.peek s with
    | Some (Kwd "+") -> Stream.junk s; Plus (t, expr s)
    | Some (Kwd "-") -> Stream.junk s; Minus (t, expr s)
    | _ -> t

and term s = 
  let f = factor s in
  match Stream.peek s with
    | Some (Kwd "*") -> Stream.junk s; Times (f, term s)
    | Some (Kwd "/") -> Stream.junk s; Divide (f, term s)
    | _ -> f
    | _ -> failwith "syntax error"

and factor s = match Stream.peek s with
  | Some (Kwd "(") -> 
      Stream.junk s;
      let e = expr s in
      begin match Stream.peek s with
	| Some (Kwd ")") -> Stream.junk s; e
	| _ -> failwith "syntax error"
      end
  | Some (Int n) ->
      Stream.junk s;
      Value (string_of_int n)
  | _ -> 
      failwith "syntax error"

let parse s = expr (lex (Stream.of_string s))
======================================================================

then you can parse the string "(1+2)*3+4" as follows:

======================================================================
let e = parse "(1+2)*3+4"
# val e : expr =
  Plus (Times (Plus (Value "1", Value "2"), Value "3"), Value "4")
======================================================================

Another more sophisticated (but more powerful) way is to use a tool
like ocamlyacc or menhir.

Hope this helps,
-- 
Jean-Christophe