(* Title: Pure/Syntax/parser.ML ID: $Id: parser.ML,v 1.48 2005/09/15 15:17:00 wenzelm Exp $ Author: Carsten Clasohm, Sonia Mahjoub, and Markus Wenzel, TU Muenchen General context-free parser for the inner syntax of terms, types, etc. *) signature PARSER = sig type gram val empty_gram: gram val extend_gram: gram -> SynExt.xprod list -> gram val make_gram: SynExt.xprod list -> gram val merge_grams: gram -> gram -> gram val pretty_gram: gram -> Pretty.T list datatype parsetree = Node of string * parsetree list | Tip of Lexicon.token val parse: gram -> string -> Lexicon.token list -> parsetree list val branching_level: int ref end; structure Parser: PARSER = struct open Lexicon SynExt; (** datatype gram **) type nt_tag = int; (*production for the NTs are stored in an array so we can identify NTs by their index*) datatype symb = Terminal of token | Nonterminal of nt_tag * int; (*(tag, precedence)*) type nt_gram = ((nt_tag list * token list) * (token option * (symb list * string * int) list) list); (*(([dependent_nts], [start_tokens]), [(start_token, [(rhs, name, prio)])])*) (*depent_nts is a list of all NTs whose lookahead depends on this NT's lookahead*) datatype gram = Gram of {nt_count: int, prod_count: int, tags: nt_tag Symtab.table, chains: (nt_tag * nt_tag list) list, (*[(to, [from])]*) lambdas: nt_tag list, prods: nt_gram Array.array}; (*"tags" is used to map NT names (i.e. strings) to tags; chain productions are not stored as normal productions but instead as an entry in "chains"; lambda productions are stored as normal productions and also as an entry in "lambdas"*) val UnknownStart = EndToken; (*productions for which no starting token is known yet are associated with this token*) (* get all NTs that are connected with a list of NTs (used for expanding chain list)*) fun connected_with _ [] relatives = relatives | connected_with chains (root :: roots) relatives = let val branches = these (AList.lookup (op =) chains root) \\ relatives; in connected_with chains (branches @ roots) (branches @ relatives) end; (* convert productions to grammar; N.B. that the chains parameter has the form [(from, [to])]; prod_count is of type "int option" and is only updated if it is <> NONE*) fun add_prods _ chains lambdas prod_count [] = (chains, lambdas, prod_count) | add_prods prods chains lambdas prod_count ((lhs, new_prod as (rhs, name, pri)) :: ps) = let val chain_from = case (pri, rhs) of (~1, [Nonterminal (id, ~1)]) => SOME id | _ => NONE; (*store chain if it does not already exist*) val (new_chain, chains') = case chain_from of NONE => (NONE, chains) | SOME from => let val old_tos = these (AList.lookup (op =) chains from) in if lhs mem old_tos then (NONE, chains) else (SOME from, AList.update (op =) (from, lhs ins old_tos) chains) end; (*propagate new chain in lookahead and lambda lists; added_starts is used later to associate existing productions with new starting tokens*) val (added_starts, lambdas') = if is_none new_chain then ([], lambdas) else let (*lookahead of chain's source*) val ((from_nts, from_tks), _) = Array.sub (prods, the new_chain); (*copy from's lookahead to chain's destinations*) fun copy_lookahead [] added = added | copy_lookahead (to :: tos) added = let val ((to_nts, to_tks), ps) = Array.sub (prods, to); val new_tks = from_tks \\ to_tks; (*added lookahead tokens*) in Array.update (prods, to, ((to_nts, to_tks @ new_tks), ps)); copy_lookahead tos (if null new_tks then added else (to, new_tks) :: added) end; val tos = connected_with chains' [lhs] [lhs]; in (copy_lookahead tos [], (if lhs mem lambdas then tos else []) union lambdas) end; (*test if new production can produce lambda (rhs must either be empty or only consist of lambda NTs)*) val (new_lambda, lambdas') = if forall (fn (Nonterminal (id, _)) => id mem lambdas' | (Terminal _) => false) rhs then (true, lambdas' union (connected_with chains' [lhs] [lhs])) else (false, lambdas'); (*list optional terminal and all nonterminals on which the lookahead of a production depends*) fun lookahead_dependency _ [] nts = (NONE, nts) | lookahead_dependency _ ((Terminal tk) :: _) nts = (SOME tk, nts) | lookahead_dependency lambdas ((Nonterminal (nt, _)) :: symbs) nts = if nt mem lambdas then lookahead_dependency lambdas symbs (nt :: nts) else (NONE, nt :: nts); (*get all known starting tokens for a nonterminal*) fun starts_for_nt nt = snd (fst (Array.sub (prods, nt))); val token_union = gen_union matching_tokens; (*update prods, lookaheads, and lambdas according to new lambda NTs*) val (added_starts', lambdas') = let (*propagate added lambda NT*) fun propagate_lambda [] added_starts lambdas= (added_starts, lambdas) | propagate_lambda (l :: ls) added_starts lambdas = let (*get lookahead for lambda NT*) val ((dependent, l_starts), _) = Array.sub (prods, l); (*check productions whose lookahead may depend on lambda NT*) fun examine_prods [] add_lambda nt_dependencies added_tks nt_prods = (add_lambda, nt_dependencies, added_tks, nt_prods) | examine_prods ((p as (rhs, _, _)) :: ps) add_lambda nt_dependencies added_tks nt_prods = let val (tk, nts) = lookahead_dependency lambdas rhs []; in if l mem nts then (*update production's lookahead*) let val new_lambda = is_none tk andalso nts subset lambdas; val new_tks = (if is_some tk then [the tk] else []) @ Library.foldl token_union ([], map starts_for_nt nts) \\ l_starts; val added_tks' = token_union (new_tks, added_tks); val nt_dependencies' = nts union nt_dependencies; (*associate production with new starting tokens*) fun copy [] nt_prods = nt_prods | copy (tk :: tks) nt_prods = let val old_prods = these (AList.lookup (op =) nt_prods tk); val prods' = p :: old_prods; in nt_prods |> AList.update (op =) (tk, prods') |> copy tks end; val nt_prods' = let val new_opt_tks = map SOME new_tks; in copy ((if new_lambda then [NONE] else []) @ new_opt_tks) nt_prods end; in examine_prods ps (add_lambda orelse new_lambda) nt_dependencies' added_tks' nt_prods' end else (*skip production*) examine_prods ps add_lambda nt_dependencies added_tks nt_prods end; (*check each NT whose lookahead depends on new lambda NT*) fun process_nts [] added_lambdas added_starts = (added_lambdas, added_starts) | process_nts (nt :: nts) added_lambdas added_starts = let val (lookahead as (old_nts, old_tks), nt_prods) = Array.sub (prods, nt); (*existing productions whose lookahead may depend on l*) val tk_prods = (these o AList.lookup (op =) nt_prods) (SOME (hd l_starts handle Empty => UnknownStart)); (*add_lambda is true if an existing production of the nt produces lambda due to the new lambda NT l*) val (add_lambda, nt_dependencies, added_tks, nt_prods') = examine_prods tk_prods false [] [] nt_prods; val added_nts = nt_dependencies \\ old_nts; val added_lambdas' = if add_lambda then nt :: added_lambdas else added_lambdas; in Array.update (prods, nt, ((added_nts @ old_nts, old_tks @ added_tks), nt_prods')); (*N.B. that because the tks component is used to access existing productions we have to add new tokens at the _end_ of the list*) if null added_tks then process_nts nts added_lambdas' added_starts else process_nts nts added_lambdas' ((nt, added_tks) :: added_starts) end; val (added_lambdas, added_starts') = process_nts dependent [] added_starts; val added_lambdas' = added_lambdas \\ lambdas; in propagate_lambda (ls @ added_lambdas') added_starts' (added_lambdas' @ lambdas) end; in propagate_lambda (lambdas' \\ lambdas) added_starts lambdas' end; (*insert production into grammar*) val (added_starts', prod_count') = if is_some chain_from then (added_starts', prod_count) (*don't store chain production*) else let (*lookahead tokens of new production and on which NTs lookahead depends*) val (start_tk, start_nts) = lookahead_dependency lambdas' rhs []; val start_tks = Library.foldl token_union (if is_some start_tk then [the start_tk] else [], map starts_for_nt start_nts); val opt_starts = (if new_lambda then [NONE] else if null start_tks then [SOME UnknownStart] else []) @ (map SOME start_tks); (*add lhs NT to list of dependent NTs in lookahead*) fun add_nts [] = () | add_nts (nt :: nts) = let val ((old_nts, old_tks), ps) = Array.sub (prods, nt); in if lhs mem old_nts then () else Array.update (prods, nt, ((lhs :: old_nts, old_tks), ps)) end; (*add new start tokens to chained NTs' lookahead list; also store new production for lhs NT*) fun add_tks [] added prod_count = (added, prod_count) | add_tks (nt :: nts) added prod_count = let val ((old_nts, old_tks), nt_prods) = Array.sub (prods, nt); val new_tks = gen_rems matching_tokens (start_tks, old_tks); (*store new production*) fun store [] prods is_new = (prods, if is_some prod_count andalso is_new then Option.map (fn x => x+1) prod_count else prod_count, is_new) | store (tk :: tks) prods is_new = let val tk_prods = (these o AList.lookup (op =) prods) tk; (*if prod_count = NONE then we can assume that grammar does not contain new production already*) val (tk_prods', is_new') = if is_some prod_count then if new_prod mem tk_prods then (tk_prods, false) else (new_prod :: tk_prods, true) else (new_prod :: tk_prods, true); val prods' = prods |> K is_new' ? AList.update (op =) (tk, tk_prods'); in store tks prods' (is_new orelse is_new') end; val (nt_prods', prod_count', changed) = if nt = lhs then store opt_starts nt_prods false else (nt_prods, prod_count, false); in if not changed andalso null new_tks then () else Array.update (prods, nt, ((old_nts, old_tks @ new_tks), nt_prods')); add_tks nts (if null new_tks then added else (nt, new_tks) :: added) prod_count' end; in add_nts start_nts; add_tks (connected_with chains' [lhs] [lhs]) [] prod_count end; (*associate productions with new lookaheads*) val dummy = let (*propagate added start tokens*) fun add_starts [] = () | add_starts ((changed_nt, new_tks) :: starts) = let (*token under which old productions which depend on changed_nt could be stored*) val key = case find_first (fn t => not (t mem new_tks)) (starts_for_nt changed_nt) of NONE => SOME UnknownStart | t => t; (*copy productions whose lookahead depends on changed_nt; if key = SOME UnknownToken then tk_prods is used to hold the productions not copied*) fun update_prods [] result = result | update_prods ((p as (rhs, _, _)) :: ps) (tk_prods, nt_prods) = let (*lookahead dependency for production*) val (tk, depends) = lookahead_dependency lambdas' rhs []; (*test if this production has to be copied*) val update = changed_nt mem depends; (*test if production could already be associated with a member of new_tks*) val lambda = length depends > 1 orelse not (null depends) andalso is_some tk andalso the tk mem new_tks; (*associate production with new starting tokens*) fun copy [] nt_prods = nt_prods | copy (tk :: tks) nt_prods = let val tk_prods = (these o AList.lookup (op =) nt_prods) (SOME tk); val tk_prods' = if not lambda then p :: tk_prods else p ins tk_prods; (*if production depends on lambda NT we have to look for duplicates*) in nt_prods |> AList.update (op =) (SOME tk, tk_prods') |> copy tks end; val result = if update then (tk_prods, copy new_tks nt_prods) else if key = SOME UnknownStart then (p :: tk_prods, nt_prods) else (tk_prods, nt_prods); in update_prods ps result end; (*copy existing productions for new starting tokens*) fun process_nts [] added = added | process_nts (nt :: nts) added = let val (lookahead as (old_nts, old_tks), nt_prods) = Array.sub (prods, nt); val tk_prods = (these o AList.lookup (op =) nt_prods) key; (*associate productions with new lookahead tokens*) val (tk_prods', nt_prods') = update_prods tk_prods ([], nt_prods); val nt_prods' = nt_prods' |> (K (key = SOME UnknownStart)) ? AList.update (op =) (key, tk_prods') val added_tks = gen_rems matching_tokens (new_tks, old_tks); in if null added_tks then (Array.update (prods, nt, (lookahead, nt_prods')); process_nts nts added) else (Array.update (prods, nt, ((old_nts, added_tks @ old_tks), nt_prods')); process_nts nts ((nt, added_tks) :: added)) end; val ((dependent, _), _) = Array.sub (prods, changed_nt); in add_starts (starts @ (process_nts dependent [])) end; in add_starts added_starts' end; in add_prods prods chains' lambdas' prod_count ps end; (* pretty_gram *) fun pretty_gram (Gram {tags, prods, chains, ...}) = let fun pretty_name name = [Pretty.str (name ^ " =")]; val taglist = Symtab.dest tags; fun pretty_symb (Terminal (Token s)) = Pretty.quote (Pretty.str s) | pretty_symb (Terminal tok) = Pretty.str (str_of_token tok) | pretty_symb (Nonterminal (tag, p)) = let val name = fst (the (find_first (fn (n, t) => t = tag) taglist)); in Pretty.str (name ^ "[" ^ string_of_int p ^ "]") end; fun pretty_const "" = [] | pretty_const c = [Pretty.str ("=> " ^ Library.quote c)]; fun pretty_pri p = [Pretty.str ("(" ^ string_of_int p ^ ")")]; fun pretty_prod name (symbs, const, pri) = Pretty.block (Pretty.breaks (pretty_name name @ map pretty_symb symbs @ pretty_const const @ pretty_pri pri)); fun pretty_nt (name, tag) = let fun prod_of_chain from = ([Nonterminal (from, ~1)], "", ~1); val nt_prods = Library.foldl (op union) ([], map snd (snd (Array.sub (prods, tag)))) @ map prod_of_chain ((these o AList.lookup (op =) chains) tag); in map (pretty_prod name) nt_prods end; in List.concat (map pretty_nt taglist) end; (** Operations on gramars **) (*The mother of all grammars*) val empty_gram = Gram {nt_count = 0, prod_count = 0, tags = Symtab.empty, chains = [], lambdas = [], prods = Array.array (0, (([], []), []))}; (*Invert list of chain productions*) fun inverse_chains [] result = result | inverse_chains ((root, branches) :: cs) result = let fun add [] result = result | add (id :: ids) result = let val old = (these o AList.lookup (op =) result) id; in add ids (AList.update (op =) (id, root :: old) result) end; in inverse_chains cs (add branches result) end; (*Add productions to a grammar*) fun extend_gram gram [] = gram | extend_gram (Gram {nt_count, prod_count, tags, chains, lambdas, prods}) xprods = let (*Get tag for existing nonterminal or create a new one*) fun get_tag nt_count tags nt = case Symtab.lookup tags nt of SOME tag => (nt_count, tags, tag) | NONE => (nt_count+1, Symtab.update_new (nt, nt_count) tags, nt_count); (*Convert symbols to the form used by the parser; delimiters and predefined terms are stored as terminals, nonterminals are converted to integer tags*) fun symb_of [] nt_count tags result = (nt_count, tags, rev result) | symb_of ((Delim s) :: ss) nt_count tags result = symb_of ss nt_count tags ((Terminal (Token s)) :: result) | symb_of ((Argument (s, p)) :: ss) nt_count tags result = let val (nt_count', tags', new_symb) = case predef_term s of NONE => let val (nt_count', tags', s_tag) = get_tag nt_count tags s; in (nt_count', tags', Nonterminal (s_tag, p)) end | SOME tk => (nt_count, tags, Terminal tk); in symb_of ss nt_count' tags' (new_symb :: result) end | symb_of (_ :: ss) nt_count tags result = symb_of ss nt_count tags result; (*Convert list of productions by invoking symb_of for each of them*) fun prod_of [] nt_count prod_count tags result = (nt_count, prod_count, tags, result) | prod_of ((XProd (lhs, xsymbs, const, pri)) :: ps) nt_count prod_count tags result = let val (nt_count', tags', lhs_tag) = get_tag nt_count tags lhs; val (nt_count'', tags'', prods) = symb_of xsymbs nt_count' tags' []; in prod_of ps nt_count'' (prod_count+1) tags'' ((lhs_tag, (prods, const, pri)) :: result) end; val (nt_count', prod_count', tags', xprods') = prod_of xprods nt_count prod_count tags []; (*Copy array containing productions of old grammar; this has to be done to preserve the old grammar while being able to change the array's content*) val prods' = let fun get_prod i = if i < nt_count then Array.sub (prods, i) else (([], []), []); in Array.tabulate (nt_count', get_prod) end; val fromto_chains = inverse_chains chains []; (*Add new productions to old ones*) val (fromto_chains', lambdas', _) = add_prods prods' fromto_chains lambdas NONE xprods'; val chains' = inverse_chains fromto_chains' []; in Gram {nt_count = nt_count', prod_count = prod_count', tags = tags', chains = chains', lambdas = lambdas', prods = prods'} end; val make_gram = extend_gram empty_gram; (*Merge two grammars*) fun merge_grams gram_a gram_b = let (*find out which grammar is bigger*) val (Gram {nt_count = nt_count1, prod_count = prod_count1, tags = tags1, chains = chains1, lambdas = lambdas1, prods = prods1}, Gram {nt_count = nt_count2, prod_count = prod_count2, tags = tags2, chains = chains2, lambdas = lambdas2, prods = prods2}) = let val Gram {prod_count = count_a, ...} = gram_a; val Gram {prod_count = count_b, ...} = gram_b; in if count_a > count_b then (gram_a, gram_b) else (gram_b, gram_a) end; (*get existing tag from grammar1 or create a new one*) fun get_tag nt_count tags nt = case Symtab.lookup tags nt of SOME tag => (nt_count, tags, tag) | NONE => (nt_count+1, Symtab.update_new (nt, nt_count) tags, nt_count) val ((nt_count1', tags1'), tag_table) = let val tag_list = Symtab.dest tags2; val table = Array.array (nt_count2, ~1); fun store_tag nt_count tags ~1 = (nt_count, tags) | store_tag nt_count tags tag = let val (nt_count', tags', tag') = get_tag nt_count tags (fst (the (find_first (fn (n, t) => t = tag) tag_list))); in Array.update (table, tag, tag'); store_tag nt_count' tags' (tag-1) end; in (store_tag nt_count1 tags1 (nt_count2-1), table) end; (*convert grammar2 tag to grammar1 tag*) fun convert_tag tag = Array.sub (tag_table, tag); (*convert chain list to raw productions*) fun mk_chain_prods [] result = result | mk_chain_prods ((to, froms) :: cs) result = let val to_tag = convert_tag to; fun make [] result = result | make (from :: froms) result = make froms ((to_tag, ([Nonterminal (convert_tag from, ~1)], "", ~1)) :: result); in mk_chain_prods cs (make froms [] @ result) end; val chain_prods = mk_chain_prods chains2 []; (*convert prods2 array to productions*) fun process_nt ~1 result = result | process_nt nt result = let val nt_prods = Library.foldl (op union) ([], map snd (snd (Array.sub (prods2, nt)))); val lhs_tag = convert_tag nt; (*convert tags in rhs*) fun process_rhs [] result = result | process_rhs (Terminal tk :: rhs) result = process_rhs rhs (result @ [Terminal tk]) | process_rhs (Nonterminal (nt, prec) :: rhs) result = process_rhs rhs (result @ [Nonterminal (convert_tag nt, prec)]); (*convert tags in productions*) fun process_prods [] result = result | process_prods ((rhs, id, prec) :: ps) result = process_prods ps ((lhs_tag, (process_rhs rhs [], id, prec)) :: result); in process_nt (nt-1) (process_prods nt_prods [] @ result) end; val raw_prods = chain_prods @ process_nt (nt_count2-1) []; val prods1' = let fun get_prod i = if i < nt_count1 then Array.sub (prods1, i) else (([], []), []); in Array.tabulate (nt_count1', get_prod) end; val fromto_chains = inverse_chains chains1 []; val (fromto_chains', lambdas', SOME prod_count1') = add_prods prods1' fromto_chains lambdas1 (SOME prod_count1) raw_prods; val chains' = inverse_chains fromto_chains' []; in Gram {nt_count = nt_count1', prod_count = prod_count1', tags = tags1', chains = chains', lambdas = lambdas', prods = prods1'} end; (** Parser **) datatype parsetree = Node of string * parsetree list | Tip of token; type state = nt_tag * int * (*identification and production precedence*) parsetree list * (*already parsed nonterminals on rhs*) symb list * (*rest of rhs*) string * (*name of production*) int; (*index for previous state list*) (*Get all rhss with precedence >= minPrec*) fun getRHS minPrec = List.filter (fn (_, _, prec:int) => prec >= minPrec); (*Get all rhss with precedence >= minPrec and < maxPrec*) fun getRHS' minPrec maxPrec = List.filter (fn (_, _, prec:int) => prec >= minPrec andalso prec < maxPrec); (*Make states using a list of rhss*) fun mkStates i minPrec lhsID rhss = let fun mkState (rhs, id, prodPrec) = (lhsID, prodPrec, [], rhs, id, i); in map mkState rhss end; (*Add parse tree to list and eliminate duplicates saving the maximum precedence*) fun conc (t: parsetree list, prec:int) [] = (NONE, [(t, prec)]) | conc (t, prec) ((t', prec') :: ts) = if t = t' then (SOME prec', if prec' >= prec then (t', prec') :: ts else (t, prec) :: ts) else let val (n, ts') = conc (t, prec) ts in (n, (t', prec') :: ts') end; (*Update entry in used*) fun update_trees ((B: nt_tag, (i, ts)) :: used) (A, t) = if A = B then let val (n, ts') = conc t ts in ((A, (i, ts')) :: used, n) end else let val (used', n) = update_trees used (A, t) in ((B, (i, ts)) :: used', n) end; (*Replace entry in used*) fun update_prec (A: nt_tag, prec) used = let fun update ((hd as (B, (_, ts))) :: used, used') = if A = B then used' @ ((A, (prec, ts)) :: used) else update (used, hd :: used') in update (used, []) end; fun getS A maxPrec Si = List.filter (fn (_, _, _, Nonterminal (B, prec) :: _, _, _) => A = B andalso prec <= maxPrec | _ => false) Si; fun getS' A maxPrec minPrec Si = List.filter (fn (_, _, _, Nonterminal (B, prec) :: _, _, _) => A = B andalso prec > minPrec andalso prec <= maxPrec | _ => false) Si; fun getStates Estate i ii A maxPrec = List.filter (fn (_, _, _, Nonterminal (B, prec) :: _, _, _) => A = B andalso prec <= maxPrec | _ => false) (Array.sub (Estate, ii)); fun movedot_term (A, j, ts, Terminal a :: sa, id, i) c = if valued_token c then (A, j, ts @ [Tip c], sa, id, i) else (A, j, ts, sa, id, i); fun movedot_nonterm ts (A, j, tss, Nonterminal _ :: sa, id, i) = (A, j, tss @ ts, sa, id, i); fun movedot_lambda _ [] = [] | movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ((t, ki) :: ts) = if k <= ki then (B, j, tss @ t, sa, id, i) :: movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ts else movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ts; val warned = ref false; (*flag for warning message*) val branching_level = ref 600; (*trigger value for warnings*) (*get all productions of a NT and NTs chained to it which can be started by specified token*) fun prods_for prods chains include_none tk nts = let fun token_assoc (list, key) = let fun assoc [] result = result | assoc ((keyi, pi) :: pairs) result = if is_some keyi andalso matching_tokens (the keyi, key) orelse include_none andalso is_none keyi then assoc pairs (pi @ result) else assoc pairs result; in assoc list [] end; fun get_prods [] result = result | get_prods (nt :: nts) result = let val nt_prods = snd (Array.sub (prods, nt)); in get_prods nts ((token_assoc (nt_prods, tk)) @ result) end; in get_prods (connected_with chains nts nts) [] end; fun PROCESSS prods chains Estate i c states = let fun all_prods_for nt = prods_for prods chains true c [nt]; fun processS used [] (Si, Sii) = (Si, Sii) | processS used (S :: States) (Si, Sii) = (case S of (_, _, _, Nonterminal (nt, minPrec) :: _, _, _) => let (*predictor operation*) val (used', new_states) = (case AList.lookup (op =) used nt of SOME (usedPrec, l) => (*nonterminal has been processed*) if usedPrec <= minPrec then (*wanted precedence has been processed*) (used, movedot_lambda S l) else (*wanted precedence hasn't been parsed yet*) let val tk_prods = all_prods_for nt; val States' = mkStates i minPrec nt (getRHS' minPrec usedPrec tk_prods); in (update_prec (nt, minPrec) used, movedot_lambda S l @ States') end | NONE => (*nonterminal is parsed for the first time*) let val tk_prods = all_prods_for nt; val States' = mkStates i minPrec nt (getRHS minPrec tk_prods); in ((nt, (minPrec, [])) :: used, States') end); val dummy = if not (!warned) andalso length (new_states @ States) > (!branching_level) then (warning "Currently parsed expression could be \ \extremely ambiguous."; warned := true) else (); in processS used' (new_states @ States) (S :: Si, Sii) end | (_, _, _, Terminal a :: _, _, _) => (*scanner operation*) processS used States (S :: Si, if matching_tokens (a, c) then movedot_term S c :: Sii else Sii) | (A, prec, ts, [], id, j) => (*completer operation*) let val tt = if id = "" then ts else [Node (id, ts)] in if j = i then (*lambda production?*) let val (used', O) = update_trees used (A, (tt, prec)); in case O of NONE => let val Slist = getS A prec Si; val States' = map (movedot_nonterm tt) Slist; in processS used' (States' @ States) (S :: Si, Sii) end | SOME n => if n >= prec then processS used' States (S :: Si, Sii) else let val Slist = getS' A prec n Si; val States' = map (movedot_nonterm tt) Slist; in processS used' (States' @ States) (S :: Si, Sii) end end else let val Slist = getStates Estate i j A prec in processS used (map (movedot_nonterm tt) Slist @ States) (S :: Si, Sii) end end) in processS [] states ([], []) end; fun syntax_error toks allowed = let val msg = if null toks then Pretty.str "Inner syntax error: unexpected end of input" else Pretty.block (Pretty.str "Inner syntax error at: \"" :: Pretty.breaks (map (Pretty.str o str_of_token) (rev (tl (rev toks)))) @ [Pretty.str "\""]); val expected = Pretty.strs ("Expected tokens: " :: map (quote o str_of_token) allowed); in error (Pretty.string_of (Pretty.blk (0, [msg, Pretty.fbrk, expected]))) end; fun produce prods chains stateset i indata prev_token = (*prev_token is used for error messages*) (case Array.sub (stateset, i) of [] => let fun some_prods_for tk nt = prods_for prods chains false tk [nt]; (*test if tk is a lookahead for a given minimum precedence*) fun reduction _ minPrec _ (Terminal _ :: _, _, prec:int) = if prec >= minPrec then true else false | reduction tk minPrec checked (Nonterminal (nt, nt_prec) :: _, _, prec) = if prec >= minPrec andalso not (nt mem checked) then let val chained = connected_with chains [nt] [nt]; in exists (reduction tk nt_prec (chained @ checked)) (some_prods_for tk nt) end else false; (*compute a list of allowed starting tokens for a list of nonterminals considering precedence*) fun get_starts [] result = result | get_starts ((nt, minPrec:int) :: nts) result = let fun get [] result = result | get ((SOME tk, prods) :: ps) result = if not (null prods) andalso exists (reduction tk minPrec [nt]) prods then get ps (tk :: result) else get ps result | get ((NONE, _) :: ps) result = get ps result; val (_, nt_prods) = Array.sub (prods, nt); val chained = map (fn nt => (nt, minPrec)) ((these o AList.lookup (op =) chains) nt); in get_starts (chained @ nts) ((get nt_prods []) union result) end; val nts = List.mapPartial (fn (_, _, _, Nonterminal (a, prec) :: _, _, _) => SOME (a, prec) | _ => NONE) (Array.sub (stateset, i-1)); val allowed = distinct (get_starts nts [] @ (List.mapPartial (fn (_, _, _, Terminal a :: _, _, _) => SOME a | _ => NONE) (Array.sub (stateset, i-1)))); in syntax_error (if prev_token = EndToken then indata else prev_token :: indata) allowed end | s => (case indata of [] => Array.sub (stateset, i) | c :: cs => let val (si, sii) = PROCESSS prods chains stateset i c s; in Array.update (stateset, i, si); Array.update (stateset, i + 1, sii); produce prods chains stateset (i + 1) cs c end)); fun get_trees l = List.mapPartial (fn (_, _, [pt], _, _, _) => SOME pt | _ => NONE) l; fun earley prods tags chains startsymbol indata = let val start_tag = case Symtab.lookup tags startsymbol of SOME tag => tag | NONE => error ("parse: Unknown startsymbol " ^ quote startsymbol); val S0 = [(~1, 0, [], [Nonterminal (start_tag, 0), Terminal EndToken], "", 0)]; val s = length indata + 1; val Estate = Array.array (s, []); in Array.update (Estate, 0, S0); warned := false; get_trees (produce prods chains Estate 0 indata EndToken) end; fun parse (Gram {tags, prods, chains, ...}) start toks = let val r = (case earley prods tags chains start toks of [] => sys_error "parse: no parse trees" | pts => pts); in r end end;