viewcvs.cgi/parser/parser.ml

open Location
open Ast

module P = struct

  let gram    = Grammar.create (Plexer.make ())
  let expr    = Grammar.Entry.create gram "expression"
  let pat     = Grammar.Entry.create gram "type/pattern expression"
  let regexp  = Grammar.Entry.create gram "type/pattern regexp"
  let const   = Grammar.Entry.create gram "scalar constant"
 
  let atom_nil = Types.mk_atom "nil"
                   
  let rec multi_prod loc = function
    | [ x ] -> x
    | x :: l -> mk loc (Prod (x, multi_prod loc l))
    | [] -> assert false

  let rec tuple loc = function
    | [ x ] -> x
    | x :: l -> mk loc (Pair (x, tuple loc l))
    | [] -> assert false
        
  EXTEND
  GLOBAL: expr pat regexp const;

  expr: [
    "top" RIGHTA
    [ "match"; e = SELF; "with"; b = branches -> mk loc (Match (e,b))
    | "map"; e = SELF; "with"; b = branches -> mk loc (Map (e,b))
    | "fun"; f = OPT LIDENT; "("; a = LIST1 arrow SEP ";"; ")";
      b = branches -> 
        mk loc (Abstraction { fun_name = f; fun_iface = a; fun_body = b })
    | (p,e1) = let_binding; "in"; e2 = expr LEVEL "top"->
        mk loc (Match (e1,[p,e2]))
    ]

    |
    [ e1 = expr; e2 = expr -> mk loc (Apply (e1,e2))
    ]
    
    | "no_appl" 
    [ c = const -> mk loc (Cst c)
    | "("; l = LIST1 expr SEP ","; ")" -> tuple loc l
    | "[";  l = LIST0 expr LEVEL "no_appl"; "]" ->
        tuple loc (l @ [mk noloc (Cst (Types.Atom atom_nil))])
    | "[";  l = LIST0 expr LEVEL "no_appl"; ";"; e = expr; "]" ->
        tuple loc (l @ [e])
    | "<"; t = expr_tag_spec; a = expr_attrib_spec; ">"; c = expr ->
        tuple loc [t;a;c]
    | "{"; r = [ expr_record_spec | -> mk loc (RecordLitt []) ]; "}" -> r
    | a = LIDENT -> mk loc (Var a)
    ]

  ];
          
  let_binding: [
    [ "let"; p = pat; "="; e = expr -> (p,e)
    | "let"; "fun"; f = LIDENT; "("; a = LIST0 arrow SEP ";"; ")";
      b = branches -> 
        let p = mk loc (Capture f) in
        let abst = { fun_name = Some f; fun_iface = a; fun_body = b } in
        let e = mk loc (Abstraction abst) in
        (p,e)
    ] 
  ];

  arrow: [
    [ t1 = pat LEVEL "no_arrow"; "->"; t2 = pat -> (t1,t2)]
  ];

  branches: [
    [ OPT "|"; l = LIST1 branch SEP "|" ; OPT "end" -> l ]
  ];

  branch: [
    [ p = pat LEVEL "no_arrow"; "->"; e = expr -> (p,e) ]
  ];

          
  regexp: [ 
    [ x = regexp; "|"; y = regexp -> Alt (x,y) ]
  | [ x = regexp; y = regexp -> Seq (x,y) ]
  | [ a = LIDENT; "::"; x = regexp -> SeqCapture (a,x) ]
  | [ x = regexp; "*" -> Star x
    | x = regexp; "*?" -> WeakStar x
    | x = regexp; "+" -> Seq (x, Star x)
    | x = regexp; "+?" -> Seq (x, WeakStar x)
    | x = regexp; "?" -> Alt (x, Epsilon)
    | x = regexp; "??" -> Alt (Epsilon, x) ]
  | [ "("; x = regexp; ")" -> x
    | e = pat LEVEL "simple" -> Elem e
    ]
  ];

  pat: [ 
      [ x = pat; "where"; 
        b = LIST1 [ a = UIDENT; "="; y = pat -> (a,y)] SEP "and"
            -> mk loc (Recurs (x,b)) ]
    | RIGHTA [ x = pat; "->"; y = pat -> mk loc (Arrow (x,y)) ]
    | "no_arrow" [ x = pat; "|"; y = pat -> mk loc (Or (x,y)) ] 
    | "simple" [ x = pat; "&"; y = pat -> mk loc (And (x,y)) 
      | x = pat; "-"; y = pat -> mk loc (Diff (x,y)) ]
    | 
      [ "{"; r = record_spec; "}" -> r
      | UIDENT "Any" -> mk loc (Internal Types.any)
      | LIDENT "_" -> mk loc (Internal Types.any)
      | a = LIDENT -> mk loc (Capture a)
      | "("; a = LIDENT; ":="; c = const; ")" -> mk loc (Constant (a,c))
      | a = UIDENT -> mk loc (PatVar a)
      | i = INT ; "--"; j = INT -> 
          let i = int_of_string i and j = int_of_string j in
          mk loc (Internal (Types.interval i j))
      | c = const -> mk loc (Internal (Types.constant c))
      | "("; l = LIST1 pat SEP ","; ")" -> multi_prod loc l
      | "["; r = [ r = regexp -> r | -> Epsilon ];
             q = [ ";"; q = pat -> q 
                 | -> mk noloc (Internal (Types.atom atom_nil)) ]; 
             "]" -> mk loc (Regexp (r,q))
      | "<"; t = tag_spec; a = attrib_spec; ">"; c = pat ->
          multi_prod loc [t;a;c]
      ]
    
  ];

  record_spec:
    [ [ r = LIST0 [ l = [LIDENT | UIDENT]; 
                  o = ["=?" -> true | "=" -> false]; 
                  x = pat ->
                    mk loc (Record (Types.label l,o,x))
                ] SEP ";" ->
        match r with
          | [] -> mk loc (Internal Types.Record.any)
          | h::t -> List.fold_left (fun t1 t2 -> mk loc (And (t1,t2))) h t
      ] ];
  
  const:
    [ 
      [ i = INT -> Types.Integer (int_of_string i)
      | x = STRING -> Types.String (Token.eval_string x)
      | "`"; a = [LIDENT | UIDENT] -> Types.Atom (Types.mk_atom a) ]
    ];

  tag_spec:
    [
      [ a = [LIDENT | UIDENT] -> 
          mk loc (Internal (Types.atom (Types.mk_atom a))) ]
    | [ t = pat -> t ]
    ];

  attrib_spec:
    [ [ r = record_spec -> r | "("; t = pat; ")" -> t ] ];

  expr_record_spec:
    [ [ r = LIST1
              [ l = [LIDENT | UIDENT]; "="; x = expr -> (Types.label l,x) ] 
              SEP ";" ->
          mk loc (RecordLitt r)
      ] ];
  
  expr_tag_spec:
    [
      [ a = [LIDENT | UIDENT] -> 
          mk loc (Cst (Types.Atom (Types.mk_atom a))) ]
    | [ e = expr LEVEL "no_appl" -> e ]
    ];

  expr_attrib_spec:
    [ [ r = expr_record_spec -> r ]
    | [ e = expr LEVEL "no_appl" -> e 
      | -> mk loc (RecordLitt []) 
      ] 
    ];
END

end

let pat_or_typ s = Grammar.Entry.parse P.pat (Stream.of_string s)

let expr s =  Grammar.Entry.parse P.expr (Stream.of_string s)
1	abate	4	open Location
2			open Ast
3
4			module P = struct
5
6			let gram = Grammar.create (Plexer.make ())
7			let expr = Grammar.Entry.create gram "expression"
8			let pat = Grammar.Entry.create gram "type/pattern expression"
9			let regexp = Grammar.Entry.create gram "type/pattern regexp"
10			let const = Grammar.Entry.create gram "scalar constant"
11
12			let atom_nil = Types.mk_atom "nil"
13
14			let rec multi_prod loc = function
15			\| [ x ] -> x
16			\| x :: l -> mk loc (Prod (x, multi_prod loc l))
17			\| [] -> assert false
18
19			let rec tuple loc = function
20			\| [ x ] -> x
21			\| x :: l -> mk loc (Pair (x, tuple loc l))
22			\| [] -> assert false
23
24			EXTEND
25			GLOBAL: expr pat regexp const;
26
27			expr: [
28			"top" RIGHTA
29			[ "match"; e = SELF; "with"; b = branches -> mk loc (Match (e,b))
30			\| "map"; e = SELF; "with"; b = branches -> mk loc (Map (e,b))
31			\| "fun"; f = OPT LIDENT; "("; a = LIST1 arrow SEP ";"; ")";
32			b = branches ->
33			mk loc (Abstraction { fun_name = f; fun_iface = a; fun_body = b })
34			\| (p,e1) = let_binding; "in"; e2 = expr LEVEL "top"->
35			mk loc (Match (e1,[p,e2]))
36			]
37
38			\|
39			[ e1 = expr; e2 = expr -> mk loc (Apply (e1,e2))
40			]
41
42			\| "no_appl"
43			[ c = const -> mk loc (Cst c)
44			\| "("; l = LIST1 expr SEP ","; ")" -> tuple loc l
45			\| "["; l = LIST0 expr LEVEL "no_appl"; "]" ->
46			tuple loc (l @ [mk noloc (Cst (Types.Atom atom_nil))])
47			\| "["; l = LIST0 expr LEVEL "no_appl"; ";"; e = expr; "]" ->
48			tuple loc (l @ [e])
49			\| "<"; t = expr_tag_spec; a = expr_attrib_spec; ">"; c = expr ->
50			tuple loc [t;a;c]
51			\| "{"; r = [ expr_record_spec \| -> mk loc (RecordLitt []) ]; "}" -> r
52			\| a = LIDENT -> mk loc (Var a)
53			]
54
55			];
56
57			let_binding: [
58			[ "let"; p = pat; "="; e = expr -> (p,e)
59			\| "let"; "fun"; f = LIDENT; "("; a = LIST0 arrow SEP ";"; ")";
60			b = branches ->
61			let p = mk loc (Capture f) in
62			let abst = { fun_name = Some f; fun_iface = a; fun_body = b } in
63			let e = mk loc (Abstraction abst) in
64			(p,e)
65			]
66			];
67
68			arrow: [
69	abate	9	[ t1 = pat LEVEL "no_arrow"; "->"; t2 = pat -> (t1,t2)]
70	abate	4	];
71
72			branches: [
73			[ OPT "\|"; l = LIST1 branch SEP "\|" ; OPT "end" -> l ]
74			];
75
76			branch: [
77	abate	6	[ p = pat LEVEL "no_arrow"; "->"; e = expr -> (p,e) ]
78	abate	4	];
79
80
81			regexp: [
82			[ x = regexp; "\|"; y = regexp -> Alt (x,y) ]
83			\| [ x = regexp; y = regexp -> Seq (x,y) ]
84			\| [ a = LIDENT; "::"; x = regexp -> SeqCapture (a,x) ]
85			\| [ x = regexp; "*" -> Star x
86			\| x = regexp; "*?" -> WeakStar x
87			\| x = regexp; "+" -> Seq (x, Star x)
88			\| x = regexp; "+?" -> Seq (x, WeakStar x)
89			\| x = regexp; "?" -> Alt (x, Epsilon)
90			\| x = regexp; "??" -> Alt (Epsilon, x) ]
91			\| [ "("; x = regexp; ")" -> x
92			\| e = pat LEVEL "simple" -> Elem e
93			]
94			];
95
96			pat: [
97			[ x = pat; "where";
98			b = LIST1 [ a = UIDENT; "="; y = pat -> (a,y)] SEP "and"
99			-> mk loc (Recurs (x,b)) ]
100			\| RIGHTA [ x = pat; "->"; y = pat -> mk loc (Arrow (x,y)) ]
101	abate	6	\| "no_arrow" [ x = pat; "\|"; y = pat -> mk loc (Or (x,y)) ]
102	abate	4	\| "simple" [ x = pat; "&"; y = pat -> mk loc (And (x,y))
103			\| x = pat; "-"; y = pat -> mk loc (Diff (x,y)) ]
104			\|
105			[ "{"; r = record_spec; "}" -> r
106			\| UIDENT "Any" -> mk loc (Internal Types.any)
107			\| LIDENT "_" -> mk loc (Internal Types.any)
108			\| a = LIDENT -> mk loc (Capture a)
109			\| "("; a = LIDENT; ":="; c = const; ")" -> mk loc (Constant (a,c))
110			\| a = UIDENT -> mk loc (PatVar a)
111			\| i = INT ; "--"; j = INT ->
112			let i = int_of_string i and j = int_of_string j in
113			mk loc (Internal (Types.interval i j))
114			\| c = const -> mk loc (Internal (Types.constant c))
115			\| "("; l = LIST1 pat SEP ","; ")" -> multi_prod loc l
116			\| "["; r = [ r = regexp -> r \| -> Epsilon ];
117			q = [ ";"; q = pat -> q
118			\| -> mk noloc (Internal (Types.atom atom_nil)) ];
119			"]" -> mk loc (Regexp (r,q))
120			\| "<"; t = tag_spec; a = attrib_spec; ">"; c = pat ->
121			multi_prod loc [t;a;c]
122			]
123
124			];
125
126			record_spec:
127			[ [ r = LIST0 [ l = [LIDENT \| UIDENT];
128			o = ["=?" -> true \| "=" -> false];
129			x = pat ->
130			mk loc (Record (Types.label l,o,x))
131			] SEP ";" ->
132			match r with
133	abate	9	\| [] -> mk loc (Internal Types.Record.any)
134			\| h::t -> List.fold_left (fun t1 t2 -> mk loc (And (t1,t2))) h t
135	abate	4	] ];
136
137			const:
138			[
139			[ i = INT -> Types.Integer (int_of_string i)
140			\| x = STRING -> Types.String (Token.eval_string x)
141			\| "`"; a = [LIDENT \| UIDENT] -> Types.Atom (Types.mk_atom a) ]
142			];
143
144			tag_spec:
145			[
146			[ a = [LIDENT \| UIDENT] ->
147			mk loc (Internal (Types.atom (Types.mk_atom a))) ]
148			\| [ t = pat -> t ]
149			];
150
151			attrib_spec:
152			[ [ r = record_spec -> r \| "("; t = pat; ")" -> t ] ];
153
154			expr_record_spec:
155			[ [ r = LIST1
156			[ l = [LIDENT \| UIDENT]; "="; x = expr -> (Types.label l,x) ]
157			SEP ";" ->
158			mk loc (RecordLitt r)
159			] ];
160
161			expr_tag_spec:
162			[
163			[ a = [LIDENT \| UIDENT] ->
164			mk loc (Cst (Types.Atom (Types.mk_atom a))) ]
165			\| [ e = expr LEVEL "no_appl" -> e ]
166			];
167
168			expr_attrib_spec:
169			[ [ r = expr_record_spec -> r ]
170			\| [ e = expr LEVEL "no_appl" -> e
171			\| -> mk loc (RecordLitt [])
172			]
173			];
174			END
175
176			end
177
178			let pat_or_typ s = Grammar.Entry.parse P.pat (Stream.of_string s)
179
180			let expr s = Grammar.Entry.parse P.expr (Stream.of_string s)