src/Pure/Syntax/parser.ML
author wenzelm
Wed Oct 31 21:59:07 2001 +0100 (2001-10-31)
changeset 12004 1703de633aaf
parent 7944 cc1930ad1a88
child 12785 27debaf2112d
permissions -rw-r--r--
IsarThy.theorem_i: no locale;
     1 (*  Title:      Pure/Syntax/parser.ML
     2     ID:         $Id$
     3     Author:     Carsten Clasohm, Sonia Mahjoub, and Markus Wenzel, TU Muenchen
     4 
     5 Isabelle's main parser (used for terms and types).
     6 *)
     7 
     8 signature PARSER =
     9   sig
    10   type gram
    11   val empty_gram: gram
    12   val extend_gram: gram -> SynExt.xprod list -> gram
    13   val merge_grams: gram -> gram -> gram
    14   val pretty_gram: gram -> Pretty.T list
    15   datatype parsetree =
    16     Node of string * parsetree list |
    17     Tip of Lexicon.token
    18   val parse: gram -> string -> Lexicon.token list -> parsetree list
    19   val branching_level: int ref
    20   end;
    21 
    22 
    23 structure Parser : PARSER =
    24 struct
    25 open Lexicon SynExt;
    26 
    27 (** datatype gram **)
    28 
    29 type nt_tag = int;              (*production for the NTs are stored in an array
    30                                   so we can identify NTs by their index*)
    31 
    32 datatype symb = Terminal of token
    33               | Nonterminal of nt_tag * int;              (*(tag, precedence)*)
    34 
    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*)
    41 
    42 datatype gram =
    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])]*)
    46            lambdas: nt_tag list,
    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"*)
    53 
    54 val UnknownStart = EndToken;       (*productions for which no starting token is
    55                                      known yet are associated with this token*)
    56 
    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;
    63 
    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) =
    70     let
    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)))
    78               end;
    79         in if pri = ~1 then
    80              case rhs of [Nonterminal (id, ~1)] => store_chain id
    81                        | _ => (None, chains)
    82            else (None, chains)
    83         end;
    84 
    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);
    92 
    93             (*copy from's lookahead to chain's destinations*)
    94             fun copy_lookahead [] added = added
    95               | copy_lookahead (to :: tos) added =
    96                 let
    97                   val ((to_nts, to_tks), ps) = Array.sub (prods, to);
    98 
    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)
   103                 end;
   104 
   105             val tos = connected_with chains' [lhs] [lhs];
   106         in (copy_lookahead tos [],
   107             (if lhs mem lambdas then tos else []) union lambdas)
   108         end;
   109 
   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]))
   116         else
   117           (false, lambdas');
   118 
   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);
   127 
   128       (*get all known starting tokens for a nonterminal*)
   129       fun starts_for_nt nt = snd (fst (Array.sub (prods, nt)));
   130 
   131       val token_union = gen_union matching_tokens;
   132 
   133       (*update prods, lookaheads, and lambdas according to new lambda NTs*)
   134       val (added_starts', lambdas') =
   135         let
   136           (*propagate added lambda NT*)
   137           fun propagate_lambda [] added_starts lambdas= (added_starts, lambdas)
   138             | propagate_lambda (l :: ls) added_starts lambdas =
   139               let
   140                 (*get lookahead for lambda NT*)
   141                 val ((dependent, l_starts), _) = Array.sub (prods, l);
   142 
   143                 (*check productions whose lookahead may depend on lamdba NT*)
   144                 fun examine_prods [] add_lambda nt_dependencies added_tks
   145                                   nt_prods =
   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 [];
   150                     in
   151                       if l mem nts then       (*update production's lookahead*)
   152                       let
   153                         val new_lambda = is_none tk andalso nts subset lambdas;
   154 
   155                         val new_tks = (if is_some tk then [the tk] else []) @
   156                           foldl token_union ([], map starts_for_nt nts) \\
   157                           l_starts;
   158   
   159                         val added_tks' = token_union (new_tks, added_tks);
   160 
   161                         val nt_dependencies' = nts union nt_dependencies;
   162 
   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;
   167 
   168                                 val prods' = p :: old_prods;
   169                             in copy tks (overwrite (nt_prods, (tk, prods')))
   170                             end;
   171   
   172                         val nt_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
   176                           end;
   177                       in examine_prods ps (add_lambda orelse new_lambda)
   178                            nt_dependencies' added_tks' nt_prods'
   179                       end
   180                       else                                  (*skip production*)
   181                         examine_prods ps add_lambda nt_dependencies
   182                                       added_tks nt_prods
   183                     end;
   184 
   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 =
   189                     let
   190                       val (lookahead as (old_nts, old_tks), nt_prods) =
   191                         Array.sub (prods, nt);
   192 
   193                       (*existing productions whose lookahead may depend on l*)
   194                       val tk_prods =
   195                         assocs nt_prods
   196                                (Some (hd l_starts  handle LIST _ => UnknownStart));
   197 
   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;
   202 
   203                       val added_nts = nt_dependencies \\ old_nts;
   204 
   205                       val added_lambdas' =
   206                         if add_lambda then nt :: added_lambdas
   207                         else added_lambdas;
   208                     in Array.update (prods, nt,
   209                                    ((added_nts @ old_nts, old_tks @ added_tks),
   210                                     nt_prods'));
   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*)
   215 
   216                        if null added_tks then
   217                          process_nts nts added_lambdas' added_starts
   218                        else
   219                          process_nts nts added_lambdas'
   220                                       ((nt, added_tks) :: added_starts)
   221                     end;
   222 
   223                 val (added_lambdas, added_starts') =
   224                   process_nts dependent [] added_starts;
   225 
   226                 val added_lambdas' = added_lambdas \\ lambdas;
   227               in propagate_lambda (ls @ added_lambdas') added_starts'
   228                                   (added_lambdas' @ lambdas)
   229               end;
   230         in propagate_lambda (lambdas' \\ lambdas) added_starts lambdas' end;
   231 
   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*)
   236         else let
   237           (*lookahead tokens of new production and on which
   238             NTs lookahead depends*)
   239           val (start_tk, start_nts) = lookahead_dependency lambdas' rhs [];
   240 
   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);
   244 
   245           val opt_starts = (if new_lambda then [None]
   246                             else if null start_tks then [Some UnknownStart]
   247                             else []) @ (map Some start_tks);
   248 
   249           (*add lhs NT to list of dependent NTs in lookahead*)
   250           fun add_nts [] = ()
   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))
   255               end;
   256 
   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 =
   261               let
   262                 val ((old_nts, old_tks), nt_prods) = Array.sub (prods, nt);
   263 
   264                 val new_tks = gen_rems matching_tokens (start_tks, old_tks);
   265 
   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;
   273 
   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);
   281 
   282                         val prods' = if is_new' then
   283                                        overwrite (prods, (tk, tk_prods'))
   284                                      else prods;
   285                     in store tks prods' (is_new orelse is_new') end;
   286 
   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),
   292                                                 nt_prods'));
   293                  add_tks nts (if null new_tks then added
   294                               else (nt, new_tks) :: added) prod_count'
   295               end;
   296         in add_nts start_nts;
   297            add_tks (connected_with chains' [lhs] [lhs]) [] prod_count
   298         end;
   299 
   300       (*associate productions with new lookaheads*)
   301       val dummy =
   302         let
   303           (*propagate added start tokens*)
   304           fun add_starts [] = ()
   305             | add_starts ((changed_nt, new_tks) :: starts) =
   306               let
   307                 (*token under which old productions which
   308                   depend on changed_nt could be stored*)
   309                 val key =
   310                  case find_first (fn t => not (t mem new_tks))
   311                                  (starts_for_nt changed_nt) of
   312                       None => Some UnknownStart
   313                     | t => t;
   314 
   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) =
   321                     let
   322                       (*lookahead dependency for production*)
   323                       val (tk, depends) = lookahead_dependency lambdas' rhs [];
   324 
   325                       (*test if this production has to be copied*)
   326                       val update = changed_nt mem depends;
   327 
   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;
   333 
   334                       (*associate production with new starting tokens*)
   335                       fun copy [] nt_prods = nt_prods
   336                         | copy (tk :: tks) nt_prods =
   337                           let
   338                             val tk_prods = assocs nt_prods (Some tk);
   339 
   340                             val tk_prods' =
   341                               if not lambda then p :: tk_prods
   342                               else p ins tk_prods;
   343                                       (*if production depends on lambda NT we
   344                                         have to look for duplicates*)
   345                          in copy tks
   346                                  (overwrite (nt_prods, (Some tk, tk_prods')))
   347                          end;
   348                       val result =
   349                         if update then
   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;
   355 
   356                 (*copy existing productions for new starting tokens*)
   357                 fun process_nts [] added = added
   358                   | process_nts (nt :: nts) added =
   359                     let
   360                       val (lookahead as (old_nts, old_tks), nt_prods) =
   361                         Array.sub (prods, nt);
   362 
   363                       val tk_prods = assocs nt_prods key;
   364 
   365                       (*associate productions with new lookahead tokens*)
   366                       val (tk_prods', nt_prods') =
   367                         update_prods tk_prods ([], nt_prods);
   368 
   369                       val nt_prods' =
   370                         if key = Some UnknownStart then
   371                           overwrite (nt_prods', (key, tk_prods'))
   372                         else nt_prods';
   373 
   374                       val added_tks =
   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)
   379                        else
   380                          (Array.update (prods, nt,
   381                             ((old_nts, added_tks @ old_tks), nt_prods'));
   382                           process_nts nts ((nt, added_tks) :: added))
   383                     end;
   384 
   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;
   389 
   390 
   391 (* pretty_gram *)
   392 
   393 fun pretty_gram (Gram {tags, prods, chains, ...}) =
   394   let
   395     fun pretty_name name = [Pretty.str (name ^ " =")];
   396 
   397     val taglist = Symtab.dest tags;
   398 
   399     fun pretty_symb (Terminal (Token s)) = Pretty.str (quote 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;
   404 
   405     fun pretty_const "" = []
   406       | pretty_const c = [Pretty.str ("=> " ^ quote c)];
   407 
   408     fun pretty_pri p = [Pretty.str ("(" ^ string_of_int p ^ ")")];
   409 
   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));
   413 
   414     fun pretty_nt (name, tag) =
   415       let
   416         fun prod_of_chain from = ([Nonterminal (from, ~1)], "", ~1);
   417 
   418         val nt_prods =
   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;
   422         
   423   in flat (map pretty_nt taglist) end;
   424 
   425 
   426 (** Operations on gramars **)
   427 
   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, (([], []), []))};
   432 
   433 
   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;
   442 
   443 
   444 (*Add productions to a grammar*)
   445 fun extend_gram gram [] = gram
   446   | extend_gram (Gram {nt_count, prod_count, tags, chains, lambdas, prods})
   447                 xprods =
   448   let
   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),
   454                  nt_count);
   455 
   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 =
   463           let
   464             val (nt_count', tags', new_symb) =
   465               case predef_term s of
   466                 None =>
   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;
   473 
   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;
   480 
   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)
   485         end;
   486 
   487     val (nt_count', prod_count', tags', xprods') =
   488       prod_of xprods nt_count prod_count tags [];
   489 
   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*)
   493     val prods' =
   494       let fun get_prod i = if i < nt_count then Array.sub (prods, i)
   495                            else (([], []), []);
   496       in Array.tabulate (nt_count', get_prod) end;
   497 
   498     val fromto_chains = inverse_chains chains [];
   499 
   500     (*Add new productions to old ones*)
   501     val (fromto_chains', lambdas', _) =
   502       add_prods prods' fromto_chains lambdas None xprods';
   503 
   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'}
   507   end;
   508 
   509 
   510 (*Merge two grammars*)
   511 fun merge_grams gram_a gram_b =
   512   let
   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)
   522       end;
   523 
   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),
   529                 nt_count)
   530 
   531     val ((nt_count1', tags1'), tag_table) =
   532       let val tag_list = Symtab.dest tags2;
   533 
   534           val table = Array.array (nt_count2, ~1);
   535 
   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)
   543               end;
   544       in (store_tag nt_count1 tags1 (nt_count2-1), table) end;
   545     
   546     (*convert grammar2 tag to grammar1 tag*)
   547     fun convert_tag tag = Array.sub (tag_table, tag);
   548 
   549     (*convert chain list to raw productions*)
   550     fun mk_chain_prods [] result = result
   551       | mk_chain_prods ((to, froms) :: cs) result =
   552         let
   553           val to_tag = convert_tag to;
   554 
   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;
   559         
   560     val chain_prods = mk_chain_prods chains2 [];
   561 
   562     (*convert prods2 array to productions*)
   563     fun process_nt ~1 result = result
   564       | process_nt nt result =
   565         let
   566           val nt_prods = foldl (op union)
   567                              ([], map snd (snd (Array.sub (prods2, nt))));
   568           val lhs_tag = convert_tag nt;
   569 
   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 =
   575                 process_rhs rhs
   576                             (result @ [Nonterminal (convert_tag nt, prec)]);
   577 
   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))
   582                                   :: result);
   583         in process_nt (nt-1) (process_prods nt_prods [] @ result) end;
   584 
   585     val raw_prods = chain_prods @ process_nt (nt_count2-1) [];
   586 
   587     val prods1' =
   588       let fun get_prod i = if i < nt_count1 then Array.sub (prods1, i)
   589                            else (([], []), []);
   590       in Array.tabulate (nt_count1', get_prod) end;
   591 
   592     val fromto_chains = inverse_chains chains1 [];
   593 
   594     val (fromto_chains', lambdas', Some prod_count1') =
   595       add_prods prods1' fromto_chains lambdas1 (Some prod_count1) raw_prods;
   596 
   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',
   600            prods = prods1'}
   601   end;
   602 
   603 
   604 (** Parser **)
   605 
   606 datatype parsetree =
   607   Node of string * parsetree list |
   608   Tip of token;
   609 
   610 type state =
   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*)
   616 
   617 
   618 (*Get all rhss with precedence >= minPrec*)
   619 fun getRHS minPrec = filter (fn (_, _, prec:int) => prec >= minPrec);
   620 
   621 (*Get all rhss with precedence >= minPrec and < maxPrec*)
   622 fun getRHS' minPrec maxPrec =
   623   filter (fn (_, _, prec:int) => prec >= minPrec andalso prec < maxPrec);
   624 
   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;
   629 
   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) =
   634       if t = t' then
   635         (Some prec', if prec' >= prec then (t', prec') :: ts 
   636                      else (t, prec) :: ts)
   637       else
   638         let val (n, ts') = conc (t, prec) ts
   639         in (n, (t', prec') :: ts') end;
   640 
   641 (*Update entry in used*)
   642 fun update_trees ((B, (i, ts)) :: used) (A, t) =
   643   if A = B then
   644     let val (n, ts') = conc t ts
   645     in ((A, (i, ts')) :: used, n) end
   646   else
   647     let val (used', n) = update_trees used (A, t)
   648     in ((B, (i, ts)) :: used', n) end;
   649 
   650 (*Replace entry in used*)
   651 fun update_prec (A, prec) used =
   652   let fun update ((hd as (B, (_, ts))) :: used, used') =
   653         if A = B
   654         then used' @ ((A, (prec, ts)) :: used)
   655         else update (used, hd :: used')
   656   in update (used, []) end;
   657 
   658 fun getS A maxPrec Si =
   659   filter
   660     (fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
   661           => A = B andalso prec <= maxPrec
   662       | _ => false) Si;
   663 
   664 fun getS' A maxPrec minPrec Si =
   665   filter
   666     (fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
   667           => A = B andalso prec > minPrec andalso prec <= maxPrec
   668       | _ => false) Si;
   669 
   670 fun getStates Estate i ii A maxPrec =
   671   filter
   672     (fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
   673           => A = B andalso prec <= maxPrec
   674       | _ => false)
   675     (Array.sub (Estate, ii));
   676 
   677 
   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);
   682 
   683 fun movedot_nonterm ts (A, j, tss, Nonterminal _ :: sa, id, i) =
   684   (A, j, tss @ ts, sa, id, i);
   685 
   686 fun movedot_lambda _ [] = []
   687   | movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ((t, ki) :: ts) =
   688       if k <= ki then
   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;
   692 
   693 
   694 val warned = ref false;                            (*flag for warning message*)
   695 val branching_level = ref 400;                   (*trigger value for warnings*)
   696 
   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;
   709 
   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;
   715 
   716 
   717 fun PROCESSS prods chains Estate i c states =
   718 let
   719 fun all_prods_for nt = prods_for prods chains true c [nt];
   720 
   721 fun processS used [] (Si, Sii) = (Si, Sii)
   722   | processS used (S :: States) (Si, Sii) =
   723       (case S of
   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*)
   733                     let
   734                       val tk_prods = all_prods_for nt;
   735                       
   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')
   740                     end
   741 
   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);
   747 
   748             val dummy =
   749               if not (!warned) andalso
   750                  length (new_states @ States) > (!branching_level) then
   751                 (warning "Currently parsed expression could be \
   752                          \extremely ambiguous.";
   753                  warned := true)
   754               else ();
   755           in
   756             processS used' (new_states @ States) (S :: Si, Sii)
   757           end
   758       | (_, _, _, Terminal a :: _, _, _) =>               (*scanner operation*)
   759           processS used States
   760             (S :: Si,
   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?*)
   765               let
   766                 val (used', O) = update_trees used (A, (tt, prec));
   767               in
   768                 case O of
   769                   None =>
   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
   773                 | Some n =>
   774                     if n >= prec then processS used' States (S :: Si, Sii)
   775                     else
   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
   779               end 
   780             else
   781               let val Slist = getStates Estate i j A prec
   782               in processS used (map (movedot_nonterm tt) Slist @ States)
   783                           (S :: Si, Sii)
   784               end
   785           end)
   786 in processS [] states ([], []) end;
   787 
   788 
   789 fun syntax_error toks allowed =
   790   let
   791     val msg =
   792       if null toks then Pretty.str "Inner syntax error: unexpected end of input"
   793       else
   794         Pretty.block (Pretty.str "Inner syntax error at: \"" ::
   795           Pretty.breaks (map (Pretty.str o str_of_token)
   796 		 (rev (tl (rev toks)))) @
   797           [Pretty.str "\""]);
   798     val expected =
   799       Pretty.strs ("Expected tokens: " :: map (quote o str_of_token) allowed);
   800   in
   801     error (Pretty.string_of (Pretty.blk (0, [msg, Pretty.fbrk, expected])))
   802   end;
   803 
   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];
   808 
   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
   812                     else false
   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];
   817                     in exists
   818                          (reduction tk nt_prec (chained @ checked))
   819                          (some_prods_for tk nt)
   820                     end
   821                   else false;
   822 
   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)
   832                             else get ps result
   833                         | get ((None, _) :: ps) result = get ps result;
   834 
   835                       val (_, nt_prods) = Array.sub (prods, nt);
   836 
   837                       val chained = map (fn nt => (nt, minPrec))
   838                                         (assocs chains nt);
   839                   in get_starts (chained @ nts)
   840                                 ((get nt_prods []) union result)
   841                   end;
   842 
   843               val nts =
   844                 mapfilter (fn (_, _, _, Nonterminal (a, prec) :: _, _, _) => 
   845                            Some (a, prec) | _ => None)
   846                           (Array.sub (stateset, i-1));
   847               val allowed =
   848                 distinct (get_starts nts [] @
   849                   (mapfilter (fn (_, _, _, Terminal a :: _, _, _) => Some a
   850                                | _ => None)
   851                              (Array.sub (stateset, i-1))));
   852           in syntax_error (if prev_token = EndToken then indata
   853                            else prev_token :: indata) allowed
   854           end
   855   | s =>
   856     (case indata of
   857        [] => Array.sub (stateset, i)
   858      | c :: cs =>
   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
   863        end));
   864 
   865 
   866 fun get_trees l = mapfilter (fn (_, _, [pt], _, _, _) => Some pt | _ => None) 
   867                             l;
   868 
   869 fun earley prods tags chains startsymbol indata =
   870   let
   871     val start_tag = case Symtab.lookup (tags, startsymbol) of
   872                        Some tag => tag
   873                      | None   => error ("parse: Unknown startsymbol " ^ 
   874                                         quote startsymbol);
   875     val S0 = [(~1, 0, [], [Nonterminal (start_tag, 0), Terminal EndToken],
   876                "", 0)];
   877     val s = length indata + 1;
   878     val Estate = Array.array (s, []);
   879   in
   880     Array.update (Estate, 0, S0);
   881     warned := false;
   882     get_trees (produce prods chains Estate 0 indata EndToken)
   883   end;
   884 
   885 
   886 fun parse (Gram {tags, prods, chains, ...}) start toks =
   887 let val r =
   888   (case earley prods tags chains start toks of
   889     [] => sys_error "parse: no parse trees"
   890   | pts => pts);
   891 in r end
   892 
   893 end;