Skip to content
This repository
Newer
Older
100644 158 lines (117 sloc) 4.589 kb
8634b74a »
2010-09-22 initial import into fresh git repo.
1 (*s: parser_combinators.mli *)
2 (*****************************************************************************)
3 (* src: Jon Harrop.
4 *
5 * "Certain applications are extremely well suited to functional
6 * programming and parsing is one of them. Specifically, the ability to
7 * write functional combinators that allow parsers for everything from
8 * integers up to symbolic expressions to be composed is more general
9 * and provides more opportunity for code reuse than the use of
10 * conventional parser generators such as ocamllex and ocamlyacc. This
11 * article explains how parser combinators may be designed and
12 * implemented in OCaml, using the standard example of a calculator."
13 *
14 * pad: a few bugfixes. I also put more restrictive and descriptive types.
15 *
16 *)
17
18 (*****************************************************************************)
19
20 (* A generic parser takes a list of stuff (either char for lexical
21 * parser or tokens for grammar parser) and return something and the
22 * remaing list of stuff. *)
23 type ('a, 'b) genp = 'a list -> 'b * 'a list
24 val val_of_parser : 'b * 'a list -> 'b
25
26 (* lexer = parser of char list *)
27 (* type 'a lexer = (char, 'a) genp *)
28
29 (* grammer = parser ot tokens *)
30 (* type 'a pparser = (token, 'a) genp *)
31
32
33 val ( ||| ) : ('a, 'b) genp -> ('a, 'b) genp -> ('a, 'b) genp
34 (* ('a -> 'b) -> ('a -> 'b) -> 'a -> 'b *)
35 val ( +++ ) : ('a, 'b) genp -> ('a, 'c) genp -> ('a, 'b * 'c) genp
36 (* ('a -> 'b * 'c) -> ('c -> 'd * 'e) -> 'a -> ('b * 'd) * 'e *)
37
38 val many : ('a, 'b) genp -> ('a, 'b list) genp
39 (* ('a -> 'b * 'a) -> 'a -> 'b list * 'a *)
40
41 val ( >| ) : ('a, 'b) genp -> ('b -> 'c) -> ('a, 'c) genp
42 (* ('a -> 'b * 'c) -> ('b -> 'd) -> 'a -> 'd * 'c *)
43
44 (* was called 'some', but confusing *)
45 val pred : ('a -> bool) -> ('a, 'a) genp
46 (* ('a -> bool) -> 'a list -> 'a * 'a list *)
47
48 val a : 'a -> ('a, 'a) genp
49 (* 'a -> 'a list -> 'a * 'a list *)
50
51 val several : ('a -> bool) -> ('a, 'a list) genp
52 (* ('a -> bool) -> 'a list -> 'a list * 'a list *)
53
54
55 module Abstr : sig
56 type t
57 val x : t
58 end
59
60 val fin : ('a, Abstr.t) genp
61 (* 'a list -> Abstr.t * 'b list *)
62
63
64 val digit : char -> bool
65 val alpha : char -> bool
66 val symbol : char -> bool
67 val alphanum : char -> bool
68 val space : char -> bool
69
70 val alphanum_underscore : char -> bool
71 val alphanum_minus : char -> bool
72 val alphanum_under_minus : char -> bool
73
74 val collect : char * char list -> string
75 val list_of_string : string -> char list
76
77
78 (*****************************************************************************)
79 type token =
80 | IDENT of string
81 | KWD of string
82 | INT of string
83 | SYM of string
84 | STR of string
85
86 val string_of_token : token -> string
87
88 type lexer = (char, token) genp
89
90 val rawident : lexer
91 (* char list -> token * char list *)
92 val rawnumber : lexer
93 (* char list -> token * char list *)
94
95 val rawsymbol : lexer
96
97 (* not space, not digit *)
98 val rawkeyword : lexer
99 (* char list -> token * char list *)
100
101 val rawstring : lexer
102
103 val lex_gen : lexer -> string -> token list
104
105 (*****************************************************************************)
106 val token : lexer
107 (* char list -> token * char list *)
108 val tokens : (char, token list) genp
109 (* char list -> token list * char list *)
110
111 val alltokens : (char, token list) genp
112 (* char list -> token list * 'a list *)
113
114 val lex : string -> token list
115
116
117 (*****************************************************************************)
118 (* cant use parser as it's a reseverd word *)
119 type 'a pparser = (token, 'a) genp
120
121 val ident : string pparser
122 (* token list -> string * token list *)
123 val int : string pparser
124 (* token list -> string * token list *)
125 val string : string pparser
126
127 type expr =
128 | Int of int
129 | Var of string
130 | Add of expr * expr
131 | Mul of expr * expr
132
133 val atom : expr pparser
134 (* token list -> expr * token list *)
135 val factor : expr pparser
136 (* token list -> expr * token list *)
137 val term : expr pparser
138 (* token list -> expr * token list *)
139 val expr : expr pparser
140 (* token list -> expr * 'a list *)
141
142 val parse : 'a pparser -> string -> 'a
143 (* (token list -> 'a * 'b) -> string -> 'a *)
144
145
146 (*****************************************************************************)
147
148 module Infix : sig
149 val ( ||| ) : ('a, 'b) genp -> ('a, 'b) genp -> ('a, 'b) genp
150 (* ('a -> 'b) -> ('a -> 'b) -> 'a -> 'b *)
151 val ( +++ ) : ('a, 'b) genp -> ('a, 'c) genp -> ('a, 'b * 'c) genp
152 (* ('a -> 'b * 'c) -> ('c -> 'd * 'e) -> 'a -> ('b * 'd) * 'e *)
153 val ( >| ) : ('a, 'b) genp -> ('b -> 'c) -> ('a, 'c) genp
154 (* ('a -> 'b * 'c) -> ('b -> 'd) -> 'a -> 'd * 'c *)
155 end
156
157 (*e: parser_combinators.mli *)
Something went wrong with that request. Please try again.