]> matita.cs.unibo.it Git - helm.git/blob - helm/ocaml/cic_notation/cicNotationParser.ml
snapshot (first version in which some extensions work, e.g. infix +)
[helm.git] / helm / ocaml / cic_notation / cicNotationParser.ml
1 (* Copyright (C) 2005, HELM Team.
2  * 
3  * This file is part of HELM, an Hypertextual, Electronic
4  * Library of Mathematics, developed at the Computer Science
5  * Department, University of Bologna, Italy.
6  * 
7  * HELM is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU General Public License
9  * as published by the Free Software Foundation; either version 2
10  * of the License, or (at your option) any later version.
11  * 
12  * HELM is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with HELM; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20  * MA  02111-1307, USA.
21  * 
22  * For details, see the HELM World-Wide-Web page,
23  * http://helm.cs.unibo.it/
24  *)
25
26 open Printf
27
28 exception Parse_error of Token.flocation * string
29 exception Level_not_found of int
30
31 let grammar = Grammar.gcreate CicNotationLexer.notation_lexer
32
33 let level1_pattern = Grammar.Entry.create grammar "level1_pattern"
34 let level2_pattern = Grammar.Entry.create grammar "level2_pattern"
35 let level3_term = Grammar.Entry.create grammar "level3_term"
36 let l2_pattern = Grammar.Entry.create grammar "l2_pattern"
37 let notation = Grammar.Entry.create grammar "notation" (* level1 <-> level 2 *)
38 let interpretation =
39   Grammar.Entry.create grammar "interpretation" (* level2 <-> level 3 *)
40
41 let return_term loc term = ()
42
43 let loc_of_floc = function
44   | { Lexing.pos_cnum = loc_begin }, { Lexing.pos_cnum = loc_end } ->
45       (loc_begin, loc_end)
46
47 let fail floc msg =
48   let (x, y) = loc_of_floc floc in
49   failwith (sprintf "Error at characters %d - %d: %s" x y msg)
50
51 let int_of_string s =
52   try
53     Pervasives.int_of_string s
54   with Failure _ ->
55     failwith (sprintf "Lexer failure: string_of_int \"%s\" failed" s)
56
57 open CicNotationPt
58
59 let boxify = function
60   | [ a ] -> a
61   | l -> Layout (Box (H, l))
62
63 let fold_binder binder pt_names body =
64   let fold_cluster binder names ty body =
65     List.fold_right
66       (fun name body -> Binder (binder, (Cic.Name name, ty), body))
67       names body
68   in
69   List.fold_right
70     (fun (names, ty) body -> fold_cluster binder names ty body)
71     pt_names body
72
73 let return_term loc term = AttributedTerm (`Loc loc, term)
74
75 EXTEND
76   GLOBAL: level1_pattern level2_pattern level3_term
77           l2_pattern
78           notation interpretation;
79 (* {{{ Grammar for concrete syntax patterns, notation level 1 *)
80   level1_pattern: [ [ p = l1_pattern; EOI -> boxify p ] ];
81   l1_pattern: [ [ p = LIST0 l1_simple_pattern -> p ] ];
82   literal: [
83     [ s = SYMBOL -> `Symbol s
84     | k = KEYWORD -> `Keyword k
85     | n = NUMBER -> `Number n
86     ]
87   ];
88   sep:       [ [ SYMBOL "\\SEP";      sep = literal -> sep ] ];
89 (*   row_sep:   [ [ SYMBOL "\\ROWSEP";   sep = literal -> sep ] ];
90   field_sep: [ [ SYMBOL "\\FIELDSEP"; sep = literal -> sep ] ]; *)
91   l1_magic_pattern: [
92     [ SYMBOL "\\LIST0"; p = l1_simple_pattern; sep = OPT sep -> List0 (p, sep)
93     | SYMBOL "\\LIST1"; p = l1_simple_pattern; sep = OPT sep -> List1 (p, sep)
94     | SYMBOL "\\OPT";   p = l1_simple_pattern -> Opt p
95     ]
96   ];
97   l1_pattern_variable: [
98     [ id = IDENT -> TermVar id
99     | SYMBOL "\\TERM"; id = IDENT -> TermVar id
100     | SYMBOL "\\NUM"; id = IDENT -> NumVar id
101     | SYMBOL "\\IDENT"; id = IDENT -> IdentVar id
102     ]
103   ];
104   l1_simple_pattern:
105     [ "layout" LEFTA
106       [ p1 = SELF; SYMBOL "\\SUB"; p2 = SELF ->
107           return_term loc (Layout (Sub (p1, p2)))
108       | p1 = SELF; SYMBOL "\\SUP"; p2 = SELF ->
109           return_term loc (Layout (Sup (p1, p2)))
110       | p1 = SELF; SYMBOL "\\BELOW"; p2 = SELF ->
111           return_term loc (Layout (Below (p1, p2)))
112       | p1 = SELF; SYMBOL "\\ABOVE"; p2 = SELF ->
113           return_term loc (Layout (Above (p1, p2)))
114       | SYMBOL "["; p1 = l1_pattern; SYMBOL "\\OVER"; p2 = l1_pattern;
115         SYMBOL "]" ->
116           return_term loc (Layout (Over (boxify p1, boxify p2)))
117       | SYMBOL "["; p1 = l1_pattern; SYMBOL "\\ATOP"; p2 = l1_pattern;
118         SYMBOL "]" ->
119           return_term loc (Layout (Atop (boxify p1, boxify p2)))
120 (*       | SYMBOL "\\ARRAY"; p = SELF; csep = OPT field_sep; rsep = OPT row_sep ->
121           return_term loc (Array (p, csep, rsep)) *)
122       | SYMBOL "\\FRAC"; p1 = SELF; p2 = SELF ->
123           return_term loc (Layout (Frac (p1, p2)))
124       | SYMBOL "\\SQRT"; p = SELF -> return_term loc (Layout (Sqrt p))
125       | SYMBOL "\\ROOT"; index = l1_pattern; SYMBOL "\\OF"; arg = SELF ->
126           return_term loc (Layout (Root (arg, Layout (Box (H, index)))))
127       | SYMBOL "\\HBOX"; SYMBOL "["; p = l1_pattern; SYMBOL "]" ->
128           return_term loc (Layout (Box (H, p)))
129       | SYMBOL "\\VBOX"; SYMBOL "["; p = l1_pattern; SYMBOL "]" ->
130           return_term loc (Layout (Box (V, p)))
131       | SYMBOL "\\BREAK" -> return_term loc (Layout Break)
132       | SYMBOL "["; p = l1_pattern; SYMBOL "]" ->
133           return_term loc (boxify p)
134       | SYMBOL "["; p = l1_pattern; SYMBOL "\\AS"; id = IDENT; SYMBOL "]" ->
135           return_term loc (Variable (Ascription (Layout (Box (H, p)), id)))
136       ]
137     | "simple" NONA
138       [ m = l1_magic_pattern -> return_term loc (Magic m)
139       | v = l1_pattern_variable -> return_term loc (Variable v)
140       | l = literal -> return_term loc (Literal l)
141       ]
142     ];
143 (* }}} *)
144 (* {{{ Grammar for ast patterns, notation level 2 *)
145   level2_pattern: [ [ p = l2_pattern; EOI -> p ] ];
146   sort: [
147     [ SYMBOL "\\PROP" -> `Prop
148     | SYMBOL "\\SET" -> `Set
149     | SYMBOL "\\TYPE" -> `Type
150     ]
151   ];
152   explicit_subst: [
153     [ (* TODO explicit substitution *)
154     ]
155   ];
156   meta_subst: [
157     [ (* TODO meta substitution *)
158     ]
159   ];
160   possibly_typed_name: [
161     [ SYMBOL "("; id = IDENT; SYMBOL ":"; typ = l2_pattern; SYMBOL ")" ->
162         Cic.Name id, Some typ
163     | id = IDENT -> Cic.Name id, None
164     ]
165   ];
166   match_pattern: [
167     [ id = IDENT -> id, []
168     | SYMBOL "("; id = IDENT; vars = LIST1 possibly_typed_name; SYMBOL ")" ->
169         id, vars
170     ]
171   ];
172   binder: [
173     [ SYMBOL <:unicode<Pi>>     (* Π *) -> `Pi
174     | SYMBOL <:unicode<exists>> (* ∃ *) -> `Exists
175     | SYMBOL <:unicode<forall>> (* ∀ *) -> `Forall
176     | SYMBOL <:unicode<lambda>> (* λ *) -> `Lambda
177     ]
178   ];
179   bound_names: [
180     [ vars = LIST1 IDENT SEP SYMBOL ",";
181       ty = OPT [ SYMBOL ":"; p = l2_pattern -> p ] ->
182         [ vars, ty ]
183     | clusters = LIST1 [
184         SYMBOL "(";
185         vars = LIST1 IDENT SEP SYMBOL ",";
186         ty = OPT [ SYMBOL ":"; p = l2_pattern -> p ];
187         SYMBOL ")" ->
188           vars, ty
189       ] ->
190         clusters
191     ]
192   ];
193   induction_kind: [
194     [ IDENT "rec" -> `Inductive
195     | IDENT "corec" -> `CoInductive
196     ]
197   ];
198   let_defs: [
199     [ defs = LIST1 [
200         name = IDENT; args = bound_names;
201         index_name = OPT [ IDENT "on"; id = IDENT -> id ];
202         ty = OPT [ SYMBOL ":" ; p = l2_pattern -> p ];
203         SYMBOL <:unicode<def>> (* ≝ *); body = l2_pattern ->
204           let body = fold_binder `Lambda args body in
205           let ty = 
206             match ty with 
207             | None -> None
208             | Some ty -> Some (fold_binder `Pi args ty)
209           in
210           let rec position_of name p = function 
211             | [] -> None, p
212             | n :: _ when n = name -> Some p, p
213             | _ :: tl -> position_of name (p + 1) tl
214           in
215           let rec find_arg name n = function 
216             | [] -> fail loc (sprintf "Argument %s not found" name)
217             | (l,_) :: tl -> 
218                 (match position_of name 0 l with
219                 | None, len -> find_arg name (n + len) tl
220                 | Some where, len -> n + where)
221           in
222           let index = 
223             match index_name with 
224             | None -> 0 
225             | Some name -> find_arg name 0 args
226           in
227           (Cic.Name name, ty), body, index
228       ] SEP IDENT "and" ->
229         defs
230     ]
231   ];
232   l2_pattern_variable: [
233     [ SYMBOL "\\NUM"; id = IDENT -> NumVar id
234     | SYMBOL "\\IDENT"; id = IDENT -> IdentVar id
235     | SYMBOL "\\FRESH"; id = IDENT -> FreshVar id
236     ]
237   ];
238   l2_magic_pattern: [
239     [ SYMBOL "\\FOLD";
240       kind = [ IDENT "left" -> `Left | IDENT "right" -> `Right ];
241       base = l2_pattern;
242       SYMBOL "\\LAMBDA"; id = IDENT; recursive = l2_pattern ->
243         Fold (kind, base, [id], recursive)
244     | SYMBOL "\\DEFAULT"; some = l2_pattern; none = l2_pattern ->
245         Default (some, none)
246     ]
247   ];
248   l2_pattern:
249     [ "0" [ ]
250     | "10" NONA (* let in *)
251       [ IDENT "let"; var = possibly_typed_name; SYMBOL <:unicode<def>> (* ≝ *);
252         p1 = l2_pattern; "in"; p2 = l2_pattern ->
253           return_term loc (LetIn (var, p1, p2))
254       | IDENT "let"; k = induction_kind; defs = let_defs; IDENT "in";
255         body = l2_pattern ->
256           return_term loc (LetRec (k, defs, body))
257       ]
258     | "20" RIGHTA (* binder *)
259       [ b = binder; names = bound_names; SYMBOL "."; body = l2_pattern ->
260           return_term loc (fold_binder b names body)
261       ]
262     | "30" [ ]
263     | "40" [ ]
264     | "50" [ ]
265     | "60" [ ]
266     | "70" LEFTA (* apply *)
267       [ p1 = l2_pattern; p2 = l2_pattern ->
268           let rec aux = function
269             | Appl (hd :: tl)
270             | AttributedTerm (_, Appl (hd :: tl)) ->
271                 aux hd @ tl
272             | term -> [term]
273           in
274           return_term loc (Appl (aux p1 @ [p2]))
275       ]
276     | "80" [ ]
277     | "90" NONA (* simple *)
278       [ id = IDENT -> return_term loc (Ident (id, None))
279       | id = IDENT; s = explicit_subst -> return_term loc (Ident (id, Some s))
280       | u = URI -> return_term loc (Uri (u, None))
281       | n = NUMBER -> prerr_endline "number"; return_term loc (Num (n, 0))
282       | IMPLICIT -> return_term loc (Implicit)
283       | m = META -> return_term loc (Meta (int_of_string m, []))
284       | m = META; s = meta_subst -> return_term loc (Meta (int_of_string m, s))
285       | s = sort -> return_term loc (Sort s)
286       | outtyp = OPT [ SYMBOL "["; ty = l2_pattern; SYMBOL "]" -> ty ];
287         IDENT "match"; t = l2_pattern;
288         indty_ident = OPT [ SYMBOL ":"; id = IDENT -> id ];
289         IDENT "with"; SYMBOL "[";
290         patterns = LIST0 [
291           lhs = match_pattern; SYMBOL <:unicode<Rightarrow>> (* ⇒ *);
292           rhs = l2_pattern ->
293             lhs, rhs
294         ] SEP SYMBOL "|";
295         SYMBOL "]" ->
296           return_term loc (Case (t, indty_ident, outtyp, patterns))
297       | SYMBOL "("; p1 = l2_pattern; SYMBOL ":"; p2 = l2_pattern; SYMBOL ")" ->
298           return_term loc (Appl [ Symbol ("cast", 0); p1; p2 ])
299       | SYMBOL "("; p = l2_pattern; SYMBOL ")" -> p
300       | v = l2_pattern_variable -> return_term loc (Variable v)
301       | m = l2_magic_pattern -> return_term loc (Magic m)
302       ]
303     | "100" [ ]
304     ];
305 (* }}} *)
306 (* {{{ Grammar for interpretation, notation level 3 *)
307   argument: [
308     [ id = IDENT -> IdentArg id
309     | SYMBOL <:unicode<eta>> (* η *); SYMBOL "."; a = SELF -> EtaArg (None, a)
310     | SYMBOL <:unicode<eta>> (* η *); id = IDENT; SYMBOL "."; a = SELF ->
311         EtaArg (Some id, a)
312     ]
313   ];
314   level3_term: [
315     [ u = URI -> UriPattern u
316     | a = argument -> ArgPattern a
317     | SYMBOL "("; terms = LIST1 SELF; SYMBOL ")" ->
318         (match terms with
319         | [] -> assert false
320         | [term] -> term
321         | terms -> ApplPattern terms)
322     ]
323   ];
324 (* }}} *)
325 (* {{{ Notation glues *)
326   associativity: [
327     [ IDENT "left";  IDENT "associative" -> `Left
328     | IDENT "right"; IDENT "associative" -> `Right
329     ]
330   ];
331   precedence: [ [ IDENT "at"; IDENT "precedence"; n = NUMBER -> n ] ];
332   notation: [
333     [ IDENT "notation"; p1 = level1_pattern; IDENT "for"; p2 = level2_pattern;
334       assoc = OPT associativity; prec = OPT precedence ->
335         ()
336     ]
337   ];
338   interpretation: [
339     [ IDENT "interpretation"; s = SYMBOL; args = LIST1 argument; IDENT "as";
340       t = level3_term ->
341         ()
342     ]
343   ];
344 (* }}} *)
345 END
346
347 let exc_located_wrapper f =
348   try
349     f ()
350   with
351   | Stdpp.Exc_located (floc, Stream.Error msg) ->
352       raise (Parse_error (floc, msg))
353   | Stdpp.Exc_located (floc, exn) ->
354       raise (Parse_error (floc, (Printexc.to_string exn)))
355
356 let parse_syntax_pattern stream =
357   exc_located_wrapper (fun () -> Grammar.Entry.parse level1_pattern stream)
358
359 let parse_ast_pattern stream =
360   exc_located_wrapper (fun () -> Grammar.Entry.parse level2_pattern stream)
361
362 let parse_interpretation stream =
363   exc_located_wrapper (fun () -> Grammar.Entry.parse level3_term stream)
364
365 (** {2 Grammar extension} *)
366
367 type associativity_kind = [ `Left | `Right | `None ]
368
369 let symbol s = Gramext.Stoken ("SYMBOL", s)
370 let ident s = Gramext.Stoken ("IDENT", s)
371 let number s = Gramext.Stoken ("NUMBER", s)
372 let term = Gramext.Sself
373
374 type env_type = (string * (value_type * value)) list
375
376 let rec pp_value =
377   function
378   | TermValue _ -> "@TERM@"
379   | StringValue s -> sprintf "\"%s\"" s
380   | NumValue n -> n
381   | OptValue (Some v) -> "Some " ^ pp_value v
382   | OptValue None -> "None"
383   | ListValue l -> sprintf "[%s]" (String.concat "; " (List.map pp_value l))
384
385 let rec pp_value_type =
386   function
387   | TermType -> "Term"
388   | StringType -> "String"
389   | NumType -> "Number"
390   | OptType t -> "Maybe " ^ pp_value_type t
391   | ListType l -> "List " ^ pp_value_type l
392
393 let pp_env env =
394   String.concat "; "
395     (List.map
396       (fun (name, (ty, value)) ->
397         sprintf "%s : %s = %s" name (pp_value_type ty) (pp_value value))
398       env)
399
400 let make_action action bindings =
401   let rec aux (vl : env_type) =
402     function
403       [] ->
404         prerr_endline "aux: make_action";
405         Gramext.action (fun (loc: location) -> action vl loc)
406     | None :: tl ->
407         prerr_endline "aux: none";
408         Gramext.action (fun _ -> aux vl tl)
409     (* LUCA: DEFCON 3 BEGIN *)
410     | Some (name, TermType) :: tl ->
411         prerr_endline "aux: term";
412         Gramext.action
413           (fun (v:term) -> aux ((name, (TermType, (TermValue v)))::vl) tl)
414     | Some (name, StringType) :: tl ->
415         prerr_endline "aux: string";
416         Gramext.action
417           (fun (v:string) ->
418             aux ((name, (StringType, (StringValue v))) :: vl) tl)
419     | Some (name, NumType) :: tl ->
420         prerr_endline "aux: num";
421         Gramext.action
422           (fun (v:string) -> aux ((name, (NumType, (NumValue v))) :: vl) tl)
423     | Some (name, OptType t) :: tl ->
424         prerr_endline "aux: opt";
425         Gramext.action
426           (fun (v:'a option) ->
427             aux ((name, (OptType t, (OptValue v))) :: vl) tl)
428     | Some (name, ListType t) :: tl ->
429         prerr_endline "aux: list";
430         Gramext.action
431           (fun (v:'a list) ->
432             aux ((name, (ListType t, (ListValue v))) :: vl) tl)
433     (* LUCA: DEFCON 3 END *)
434   in
435     aux [] (List.rev bindings)
436
437 let flatten_opt =
438   let rec aux acc =
439     function
440       [] -> List.rev acc
441     | None::tl -> aux acc tl
442     | Some hd::tl -> aux (hd::acc) tl
443   in
444   aux []
445
446   (* given a level 1 pattern computes the new RHS of "term" grammar entry *)
447 let extract_term_production pattern =
448   let rec aux = function
449     | Literal l -> aux_literal l
450     | Layout l -> aux_layout l
451     | Magic m -> aux_magic m
452     | Variable v -> aux_variable v
453     | _ -> assert false
454   and aux_literal = function
455     | `Symbol s -> [None, symbol s]
456     | `Keyword s -> [None, ident s]
457     | `Number s -> [None, number s]
458   and aux_layout = function
459     | Sub (p1, p2) -> aux p1 @ [None, symbol "\\SUB"] @ aux p2
460     | Sup (p1, p2) -> aux p1 @ [None, symbol "\\SUP"] @ aux p2
461     | Below (p1, p2) -> aux p1 @ [None, symbol "\\BELOW"] @ aux p2
462     | Above (p1, p2) -> aux p1 @ [None, symbol "\\ABOVE"] @ aux p2
463     | Frac (p1, p2) -> aux p1 @ [None, symbol "\\FRAC"] @ aux p2
464     | Atop (p1, p2) -> aux p1 @ [None, symbol "\\ATOP"] @ aux p2
465     | Over (p1, p2) -> aux p1 @ [None, symbol "\\OVER"] @ aux p2
466     | Root (p1, p2) ->
467         [None, symbol "\\ROOT"] @ aux p2 @ [None, symbol "\\OF"] @ aux p1
468     | Sqrt p -> [None, symbol "\\SQRT"] @ aux p
469     | Break -> []
470     | Box (_, pl) -> List.flatten (List.map aux pl)
471   and aux_magic = function
472     | Opt p ->
473         let p_bindings, p_atoms = List.split (aux p) in
474         let p_names = flatten_opt p_bindings in
475         [ None,
476           Gramext.srules
477             [ [ Gramext.Sopt
478                   (Gramext.srules
479                     [ p_atoms,
480                       (make_action
481                         (fun (env : env_type) (loc : location) ->
482                           prerr_endline "inner opt action";
483                           env)
484                         p_bindings)])],
485               Gramext.action
486                 (fun (env_opt : env_type option) (loc : location) ->
487                   match env_opt with
488                     Some env ->
489                       prerr_endline "opt action (Some _)";
490                       List.map
491                         (fun (name, (typ, v)) ->
492                           (name, (OptType typ, OptValue (Some v))))
493                         env
494                   | None -> 
495                       prerr_endline "opt action (None)";
496                       List.map
497                         (fun (name, typ) ->
498                           (name, (OptType typ, OptValue None)))
499                         p_names) ]]
500     | _ -> assert false
501   and aux_variable = function
502     | NumVar s -> [Some (s, NumType), number ""]
503     | TermVar s -> [Some (s, TermType), term]
504     | IdentVar s -> [Some (s, StringType), ident ""]
505     | Ascription (p, s) -> assert false (* TODO *)
506     | FreshVar _ -> assert false
507   in
508   aux pattern
509
510 let level_of_int precedence =
511   (* TODO "mod" test to be removed as soon as we add all 100 levels *)
512   if precedence mod 10 <> 0 || precedence < 0 || precedence > 100 then
513     raise (Level_not_found precedence);
514   string_of_int precedence
515
516 type rule_id = Token.t Gramext.g_symbol list
517
518 let extend level1_pattern ?(precedence = 0) ?associativity action =
519   let p_bindings, p_atoms =
520     List.split (extract_term_production level1_pattern)
521   in
522   let level = level_of_int precedence in
523   let p_names = flatten_opt p_bindings in
524   let entry = Grammar.Entry.obj (l2_pattern: 'a Grammar.Entry.e) in
525   let _ =
526     prerr_endline (string_of_int (List.length p_bindings));
527     Grammar.extend
528       [ entry, Some (Gramext.Level level),
529         [ Some level,  (* TODO should we put None here? *)
530           associativity,
531           [ p_atoms, 
532             (make_action
533               (fun (env: env_type) (loc: location) -> (action env loc))
534               p_bindings) ]]]
535   in
536   p_atoms
537
538 let delete atoms = Grammar.delete_rule l2_pattern atoms
539
540 let print_l2_pattern () =
541   Grammar.print_entry Format.std_formatter (Grammar.Entry.obj l2_pattern);
542   Format.pp_print_flush Format.std_formatter ();
543   flush stdout
544
545 (* vim:set encoding=utf8 foldmethod=marker: *)