(* Title: Pure/Syntax/parser.ML
ID: $Id$
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 assoc (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;