viewcvs.cgi/parser/parser.ml

open Location
open Ast

  let gram    = Grammar.create (Plexer.make ())
  let prog    = Grammar.Entry.create gram "prog"
  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: prog expr pat regexp const;

  prog: [
    [ l = LIST0 [ e = expr -> mk loc (EvalStatement e) ] SEP ";;";
       "EOF"  -> l ]
  ];

  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

let pat = Grammar.Entry.parse pat
let expr = Grammar.Entry.parse expr
let prog = Grammar.Entry.parse prog

module From_string = struct
  let pat s = pat (Stream.of_string s)
  let expr s = expr (Stream.of_string s)
end

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