replaced old_style infixes eq_set, subset, union, inter and variants by generic versions
1 (* Title: Pure/Syntax/parser.ML
2 Author: Carsten Clasohm, Sonia Mahjoub, and Markus Wenzel, TU Muenchen
4 General context-free parser for the inner syntax of terms, types, etc.
11 val extend_gram: gram -> SynExt.xprod list -> gram
12 val make_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 guess_infix_lr: gram -> string -> (string * bool * bool * int) option
20 val branching_level: int Unsynchronized.ref
23 structure Parser: PARSER =
31 type nt_tag = int; (*production for the NTs are stored in an array
32 so we can identify NTs by their index*)
34 datatype symb = Terminal of token
35 | Nonterminal of nt_tag * int; (*(tag, precedence)*)
37 type nt_gram = ((nt_tag list * token list) *
38 (token option * (symb list * string * int) list) list);
39 (*(([dependent_nts], [start_tokens]),
40 [(start_token, [(rhs, name, prio)])])*)
41 (*depent_nts is a list of all NTs whose lookahead
42 depends on this NT's lookahead*)
45 Gram of {nt_count: int, prod_count: int,
46 tags: nt_tag Symtab.table,
47 chains: (nt_tag * nt_tag list) list, (*[(to, [from])]*)
49 prods: nt_gram Array.array};
50 (*"tags" is used to map NT names (i.e. strings) to tags;
51 chain productions are not stored as normal productions
52 but instead as an entry in "chains";
53 lambda productions are stored as normal productions
54 and also as an entry in "lambdas"*)
56 val UnknownStart = eof; (*productions for which no starting token is
57 known yet are associated with this token*)
59 (* get all NTs that are connected with a list of NTs
60 (used for expanding chain list)*)
61 fun connected_with _ ([]: nt_tag list) relatives = relatives
62 | connected_with chains (root :: roots) relatives =
63 let val branches = subtract (op =) relatives (these (AList.lookup (op =) chains root));
64 in connected_with chains (branches @ roots) (branches @ relatives) end;
66 (* convert productions to grammar;
67 N.B. that the chains parameter has the form [(from, [to])];
68 prod_count is of type "int option" and is only updated if it is <> NONE*)
69 fun add_prods _ chains lambdas prod_count [] = (chains, lambdas, prod_count)
70 | add_prods prods chains lambdas prod_count
71 ((lhs, new_prod as (rhs, name, pri)) :: ps) =
73 val chain_from = case (pri, rhs) of (~1, [Nonterminal (id, ~1)]) => SOME id | _ => NONE;
75 (*store chain if it does not already exist*)
76 val (new_chain, chains') = case chain_from of NONE => (NONE, chains) | SOME from =>
77 let val old_tos = these (AList.lookup (op =) chains from) in
78 if member (op =) old_tos lhs then (NONE, chains)
79 else (SOME from, AList.update (op =) (from, insert (op =) lhs old_tos) chains)
82 (*propagate new chain in lookahead and lambda lists;
83 added_starts is used later to associate existing
84 productions with new starting tokens*)
85 val (added_starts, lambdas') =
86 if is_none new_chain then ([], lambdas) else
87 let (*lookahead of chain's source*)
88 val ((from_nts, from_tks), _) = Array.sub (prods, the new_chain);
90 (*copy from's lookahead to chain's destinations*)
91 fun copy_lookahead [] added = added
92 | copy_lookahead (to :: tos) added =
94 val ((to_nts, to_tks), ps) = Array.sub (prods, to);
96 val new_tks = subtract (op =) to_tks from_tks; (*added lookahead tokens*)
97 in Array.update (prods, to, ((to_nts, to_tks @ new_tks), ps));
98 copy_lookahead tos (if null new_tks then added
99 else (to, new_tks) :: added)
102 val tos = connected_with chains' [lhs] [lhs];
103 in (copy_lookahead tos [],
104 gen_union (op =) (if member (op =) lambdas lhs then tos else [], lambdas))
107 (*test if new production can produce lambda
108 (rhs must either be empty or only consist of lambda NTs)*)
109 val (new_lambda, lambdas') =
110 if forall (fn (Nonterminal (id, _)) => member (op =) lambdas' id
111 | (Terminal _) => false) rhs then
112 (true, gen_union (op =) (lambdas', connected_with chains' [lhs] [lhs]))
116 (*list optional terminal and all nonterminals on which the lookahead
117 of a production depends*)
118 fun lookahead_dependency _ [] nts = (NONE, nts)
119 | lookahead_dependency _ ((Terminal tk) :: _) nts = (SOME tk, nts)
120 | lookahead_dependency lambdas ((Nonterminal (nt, _)) :: symbs) nts =
121 if member (op =) lambdas nt then
122 lookahead_dependency lambdas symbs (nt :: nts)
123 else (NONE, nt :: nts);
125 (*get all known starting tokens for a nonterminal*)
126 fun starts_for_nt nt = snd (fst (Array.sub (prods, nt)));
128 val token_union = gen_union matching_tokens;
130 (*update prods, lookaheads, and lambdas according to new lambda NTs*)
131 val (added_starts', lambdas') =
133 (*propagate added lambda NT*)
134 fun propagate_lambda [] added_starts lambdas= (added_starts, lambdas)
135 | propagate_lambda (l :: ls) added_starts lambdas =
137 (*get lookahead for lambda NT*)
138 val ((dependent, l_starts), _) = Array.sub (prods, l);
140 (*check productions whose lookahead may depend on lambda NT*)
141 fun examine_prods [] add_lambda nt_dependencies added_tks
143 (add_lambda, nt_dependencies, added_tks, nt_prods)
144 | examine_prods ((p as (rhs, _, _)) :: ps) add_lambda
145 nt_dependencies added_tks nt_prods =
146 let val (tk, nts) = lookahead_dependency lambdas rhs [];
148 if member (op =) nts l then (*update production's lookahead*)
150 val new_lambda = is_none tk andalso gen_subset (op =) (nts, lambdas);
152 val new_tks = subtract (op =) l_starts
153 ((if is_some tk then [the tk] else []) @
154 Library.foldl token_union ([], map starts_for_nt nts));
156 val added_tks' = token_union (new_tks, added_tks);
158 val nt_dependencies' = gen_union (op =) (nts, nt_dependencies);
160 (*associate production with new starting tokens*)
161 fun copy ([]: token option list) nt_prods = nt_prods
162 | copy (tk :: tks) nt_prods =
163 let val old_prods = these (AList.lookup (op =) nt_prods tk);
165 val prods' = p :: old_prods;
167 |> AList.update (op =) (tk, prods')
172 let val new_opt_tks = map SOME new_tks;
173 in copy ((if new_lambda then [NONE] else []) @
174 new_opt_tks) nt_prods
176 in examine_prods ps (add_lambda orelse new_lambda)
177 nt_dependencies' added_tks' nt_prods'
179 else (*skip production*)
180 examine_prods ps add_lambda nt_dependencies
184 (*check each NT whose lookahead depends on new lambda NT*)
185 fun process_nts [] added_lambdas added_starts =
186 (added_lambdas, added_starts)
187 | process_nts (nt :: nts) added_lambdas added_starts =
189 val (lookahead as (old_nts, old_tks), nt_prods) =
190 Array.sub (prods, nt);
192 (*existing productions whose lookahead may depend on l*)
194 (these o AList.lookup (op =) nt_prods)
195 (SOME (hd l_starts handle Empty => UnknownStart));
197 (*add_lambda is true if an existing production of the nt
198 produces lambda due to the new lambda NT l*)
199 val (add_lambda, nt_dependencies, added_tks, nt_prods') =
200 examine_prods tk_prods false [] [] nt_prods;
202 val added_nts = subtract (op =) old_nts nt_dependencies;
205 if add_lambda then nt :: added_lambdas
207 in Array.update (prods, nt,
208 ((added_nts @ old_nts, old_tks @ added_tks),
210 (*N.B. that because the tks component
211 is used to access existing
212 productions we have to add new
213 tokens at the _end_ of the list*)
215 if null added_tks then
216 process_nts nts added_lambdas' added_starts
218 process_nts nts added_lambdas'
219 ((nt, added_tks) :: added_starts)
222 val (added_lambdas, added_starts') =
223 process_nts dependent [] added_starts;
225 val added_lambdas' = subtract (op =) lambdas added_lambdas;
226 in propagate_lambda (ls @ added_lambdas') added_starts'
227 (added_lambdas' @ lambdas)
229 in propagate_lambda (subtract (op =) lambdas lambdas') added_starts lambdas' end;
231 (*insert production into grammar*)
232 val (added_starts', prod_count') =
233 if is_some chain_from then (added_starts', prod_count) (*don't store chain production*)
235 (*lookahead tokens of new production and on which
236 NTs lookahead depends*)
237 val (start_tk, start_nts) = lookahead_dependency lambdas' rhs [];
239 val start_tks = Library.foldl token_union
240 (if is_some start_tk then [the start_tk] else [],
241 map starts_for_nt start_nts);
243 val opt_starts = (if new_lambda then [NONE]
244 else if null start_tks then [SOME UnknownStart]
245 else []) @ (map SOME start_tks);
247 (*add lhs NT to list of dependent NTs in lookahead*)
249 | add_nts (nt :: nts) =
250 let val ((old_nts, old_tks), ps) = Array.sub (prods, nt);
251 in if member (op =) old_nts lhs then ()
252 else Array.update (prods, nt, ((lhs :: old_nts, old_tks), ps))
255 (*add new start tokens to chained NTs' lookahead list;
256 also store new production for lhs NT*)
257 fun add_tks [] added prod_count = (added, prod_count)
258 | add_tks (nt :: nts) added prod_count =
260 val ((old_nts, old_tks), nt_prods) = Array.sub (prods, nt);
262 val new_tks = subtract matching_tokens old_tks start_tks;
264 (*store new production*)
265 fun store [] prods is_new =
266 (prods, if is_some prod_count andalso is_new then
267 Option.map (fn x => x+1) prod_count
268 else prod_count, is_new)
269 | store (tk :: tks) prods is_new =
270 let val tk_prods = (these o AList.lookup (op =) prods) tk;
272 (*if prod_count = NONE then we can assume that
273 grammar does not contain new production already*)
274 val (tk_prods', is_new') =
275 if is_some prod_count then
276 if member (op =) tk_prods new_prod then (tk_prods, false)
277 else (new_prod :: tk_prods, true)
278 else (new_prod :: tk_prods, true);
281 |> is_new' ? AList.update (op =) (tk: token option, tk_prods');
282 in store tks prods' (is_new orelse is_new') end;
284 val (nt_prods', prod_count', changed) =
285 if nt = lhs then store opt_starts nt_prods false
286 else (nt_prods, prod_count, false);
287 in if not changed andalso null new_tks then ()
288 else Array.update (prods, nt, ((old_nts, old_tks @ new_tks),
290 add_tks nts (if null new_tks then added
291 else (nt, new_tks) :: added) prod_count'
293 in add_nts start_nts;
294 add_tks (connected_with chains' [lhs] [lhs]) [] prod_count
297 (*associate productions with new lookaheads*)
300 (*propagate added start tokens*)
301 fun add_starts [] = ()
302 | add_starts ((changed_nt, new_tks) :: starts) =
304 (*token under which old productions which
305 depend on changed_nt could be stored*)
307 case find_first (not o member (op =) new_tks)
308 (starts_for_nt changed_nt) of
309 NONE => SOME UnknownStart
312 (*copy productions whose lookahead depends on changed_nt;
313 if key = SOME UnknownToken then tk_prods is used to hold
314 the productions not copied*)
315 fun update_prods [] result = result
316 | update_prods ((p as (rhs, _: string, _: nt_tag)) :: ps)
317 (tk_prods, nt_prods) =
319 (*lookahead dependency for production*)
320 val (tk, depends) = lookahead_dependency lambdas' rhs [];
322 (*test if this production has to be copied*)
323 val update = member (op =) depends changed_nt;
325 (*test if production could already be associated with
326 a member of new_tks*)
327 val lambda = length depends > 1 orelse
328 not (null depends) andalso is_some tk
329 andalso member (op =) new_tks (the tk);
331 (*associate production with new starting tokens*)
332 fun copy ([]: token list) nt_prods = nt_prods
333 | copy (tk :: tks) nt_prods =
335 val tk_prods = (these o AList.lookup (op =) nt_prods) (SOME tk);
338 if not lambda then p :: tk_prods
339 else insert (op =) p tk_prods;
340 (*if production depends on lambda NT we
341 have to look for duplicates*)
344 |> AList.update (op =) (SOME tk, tk_prods')
349 (tk_prods, copy new_tks nt_prods)
350 else if key = SOME UnknownStart then
351 (p :: tk_prods, nt_prods)
352 else (tk_prods, nt_prods);
353 in update_prods ps result end;
355 (*copy existing productions for new starting tokens*)
356 fun process_nts [] added = added
357 | process_nts (nt :: nts) added =
359 val (lookahead as (old_nts, old_tks), nt_prods) =
360 Array.sub (prods, nt);
362 val tk_prods = (these o AList.lookup (op =) nt_prods) key;
364 (*associate productions with new lookahead tokens*)
365 val (tk_prods', nt_prods') =
366 update_prods tk_prods ([], nt_prods);
370 |> (key = SOME UnknownStart) ? AList.update (op =) (key, tk_prods')
373 subtract matching_tokens old_tks new_tks;
374 in if null added_tks then
375 (Array.update (prods, nt, (lookahead, nt_prods'));
376 process_nts nts added)
378 (Array.update (prods, nt,
379 ((old_nts, added_tks @ old_tks), nt_prods'));
380 process_nts nts ((nt, added_tks) :: added))
383 val ((dependent, _), _) = Array.sub (prods, changed_nt);
384 in add_starts (starts @ (process_nts dependent [])) end;
385 in add_starts added_starts' end;
386 in add_prods prods chains' lambdas' prod_count ps end;
391 fun pretty_gram (Gram {tags, prods, chains, ...}) =
393 fun pretty_name name = [Pretty.str (name ^ " =")];
395 val nt_name = the o Inttab.lookup (Inttab.make (map swap (Symtab.dest tags)));
397 fun pretty_symb (Terminal (Token (Literal, s, _))) = Pretty.quote (Pretty.str s)
398 | pretty_symb (Terminal tok) = Pretty.str (str_of_token tok)
399 | pretty_symb (Nonterminal (tag, p)) =
400 Pretty.str (nt_name tag ^ "[" ^ signed_string_of_int p ^ "]");
402 fun pretty_const "" = []
403 | pretty_const c = [Pretty.str ("=> " ^ quote c)];
405 fun pretty_pri p = [Pretty.str ("(" ^ signed_string_of_int p ^ ")")];
407 fun pretty_prod name (symbs, const, pri) =
408 Pretty.block (Pretty.breaks (pretty_name name @
409 map pretty_symb symbs @ pretty_const const @ pretty_pri pri));
411 fun pretty_nt (name, tag) =
413 fun prod_of_chain from = ([Nonterminal (from, ~1)], "", ~1);
416 Library.foldl (gen_union op =) ([], map snd (snd (Array.sub (prods, tag)))) @
417 map prod_of_chain ((these o AList.lookup (op =) chains) tag);
418 in map (pretty_prod name) nt_prods end;
420 in maps pretty_nt (sort_wrt fst (Symtab.dest tags)) end;
423 (** Operations on gramars **)
425 (*The mother of all grammars*)
426 val empty_gram = Gram {nt_count = 0, prod_count = 0,
427 tags = Symtab.empty, chains = [], lambdas = [],
428 prods = Array.array (0, (([], []), []))};
431 (*Invert list of chain productions*)
432 fun inverse_chains [] result = result
433 | inverse_chains ((root, branches: nt_tag list) :: cs) result =
434 let fun add ([]: nt_tag list) result = result
435 | add (id :: ids) result =
436 let val old = (these o AList.lookup (op =) result) id;
437 in add ids (AList.update (op =) (id, root :: old) result) end;
438 in inverse_chains cs (add branches result) end;
441 (*Add productions to a grammar*)
442 fun extend_gram gram [] = gram
443 | extend_gram (Gram {nt_count, prod_count, tags, chains, lambdas, prods})
446 (*Get tag for existing nonterminal or create a new one*)
447 fun get_tag nt_count tags nt =
448 case Symtab.lookup tags nt of
449 SOME tag => (nt_count, tags, tag)
450 | NONE => (nt_count+1, Symtab.update_new (nt, nt_count) tags,
453 (*Convert symbols to the form used by the parser;
454 delimiters and predefined terms are stored as terminals,
455 nonterminals are converted to integer tags*)
456 fun symb_of [] nt_count tags result = (nt_count, tags, rev result)
457 | symb_of ((Delim s) :: ss) nt_count tags result =
458 symb_of ss nt_count tags (Terminal (Token (Literal, s, Position.no_range)) :: result)
459 | symb_of ((Argument (s, p)) :: ss) nt_count tags result =
461 val (nt_count', tags', new_symb) =
462 case predef_term s of
464 let val (nt_count', tags', s_tag) = get_tag nt_count tags s;
465 in (nt_count', tags', Nonterminal (s_tag, p)) end
466 | SOME tk => (nt_count, tags, Terminal tk);
467 in symb_of ss nt_count' tags' (new_symb :: result) end
468 | symb_of (_ :: ss) nt_count tags result =
469 symb_of ss nt_count tags result;
471 (*Convert list of productions by invoking symb_of for each of them*)
472 fun prod_of [] nt_count prod_count tags result =
473 (nt_count, prod_count, tags, result)
474 | prod_of ((XProd (lhs, xsymbs, const, pri)) :: ps)
475 nt_count prod_count tags result =
476 let val (nt_count', tags', lhs_tag) = get_tag nt_count tags lhs;
478 val (nt_count'', tags'', prods) =
479 symb_of xsymbs nt_count' tags' [];
480 in prod_of ps nt_count'' (prod_count+1) tags''
481 ((lhs_tag, (prods, const, pri)) :: result)
484 val (nt_count', prod_count', tags', xprods') =
485 prod_of xprods nt_count prod_count tags [];
487 (*Copy array containing productions of old grammar;
488 this has to be done to preserve the old grammar while being able
489 to change the array's content*)
491 let fun get_prod i = if i < nt_count then Array.sub (prods, i)
493 in Array.tabulate (nt_count', get_prod) end;
495 val fromto_chains = inverse_chains chains [];
497 (*Add new productions to old ones*)
498 val (fromto_chains', lambdas', _) =
499 add_prods prods' fromto_chains lambdas NONE xprods';
501 val chains' = inverse_chains fromto_chains' [];
502 in Gram {nt_count = nt_count', prod_count = prod_count', tags = tags',
503 chains = chains', lambdas = lambdas', prods = prods'}
506 val make_gram = extend_gram empty_gram;
509 (*Merge two grammars*)
510 fun merge_grams gram_a gram_b =
512 (*find out which grammar is bigger*)
513 val (Gram {nt_count = nt_count1, prod_count = prod_count1, tags = tags1,
514 chains = chains1, lambdas = lambdas1, prods = prods1},
515 Gram {nt_count = nt_count2, prod_count = prod_count2, tags = tags2,
516 chains = chains2, lambdas = lambdas2, prods = prods2}) =
517 let val Gram {prod_count = count_a, ...} = gram_a;
518 val Gram {prod_count = count_b, ...} = gram_b;
519 in if count_a > count_b then (gram_a, gram_b)
520 else (gram_b, gram_a)
523 (*get existing tag from grammar1 or create a new one*)
524 fun get_tag nt_count tags nt =
525 case Symtab.lookup tags nt of
526 SOME tag => (nt_count, tags, tag)
527 | NONE => (nt_count+1, Symtab.update_new (nt, nt_count) tags,
530 val ((nt_count1', tags1'), tag_table) =
531 let val tag_list = Symtab.dest tags2;
533 val table = Array.array (nt_count2, ~1);
535 fun store_tag nt_count tags ~1 = (nt_count, tags)
536 | store_tag nt_count tags tag =
537 let val (nt_count', tags', tag') =
538 get_tag nt_count tags
539 (fst (the (find_first (fn (n, t) => t = tag) tag_list)));
540 in Array.update (table, tag, tag');
541 store_tag nt_count' tags' (tag-1)
543 in (store_tag nt_count1 tags1 (nt_count2-1), table) end;
545 (*convert grammar2 tag to grammar1 tag*)
546 fun convert_tag tag = Array.sub (tag_table, tag);
548 (*convert chain list to raw productions*)
549 fun mk_chain_prods [] result = result
550 | mk_chain_prods ((to, froms) :: cs) result =
552 val to_tag = convert_tag to;
554 fun make [] result = result
555 | make (from :: froms) result = make froms ((to_tag,
556 ([Nonterminal (convert_tag from, ~1)], "", ~1)) :: result);
557 in mk_chain_prods cs (make froms [] @ result) end;
559 val chain_prods = mk_chain_prods chains2 [];
561 (*convert prods2 array to productions*)
562 fun process_nt ~1 result = result
563 | process_nt nt result =
565 val nt_prods = Library.foldl (gen_union op =)
566 ([], map snd (snd (Array.sub (prods2, nt))));
567 val lhs_tag = convert_tag nt;
569 (*convert tags in rhs*)
570 fun process_rhs [] result = result
571 | process_rhs (Terminal tk :: rhs) result =
572 process_rhs rhs (result @ [Terminal tk])
573 | process_rhs (Nonterminal (nt, prec) :: rhs) result =
575 (result @ [Nonterminal (convert_tag nt, prec)]);
577 (*convert tags in productions*)
578 fun process_prods [] result = result
579 | process_prods ((rhs, id, prec) :: ps) result =
580 process_prods ps ((lhs_tag, (process_rhs rhs [], id, prec))
582 in process_nt (nt-1) (process_prods nt_prods [] @ result) end;
584 val raw_prods = chain_prods @ process_nt (nt_count2-1) [];
587 let fun get_prod i = if i < nt_count1 then Array.sub (prods1, i)
589 in Array.tabulate (nt_count1', get_prod) end;
591 val fromto_chains = inverse_chains chains1 [];
593 val (fromto_chains', lambdas', SOME prod_count1') =
594 add_prods prods1' fromto_chains lambdas1 (SOME prod_count1) raw_prods;
596 val chains' = inverse_chains fromto_chains' [];
597 in Gram {nt_count = nt_count1', prod_count = prod_count1',
598 tags = tags1', chains = chains', lambdas = lambdas',
606 Node of string * parsetree list |
610 nt_tag * int * (*identification and production precedence*)
611 parsetree list * (*already parsed nonterminals on rhs*)
612 symb list * (*rest of rhs*)
613 string * (*name of production*)
614 int; (*index for previous state list*)
617 (*Get all rhss with precedence >= minPrec*)
618 fun getRHS minPrec = List.filter (fn (_, _, prec:int) => prec >= minPrec);
620 (*Get all rhss with precedence >= minPrec and < maxPrec*)
621 fun getRHS' minPrec maxPrec =
622 List.filter (fn (_, _, prec:int) => prec >= minPrec andalso prec < maxPrec);
624 (*Make states using a list of rhss*)
625 fun mkStates i minPrec lhsID rhss =
626 let fun mkState (rhs, id, prodPrec) = (lhsID, prodPrec, [], rhs, id, i);
627 in map mkState rhss end;
629 (*Add parse tree to list and eliminate duplicates
630 saving the maximum precedence*)
631 fun conc (t: parsetree list, prec:int) [] = (NONE, [(t, prec)])
632 | conc (t, prec) ((t', prec') :: ts) =
634 (SOME prec', if prec' >= prec then (t', prec') :: ts
635 else (t, prec) :: ts)
637 let val (n, ts') = conc (t, prec) ts
638 in (n, (t', prec') :: ts') end;
640 (*Update entry in used*)
641 fun update_trees ((B: nt_tag, (i, ts)) :: used) (A, t) =
643 let val (n, ts') = conc t ts
644 in ((A, (i, ts')) :: used, n) end
646 let val (used', n) = update_trees used (A, t)
647 in ((B, (i, ts)) :: used', n) end;
649 (*Replace entry in used*)
650 fun update_prec (A: nt_tag, prec) used =
651 let fun update ((hd as (B, (_, ts))) :: used, used') =
653 then used' @ ((A, (prec, ts)) :: used)
654 else update (used, hd :: used')
655 in update (used, []) end;
657 fun getS A maxPrec Si =
659 (fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
660 => A = B andalso prec <= maxPrec
663 fun getS' A maxPrec minPrec Si =
665 (fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
666 => A = B andalso prec > minPrec andalso prec <= maxPrec
669 fun getStates Estate i ii A maxPrec =
671 (fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
672 => A = B andalso prec <= maxPrec
674 (Array.sub (Estate, ii));
677 fun movedot_term (A, j, ts, Terminal a :: sa, id, i) c =
678 if valued_token c then
679 (A, j, ts @ [Tip c], sa, id, i)
680 else (A, j, ts, sa, id, i);
682 fun movedot_nonterm ts (A, j, tss, Nonterminal _ :: sa, id, i) =
683 (A, j, tss @ ts, sa, id, i);
685 fun movedot_lambda _ [] = []
686 | movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ((t, ki) :: ts) =
688 (B, j, tss @ t, sa, id, i) ::
689 movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ts
690 else movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ts;
693 val branching_level = Unsynchronized.ref 600; (*trigger value for warnings*)
695 (*get all productions of a NT and NTs chained to it which can
696 be started by specified token*)
697 fun prods_for prods chains include_none tk nts =
699 fun token_assoc (list, key) =
700 let fun assoc [] result = result
701 | assoc ((keyi, pi) :: pairs) result =
702 if is_some keyi andalso matching_tokens (the keyi, key)
703 orelse include_none andalso is_none keyi then
704 assoc pairs (pi @ result)
705 else assoc pairs result;
706 in assoc list [] end;
708 fun get_prods [] result = result
709 | get_prods (nt :: nts) result =
710 let val nt_prods = snd (Array.sub (prods, nt));
711 in get_prods nts ((token_assoc (nt_prods, tk)) @ result) end;
712 in get_prods (connected_with chains nts nts) [] end;
715 fun PROCESSS warned prods chains Estate i c states =
717 fun all_prods_for nt = prods_for prods chains true c [nt];
719 fun processS used [] (Si, Sii) = (Si, Sii)
720 | processS used (S :: States) (Si, Sii) =
722 (_, _, _, Nonterminal (nt, minPrec) :: _, _, _) =>
723 let (*predictor operation*)
724 val (used', new_states) =
725 (case AList.lookup (op =) used nt of
726 SOME (usedPrec, l) => (*nonterminal has been processed*)
727 if usedPrec <= minPrec then
728 (*wanted precedence has been processed*)
729 (used, movedot_lambda S l)
730 else (*wanted precedence hasn't been parsed yet*)
732 val tk_prods = all_prods_for nt;
734 val States' = mkStates i minPrec nt
735 (getRHS' minPrec usedPrec tk_prods);
736 in (update_prec (nt, minPrec) used,
737 movedot_lambda S l @ States')
740 | NONE => (*nonterminal is parsed for the first time*)
741 let val tk_prods = all_prods_for nt;
742 val States' = mkStates i minPrec nt
743 (getRHS minPrec tk_prods);
744 in ((nt, (minPrec, [])) :: used, States') end);
747 if not (!warned) andalso
748 length (new_states @ States) > (!branching_level) then
749 (warning "Currently parsed expression could be extremely ambiguous.";
753 processS used' (new_states @ States) (S :: Si, Sii)
755 | (_, _, _, Terminal a :: _, _, _) => (*scanner operation*)
758 if matching_tokens (a, c) then movedot_term S c :: Sii else Sii)
759 | (A, prec, ts, [], id, j) => (*completer operation*)
760 let val tt = if id = "" then ts else [Node (id, ts)] in
761 if j = i then (*lambda production?*)
763 val (used', O) = update_trees used (A, (tt, prec));
767 let val Slist = getS A prec Si;
768 val States' = map (movedot_nonterm tt) Slist;
769 in processS used' (States' @ States) (S :: Si, Sii) end
771 if n >= prec then processS used' States (S :: Si, Sii)
773 let val Slist = getS' A prec n Si;
774 val States' = map (movedot_nonterm tt) Slist;
775 in processS used' (States' @ States) (S :: Si, Sii) end
778 let val Slist = getStates Estate i j A prec
779 in processS used (map (movedot_nonterm tt) Slist @ States)
783 in processS [] states ([], []) end;
786 fun produce warned prods tags chains stateset i indata prev_token =
787 (case Array.sub (stateset, i) of
790 val toks = if is_eof prev_token then indata else prev_token :: indata;
791 val pos = Position.str_of (pos_of_token prev_token);
793 if null toks then error ("Inner syntax error: unexpected end of input" ^ pos)
794 else error (Pretty.string_of (Pretty.block
795 (Pretty.str ("Inner syntax error" ^ pos ^ " at \"") ::
796 Pretty.breaks (map (Pretty.str o str_of_token) (#1 (split_last toks))) @
801 [] => Array.sub (stateset, i)
803 let val (si, sii) = PROCESSS warned prods chains stateset i c s;
804 in Array.update (stateset, i, si);
805 Array.update (stateset, i + 1, sii);
806 produce warned prods tags chains stateset (i + 1) cs c
810 fun get_trees l = map_filter (fn (_, _, [pt], _, _, _) => SOME pt | _ => NONE)
813 fun earley prods tags chains startsymbol indata =
815 val start_tag = case Symtab.lookup tags startsymbol of
817 | NONE => error ("parse: Unknown startsymbol " ^
819 val S0 = [(~1, 0, [], [Nonterminal (start_tag, 0), Terminal eof], "", 0)];
820 val s = length indata + 1;
821 val Estate = Array.array (s, []);
823 Array.update (Estate, 0, S0);
824 get_trees (produce (Unsynchronized.ref false) prods tags chains Estate 0 indata eof)
828 fun parse (Gram {tags, prods, chains, ...}) start toks =
831 (case try List.last toks of
832 NONE => Position.none
833 | SOME (Token (_, _, (_, end_pos))) => end_pos);
835 (case earley prods tags chains start (toks @ [mk_eof end_pos]) of
836 [] => sys_error "parse: no parse trees"
841 fun guess_infix_lr (Gram gram) c = (*based on educated guess*)
843 fun freeze a = map (curry Array.sub a) (0 upto Array.length a - 1);
844 val prods = maps snd (maps snd (freeze (#prods gram)));
845 fun guess (SOME ([Nonterminal (_, k), Terminal (Token (Literal, s, _)), Nonterminal (_, l)], _, j)) =
846 if k = j andalso l = j + 1 then SOME (s, true, false, j)
847 else if k = j + 1 then if l = j then SOME (s, false, true, j)
848 else if l = j + 1 then SOME (s, false, false, j)
852 in guess (find_first (fn (_, s, _) => s = c) prods) end;