wenzelm@18
|
1 |
(* Title: Pure/Syntax/parser.ML
|
wenzelm@46
|
2 |
ID: $Id$
|
wenzelm@2186
|
3 |
Author: Carsten Clasohm, Sonia Mahjoub, and Markus Wenzel, TU Muenchen
|
wenzelm@18
|
4 |
|
wenzelm@15979
|
5 |
General context-free parser for the inner syntax of terms, types, etc.
|
wenzelm@18
|
6 |
*)
|
wenzelm@18
|
7 |
|
wenzelm@18
|
8 |
signature PARSER =
|
wenzelm@15752
|
9 |
sig
|
paulson@1507
|
10 |
type gram
|
paulson@1507
|
11 |
val empty_gram: gram
|
paulson@1507
|
12 |
val extend_gram: gram -> SynExt.xprod list -> gram
|
wenzelm@15752
|
13 |
val make_gram: SynExt.xprod list -> gram
|
paulson@1507
|
14 |
val merge_grams: gram -> gram -> gram
|
paulson@1507
|
15 |
val pretty_gram: gram -> Pretty.T list
|
paulson@1507
|
16 |
datatype parsetree =
|
paulson@1507
|
17 |
Node of string * parsetree list |
|
paulson@1507
|
18 |
Tip of Lexicon.token
|
paulson@1507
|
19 |
val parse: gram -> string -> Lexicon.token list -> parsetree list
|
paulson@1507
|
20 |
val branching_level: int ref
|
wenzelm@15752
|
21 |
end;
|
wenzelm@18
|
22 |
|
wenzelm@15752
|
23 |
structure Parser: PARSER =
|
wenzelm@15752
|
24 |
struct
|
paulson@1507
|
25 |
|
wenzelm@237
|
26 |
open Lexicon SynExt;
|
wenzelm@18
|
27 |
|
wenzelm@15752
|
28 |
|
wenzelm@18
|
29 |
(** datatype gram **)
|
wenzelm@18
|
30 |
|
clasohm@1175
|
31 |
type nt_tag = int; (*production for the NTs are stored in an array
|
clasohm@1175
|
32 |
so we can identify NTs by their index*)
|
wenzelm@18
|
33 |
|
clasohm@1147
|
34 |
datatype symb = Terminal of token
|
clasohm@1175
|
35 |
| Nonterminal of nt_tag * int; (*(tag, precedence)*)
|
wenzelm@18
|
36 |
|
clasohm@1175
|
37 |
type nt_gram = ((nt_tag list * token list) *
|
clasohm@1147
|
38 |
(token option * (symb list * string * int) list) list);
|
clasohm@1147
|
39 |
(*(([dependent_nts], [start_tokens]),
|
clasohm@1147
|
40 |
[(start_token, [(rhs, name, prio)])])*)
|
clasohm@1175
|
41 |
(*depent_nts is a list of all NTs whose lookahead
|
clasohm@1175
|
42 |
depends on this NT's lookahead*)
|
clasohm@330
|
43 |
|
clasohm@1147
|
44 |
datatype gram =
|
clasohm@1147
|
45 |
Gram of {nt_count: int, prod_count: int,
|
clasohm@1147
|
46 |
tags: nt_tag Symtab.table,
|
clasohm@1147
|
47 |
chains: (nt_tag * nt_tag list) list, (*[(to, [from])]*)
|
clasohm@1147
|
48 |
lambdas: nt_tag list,
|
clasohm@1175
|
49 |
prods: nt_gram Array.array};
|
clasohm@1175
|
50 |
(*"tags" is used to map NT names (i.e. strings) to tags;
|
clasohm@1175
|
51 |
chain productions are not stored as normal productions
|
clasohm@1175
|
52 |
but instead as an entry in "chains";
|
clasohm@1175
|
53 |
lambda productions are stored as normal productions
|
clasohm@1175
|
54 |
and also as an entry in "lambdas"*)
|
clasohm@330
|
55 |
|
clasohm@1175
|
56 |
val UnknownStart = EndToken; (*productions for which no starting token is
|
clasohm@1175
|
57 |
known yet are associated with this token*)
|
clasohm@330
|
58 |
|
wenzelm@15752
|
59 |
(* get all NTs that are connected with a list of NTs
|
clasohm@1175
|
60 |
(used for expanding chain list)*)
|
clasohm@1147
|
61 |
fun connected_with _ [] relatives = relatives
|
clasohm@1147
|
62 |
| connected_with chains (root :: roots) relatives =
|
wenzelm@19305
|
63 |
let val branches = subtract (op =) relatives (these (AList.lookup (op =) chains root));
|
clasohm@1147
|
64 |
in connected_with chains (branches @ roots) (branches @ relatives) end;
|
clasohm@330
|
65 |
|
clasohm@1147
|
66 |
(* convert productions to grammar;
|
clasohm@1175
|
67 |
N.B. that the chains parameter has the form [(from, [to])];
|
skalberg@15531
|
68 |
prod_count is of type "int option" and is only updated if it is <> NONE*)
|
clasohm@1147
|
69 |
fun add_prods _ chains lambdas prod_count [] = (chains, lambdas, prod_count)
|
clasohm@1147
|
70 |
| add_prods prods chains lambdas prod_count
|
clasohm@1147
|
71 |
((lhs, new_prod as (rhs, name, pri)) :: ps) =
|
clasohm@1147
|
72 |
let
|
wenzelm@15752
|
73 |
val chain_from = case (pri, rhs) of (~1, [Nonterminal (id, ~1)]) => SOME id | _ => NONE;
|
wenzelm@15752
|
74 |
|
wenzelm@15752
|
75 |
(*store chain if it does not already exist*)
|
wenzelm@15752
|
76 |
val (new_chain, chains') = case chain_from of NONE => (NONE, chains) | SOME from =>
|
haftmann@17192
|
77 |
let val old_tos = these (AList.lookup (op =) chains from) in
|
wenzelm@20664
|
78 |
if member (op =) old_tos lhs then (NONE, chains)
|
haftmann@17192
|
79 |
else (SOME from, AList.update (op =) (from, lhs ins old_tos) chains)
|
clasohm@1175
|
80 |
end;
|
clasohm@330
|
81 |
|
clasohm@1175
|
82 |
(*propagate new chain in lookahead and lambda lists;
|
clasohm@1175
|
83 |
added_starts is used later to associate existing
|
clasohm@1175
|
84 |
productions with new starting tokens*)
|
clasohm@1147
|
85 |
val (added_starts, lambdas') =
|
clasohm@1147
|
86 |
if is_none new_chain then ([], lambdas) else
|
clasohm@1175
|
87 |
let (*lookahead of chain's source*)
|
wenzelm@15979
|
88 |
val ((from_nts, from_tks), _) = Array.sub (prods, the new_chain);
|
clasohm@330
|
89 |
|
clasohm@1175
|
90 |
(*copy from's lookahead to chain's destinations*)
|
clasohm@1147
|
91 |
fun copy_lookahead [] added = added
|
clasohm@1147
|
92 |
| copy_lookahead (to :: tos) added =
|
clasohm@1175
|
93 |
let
|
clasohm@1175
|
94 |
val ((to_nts, to_tks), ps) = Array.sub (prods, to);
|
clasohm@1147
|
95 |
|
wenzelm@19305
|
96 |
val new_tks = subtract (op =) to_tks from_tks; (*added lookahead tokens*)
|
clasohm@1175
|
97 |
in Array.update (prods, to, ((to_nts, to_tks @ new_tks), ps));
|
clasohm@1147
|
98 |
copy_lookahead tos (if null new_tks then added
|
clasohm@1147
|
99 |
else (to, new_tks) :: added)
|
clasohm@1147
|
100 |
end;
|
clasohm@1147
|
101 |
|
clasohm@1147
|
102 |
val tos = connected_with chains' [lhs] [lhs];
|
clasohm@1175
|
103 |
in (copy_lookahead tos [],
|
wenzelm@20664
|
104 |
(if member (op =) lambdas lhs then tos else []) union lambdas)
|
clasohm@1147
|
105 |
end;
|
clasohm@1147
|
106 |
|
clasohm@1175
|
107 |
(*test if new production can produce lambda
|
clasohm@1175
|
108 |
(rhs must either be empty or only consist of lambda NTs)*)
|
clasohm@1175
|
109 |
val (new_lambda, lambdas') =
|
wenzelm@20664
|
110 |
if forall (fn (Nonterminal (id, _)) => member (op =) lambdas' id
|
clasohm@1175
|
111 |
| (Terminal _) => false) rhs then
|
clasohm@1175
|
112 |
(true, lambdas' union (connected_with chains' [lhs] [lhs]))
|
clasohm@1175
|
113 |
else
|
clasohm@1175
|
114 |
(false, lambdas');
|
clasohm@1147
|
115 |
|
clasohm@1175
|
116 |
(*list optional terminal and all nonterminals on which the lookahead
|
clasohm@1175
|
117 |
of a production depends*)
|
skalberg@15531
|
118 |
fun lookahead_dependency _ [] nts = (NONE, nts)
|
skalberg@15531
|
119 |
| lookahead_dependency _ ((Terminal tk) :: _) nts = (SOME tk, nts)
|
clasohm@1147
|
120 |
| lookahead_dependency lambdas ((Nonterminal (nt, _)) :: symbs) nts =
|
wenzelm@20664
|
121 |
if member (op =) lambdas nt then
|
clasohm@1147
|
122 |
lookahead_dependency lambdas symbs (nt :: nts)
|
skalberg@15531
|
123 |
else (NONE, nt :: nts);
|
clasohm@1147
|
124 |
|
clasohm@1175
|
125 |
(*get all known starting tokens for a nonterminal*)
|
clasohm@1175
|
126 |
fun starts_for_nt nt = snd (fst (Array.sub (prods, nt)));
|
clasohm@1175
|
127 |
|
clasohm@1147
|
128 |
val token_union = gen_union matching_tokens;
|
clasohm@1147
|
129 |
|
clasohm@1147
|
130 |
(*update prods, lookaheads, and lambdas according to new lambda NTs*)
|
clasohm@1147
|
131 |
val (added_starts', lambdas') =
|
clasohm@1147
|
132 |
let
|
clasohm@1147
|
133 |
(*propagate added lambda NT*)
|
clasohm@1175
|
134 |
fun propagate_lambda [] added_starts lambdas= (added_starts, lambdas)
|
clasohm@1147
|
135 |
| propagate_lambda (l :: ls) added_starts lambdas =
|
clasohm@1147
|
136 |
let
|
clasohm@1175
|
137 |
(*get lookahead for lambda NT*)
|
clasohm@1175
|
138 |
val ((dependent, l_starts), _) = Array.sub (prods, l);
|
clasohm@1147
|
139 |
|
wenzelm@15752
|
140 |
(*check productions whose lookahead may depend on lambda NT*)
|
clasohm@1147
|
141 |
fun examine_prods [] add_lambda nt_dependencies added_tks
|
clasohm@1175
|
142 |
nt_prods =
|
clasohm@1147
|
143 |
(add_lambda, nt_dependencies, added_tks, nt_prods)
|
clasohm@1147
|
144 |
| examine_prods ((p as (rhs, _, _)) :: ps) add_lambda
|
clasohm@1147
|
145 |
nt_dependencies added_tks nt_prods =
|
clasohm@1147
|
146 |
let val (tk, nts) = lookahead_dependency lambdas rhs [];
|
clasohm@1147
|
147 |
in
|
wenzelm@20664
|
148 |
if member (op =) nts l then (*update production's lookahead*)
|
clasohm@1147
|
149 |
let
|
clasohm@1147
|
150 |
val new_lambda = is_none tk andalso nts subset lambdas;
|
clasohm@1147
|
151 |
|
wenzelm@19305
|
152 |
val new_tks = subtract (op =) l_starts
|
wenzelm@19305
|
153 |
((if is_some tk then [the tk] else []) @
|
wenzelm@19305
|
154 |
Library.foldl token_union ([], map starts_for_nt nts));
|
wenzelm@15752
|
155 |
|
clasohm@1147
|
156 |
val added_tks' = token_union (new_tks, added_tks);
|
clasohm@1147
|
157 |
|
clasohm@1147
|
158 |
val nt_dependencies' = nts union nt_dependencies;
|
clasohm@1147
|
159 |
|
clasohm@1175
|
160 |
(*associate production with new starting tokens*)
|
clasohm@1175
|
161 |
fun copy [] nt_prods = nt_prods
|
clasohm@1175
|
162 |
| copy (tk :: tks) nt_prods =
|
haftmann@17192
|
163 |
let val old_prods = these (AList.lookup (op =) nt_prods tk);
|
clasohm@1175
|
164 |
|
clasohm@1175
|
165 |
val prods' = p :: old_prods;
|
haftmann@17192
|
166 |
in nt_prods
|
haftmann@17192
|
167 |
|> AList.update (op =) (tk, prods')
|
haftmann@17192
|
168 |
|> copy tks
|
clasohm@1175
|
169 |
end;
|
wenzelm@15752
|
170 |
|
clasohm@1147
|
171 |
val nt_prods' =
|
skalberg@15531
|
172 |
let val new_opt_tks = map SOME new_tks;
|
skalberg@15531
|
173 |
in copy ((if new_lambda then [NONE] else []) @
|
clasohm@1175
|
174 |
new_opt_tks) nt_prods
|
clasohm@1147
|
175 |
end;
|
clasohm@1147
|
176 |
in examine_prods ps (add_lambda orelse new_lambda)
|
clasohm@1147
|
177 |
nt_dependencies' added_tks' nt_prods'
|
clasohm@1147
|
178 |
end
|
clasohm@1175
|
179 |
else (*skip production*)
|
clasohm@1175
|
180 |
examine_prods ps add_lambda nt_dependencies
|
clasohm@1175
|
181 |
added_tks nt_prods
|
clasohm@1147
|
182 |
end;
|
clasohm@1147
|
183 |
|
clasohm@1147
|
184 |
(*check each NT whose lookahead depends on new lambda NT*)
|
clasohm@1147
|
185 |
fun process_nts [] added_lambdas added_starts =
|
clasohm@1147
|
186 |
(added_lambdas, added_starts)
|
clasohm@1147
|
187 |
| process_nts (nt :: nts) added_lambdas added_starts =
|
clasohm@1147
|
188 |
let
|
clasohm@1147
|
189 |
val (lookahead as (old_nts, old_tks), nt_prods) =
|
clasohm@1147
|
190 |
Array.sub (prods, nt);
|
clasohm@1147
|
191 |
|
clasohm@1175
|
192 |
(*existing productions whose lookahead may depend on l*)
|
clasohm@1175
|
193 |
val tk_prods =
|
haftmann@17192
|
194 |
(these o AList.lookup (op =) nt_prods)
|
skalberg@15570
|
195 |
(SOME (hd l_starts handle Empty => UnknownStart));
|
clasohm@1147
|
196 |
|
clasohm@1175
|
197 |
(*add_lambda is true if an existing production of the nt
|
clasohm@1175
|
198 |
produces lambda due to the new lambda NT l*)
|
clasohm@1147
|
199 |
val (add_lambda, nt_dependencies, added_tks, nt_prods') =
|
clasohm@1147
|
200 |
examine_prods tk_prods false [] [] nt_prods;
|
clasohm@1147
|
201 |
|
wenzelm@19305
|
202 |
val added_nts = subtract (op =) old_nts nt_dependencies;
|
clasohm@1147
|
203 |
|
clasohm@1147
|
204 |
val added_lambdas' =
|
clasohm@1147
|
205 |
if add_lambda then nt :: added_lambdas
|
clasohm@1147
|
206 |
else added_lambdas;
|
clasohm@1147
|
207 |
in Array.update (prods, nt,
|
clasohm@1175
|
208 |
((added_nts @ old_nts, old_tks @ added_tks),
|
clasohm@1175
|
209 |
nt_prods'));
|
clasohm@1175
|
210 |
(*N.B. that because the tks component
|
clasohm@1175
|
211 |
is used to access existing
|
clasohm@1175
|
212 |
productions we have to add new
|
clasohm@1175
|
213 |
tokens at the _end_ of the list*)
|
clasohm@1175
|
214 |
|
clasohm@1147
|
215 |
if null added_tks then
|
clasohm@1147
|
216 |
process_nts nts added_lambdas' added_starts
|
clasohm@1147
|
217 |
else
|
clasohm@1147
|
218 |
process_nts nts added_lambdas'
|
clasohm@1147
|
219 |
((nt, added_tks) :: added_starts)
|
clasohm@1147
|
220 |
end;
|
clasohm@1147
|
221 |
|
clasohm@1147
|
222 |
val (added_lambdas, added_starts') =
|
clasohm@1147
|
223 |
process_nts dependent [] added_starts;
|
clasohm@1147
|
224 |
|
wenzelm@19305
|
225 |
val added_lambdas' = subtract (op =) lambdas added_lambdas;
|
clasohm@1147
|
226 |
in propagate_lambda (ls @ added_lambdas') added_starts'
|
clasohm@1147
|
227 |
(added_lambdas' @ lambdas)
|
clasohm@1147
|
228 |
end;
|
wenzelm@19305
|
229 |
in propagate_lambda (subtract (op =) lambdas lambdas') added_starts lambdas' end;
|
clasohm@1147
|
230 |
|
clasohm@1147
|
231 |
(*insert production into grammar*)
|
clasohm@1147
|
232 |
val (added_starts', prod_count') =
|
wenzelm@15979
|
233 |
if is_some chain_from then (added_starts', prod_count) (*don't store chain production*)
|
clasohm@1147
|
234 |
else let
|
clasohm@1175
|
235 |
(*lookahead tokens of new production and on which
|
clasohm@1175
|
236 |
NTs lookahead depends*)
|
clasohm@1175
|
237 |
val (start_tk, start_nts) = lookahead_dependency lambdas' rhs [];
|
clasohm@1147
|
238 |
|
skalberg@15570
|
239 |
val start_tks = Library.foldl token_union
|
wenzelm@15979
|
240 |
(if is_some start_tk then [the start_tk] else [],
|
clasohm@1175
|
241 |
map starts_for_nt start_nts);
|
clasohm@1175
|
242 |
|
skalberg@15531
|
243 |
val opt_starts = (if new_lambda then [NONE]
|
skalberg@15531
|
244 |
else if null start_tks then [SOME UnknownStart]
|
skalberg@15531
|
245 |
else []) @ (map SOME start_tks);
|
clasohm@1147
|
246 |
|
clasohm@1147
|
247 |
(*add lhs NT to list of dependent NTs in lookahead*)
|
clasohm@1147
|
248 |
fun add_nts [] = ()
|
clasohm@1147
|
249 |
| add_nts (nt :: nts) =
|
clasohm@1147
|
250 |
let val ((old_nts, old_tks), ps) = Array.sub (prods, nt);
|
wenzelm@20664
|
251 |
in if member (op =) old_nts lhs then ()
|
clasohm@1175
|
252 |
else Array.update (prods, nt, ((lhs :: old_nts, old_tks), ps))
|
clasohm@1147
|
253 |
end;
|
clasohm@1147
|
254 |
|
clasohm@1175
|
255 |
(*add new start tokens to chained NTs' lookahead list;
|
clasohm@1147
|
256 |
also store new production for lhs NT*)
|
clasohm@1147
|
257 |
fun add_tks [] added prod_count = (added, prod_count)
|
clasohm@1147
|
258 |
| add_tks (nt :: nts) added prod_count =
|
clasohm@1147
|
259 |
let
|
clasohm@1175
|
260 |
val ((old_nts, old_tks), nt_prods) = Array.sub (prods, nt);
|
clasohm@1147
|
261 |
|
clasohm@1175
|
262 |
val new_tks = gen_rems matching_tokens (start_tks, old_tks);
|
clasohm@1147
|
263 |
|
clasohm@1175
|
264 |
(*store new production*)
|
clasohm@1147
|
265 |
fun store [] prods is_new =
|
wenzelm@15979
|
266 |
(prods, if is_some prod_count andalso is_new then
|
skalberg@15570
|
267 |
Option.map (fn x => x+1) prod_count
|
clasohm@1175
|
268 |
else prod_count, is_new)
|
clasohm@1175
|
269 |
| store (tk :: tks) prods is_new =
|
haftmann@17192
|
270 |
let val tk_prods = (these o AList.lookup (op =) prods) tk;
|
clasohm@1147
|
271 |
|
skalberg@15531
|
272 |
(*if prod_count = NONE then we can assume that
|
clasohm@1175
|
273 |
grammar does not contain new production already*)
|
clasohm@1175
|
274 |
val (tk_prods', is_new') =
|
wenzelm@15979
|
275 |
if is_some prod_count then
|
wenzelm@20664
|
276 |
if member (op =) tk_prods new_prod then (tk_prods, false)
|
clasohm@1147
|
277 |
else (new_prod :: tk_prods, true)
|
clasohm@1147
|
278 |
else (new_prod :: tk_prods, true);
|
clasohm@1147
|
279 |
|
haftmann@17192
|
280 |
val prods' = prods
|
haftmann@17192
|
281 |
|> K is_new' ? AList.update (op =) (tk, tk_prods');
|
clasohm@1175
|
282 |
in store tks prods' (is_new orelse is_new') end;
|
clasohm@1175
|
283 |
|
clasohm@1175
|
284 |
val (nt_prods', prod_count', changed) =
|
clasohm@1175
|
285 |
if nt = lhs then store opt_starts nt_prods false
|
clasohm@1175
|
286 |
else (nt_prods, prod_count, false);
|
clasohm@1175
|
287 |
in if not changed andalso null new_tks then ()
|
clasohm@1175
|
288 |
else Array.update (prods, nt, ((old_nts, old_tks @ new_tks),
|
clasohm@1175
|
289 |
nt_prods'));
|
clasohm@1147
|
290 |
add_tks nts (if null new_tks then added
|
clasohm@1147
|
291 |
else (nt, new_tks) :: added) prod_count'
|
clasohm@1147
|
292 |
end;
|
clasohm@1147
|
293 |
in add_nts start_nts;
|
clasohm@1147
|
294 |
add_tks (connected_with chains' [lhs] [lhs]) [] prod_count
|
clasohm@330
|
295 |
end;
|
clasohm@330
|
296 |
|
clasohm@1175
|
297 |
(*associate productions with new lookaheads*)
|
clasohm@1147
|
298 |
val dummy =
|
clasohm@1147
|
299 |
let
|
clasohm@1147
|
300 |
(*propagate added start tokens*)
|
clasohm@1147
|
301 |
fun add_starts [] = ()
|
clasohm@1147
|
302 |
| add_starts ((changed_nt, new_tks) :: starts) =
|
clasohm@1147
|
303 |
let
|
clasohm@1175
|
304 |
(*token under which old productions which
|
clasohm@1175
|
305 |
depend on changed_nt could be stored*)
|
clasohm@1175
|
306 |
val key =
|
wenzelm@20664
|
307 |
case find_first (not o member (op =) new_tks)
|
clasohm@1175
|
308 |
(starts_for_nt changed_nt) of
|
skalberg@15531
|
309 |
NONE => SOME UnknownStart
|
clasohm@1175
|
310 |
| t => t;
|
clasohm@1175
|
311 |
|
clasohm@1175
|
312 |
(*copy productions whose lookahead depends on changed_nt;
|
skalberg@15531
|
313 |
if key = SOME UnknownToken then tk_prods is used to hold
|
clasohm@1175
|
314 |
the productions not copied*)
|
clasohm@1147
|
315 |
fun update_prods [] result = result
|
clasohm@1147
|
316 |
| update_prods ((p as (rhs, _, _)) :: ps)
|
clasohm@1147
|
317 |
(tk_prods, nt_prods) =
|
clasohm@1147
|
318 |
let
|
clasohm@1175
|
319 |
(*lookahead dependency for production*)
|
clasohm@1147
|
320 |
val (tk, depends) = lookahead_dependency lambdas' rhs [];
|
clasohm@330
|
321 |
|
clasohm@1175
|
322 |
(*test if this production has to be copied*)
|
wenzelm@20664
|
323 |
val update = member (op =) depends changed_nt;
|
clasohm@1175
|
324 |
|
clasohm@1175
|
325 |
(*test if production could already be associated with
|
clasohm@1175
|
326 |
a member of new_tks*)
|
clasohm@1147
|
327 |
val lambda = length depends > 1 orelse
|
wenzelm@15979
|
328 |
not (null depends) andalso is_some tk
|
wenzelm@20664
|
329 |
andalso member (op =) new_tks (the tk);
|
clasohm@330
|
330 |
|
clasohm@1175
|
331 |
(*associate production with new starting tokens*)
|
clasohm@1147
|
332 |
fun copy [] nt_prods = nt_prods
|
clasohm@1147
|
333 |
| copy (tk :: tks) nt_prods =
|
clasohm@1147
|
334 |
let
|
haftmann@17192
|
335 |
val tk_prods = (these o AList.lookup (op =) nt_prods) (SOME tk);
|
clasohm@1147
|
336 |
|
clasohm@1147
|
337 |
val tk_prods' =
|
clasohm@1147
|
338 |
if not lambda then p :: tk_prods
|
clasohm@1147
|
339 |
else p ins tk_prods;
|
clasohm@1147
|
340 |
(*if production depends on lambda NT we
|
clasohm@1147
|
341 |
have to look for duplicates*)
|
haftmann@17192
|
342 |
in
|
haftmann@17192
|
343 |
nt_prods
|
haftmann@17192
|
344 |
|> AList.update (op =) (SOME tk, tk_prods')
|
haftmann@17192
|
345 |
|> copy tks
|
clasohm@1147
|
346 |
end;
|
clasohm@1147
|
347 |
val result =
|
clasohm@1175
|
348 |
if update then
|
clasohm@1175
|
349 |
(tk_prods, copy new_tks nt_prods)
|
skalberg@15531
|
350 |
else if key = SOME UnknownStart then
|
clasohm@1175
|
351 |
(p :: tk_prods, nt_prods)
|
clasohm@1175
|
352 |
else (tk_prods, nt_prods);
|
clasohm@1147
|
353 |
in update_prods ps result end;
|
clasohm@1147
|
354 |
|
clasohm@1147
|
355 |
(*copy existing productions for new starting tokens*)
|
clasohm@1175
|
356 |
fun process_nts [] added = added
|
clasohm@1175
|
357 |
| process_nts (nt :: nts) added =
|
clasohm@1147
|
358 |
let
|
clasohm@1147
|
359 |
val (lookahead as (old_nts, old_tks), nt_prods) =
|
clasohm@1147
|
360 |
Array.sub (prods, nt);
|
clasohm@1147
|
361 |
|
haftmann@17192
|
362 |
val tk_prods = (these o AList.lookup (op =) nt_prods) key;
|
clasohm@1147
|
363 |
|
clasohm@1175
|
364 |
(*associate productions with new lookahead tokens*)
|
clasohm@1147
|
365 |
val (tk_prods', nt_prods') =
|
clasohm@1147
|
366 |
update_prods tk_prods ([], nt_prods);
|
clasohm@1147
|
367 |
|
clasohm@1147
|
368 |
val nt_prods' =
|
haftmann@17192
|
369 |
nt_prods'
|
haftmann@17192
|
370 |
|> (K (key = SOME UnknownStart)) ? AList.update (op =) (key, tk_prods')
|
clasohm@1147
|
371 |
|
clasohm@1175
|
372 |
val added_tks =
|
clasohm@1175
|
373 |
gen_rems matching_tokens (new_tks, old_tks);
|
clasohm@1147
|
374 |
in if null added_tks then
|
clasohm@1147
|
375 |
(Array.update (prods, nt, (lookahead, nt_prods'));
|
clasohm@1175
|
376 |
process_nts nts added)
|
clasohm@1147
|
377 |
else
|
clasohm@1147
|
378 |
(Array.update (prods, nt,
|
clasohm@1147
|
379 |
((old_nts, added_tks @ old_tks), nt_prods'));
|
clasohm@1175
|
380 |
process_nts nts ((nt, added_tks) :: added))
|
clasohm@330
|
381 |
end;
|
clasohm@330
|
382 |
|
clasohm@1175
|
383 |
val ((dependent, _), _) = Array.sub (prods, changed_nt);
|
clasohm@1175
|
384 |
in add_starts (starts @ (process_nts dependent [])) end;
|
clasohm@1147
|
385 |
in add_starts added_starts' end;
|
clasohm@1147
|
386 |
in add_prods prods chains' lambdas' prod_count ps end;
|
wenzelm@18
|
387 |
|
wenzelm@18
|
388 |
|
wenzelm@237
|
389 |
(* pretty_gram *)
|
wenzelm@18
|
390 |
|
clasohm@1147
|
391 |
fun pretty_gram (Gram {tags, prods, chains, ...}) =
|
wenzelm@237
|
392 |
let
|
wenzelm@237
|
393 |
fun pretty_name name = [Pretty.str (name ^ " =")];
|
wenzelm@18
|
394 |
|
clasohm@1147
|
395 |
val taglist = Symtab.dest tags;
|
clasohm@1147
|
396 |
|
berghofe@14600
|
397 |
fun pretty_symb (Terminal (Token s)) = Pretty.quote (Pretty.str s)
|
wenzelm@237
|
398 |
| pretty_symb (Terminal tok) = Pretty.str (str_of_token tok)
|
clasohm@1147
|
399 |
| pretty_symb (Nonterminal (tag, p)) =
|
wenzelm@15979
|
400 |
let val name = fst (the (find_first (fn (n, t) => t = tag) taglist));
|
clasohm@1147
|
401 |
in Pretty.str (name ^ "[" ^ string_of_int p ^ "]") end;
|
wenzelm@18
|
402 |
|
wenzelm@237
|
403 |
fun pretty_const "" = []
|
berghofe@14600
|
404 |
| pretty_const c = [Pretty.str ("=> " ^ Library.quote c)];
|
wenzelm@237
|
405 |
|
wenzelm@237
|
406 |
fun pretty_pri p = [Pretty.str ("(" ^ string_of_int p ^ ")")];
|
wenzelm@237
|
407 |
|
clasohm@1147
|
408 |
fun pretty_prod name (symbs, const, pri) =
|
wenzelm@237
|
409 |
Pretty.block (Pretty.breaks (pretty_name name @
|
wenzelm@237
|
410 |
map pretty_symb symbs @ pretty_const const @ pretty_pri pri));
|
clasohm@1147
|
411 |
|
clasohm@1147
|
412 |
fun pretty_nt (name, tag) =
|
clasohm@1147
|
413 |
let
|
clasohm@1147
|
414 |
fun prod_of_chain from = ([Nonterminal (from, ~1)], "", ~1);
|
clasohm@1147
|
415 |
|
clasohm@1147
|
416 |
val nt_prods =
|
skalberg@15570
|
417 |
Library.foldl (op union) ([], map snd (snd (Array.sub (prods, tag)))) @
|
haftmann@17192
|
418 |
map prod_of_chain ((these o AList.lookup (op =) chains) tag);
|
clasohm@1147
|
419 |
in map (pretty_prod name) nt_prods end;
|
wenzelm@15752
|
420 |
|
wenzelm@19482
|
421 |
in maps pretty_nt taglist end;
|
clasohm@1147
|
422 |
|
clasohm@1147
|
423 |
|
clasohm@1438
|
424 |
(** Operations on gramars **)
|
clasohm@1147
|
425 |
|
clasohm@1438
|
426 |
(*The mother of all grammars*)
|
clasohm@1147
|
427 |
val empty_gram = Gram {nt_count = 0, prod_count = 0,
|
wenzelm@4487
|
428 |
tags = Symtab.empty, chains = [], lambdas = [],
|
clasohm@1147
|
429 |
prods = Array.array (0, (([], []), []))};
|
clasohm@1147
|
430 |
|
clasohm@1438
|
431 |
|
clasohm@1438
|
432 |
(*Invert list of chain productions*)
|
clasohm@1147
|
433 |
fun inverse_chains [] result = result
|
clasohm@1147
|
434 |
| inverse_chains ((root, branches) :: cs) result =
|
clasohm@1147
|
435 |
let fun add [] result = result
|
clasohm@1147
|
436 |
| add (id :: ids) result =
|
haftmann@17192
|
437 |
let val old = (these o AList.lookup (op =) result) id;
|
haftmann@17192
|
438 |
in add ids (AList.update (op =) (id, root :: old) result) end;
|
clasohm@1147
|
439 |
in inverse_chains cs (add branches result) end;
|
clasohm@1147
|
440 |
|
clasohm@1438
|
441 |
|
clasohm@1438
|
442 |
(*Add productions to a grammar*)
|
clasohm@1147
|
443 |
fun extend_gram gram [] = gram
|
clasohm@1147
|
444 |
| extend_gram (Gram {nt_count, prod_count, tags, chains, lambdas, prods})
|
clasohm@1147
|
445 |
xprods =
|
clasohm@1147
|
446 |
let
|
clasohm@1438
|
447 |
(*Get tag for existing nonterminal or create a new one*)
|
clasohm@1147
|
448 |
fun get_tag nt_count tags nt =
|
wenzelm@17412
|
449 |
case Symtab.lookup tags nt of
|
skalberg@15531
|
450 |
SOME tag => (nt_count, tags, tag)
|
wenzelm@17412
|
451 |
| NONE => (nt_count+1, Symtab.update_new (nt, nt_count) tags,
|
clasohm@1147
|
452 |
nt_count);
|
clasohm@1438
|
453 |
|
clasohm@1438
|
454 |
(*Convert symbols to the form used by the parser;
|
clasohm@1438
|
455 |
delimiters and predefined terms are stored as terminals,
|
clasohm@1438
|
456 |
nonterminals are converted to integer tags*)
|
clasohm@1147
|
457 |
fun symb_of [] nt_count tags result = (nt_count, tags, rev result)
|
clasohm@1147
|
458 |
| symb_of ((Delim s) :: ss) nt_count tags result =
|
clasohm@1147
|
459 |
symb_of ss nt_count tags ((Terminal (Token s)) :: result)
|
clasohm@1147
|
460 |
| symb_of ((Argument (s, p)) :: ss) nt_count tags result =
|
clasohm@1147
|
461 |
let
|
clasohm@1147
|
462 |
val (nt_count', tags', new_symb) =
|
clasohm@1147
|
463 |
case predef_term s of
|
skalberg@15531
|
464 |
NONE =>
|
clasohm@1147
|
465 |
let val (nt_count', tags', s_tag) = get_tag nt_count tags s;
|
clasohm@1147
|
466 |
in (nt_count', tags', Nonterminal (s_tag, p)) end
|
skalberg@15531
|
467 |
| SOME tk => (nt_count, tags, Terminal tk);
|
clasohm@1147
|
468 |
in symb_of ss nt_count' tags' (new_symb :: result) end
|
clasohm@1147
|
469 |
| symb_of (_ :: ss) nt_count tags result =
|
clasohm@1147
|
470 |
symb_of ss nt_count tags result;
|
clasohm@1147
|
471 |
|
clasohm@1438
|
472 |
(*Convert list of productions by invoking symb_of for each of them*)
|
clasohm@1147
|
473 |
fun prod_of [] nt_count prod_count tags result =
|
clasohm@1147
|
474 |
(nt_count, prod_count, tags, result)
|
clasohm@1147
|
475 |
| prod_of ((XProd (lhs, xsymbs, const, pri)) :: ps)
|
clasohm@1147
|
476 |
nt_count prod_count tags result =
|
clasohm@1147
|
477 |
let val (nt_count', tags', lhs_tag) = get_tag nt_count tags lhs;
|
clasohm@1147
|
478 |
|
clasohm@1147
|
479 |
val (nt_count'', tags'', prods) =
|
clasohm@1147
|
480 |
symb_of xsymbs nt_count' tags' [];
|
clasohm@1147
|
481 |
in prod_of ps nt_count'' (prod_count+1) tags''
|
clasohm@1147
|
482 |
((lhs_tag, (prods, const, pri)) :: result)
|
clasohm@1147
|
483 |
end;
|
clasohm@1147
|
484 |
|
clasohm@1438
|
485 |
val (nt_count', prod_count', tags', xprods') =
|
clasohm@1147
|
486 |
prod_of xprods nt_count prod_count tags [];
|
clasohm@1147
|
487 |
|
clasohm@1438
|
488 |
(*Copy array containing productions of old grammar;
|
clasohm@1438
|
489 |
this has to be done to preserve the old grammar while being able
|
clasohm@1438
|
490 |
to change the array's content*)
|
clasohm@1147
|
491 |
val prods' =
|
clasohm@1147
|
492 |
let fun get_prod i = if i < nt_count then Array.sub (prods, i)
|
clasohm@1147
|
493 |
else (([], []), []);
|
clasohm@1147
|
494 |
in Array.tabulate (nt_count', get_prod) end;
|
clasohm@1147
|
495 |
|
clasohm@1147
|
496 |
val fromto_chains = inverse_chains chains [];
|
clasohm@1147
|
497 |
|
clasohm@1438
|
498 |
(*Add new productions to old ones*)
|
clasohm@1147
|
499 |
val (fromto_chains', lambdas', _) =
|
skalberg@15531
|
500 |
add_prods prods' fromto_chains lambdas NONE xprods';
|
clasohm@1147
|
501 |
|
clasohm@1147
|
502 |
val chains' = inverse_chains fromto_chains' [];
|
clasohm@1177
|
503 |
in Gram {nt_count = nt_count', prod_count = prod_count', tags = tags',
|
clasohm@1147
|
504 |
chains = chains', lambdas = lambdas', prods = prods'}
|
wenzelm@18
|
505 |
end;
|
wenzelm@18
|
506 |
|
wenzelm@15752
|
507 |
val make_gram = extend_gram empty_gram;
|
wenzelm@15752
|
508 |
|
wenzelm@18
|
509 |
|
clasohm@1438
|
510 |
(*Merge two grammars*)
|
clasohm@1147
|
511 |
fun merge_grams gram_a gram_b =
|
clasohm@1147
|
512 |
let
|
clasohm@1147
|
513 |
(*find out which grammar is bigger*)
|
clasohm@1147
|
514 |
val (Gram {nt_count = nt_count1, prod_count = prod_count1, tags = tags1,
|
clasohm@1147
|
515 |
chains = chains1, lambdas = lambdas1, prods = prods1},
|
clasohm@1147
|
516 |
Gram {nt_count = nt_count2, prod_count = prod_count2, tags = tags2,
|
clasohm@1147
|
517 |
chains = chains2, lambdas = lambdas2, prods = prods2}) =
|
clasohm@1147
|
518 |
let val Gram {prod_count = count_a, ...} = gram_a;
|
clasohm@1147
|
519 |
val Gram {prod_count = count_b, ...} = gram_b;
|
clasohm@1147
|
520 |
in if count_a > count_b then (gram_a, gram_b)
|
clasohm@1147
|
521 |
else (gram_b, gram_a)
|
clasohm@1147
|
522 |
end;
|
clasohm@1147
|
523 |
|
clasohm@1147
|
524 |
(*get existing tag from grammar1 or create a new one*)
|
clasohm@1147
|
525 |
fun get_tag nt_count tags nt =
|
wenzelm@17412
|
526 |
case Symtab.lookup tags nt of
|
skalberg@15531
|
527 |
SOME tag => (nt_count, tags, tag)
|
wenzelm@17412
|
528 |
| NONE => (nt_count+1, Symtab.update_new (nt, nt_count) tags,
|
clasohm@1147
|
529 |
nt_count)
|
clasohm@1147
|
530 |
|
clasohm@1147
|
531 |
val ((nt_count1', tags1'), tag_table) =
|
clasohm@1147
|
532 |
let val tag_list = Symtab.dest tags2;
|
clasohm@1147
|
533 |
|
clasohm@1147
|
534 |
val table = Array.array (nt_count2, ~1);
|
clasohm@1147
|
535 |
|
clasohm@1147
|
536 |
fun store_tag nt_count tags ~1 = (nt_count, tags)
|
clasohm@1147
|
537 |
| store_tag nt_count tags tag =
|
clasohm@1147
|
538 |
let val (nt_count', tags', tag') =
|
clasohm@1147
|
539 |
get_tag nt_count tags
|
wenzelm@15979
|
540 |
(fst (the (find_first (fn (n, t) => t = tag) tag_list)));
|
clasohm@1147
|
541 |
in Array.update (table, tag, tag');
|
clasohm@1147
|
542 |
store_tag nt_count' tags' (tag-1)
|
clasohm@1147
|
543 |
end;
|
clasohm@1147
|
544 |
in (store_tag nt_count1 tags1 (nt_count2-1), table) end;
|
wenzelm@15752
|
545 |
|
clasohm@1147
|
546 |
(*convert grammar2 tag to grammar1 tag*)
|
clasohm@1147
|
547 |
fun convert_tag tag = Array.sub (tag_table, tag);
|
clasohm@1147
|
548 |
|
clasohm@1147
|
549 |
(*convert chain list to raw productions*)
|
clasohm@1147
|
550 |
fun mk_chain_prods [] result = result
|
clasohm@1147
|
551 |
| mk_chain_prods ((to, froms) :: cs) result =
|
clasohm@1147
|
552 |
let
|
clasohm@1147
|
553 |
val to_tag = convert_tag to;
|
clasohm@1147
|
554 |
|
clasohm@1147
|
555 |
fun make [] result = result
|
clasohm@1147
|
556 |
| make (from :: froms) result = make froms ((to_tag,
|
clasohm@1147
|
557 |
([Nonterminal (convert_tag from, ~1)], "", ~1)) :: result);
|
clasohm@1147
|
558 |
in mk_chain_prods cs (make froms [] @ result) end;
|
wenzelm@15752
|
559 |
|
clasohm@1147
|
560 |
val chain_prods = mk_chain_prods chains2 [];
|
clasohm@1147
|
561 |
|
clasohm@1147
|
562 |
(*convert prods2 array to productions*)
|
clasohm@1147
|
563 |
fun process_nt ~1 result = result
|
clasohm@1147
|
564 |
| process_nt nt result =
|
clasohm@1147
|
565 |
let
|
skalberg@15570
|
566 |
val nt_prods = Library.foldl (op union)
|
clasohm@1147
|
567 |
([], map snd (snd (Array.sub (prods2, nt))));
|
clasohm@1147
|
568 |
val lhs_tag = convert_tag nt;
|
clasohm@1147
|
569 |
|
clasohm@1147
|
570 |
(*convert tags in rhs*)
|
clasohm@1147
|
571 |
fun process_rhs [] result = result
|
clasohm@1147
|
572 |
| process_rhs (Terminal tk :: rhs) result =
|
clasohm@1147
|
573 |
process_rhs rhs (result @ [Terminal tk])
|
clasohm@1147
|
574 |
| process_rhs (Nonterminal (nt, prec) :: rhs) result =
|
clasohm@1147
|
575 |
process_rhs rhs
|
clasohm@1147
|
576 |
(result @ [Nonterminal (convert_tag nt, prec)]);
|
clasohm@1147
|
577 |
|
clasohm@1147
|
578 |
(*convert tags in productions*)
|
clasohm@1147
|
579 |
fun process_prods [] result = result
|
clasohm@1147
|
580 |
| process_prods ((rhs, id, prec) :: ps) result =
|
clasohm@1147
|
581 |
process_prods ps ((lhs_tag, (process_rhs rhs [], id, prec))
|
clasohm@1147
|
582 |
:: result);
|
clasohm@1147
|
583 |
in process_nt (nt-1) (process_prods nt_prods [] @ result) end;
|
clasohm@1147
|
584 |
|
clasohm@1147
|
585 |
val raw_prods = chain_prods @ process_nt (nt_count2-1) [];
|
clasohm@1147
|
586 |
|
clasohm@1147
|
587 |
val prods1' =
|
clasohm@1147
|
588 |
let fun get_prod i = if i < nt_count1 then Array.sub (prods1, i)
|
clasohm@1147
|
589 |
else (([], []), []);
|
clasohm@1147
|
590 |
in Array.tabulate (nt_count1', get_prod) end;
|
clasohm@1147
|
591 |
|
clasohm@1147
|
592 |
val fromto_chains = inverse_chains chains1 [];
|
clasohm@1147
|
593 |
|
skalberg@15531
|
594 |
val (fromto_chains', lambdas', SOME prod_count1') =
|
skalberg@15531
|
595 |
add_prods prods1' fromto_chains lambdas1 (SOME prod_count1) raw_prods;
|
clasohm@1147
|
596 |
|
clasohm@1147
|
597 |
val chains' = inverse_chains fromto_chains' [];
|
clasohm@1147
|
598 |
in Gram {nt_count = nt_count1', prod_count = prod_count1',
|
clasohm@1147
|
599 |
tags = tags1', chains = chains', lambdas = lambdas',
|
clasohm@1147
|
600 |
prods = prods1'}
|
clasohm@1147
|
601 |
end;
|
clasohm@1147
|
602 |
|
wenzelm@18
|
603 |
|
clasohm@1438
|
604 |
(** Parser **)
|
wenzelm@18
|
605 |
|
wenzelm@237
|
606 |
datatype parsetree =
|
wenzelm@237
|
607 |
Node of string * parsetree list |
|
wenzelm@237
|
608 |
Tip of token;
|
wenzelm@237
|
609 |
|
wenzelm@18
|
610 |
type state =
|
clasohm@1147
|
611 |
nt_tag * int * (*identification and production precedence*)
|
clasohm@1147
|
612 |
parsetree list * (*already parsed nonterminals on rhs*)
|
clasohm@1147
|
613 |
symb list * (*rest of rhs*)
|
clasohm@1147
|
614 |
string * (*name of production*)
|
clasohm@1147
|
615 |
int; (*index for previous state list*)
|
wenzelm@18
|
616 |
|
wenzelm@18
|
617 |
|
clasohm@330
|
618 |
(*Get all rhss with precedence >= minPrec*)
|
skalberg@15570
|
619 |
fun getRHS minPrec = List.filter (fn (_, _, prec:int) => prec >= minPrec);
|
wenzelm@18
|
620 |
|
clasohm@330
|
621 |
(*Get all rhss with precedence >= minPrec and < maxPrec*)
|
clasohm@330
|
622 |
fun getRHS' minPrec maxPrec =
|
skalberg@15570
|
623 |
List.filter (fn (_, _, prec:int) => prec >= minPrec andalso prec < maxPrec);
|
wenzelm@237
|
624 |
|
clasohm@330
|
625 |
(*Make states using a list of rhss*)
|
clasohm@330
|
626 |
fun mkStates i minPrec lhsID rhss =
|
clasohm@330
|
627 |
let fun mkState (rhs, id, prodPrec) = (lhsID, prodPrec, [], rhs, id, i);
|
clasohm@330
|
628 |
in map mkState rhss end;
|
clasohm@697
|
629 |
|
wenzelm@15752
|
630 |
(*Add parse tree to list and eliminate duplicates
|
clasohm@330
|
631 |
saving the maximum precedence*)
|
wenzelm@16668
|
632 |
fun conc (t: parsetree list, prec:int) [] = (NONE, [(t, prec)])
|
clasohm@330
|
633 |
| conc (t, prec) ((t', prec') :: ts) =
|
clasohm@330
|
634 |
if t = t' then
|
wenzelm@15752
|
635 |
(SOME prec', if prec' >= prec then (t', prec') :: ts
|
clasohm@330
|
636 |
else (t, prec) :: ts)
|
clasohm@330
|
637 |
else
|
clasohm@330
|
638 |
let val (n, ts') = conc (t, prec) ts
|
clasohm@330
|
639 |
in (n, (t', prec') :: ts') end;
|
wenzelm@18
|
640 |
|
clasohm@330
|
641 |
(*Update entry in used*)
|
wenzelm@16668
|
642 |
fun update_trees ((B: nt_tag, (i, ts)) :: used) (A, t) =
|
wenzelm@237
|
643 |
if A = B then
|
wenzelm@237
|
644 |
let val (n, ts') = conc t ts
|
wenzelm@237
|
645 |
in ((A, (i, ts')) :: used, n) end
|
wenzelm@237
|
646 |
else
|
clasohm@697
|
647 |
let val (used', n) = update_trees used (A, t)
|
wenzelm@237
|
648 |
in ((B, (i, ts)) :: used', n) end;
|
wenzelm@18
|
649 |
|
clasohm@330
|
650 |
(*Replace entry in used*)
|
wenzelm@16668
|
651 |
fun update_prec (A: nt_tag, prec) used =
|
clasohm@697
|
652 |
let fun update ((hd as (B, (_, ts))) :: used, used') =
|
clasohm@330
|
653 |
if A = B
|
clasohm@330
|
654 |
then used' @ ((A, (prec, ts)) :: used)
|
clasohm@330
|
655 |
else update (used, hd :: used')
|
clasohm@330
|
656 |
in update (used, []) end;
|
wenzelm@18
|
657 |
|
clasohm@330
|
658 |
fun getS A maxPrec Si =
|
skalberg@15570
|
659 |
List.filter
|
clasohm@1147
|
660 |
(fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
|
clasohm@330
|
661 |
=> A = B andalso prec <= maxPrec
|
wenzelm@237
|
662 |
| _ => false) Si;
|
wenzelm@18
|
663 |
|
clasohm@330
|
664 |
fun getS' A maxPrec minPrec Si =
|
skalberg@15570
|
665 |
List.filter
|
clasohm@1147
|
666 |
(fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
|
clasohm@330
|
667 |
=> A = B andalso prec > minPrec andalso prec <= maxPrec
|
wenzelm@237
|
668 |
| _ => false) Si;
|
wenzelm@18
|
669 |
|
clasohm@330
|
670 |
fun getStates Estate i ii A maxPrec =
|
skalberg@15570
|
671 |
List.filter
|
clasohm@1147
|
672 |
(fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
|
clasohm@330
|
673 |
=> A = B andalso prec <= maxPrec
|
wenzelm@237
|
674 |
| _ => false)
|
wenzelm@237
|
675 |
(Array.sub (Estate, ii));
|
wenzelm@18
|
676 |
|
wenzelm@18
|
677 |
|
clasohm@1147
|
678 |
fun movedot_term (A, j, ts, Terminal a :: sa, id, i) c =
|
wenzelm@237
|
679 |
if valued_token c then
|
clasohm@697
|
680 |
(A, j, ts @ [Tip c], sa, id, i)
|
wenzelm@237
|
681 |
else (A, j, ts, sa, id, i);
|
wenzelm@18
|
682 |
|
clasohm@1147
|
683 |
fun movedot_nonterm ts (A, j, tss, Nonterminal _ :: sa, id, i) =
|
wenzelm@237
|
684 |
(A, j, tss @ ts, sa, id, i);
|
wenzelm@18
|
685 |
|
wenzelm@237
|
686 |
fun movedot_lambda _ [] = []
|
clasohm@1147
|
687 |
| movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ((t, ki) :: ts) =
|
wenzelm@237
|
688 |
if k <= ki then
|
wenzelm@237
|
689 |
(B, j, tss @ t, sa, id, i) ::
|
clasohm@1147
|
690 |
movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ts
|
clasohm@1147
|
691 |
else movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ts;
|
wenzelm@18
|
692 |
|
wenzelm@18
|
693 |
|
clasohm@1147
|
694 |
val warned = ref false; (*flag for warning message*)
|
kleing@13057
|
695 |
val branching_level = ref 600; (*trigger value for warnings*)
|
wenzelm@18
|
696 |
|
clasohm@1147
|
697 |
(*get all productions of a NT and NTs chained to it which can
|
clasohm@1147
|
698 |
be started by specified token*)
|
clasohm@1147
|
699 |
fun prods_for prods chains include_none tk nts =
|
wenzelm@15979
|
700 |
let
|
wenzelm@15979
|
701 |
fun token_assoc (list, key) =
|
clasohm@1147
|
702 |
let fun assoc [] result = result
|
clasohm@1147
|
703 |
| assoc ((keyi, pi) :: pairs) result =
|
wenzelm@15979
|
704 |
if is_some keyi andalso matching_tokens (the keyi, key)
|
wenzelm@15752
|
705 |
orelse include_none andalso is_none keyi then
|
clasohm@1147
|
706 |
assoc pairs (pi @ result)
|
clasohm@1147
|
707 |
else assoc pairs result;
|
clasohm@1147
|
708 |
in assoc list [] end;
|
clasohm@1147
|
709 |
|
clasohm@1147
|
710 |
fun get_prods [] result = result
|
clasohm@1147
|
711 |
| get_prods (nt :: nts) result =
|
clasohm@1147
|
712 |
let val nt_prods = snd (Array.sub (prods, nt));
|
wenzelm@15979
|
713 |
in get_prods nts ((token_assoc (nt_prods, tk)) @ result) end;
|
clasohm@1147
|
714 |
in get_prods (connected_with chains nts nts) [] end;
|
clasohm@1147
|
715 |
|
clasohm@1147
|
716 |
|
clasohm@1147
|
717 |
fun PROCESSS prods chains Estate i c states =
|
wenzelm@18
|
718 |
let
|
clasohm@1147
|
719 |
fun all_prods_for nt = prods_for prods chains true c [nt];
|
clasohm@330
|
720 |
|
wenzelm@237
|
721 |
fun processS used [] (Si, Sii) = (Si, Sii)
|
wenzelm@237
|
722 |
| processS used (S :: States) (Si, Sii) =
|
wenzelm@237
|
723 |
(case S of
|
clasohm@1147
|
724 |
(_, _, _, Nonterminal (nt, minPrec) :: _, _, _) =>
|
clasohm@330
|
725 |
let (*predictor operation*)
|
clasohm@697
|
726 |
val (used', new_states) =
|
haftmann@17314
|
727 |
(case AList.lookup (op =) used nt of
|
skalberg@15531
|
728 |
SOME (usedPrec, l) => (*nonterminal has been processed*)
|
clasohm@330
|
729 |
if usedPrec <= minPrec then
|
clasohm@330
|
730 |
(*wanted precedence has been processed*)
|
clasohm@330
|
731 |
(used, movedot_lambda S l)
|
clasohm@330
|
732 |
else (*wanted precedence hasn't been parsed yet*)
|
clasohm@1147
|
733 |
let
|
clasohm@1147
|
734 |
val tk_prods = all_prods_for nt;
|
wenzelm@15752
|
735 |
|
clasohm@1147
|
736 |
val States' = mkStates i minPrec nt
|
clasohm@1147
|
737 |
(getRHS' minPrec usedPrec tk_prods);
|
wenzelm@15752
|
738 |
in (update_prec (nt, minPrec) used,
|
clasohm@330
|
739 |
movedot_lambda S l @ States')
|
wenzelm@237
|
740 |
end
|
wenzelm@18
|
741 |
|
skalberg@15531
|
742 |
| NONE => (*nonterminal is parsed for the first time*)
|
clasohm@1147
|
743 |
let val tk_prods = all_prods_for nt;
|
clasohm@1147
|
744 |
val States' = mkStates i minPrec nt
|
clasohm@1147
|
745 |
(getRHS minPrec tk_prods);
|
clasohm@1147
|
746 |
in ((nt, (minPrec, [])) :: used, States') end);
|
clasohm@697
|
747 |
|
clasohm@1147
|
748 |
val dummy =
|
clasohm@1147
|
749 |
if not (!warned) andalso
|
clasohm@1147
|
750 |
length (new_states @ States) > (!branching_level) then
|
wenzelm@19305
|
751 |
(warning "Currently parsed expression could be extremely ambiguous.";
|
clasohm@1147
|
752 |
warned := true)
|
clasohm@1147
|
753 |
else ();
|
wenzelm@237
|
754 |
in
|
clasohm@697
|
755 |
processS used' (new_states @ States) (S :: Si, Sii)
|
wenzelm@237
|
756 |
end
|
clasohm@1147
|
757 |
| (_, _, _, Terminal a :: _, _, _) => (*scanner operation*)
|
wenzelm@237
|
758 |
processS used States
|
wenzelm@237
|
759 |
(S :: Si,
|
wenzelm@237
|
760 |
if matching_tokens (a, c) then movedot_term S c :: Sii else Sii)
|
clasohm@330
|
761 |
| (A, prec, ts, [], id, j) => (*completer operation*)
|
clasohm@697
|
762 |
let val tt = if id = "" then ts else [Node (id, ts)] in
|
clasohm@330
|
763 |
if j = i then (*lambda production?*)
|
wenzelm@237
|
764 |
let
|
clasohm@697
|
765 |
val (used', O) = update_trees used (A, (tt, prec));
|
wenzelm@237
|
766 |
in
|
clasohm@1147
|
767 |
case O of
|
skalberg@15531
|
768 |
NONE =>
|
clasohm@1147
|
769 |
let val Slist = getS A prec Si;
|
clasohm@1147
|
770 |
val States' = map (movedot_nonterm tt) Slist;
|
clasohm@1147
|
771 |
in processS used' (States' @ States) (S :: Si, Sii) end
|
skalberg@15531
|
772 |
| SOME n =>
|
clasohm@1147
|
773 |
if n >= prec then processS used' States (S :: Si, Sii)
|
wenzelm@237
|
774 |
else
|
clasohm@1147
|
775 |
let val Slist = getS' A prec n Si;
|
clasohm@1147
|
776 |
val States' = map (movedot_nonterm tt) Slist;
|
clasohm@1147
|
777 |
in processS used' (States' @ States) (S :: Si, Sii) end
|
wenzelm@15752
|
778 |
end
|
wenzelm@237
|
779 |
else
|
clasohm@1147
|
780 |
let val Slist = getStates Estate i j A prec
|
clasohm@1147
|
781 |
in processS used (map (movedot_nonterm tt) Slist @ States)
|
clasohm@1147
|
782 |
(S :: Si, Sii)
|
clasohm@682
|
783 |
end
|
wenzelm@237
|
784 |
end)
|
clasohm@682
|
785 |
in processS [] states ([], []) end;
|
wenzelm@18
|
786 |
|
wenzelm@18
|
787 |
|
clasohm@362
|
788 |
fun syntax_error toks allowed =
|
wenzelm@4698
|
789 |
let
|
wenzelm@4698
|
790 |
val msg =
|
wenzelm@4698
|
791 |
if null toks then Pretty.str "Inner syntax error: unexpected end of input"
|
wenzelm@4698
|
792 |
else
|
wenzelm@4698
|
793 |
Pretty.block (Pretty.str "Inner syntax error at: \"" ::
|
oheimb@7944
|
794 |
Pretty.breaks (map (Pretty.str o str_of_token)
|
wenzelm@15752
|
795 |
(rev (tl (rev toks)))) @
|
wenzelm@4698
|
796 |
[Pretty.str "\""]);
|
wenzelm@4698
|
797 |
val expected =
|
wenzelm@4698
|
798 |
Pretty.strs ("Expected tokens: " :: map (quote o str_of_token) allowed);
|
wenzelm@4698
|
799 |
in
|
wenzelm@4698
|
800 |
error (Pretty.string_of (Pretty.blk (0, [msg, Pretty.fbrk, expected])))
|
wenzelm@4698
|
801 |
end;
|
wenzelm@18
|
802 |
|
clasohm@1147
|
803 |
fun produce prods chains stateset i indata prev_token =
|
clasohm@1147
|
804 |
(*prev_token is used for error messages*)
|
wenzelm@237
|
805 |
(case Array.sub (stateset, i) of
|
clasohm@1147
|
806 |
[] => let fun some_prods_for tk nt = prods_for prods chains false tk [nt];
|
clasohm@373
|
807 |
|
clasohm@373
|
808 |
(*test if tk is a lookahead for a given minimum precedence*)
|
clasohm@1147
|
809 |
fun reduction _ minPrec _ (Terminal _ :: _, _, prec:int) =
|
clasohm@373
|
810 |
if prec >= minPrec then true
|
clasohm@373
|
811 |
else false
|
wenzelm@15752
|
812 |
| reduction tk minPrec checked
|
clasohm@1147
|
813 |
(Nonterminal (nt, nt_prec) :: _, _, prec) =
|
wenzelm@20664
|
814 |
if prec >= minPrec andalso not (member (op =) checked nt) then
|
clasohm@1147
|
815 |
let val chained = connected_with chains [nt] [nt];
|
clasohm@1147
|
816 |
in exists
|
clasohm@1147
|
817 |
(reduction tk nt_prec (chained @ checked))
|
clasohm@1147
|
818 |
(some_prods_for tk nt)
|
clasohm@1147
|
819 |
end
|
clasohm@1147
|
820 |
else false;
|
clasohm@373
|
821 |
|
wenzelm@15752
|
822 |
(*compute a list of allowed starting tokens
|
clasohm@373
|
823 |
for a list of nonterminals considering precedence*)
|
clasohm@1147
|
824 |
fun get_starts [] result = result
|
clasohm@1147
|
825 |
| get_starts ((nt, minPrec:int) :: nts) result =
|
clasohm@1147
|
826 |
let fun get [] result = result
|
skalberg@15531
|
827 |
| get ((SOME tk, prods) :: ps) result =
|
clasohm@1147
|
828 |
if not (null prods) andalso
|
clasohm@1147
|
829 |
exists (reduction tk minPrec [nt]) prods
|
clasohm@1147
|
830 |
then get ps (tk :: result)
|
clasohm@1147
|
831 |
else get ps result
|
skalberg@15531
|
832 |
| get ((NONE, _) :: ps) result = get ps result;
|
clasohm@362
|
833 |
|
clasohm@1147
|
834 |
val (_, nt_prods) = Array.sub (prods, nt);
|
clasohm@1147
|
835 |
|
clasohm@1147
|
836 |
val chained = map (fn nt => (nt, minPrec))
|
haftmann@17192
|
837 |
((these o AList.lookup (op =) chains) nt);
|
clasohm@1147
|
838 |
in get_starts (chained @ nts)
|
clasohm@1147
|
839 |
((get nt_prods []) union result)
|
clasohm@1147
|
840 |
end;
|
clasohm@1147
|
841 |
|
clasohm@1147
|
842 |
val nts =
|
wenzelm@19482
|
843 |
map_filter (fn (_, _, _, Nonterminal (a, prec) :: _, _, _) =>
|
skalberg@15531
|
844 |
SOME (a, prec) | _ => NONE)
|
clasohm@1147
|
845 |
(Array.sub (stateset, i-1));
|
clasohm@1147
|
846 |
val allowed =
|
wenzelm@19046
|
847 |
distinct (op =) (get_starts nts [] @
|
wenzelm@19482
|
848 |
(map_filter (fn (_, _, _, Terminal a :: _, _, _) => SOME a
|
skalberg@15531
|
849 |
| _ => NONE)
|
clasohm@1147
|
850 |
(Array.sub (stateset, i-1))));
|
clasohm@362
|
851 |
in syntax_error (if prev_token = EndToken then indata
|
clasohm@362
|
852 |
else prev_token :: indata) allowed
|
clasohm@362
|
853 |
end
|
wenzelm@237
|
854 |
| s =>
|
wenzelm@237
|
855 |
(case indata of
|
clasohm@1147
|
856 |
[] => Array.sub (stateset, i)
|
clasohm@1147
|
857 |
| c :: cs =>
|
clasohm@1147
|
858 |
let val (si, sii) = PROCESSS prods chains stateset i c s;
|
clasohm@1147
|
859 |
in Array.update (stateset, i, si);
|
clasohm@1147
|
860 |
Array.update (stateset, i + 1, sii);
|
clasohm@1147
|
861 |
produce prods chains stateset (i + 1) cs c
|
clasohm@1147
|
862 |
end));
|
wenzelm@18
|
863 |
|
wenzelm@18
|
864 |
|
wenzelm@19482
|
865 |
fun get_trees l = map_filter (fn (_, _, [pt], _, _, _) => SOME pt | _ => NONE)
|
paulson@2229
|
866 |
l;
|
wenzelm@18
|
867 |
|
clasohm@1147
|
868 |
fun earley prods tags chains startsymbol indata =
|
wenzelm@237
|
869 |
let
|
wenzelm@17412
|
870 |
val start_tag = case Symtab.lookup tags startsymbol of
|
skalberg@15531
|
871 |
SOME tag => tag
|
wenzelm@15752
|
872 |
| NONE => error ("parse: Unknown startsymbol " ^
|
clasohm@624
|
873 |
quote startsymbol);
|
clasohm@1147
|
874 |
val S0 = [(~1, 0, [], [Nonterminal (start_tag, 0), Terminal EndToken],
|
clasohm@1147
|
875 |
"", 0)];
|
clasohm@330
|
876 |
val s = length indata + 1;
|
wenzelm@237
|
877 |
val Estate = Array.array (s, []);
|
wenzelm@237
|
878 |
in
|
wenzelm@237
|
879 |
Array.update (Estate, 0, S0);
|
clasohm@1147
|
880 |
warned := false;
|
clasohm@1147
|
881 |
get_trees (produce prods chains Estate 0 indata EndToken)
|
wenzelm@237
|
882 |
end;
|
wenzelm@18
|
883 |
|
wenzelm@18
|
884 |
|
clasohm@1147
|
885 |
fun parse (Gram {tags, prods, chains, ...}) start toks =
|
clasohm@624
|
886 |
let val r =
|
clasohm@1147
|
887 |
(case earley prods tags chains start toks of
|
wenzelm@237
|
888 |
[] => sys_error "parse: no parse trees"
|
clasohm@330
|
889 |
| pts => pts);
|
clasohm@624
|
890 |
in r end
|
wenzelm@18
|
891 |
|
wenzelm@18
|
892 |
end;
|