|
1 (* $Id$ *) |
|
2 |
|
3 signature LAZY_SCAN = |
|
4 sig |
|
5 |
|
6 exception SyntaxError |
|
7 |
|
8 type ('a,'b) scanner = 'a LazySeq.seq -> 'b * 'a LazySeq.seq |
|
9 |
|
10 val :-- : ('a,'b) scanner * ('b -> ('a,'c) scanner) |
|
11 -> ('a,'b*'c) scanner |
|
12 val -- : ('a,'b) scanner * ('a,'c) scanner -> ('a,'b*'c) scanner |
|
13 val >> : ('a,'b) scanner * ('b -> 'c) -> ('a,'c) scanner |
|
14 val --| : ('a,'b) scanner * ('a,'c) scanner -> ('a,'b) scanner |
|
15 val |-- : ('a,'b) scanner * ('a,'c) scanner -> ('a,'c) scanner |
|
16 val ^^ : ('a,string) scanner * ('a,string) scanner |
|
17 -> ('a,string) scanner |
|
18 val || : ('a,'b) scanner * ('a,'b) scanner -> ('a,'b) scanner |
|
19 val one : ('a -> bool) -> ('a,'a) scanner |
|
20 val succeed : 'b -> ('a,'b) scanner |
|
21 val any : ('a -> bool) -> ('a,'a list) scanner |
|
22 val any1 : ('a -> bool) -> ('a,'a list) scanner |
|
23 val optional : ('a,'b) scanner -> 'b -> ('a,'b) scanner |
|
24 val option : ('a,'b) scanner -> ('a,'b option) scanner |
|
25 val repeat : ('a,'b) scanner -> ('a,'b list) scanner |
|
26 val repeat1 : ('a,'b) scanner -> ('a,'b list) scanner |
|
27 val ahead : ('a,'b) scanner -> ('a,'b) scanner |
|
28 val unless : ('a LazySeq.seq -> bool) -> ('a,'b) scanner -> ('a,'b) scanner |
|
29 val $$ : ''a -> (''a,''a) scanner |
|
30 val !! : ('a LazySeq.seq -> string) -> ('a,'b) scanner -> ('a,'b) scanner |
|
31 val scan_full: ('a,'b) scanner -> 'a LazySeq.seq -> 'b LazySeq.seq |
|
32 |
|
33 end |
|
34 |
|
35 structure LazyScan :> LAZY_SCAN = |
|
36 struct |
|
37 |
|
38 infix 7 |-- --| |
|
39 infix 5 :-- -- ^^ |
|
40 infix 3 >> |
|
41 infix 0 || |
|
42 |
|
43 exception SyntaxError |
|
44 exception Fail of string |
|
45 |
|
46 type ('a,'b) scanner = 'a LazySeq.seq -> 'b * 'a LazySeq.seq |
|
47 |
|
48 fun (sc1 :-- sc2) toks = |
|
49 let |
|
50 val (x,toks2) = sc1 toks |
|
51 val (y,toks3) = sc2 x toks2 |
|
52 in |
|
53 ((x,y),toks3) |
|
54 end |
|
55 |
|
56 fun (sc1 -- sc2) toks = |
|
57 let |
|
58 val (x,toks2) = sc1 toks |
|
59 val (y,toks3) = sc2 toks2 |
|
60 in |
|
61 ((x,y),toks3) |
|
62 end |
|
63 |
|
64 fun (sc >> f) toks = |
|
65 let |
|
66 val (x,toks2) = sc toks |
|
67 in |
|
68 (f x,toks2) |
|
69 end |
|
70 |
|
71 fun (sc1 --| sc2) toks = |
|
72 let |
|
73 val (x,toks2) = sc1 toks |
|
74 val (_,toks3) = sc2 toks2 |
|
75 in |
|
76 (x,toks3) |
|
77 end |
|
78 |
|
79 fun (sc1 |-- sc2) toks = |
|
80 let |
|
81 val (_,toks2) = sc1 toks |
|
82 in |
|
83 sc2 toks2 |
|
84 end |
|
85 |
|
86 fun (sc1 ^^ sc2) toks = |
|
87 let |
|
88 val (x,toks2) = sc1 toks |
|
89 val (y,toks3) = sc2 toks2 |
|
90 in |
|
91 (x^y,toks3) |
|
92 end |
|
93 |
|
94 fun (sc1 || sc2) toks = |
|
95 (sc1 toks) |
|
96 handle SyntaxError => sc2 toks |
|
97 |
|
98 fun one p toks = |
|
99 case LazySeq.getItem toks of |
|
100 None => raise SyntaxError |
|
101 | Some(t,toks) => if p t |
|
102 then (t,toks) |
|
103 else raise SyntaxError |
|
104 |
|
105 fun succeed e toks = (e,toks) |
|
106 |
|
107 fun any p toks = |
|
108 case LazySeq.getItem toks of |
|
109 None => ([],toks) |
|
110 | Some(x,toks2) => if p x |
|
111 then |
|
112 let |
|
113 val (xs,toks3) = any p toks2 |
|
114 in |
|
115 (x::xs,toks3) |
|
116 end |
|
117 else ([],toks) |
|
118 |
|
119 fun any1 p toks = |
|
120 let |
|
121 val (x,toks2) = one p toks |
|
122 val (xs,toks3) = any p toks2 |
|
123 in |
|
124 (x::xs,toks3) |
|
125 end |
|
126 |
|
127 fun optional sc def = sc || succeed def |
|
128 fun option sc = (sc >> Some) || succeed None |
|
129 |
|
130 (* |
|
131 fun repeat sc = |
|
132 let |
|
133 fun R toks = |
|
134 let |
|
135 val (x,toks2) = sc toks |
|
136 val (xs,toks3) = R toks2 |
|
137 in |
|
138 (x::xs,toks3) |
|
139 end |
|
140 handle SyntaxError => ([],toks) |
|
141 in |
|
142 R |
|
143 end |
|
144 *) |
|
145 |
|
146 (* A tail-recursive version of repeat. It is (ever so) slightly slower |
|
147 * than the above, non-tail-recursive version (due to the garbage generation |
|
148 * associated with the reversal of the list). However, this version will be |
|
149 * able to process input where the former version must give up (due to stack |
|
150 * overflow). The slowdown seems to be around the one percent mark. |
|
151 *) |
|
152 fun repeat sc = |
|
153 let |
|
154 fun R xs toks = |
|
155 case Some (sc toks) handle SyntaxError => None of |
|
156 Some (x,toks2) => R (x::xs) toks2 |
|
157 | None => (List.rev xs,toks) |
|
158 in |
|
159 R [] |
|
160 end |
|
161 |
|
162 fun repeat1 sc toks = |
|
163 let |
|
164 val (x,toks2) = sc toks |
|
165 val (xs,toks3) = repeat sc toks2 |
|
166 in |
|
167 (x::xs,toks3) |
|
168 end |
|
169 |
|
170 fun ahead (sc:'a->'b*'a) toks = (#1 (sc toks),toks) |
|
171 |
|
172 fun unless test sc toks = |
|
173 let |
|
174 val test_failed = (test toks;false) handle SyntaxError => true |
|
175 in |
|
176 if test_failed |
|
177 then sc toks |
|
178 else raise SyntaxError |
|
179 end |
|
180 |
|
181 fun $$ arg = one (fn x => x = arg) |
|
182 |
|
183 fun !! f sc toks = (sc toks |
|
184 handle SyntaxError => raise Fail (f toks)) |
|
185 |
|
186 fun scan_full sc toks = |
|
187 let |
|
188 fun F toks = |
|
189 if LazySeq.null toks |
|
190 then None |
|
191 else |
|
192 let |
|
193 val (x,toks') = sc toks |
|
194 in |
|
195 Some(x,LazySeq.make (fn () => F toks')) |
|
196 end |
|
197 in |
|
198 LazySeq.make (fn () => F toks) |
|
199 end |
|
200 |
|
201 end |