Deleted Library.option type.
1 (* Title: Pure/Syntax/parser.ML
3 Author: Carsten Clasohm, Sonia Mahjoub, and Markus Wenzel, TU Muenchen
5 Isabelle's main parser (used for terms and types).
12 val extend_gram: gram -> SynExt.xprod list -> gram
13 val merge_grams: gram -> gram -> gram
14 val pretty_gram: gram -> Pretty.T list
16 Node of string * parsetree list |
18 val parse: gram -> string -> Lexicon.token list -> parsetree list
19 val branching_level: int ref
23 structure Parser : PARSER =
29 type nt_tag = int; (*production for the NTs are stored in an array
30 so we can identify NTs by their index*)
32 datatype symb = Terminal of token
33 | Nonterminal of nt_tag * int; (*(tag, precedence)*)
35 type nt_gram = ((nt_tag list * token list) *
36 (token option * (symb list * string * int) list) list);
37 (*(([dependent_nts], [start_tokens]),
38 [(start_token, [(rhs, name, prio)])])*)
39 (*depent_nts is a list of all NTs whose lookahead
40 depends on this NT's lookahead*)
43 Gram of {nt_count: int, prod_count: int,
44 tags: nt_tag Symtab.table,
45 chains: (nt_tag * nt_tag list) list, (*[(to, [from])]*)
47 prods: nt_gram Array.array};
48 (*"tags" is used to map NT names (i.e. strings) to tags;
49 chain productions are not stored as normal productions
50 but instead as an entry in "chains";
51 lambda productions are stored as normal productions
52 and also as an entry in "lambdas"*)
54 val UnknownStart = EndToken; (*productions for which no starting token is
55 known yet are associated with this token*)
57 (* get all NTs that are connected with a list of NTs
58 (used for expanding chain list)*)
59 fun connected_with _ [] relatives = relatives
60 | connected_with chains (root :: roots) relatives =
61 let val branches = (assocs chains root) \\ relatives;
62 in connected_with chains (branches @ roots) (branches @ relatives) end;
64 (* convert productions to grammar;
65 N.B. that the chains parameter has the form [(from, [to])];
66 prod_count is of type "int option" and is only updated if it is <> NONE*)
67 fun add_prods _ chains lambdas prod_count [] = (chains, lambdas, prod_count)
68 | add_prods prods chains lambdas prod_count
69 ((lhs, new_prod as (rhs, name, pri)) :: ps) =
71 (*test if new_prod is a chain production*)
72 val (new_chain, chains') =
73 let (*store chain if it does not already exist*)
74 fun store_chain from =
75 let val old_tos = assocs chains from;
76 in if lhs mem old_tos then (NONE, chains)
77 else (SOME from, overwrite (chains, (from, lhs ins old_tos)))
80 case rhs of [Nonterminal (id, ~1)] => store_chain id
85 (*propagate new chain in lookahead and lambda lists;
86 added_starts is used later to associate existing
87 productions with new starting tokens*)
88 val (added_starts, lambdas') =
89 if is_none new_chain then ([], lambdas) else
90 let (*lookahead of chain's source*)
91 val ((from_nts, from_tks), _) = Array.sub (prods, the new_chain);
93 (*copy from's lookahead to chain's destinations*)
94 fun copy_lookahead [] added = added
95 | copy_lookahead (to :: tos) added =
97 val ((to_nts, to_tks), ps) = Array.sub (prods, to);
99 val new_tks = from_tks \\ to_tks; (*added lookahead tokens*)
100 in Array.update (prods, to, ((to_nts, to_tks @ new_tks), ps));
101 copy_lookahead tos (if null new_tks then added
102 else (to, new_tks) :: added)
105 val tos = connected_with chains' [lhs] [lhs];
106 in (copy_lookahead tos [],
107 (if lhs mem lambdas then tos else []) union lambdas)
110 (*test if new production can produce lambda
111 (rhs must either be empty or only consist of lambda NTs)*)
112 val (new_lambda, lambdas') =
113 if forall (fn (Nonterminal (id, _)) => id mem lambdas'
114 | (Terminal _) => false) rhs then
115 (true, lambdas' union (connected_with chains' [lhs] [lhs]))
119 (*list optional terminal and all nonterminals on which the lookahead
120 of a production depends*)
121 fun lookahead_dependency _ [] nts = (NONE, nts)
122 | lookahead_dependency _ ((Terminal tk) :: _) nts = (SOME tk, nts)
123 | lookahead_dependency lambdas ((Nonterminal (nt, _)) :: symbs) nts =
124 if nt mem lambdas then
125 lookahead_dependency lambdas symbs (nt :: nts)
126 else (NONE, nt :: nts);
128 (*get all known starting tokens for a nonterminal*)
129 fun starts_for_nt nt = snd (fst (Array.sub (prods, nt)));
131 val token_union = gen_union matching_tokens;
133 (*update prods, lookaheads, and lambdas according to new lambda NTs*)
134 val (added_starts', lambdas') =
136 (*propagate added lambda NT*)
137 fun propagate_lambda [] added_starts lambdas= (added_starts, lambdas)
138 | propagate_lambda (l :: ls) added_starts lambdas =
140 (*get lookahead for lambda NT*)
141 val ((dependent, l_starts), _) = Array.sub (prods, l);
143 (*check productions whose lookahead may depend on lamdba NT*)
144 fun examine_prods [] add_lambda nt_dependencies added_tks
146 (add_lambda, nt_dependencies, added_tks, nt_prods)
147 | examine_prods ((p as (rhs, _, _)) :: ps) add_lambda
148 nt_dependencies added_tks nt_prods =
149 let val (tk, nts) = lookahead_dependency lambdas rhs [];
151 if l mem nts then (*update production's lookahead*)
153 val new_lambda = is_none tk andalso nts subset lambdas;
155 val new_tks = (if is_some tk then [the tk] else []) @
156 foldl token_union ([], map starts_for_nt nts) \\
159 val added_tks' = token_union (new_tks, added_tks);
161 val nt_dependencies' = nts union nt_dependencies;
163 (*associate production with new starting tokens*)
164 fun copy [] nt_prods = nt_prods
165 | copy (tk :: tks) nt_prods =
166 let val old_prods = assocs nt_prods tk;
168 val prods' = p :: old_prods;
169 in copy tks (overwrite (nt_prods, (tk, prods')))
173 let val new_opt_tks = map SOME new_tks;
174 in copy ((if new_lambda then [NONE] else []) @
175 new_opt_tks) nt_prods
177 in examine_prods ps (add_lambda orelse new_lambda)
178 nt_dependencies' added_tks' nt_prods'
180 else (*skip production*)
181 examine_prods ps add_lambda nt_dependencies
185 (*check each NT whose lookahead depends on new lambda NT*)
186 fun process_nts [] added_lambdas added_starts =
187 (added_lambdas, added_starts)
188 | process_nts (nt :: nts) added_lambdas added_starts =
190 val (lookahead as (old_nts, old_tks), nt_prods) =
191 Array.sub (prods, nt);
193 (*existing productions whose lookahead may depend on l*)
196 (SOME (hd l_starts handle LIST _ => UnknownStart));
198 (*add_lambda is true if an existing production of the nt
199 produces lambda due to the new lambda NT l*)
200 val (add_lambda, nt_dependencies, added_tks, nt_prods') =
201 examine_prods tk_prods false [] [] nt_prods;
203 val added_nts = nt_dependencies \\ old_nts;
206 if add_lambda then nt :: added_lambdas
208 in Array.update (prods, nt,
209 ((added_nts @ old_nts, old_tks @ added_tks),
211 (*N.B. that because the tks component
212 is used to access existing
213 productions we have to add new
214 tokens at the _end_ of the list*)
216 if null added_tks then
217 process_nts nts added_lambdas' added_starts
219 process_nts nts added_lambdas'
220 ((nt, added_tks) :: added_starts)
223 val (added_lambdas, added_starts') =
224 process_nts dependent [] added_starts;
226 val added_lambdas' = added_lambdas \\ lambdas;
227 in propagate_lambda (ls @ added_lambdas') added_starts'
228 (added_lambdas' @ lambdas)
230 in propagate_lambda (lambdas' \\ lambdas) added_starts lambdas' end;
232 (*insert production into grammar*)
233 val (added_starts', prod_count') =
234 if is_some new_chain then (added_starts', prod_count)
235 (*don't store chain production*)
237 (*lookahead tokens of new production and on which
238 NTs lookahead depends*)
239 val (start_tk, start_nts) = lookahead_dependency lambdas' rhs [];
241 val start_tks = foldl token_union
242 (if is_some start_tk then [the start_tk] else [],
243 map starts_for_nt start_nts);
245 val opt_starts = (if new_lambda then [NONE]
246 else if null start_tks then [SOME UnknownStart]
247 else []) @ (map SOME start_tks);
249 (*add lhs NT to list of dependent NTs in lookahead*)
251 | add_nts (nt :: nts) =
252 let val ((old_nts, old_tks), ps) = Array.sub (prods, nt);
253 in if lhs mem old_nts then ()
254 else Array.update (prods, nt, ((lhs :: old_nts, old_tks), ps))
257 (*add new start tokens to chained NTs' lookahead list;
258 also store new production for lhs NT*)
259 fun add_tks [] added prod_count = (added, prod_count)
260 | add_tks (nt :: nts) added prod_count =
262 val ((old_nts, old_tks), nt_prods) = Array.sub (prods, nt);
264 val new_tks = gen_rems matching_tokens (start_tks, old_tks);
266 (*store new production*)
267 fun store [] prods is_new =
268 (prods, if is_some prod_count andalso is_new then
269 apsome (fn x => x+1) prod_count
270 else prod_count, is_new)
271 | store (tk :: tks) prods is_new =
272 let val tk_prods = assocs prods tk;
274 (*if prod_count = NONE then we can assume that
275 grammar does not contain new production already*)
276 val (tk_prods', is_new') =
277 if is_some prod_count then
278 if new_prod mem tk_prods then (tk_prods, false)
279 else (new_prod :: tk_prods, true)
280 else (new_prod :: tk_prods, true);
282 val prods' = if is_new' then
283 overwrite (prods, (tk, tk_prods'))
285 in store tks prods' (is_new orelse is_new') end;
287 val (nt_prods', prod_count', changed) =
288 if nt = lhs then store opt_starts nt_prods false
289 else (nt_prods, prod_count, false);
290 in if not changed andalso null new_tks then ()
291 else Array.update (prods, nt, ((old_nts, old_tks @ new_tks),
293 add_tks nts (if null new_tks then added
294 else (nt, new_tks) :: added) prod_count'
296 in add_nts start_nts;
297 add_tks (connected_with chains' [lhs] [lhs]) [] prod_count
300 (*associate productions with new lookaheads*)
303 (*propagate added start tokens*)
304 fun add_starts [] = ()
305 | add_starts ((changed_nt, new_tks) :: starts) =
307 (*token under which old productions which
308 depend on changed_nt could be stored*)
310 case find_first (fn t => not (t mem new_tks))
311 (starts_for_nt changed_nt) of
312 NONE => SOME UnknownStart
315 (*copy productions whose lookahead depends on changed_nt;
316 if key = SOME UnknownToken then tk_prods is used to hold
317 the productions not copied*)
318 fun update_prods [] result = result
319 | update_prods ((p as (rhs, _, _)) :: ps)
320 (tk_prods, nt_prods) =
322 (*lookahead dependency for production*)
323 val (tk, depends) = lookahead_dependency lambdas' rhs [];
325 (*test if this production has to be copied*)
326 val update = changed_nt mem depends;
328 (*test if production could already be associated with
329 a member of new_tks*)
330 val lambda = length depends > 1 orelse
331 not (null depends) andalso is_some tk
332 andalso the tk mem new_tks;
334 (*associate production with new starting tokens*)
335 fun copy [] nt_prods = nt_prods
336 | copy (tk :: tks) nt_prods =
338 val tk_prods = assocs nt_prods (SOME tk);
341 if not lambda then p :: tk_prods
343 (*if production depends on lambda NT we
344 have to look for duplicates*)
346 (overwrite (nt_prods, (SOME tk, tk_prods')))
350 (tk_prods, copy new_tks nt_prods)
351 else if key = SOME UnknownStart then
352 (p :: tk_prods, nt_prods)
353 else (tk_prods, nt_prods);
354 in update_prods ps result end;
356 (*copy existing productions for new starting tokens*)
357 fun process_nts [] added = added
358 | process_nts (nt :: nts) added =
360 val (lookahead as (old_nts, old_tks), nt_prods) =
361 Array.sub (prods, nt);
363 val tk_prods = assocs nt_prods key;
365 (*associate productions with new lookahead tokens*)
366 val (tk_prods', nt_prods') =
367 update_prods tk_prods ([], nt_prods);
370 if key = SOME UnknownStart then
371 overwrite (nt_prods', (key, tk_prods'))
375 gen_rems matching_tokens (new_tks, old_tks);
376 in if null added_tks then
377 (Array.update (prods, nt, (lookahead, nt_prods'));
378 process_nts nts added)
380 (Array.update (prods, nt,
381 ((old_nts, added_tks @ old_tks), nt_prods'));
382 process_nts nts ((nt, added_tks) :: added))
385 val ((dependent, _), _) = Array.sub (prods, changed_nt);
386 in add_starts (starts @ (process_nts dependent [])) end;
387 in add_starts added_starts' end;
388 in add_prods prods chains' lambdas' prod_count ps end;
393 fun pretty_gram (Gram {tags, prods, chains, ...}) =
395 fun pretty_name name = [Pretty.str (name ^ " =")];
397 val taglist = Symtab.dest tags;
399 fun pretty_symb (Terminal (Token s)) = Pretty.quote (Pretty.str s)
400 | pretty_symb (Terminal tok) = Pretty.str (str_of_token tok)
401 | pretty_symb (Nonterminal (tag, p)) =
402 let val name = fst (the (find_first (fn (n, t) => t = tag) taglist));
403 in Pretty.str (name ^ "[" ^ string_of_int p ^ "]") end;
405 fun pretty_const "" = []
406 | pretty_const c = [Pretty.str ("=> " ^ Library.quote c)];
408 fun pretty_pri p = [Pretty.str ("(" ^ string_of_int p ^ ")")];
410 fun pretty_prod name (symbs, const, pri) =
411 Pretty.block (Pretty.breaks (pretty_name name @
412 map pretty_symb symbs @ pretty_const const @ pretty_pri pri));
414 fun pretty_nt (name, tag) =
416 fun prod_of_chain from = ([Nonterminal (from, ~1)], "", ~1);
419 foldl (op union) ([], map snd (snd (Array.sub (prods, tag)))) @
420 map prod_of_chain (assocs chains tag);
421 in map (pretty_prod name) nt_prods end;
423 in flat (map pretty_nt taglist) end;
426 (** Operations on gramars **)
428 (*The mother of all grammars*)
429 val empty_gram = Gram {nt_count = 0, prod_count = 0,
430 tags = Symtab.empty, chains = [], lambdas = [],
431 prods = Array.array (0, (([], []), []))};
434 (*Invert list of chain productions*)
435 fun inverse_chains [] result = result
436 | inverse_chains ((root, branches) :: cs) result =
437 let fun add [] result = result
438 | add (id :: ids) result =
439 let val old = assocs result id;
440 in add ids (overwrite (result, (id, root :: old))) end;
441 in inverse_chains cs (add branches result) end;
444 (*Add productions to a grammar*)
445 fun extend_gram gram [] = gram
446 | extend_gram (Gram {nt_count, prod_count, tags, chains, lambdas, prods})
449 (*Get tag for existing nonterminal or create a new one*)
450 fun get_tag nt_count tags nt =
451 case Symtab.lookup (tags, nt) of
452 SOME tag => (nt_count, tags, tag)
453 | NONE => (nt_count+1, Symtab.update_new ((nt, nt_count), tags),
456 (*Convert symbols to the form used by the parser;
457 delimiters and predefined terms are stored as terminals,
458 nonterminals are converted to integer tags*)
459 fun symb_of [] nt_count tags result = (nt_count, tags, rev result)
460 | symb_of ((Delim s) :: ss) nt_count tags result =
461 symb_of ss nt_count tags ((Terminal (Token s)) :: result)
462 | symb_of ((Argument (s, p)) :: ss) nt_count tags result =
464 val (nt_count', tags', new_symb) =
465 case predef_term s of
467 let val (nt_count', tags', s_tag) = get_tag nt_count tags s;
468 in (nt_count', tags', Nonterminal (s_tag, p)) end
469 | SOME tk => (nt_count, tags, Terminal tk);
470 in symb_of ss nt_count' tags' (new_symb :: result) end
471 | symb_of (_ :: ss) nt_count tags result =
472 symb_of ss nt_count tags result;
474 (*Convert list of productions by invoking symb_of for each of them*)
475 fun prod_of [] nt_count prod_count tags result =
476 (nt_count, prod_count, tags, result)
477 | prod_of ((XProd (lhs, xsymbs, const, pri)) :: ps)
478 nt_count prod_count tags result =
479 let val (nt_count', tags', lhs_tag) = get_tag nt_count tags lhs;
481 val (nt_count'', tags'', prods) =
482 symb_of xsymbs nt_count' tags' [];
483 in prod_of ps nt_count'' (prod_count+1) tags''
484 ((lhs_tag, (prods, const, pri)) :: result)
487 val (nt_count', prod_count', tags', xprods') =
488 prod_of xprods nt_count prod_count tags [];
490 (*Copy array containing productions of old grammar;
491 this has to be done to preserve the old grammar while being able
492 to change the array's content*)
494 let fun get_prod i = if i < nt_count then Array.sub (prods, i)
496 in Array.tabulate (nt_count', get_prod) end;
498 val fromto_chains = inverse_chains chains [];
500 (*Add new productions to old ones*)
501 val (fromto_chains', lambdas', _) =
502 add_prods prods' fromto_chains lambdas NONE xprods';
504 val chains' = inverse_chains fromto_chains' [];
505 in Gram {nt_count = nt_count', prod_count = prod_count', tags = tags',
506 chains = chains', lambdas = lambdas', prods = prods'}
510 (*Merge two grammars*)
511 fun merge_grams gram_a gram_b =
513 (*find out which grammar is bigger*)
514 val (Gram {nt_count = nt_count1, prod_count = prod_count1, tags = tags1,
515 chains = chains1, lambdas = lambdas1, prods = prods1},
516 Gram {nt_count = nt_count2, prod_count = prod_count2, tags = tags2,
517 chains = chains2, lambdas = lambdas2, prods = prods2}) =
518 let val Gram {prod_count = count_a, ...} = gram_a;
519 val Gram {prod_count = count_b, ...} = gram_b;
520 in if count_a > count_b then (gram_a, gram_b)
521 else (gram_b, gram_a)
524 (*get existing tag from grammar1 or create a new one*)
525 fun get_tag nt_count tags nt =
526 case Symtab.lookup (tags, nt) of
527 SOME tag => (nt_count, tags, tag)
528 | NONE => (nt_count+1, Symtab.update_new ((nt, nt_count), tags),
531 val ((nt_count1', tags1'), tag_table) =
532 let val tag_list = Symtab.dest tags2;
534 val table = Array.array (nt_count2, ~1);
536 fun store_tag nt_count tags ~1 = (nt_count, tags)
537 | store_tag nt_count tags tag =
538 let val (nt_count', tags', tag') =
539 get_tag nt_count tags
540 (fst (the (find_first (fn (n, t) => t = tag) tag_list)));
541 in Array.update (table, tag, tag');
542 store_tag nt_count' tags' (tag-1)
544 in (store_tag nt_count1 tags1 (nt_count2-1), table) end;
546 (*convert grammar2 tag to grammar1 tag*)
547 fun convert_tag tag = Array.sub (tag_table, tag);
549 (*convert chain list to raw productions*)
550 fun mk_chain_prods [] result = result
551 | mk_chain_prods ((to, froms) :: cs) result =
553 val to_tag = convert_tag to;
555 fun make [] result = result
556 | make (from :: froms) result = make froms ((to_tag,
557 ([Nonterminal (convert_tag from, ~1)], "", ~1)) :: result);
558 in mk_chain_prods cs (make froms [] @ result) end;
560 val chain_prods = mk_chain_prods chains2 [];
562 (*convert prods2 array to productions*)
563 fun process_nt ~1 result = result
564 | process_nt nt result =
566 val nt_prods = foldl (op union)
567 ([], map snd (snd (Array.sub (prods2, nt))));
568 val lhs_tag = convert_tag nt;
570 (*convert tags in rhs*)
571 fun process_rhs [] result = result
572 | process_rhs (Terminal tk :: rhs) result =
573 process_rhs rhs (result @ [Terminal tk])
574 | process_rhs (Nonterminal (nt, prec) :: rhs) result =
576 (result @ [Nonterminal (convert_tag nt, prec)]);
578 (*convert tags in productions*)
579 fun process_prods [] result = result
580 | process_prods ((rhs, id, prec) :: ps) result =
581 process_prods ps ((lhs_tag, (process_rhs rhs [], id, prec))
583 in process_nt (nt-1) (process_prods nt_prods [] @ result) end;
585 val raw_prods = chain_prods @ process_nt (nt_count2-1) [];
588 let fun get_prod i = if i < nt_count1 then Array.sub (prods1, i)
590 in Array.tabulate (nt_count1', get_prod) end;
592 val fromto_chains = inverse_chains chains1 [];
594 val (fromto_chains', lambdas', SOME prod_count1') =
595 add_prods prods1' fromto_chains lambdas1 (SOME prod_count1) raw_prods;
597 val chains' = inverse_chains fromto_chains' [];
598 in Gram {nt_count = nt_count1', prod_count = prod_count1',
599 tags = tags1', chains = chains', lambdas = lambdas',
607 Node of string * parsetree list |
611 nt_tag * int * (*identification and production precedence*)
612 parsetree list * (*already parsed nonterminals on rhs*)
613 symb list * (*rest of rhs*)
614 string * (*name of production*)
615 int; (*index for previous state list*)
618 (*Get all rhss with precedence >= minPrec*)
619 fun getRHS minPrec = filter (fn (_, _, prec:int) => prec >= minPrec);
621 (*Get all rhss with precedence >= minPrec and < maxPrec*)
622 fun getRHS' minPrec maxPrec =
623 filter (fn (_, _, prec:int) => prec >= minPrec andalso prec < maxPrec);
625 (*Make states using a list of rhss*)
626 fun mkStates i minPrec lhsID rhss =
627 let fun mkState (rhs, id, prodPrec) = (lhsID, prodPrec, [], rhs, id, i);
628 in map mkState rhss end;
630 (*Add parse tree to list and eliminate duplicates
631 saving the maximum precedence*)
632 fun conc (t, prec:int) [] = (NONE, [(t, prec)])
633 | conc (t, prec) ((t', prec') :: ts) =
635 (SOME prec', if prec' >= prec then (t', prec') :: ts
636 else (t, prec) :: ts)
638 let val (n, ts') = conc (t, prec) ts
639 in (n, (t', prec') :: ts') end;
641 (*Update entry in used*)
642 fun update_trees ((B, (i, ts)) :: used) (A, t) =
644 let val (n, ts') = conc t ts
645 in ((A, (i, ts')) :: used, n) end
647 let val (used', n) = update_trees used (A, t)
648 in ((B, (i, ts)) :: used', n) end;
650 (*Replace entry in used*)
651 fun update_prec (A, prec) used =
652 let fun update ((hd as (B, (_, ts))) :: used, used') =
654 then used' @ ((A, (prec, ts)) :: used)
655 else update (used, hd :: used')
656 in update (used, []) end;
658 fun getS A maxPrec Si =
660 (fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
661 => A = B andalso prec <= maxPrec
664 fun getS' A maxPrec minPrec Si =
666 (fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
667 => A = B andalso prec > minPrec andalso prec <= maxPrec
670 fun getStates Estate i ii A maxPrec =
672 (fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
673 => A = B andalso prec <= maxPrec
675 (Array.sub (Estate, ii));
678 fun movedot_term (A, j, ts, Terminal a :: sa, id, i) c =
679 if valued_token c then
680 (A, j, ts @ [Tip c], sa, id, i)
681 else (A, j, ts, sa, id, i);
683 fun movedot_nonterm ts (A, j, tss, Nonterminal _ :: sa, id, i) =
684 (A, j, tss @ ts, sa, id, i);
686 fun movedot_lambda _ [] = []
687 | movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ((t, ki) :: ts) =
689 (B, j, tss @ t, sa, id, i) ::
690 movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ts
691 else movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ts;
694 val warned = ref false; (*flag for warning message*)
695 val branching_level = ref 600; (*trigger value for warnings*)
697 (*get all productions of a NT and NTs chained to it which can
698 be started by specified token*)
699 fun prods_for prods chains include_none tk nts =
700 let (*similar to token_assoc but does not automatically include 'NONE' key*)
701 fun token_assoc2 (list, key) =
702 let fun assoc [] result = result
703 | assoc ((keyi, pi) :: pairs) result =
704 if is_some keyi andalso matching_tokens (the keyi, key)
705 orelse include_none andalso is_none keyi then
706 assoc pairs (pi @ result)
707 else assoc pairs result;
708 in assoc list [] end;
710 fun get_prods [] result = result
711 | get_prods (nt :: nts) result =
712 let val nt_prods = snd (Array.sub (prods, nt));
713 in get_prods nts ((token_assoc2 (nt_prods, tk)) @ result) end;
714 in get_prods (connected_with chains nts nts) [] end;
717 fun PROCESSS prods chains Estate i c states =
719 fun all_prods_for nt = prods_for prods chains true c [nt];
721 fun processS used [] (Si, Sii) = (Si, Sii)
722 | processS used (S :: States) (Si, Sii) =
724 (_, _, _, Nonterminal (nt, minPrec) :: _, _, _) =>
725 let (*predictor operation*)
726 val (used', new_states) =
727 (case assoc (used, nt) of
728 SOME (usedPrec, l) => (*nonterminal has been processed*)
729 if usedPrec <= minPrec then
730 (*wanted precedence has been processed*)
731 (used, movedot_lambda S l)
732 else (*wanted precedence hasn't been parsed yet*)
734 val tk_prods = all_prods_for nt;
736 val States' = mkStates i minPrec nt
737 (getRHS' minPrec usedPrec tk_prods);
738 in (update_prec (nt, minPrec) used,
739 movedot_lambda S l @ States')
742 | NONE => (*nonterminal is parsed for the first time*)
743 let val tk_prods = all_prods_for nt;
744 val States' = mkStates i minPrec nt
745 (getRHS minPrec tk_prods);
746 in ((nt, (minPrec, [])) :: used, States') end);
749 if not (!warned) andalso
750 length (new_states @ States) > (!branching_level) then
751 (warning "Currently parsed expression could be \
752 \extremely ambiguous.";
756 processS used' (new_states @ States) (S :: Si, Sii)
758 | (_, _, _, Terminal a :: _, _, _) => (*scanner operation*)
761 if matching_tokens (a, c) then movedot_term S c :: Sii else Sii)
762 | (A, prec, ts, [], id, j) => (*completer operation*)
763 let val tt = if id = "" then ts else [Node (id, ts)] in
764 if j = i then (*lambda production?*)
766 val (used', O) = update_trees used (A, (tt, prec));
770 let val Slist = getS A prec Si;
771 val States' = map (movedot_nonterm tt) Slist;
772 in processS used' (States' @ States) (S :: Si, Sii) end
774 if n >= prec then processS used' States (S :: Si, Sii)
776 let val Slist = getS' A prec n Si;
777 val States' = map (movedot_nonterm tt) Slist;
778 in processS used' (States' @ States) (S :: Si, Sii) end
781 let val Slist = getStates Estate i j A prec
782 in processS used (map (movedot_nonterm tt) Slist @ States)
786 in processS [] states ([], []) end;
789 fun syntax_error toks allowed =
792 if null toks then Pretty.str "Inner syntax error: unexpected end of input"
794 Pretty.block (Pretty.str "Inner syntax error at: \"" ::
795 Pretty.breaks (map (Pretty.str o str_of_token)
796 (rev (tl (rev toks)))) @
799 Pretty.strs ("Expected tokens: " :: map (quote o str_of_token) allowed);
801 error (Pretty.string_of (Pretty.blk (0, [msg, Pretty.fbrk, expected])))
804 fun produce prods chains stateset i indata prev_token =
805 (*prev_token is used for error messages*)
806 (case Array.sub (stateset, i) of
807 [] => let fun some_prods_for tk nt = prods_for prods chains false tk [nt];
809 (*test if tk is a lookahead for a given minimum precedence*)
810 fun reduction _ minPrec _ (Terminal _ :: _, _, prec:int) =
811 if prec >= minPrec then true
813 | reduction tk minPrec checked
814 (Nonterminal (nt, nt_prec) :: _, _, prec) =
815 if prec >= minPrec andalso not (nt mem checked) then
816 let val chained = connected_with chains [nt] [nt];
818 (reduction tk nt_prec (chained @ checked))
819 (some_prods_for tk nt)
823 (*compute a list of allowed starting tokens
824 for a list of nonterminals considering precedence*)
825 fun get_starts [] result = result
826 | get_starts ((nt, minPrec:int) :: nts) result =
827 let fun get [] result = result
828 | get ((SOME tk, prods) :: ps) result =
829 if not (null prods) andalso
830 exists (reduction tk minPrec [nt]) prods
831 then get ps (tk :: result)
833 | get ((NONE, _) :: ps) result = get ps result;
835 val (_, nt_prods) = Array.sub (prods, nt);
837 val chained = map (fn nt => (nt, minPrec))
839 in get_starts (chained @ nts)
840 ((get nt_prods []) union result)
844 mapfilter (fn (_, _, _, Nonterminal (a, prec) :: _, _, _) =>
845 SOME (a, prec) | _ => NONE)
846 (Array.sub (stateset, i-1));
848 distinct (get_starts nts [] @
849 (mapfilter (fn (_, _, _, Terminal a :: _, _, _) => SOME a
851 (Array.sub (stateset, i-1))));
852 in syntax_error (if prev_token = EndToken then indata
853 else prev_token :: indata) allowed
857 [] => Array.sub (stateset, i)
859 let val (si, sii) = PROCESSS prods chains stateset i c s;
860 in Array.update (stateset, i, si);
861 Array.update (stateset, i + 1, sii);
862 produce prods chains stateset (i + 1) cs c
866 fun get_trees l = mapfilter (fn (_, _, [pt], _, _, _) => SOME pt | _ => NONE)
869 fun earley prods tags chains startsymbol indata =
871 val start_tag = case Symtab.lookup (tags, startsymbol) of
873 | NONE => error ("parse: Unknown startsymbol " ^
875 val S0 = [(~1, 0, [], [Nonterminal (start_tag, 0), Terminal EndToken],
877 val s = length indata + 1;
878 val Estate = Array.array (s, []);
880 Array.update (Estate, 0, S0);
882 get_trees (produce prods chains Estate 0 indata EndToken)
886 fun parse (Gram {tags, prods, chains, ...}) start toks =
888 (case earley prods tags chains start toks of
889 [] => sys_error "parse: no parse trees"