src/Pure/Syntax/parser.ML
author wenzelm
Fri Jul 02 21:48:54 2010 +0200 (2010-07-02 ago)
changeset 37684 d123b1e08856
parent 37683 ece640e48a6c
child 37852 a902f158b4fc
permissions -rw-r--r--
standard argument order;
tuned;
     1 (*  Title:      Pure/Syntax/parser.ML
     2     Author:     Carsten Clasohm, Sonia Mahjoub, and Markus Wenzel, TU Muenchen
     3 
     4 General context-free parser for the inner syntax of terms, types, etc.
     5 *)
     6 
     7 signature PARSER =
     8 sig
     9   type gram
    10   val empty_gram: gram
    11   val extend_gram: Syn_Ext.xprod list -> gram -> gram
    12   val make_gram: Syn_Ext.xprod list -> gram
    13   val merge_gram: 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 guess_infix_lr: gram -> string -> (string * bool * bool * int) option
    20   val branching_level: int Unsynchronized.ref
    21 end;
    22 
    23 structure Parser: PARSER =
    24 struct
    25 
    26 (** datatype gram **)
    27 
    28 type nt_tag = int;              (*production for the NTs are stored in an array
    29                                   so we can identify NTs by their index*)
    30 
    31 datatype symb = Terminal of Lexicon.token
    32               | Nonterminal of nt_tag * int;              (*(tag, precedence)*)
    33 
    34 type nt_gram = ((nt_tag list * Lexicon.token list) *
    35                 (Lexicon.token option * (symb list * string * int) list) list);
    36                                      (*(([dependent_nts], [start_tokens]),
    37                                         [(start_token, [(rhs, name, prio)])])*)
    38                               (*depent_nts is a list of all NTs whose lookahead
    39                                 depends on this NT's lookahead*)
    40 
    41 datatype gram =
    42   Gram of {nt_count: int, prod_count: int,
    43            tags: nt_tag Symtab.table,
    44            chains: (nt_tag * nt_tag list) list,              (*[(to, [from])]*)
    45            lambdas: nt_tag list,
    46            prods: nt_gram Array.array};
    47                        (*"tags" is used to map NT names (i.e. strings) to tags;
    48                          chain productions are not stored as normal productions
    49                          but instead as an entry in "chains";
    50                          lambda productions are stored as normal productions
    51                          and also as an entry in "lambdas"*)
    52 
    53 val UnknownStart = Lexicon.eof;       (*productions for which no starting token is
    54                                         known yet are associated with this token*)
    55 
    56 (* get all NTs that are connected with a list of NTs
    57    (used for expanding chain list)*)
    58 fun connected_with _ ([]: nt_tag list) relatives = relatives
    59   | connected_with chains (root :: roots) relatives =
    60     let val branches = subtract (op =) relatives (these (AList.lookup (op =) chains root));
    61     in connected_with chains (branches @ roots) (branches @ relatives) end;
    62 
    63 (* convert productions to grammar;
    64    N.B. that the chains parameter has the form [(from, [to])];
    65    prod_count is of type "int option" and is only updated if it is <> NONE*)
    66 fun add_prods _ chains lambdas prod_count [] = (chains, lambdas, prod_count)
    67   | add_prods prods chains lambdas prod_count
    68               ((lhs, new_prod as (rhs, name, pri)) :: ps) =
    69     let
    70       val chain_from = case (pri, rhs) of (~1, [Nonterminal (id, ~1)]) => SOME id | _ => NONE;
    71 
    72       (*store chain if it does not already exist*)
    73       val (new_chain, chains') = case chain_from of NONE => (NONE, chains) | SOME from =>
    74         let val old_tos = these (AList.lookup (op =) chains from) in
    75           if member (op =) old_tos lhs then (NONE, chains)
    76           else (SOME from, AList.update (op =) (from, insert (op =) lhs old_tos) chains)
    77         end;
    78 
    79       (*propagate new chain in lookahead and lambda lists;
    80         added_starts is used later to associate existing
    81         productions with new starting tokens*)
    82       val (added_starts, lambdas') =
    83         if is_none new_chain then ([], lambdas) else
    84         let (*lookahead of chain's source*)
    85             val ((from_nts, from_tks), _) = Array.sub (prods, the new_chain);
    86 
    87             (*copy from's lookahead to chain's destinations*)
    88             fun copy_lookahead [] added = added
    89               | copy_lookahead (to :: tos) added =
    90                 let
    91                   val ((to_nts, to_tks), ps) = Array.sub (prods, to);
    92 
    93                   val new_tks = subtract (op =) to_tks from_tks;  (*added lookahead tokens*)
    94                 in Array.update (prods, to, ((to_nts, to_tks @ new_tks), ps));
    95                    copy_lookahead tos (if null new_tks then added
    96                                        else (to, new_tks) :: added)
    97                 end;
    98 
    99             val tos = connected_with chains' [lhs] [lhs];
   100         in (copy_lookahead tos [],
   101             union (op =) (if member (op =) lambdas lhs then tos else []) lambdas)
   102         end;
   103 
   104       (*test if new production can produce lambda
   105         (rhs must either be empty or only consist of lambda NTs)*)
   106       val (new_lambda, lambdas') =
   107         if forall (fn (Nonterminal (id, _)) => member (op =) lambdas' id
   108                     | (Terminal _) => false) rhs then
   109           (true, union (op =) lambdas' (connected_with chains' [lhs] [lhs]))
   110         else
   111           (false, lambdas');
   112 
   113       (*list optional terminal and all nonterminals on which the lookahead
   114         of a production depends*)
   115       fun lookahead_dependency _ [] nts = (NONE, nts)
   116         | lookahead_dependency _ ((Terminal tk) :: _) nts = (SOME tk, nts)
   117         | lookahead_dependency lambdas ((Nonterminal (nt, _)) :: symbs) nts =
   118             if member (op =) lambdas nt then
   119               lookahead_dependency lambdas symbs (nt :: nts)
   120             else (NONE, nt :: nts);
   121 
   122       (*get all known starting tokens for a nonterminal*)
   123       fun starts_for_nt nt = snd (fst (Array.sub (prods, nt)));
   124 
   125       val token_union = uncurry (union Lexicon.matching_tokens);
   126 
   127       (*update prods, lookaheads, and lambdas according to new lambda NTs*)
   128       val (added_starts', lambdas') =
   129         let
   130           (*propagate added lambda NT*)
   131           fun propagate_lambda [] added_starts lambdas= (added_starts, lambdas)
   132             | propagate_lambda (l :: ls) added_starts lambdas =
   133               let
   134                 (*get lookahead for lambda NT*)
   135                 val ((dependent, l_starts), _) = Array.sub (prods, l);
   136 
   137                 (*check productions whose lookahead may depend on lambda NT*)
   138                 fun examine_prods [] add_lambda nt_dependencies added_tks
   139                                   nt_prods =
   140                       (add_lambda, nt_dependencies, added_tks, nt_prods)
   141                   | examine_prods ((p as (rhs, _, _)) :: ps) add_lambda
   142                       nt_dependencies added_tks nt_prods =
   143                     let val (tk, nts) = lookahead_dependency lambdas rhs [];
   144                     in
   145                       if member (op =) nts l then       (*update production's lookahead*)
   146                       let
   147                         val new_lambda = is_none tk andalso subset (op =) (nts, lambdas);
   148 
   149                         val new_tks = subtract (op =) l_starts
   150                           ((if is_some tk then [the tk] else []) @
   151                             Library.foldl token_union ([], map starts_for_nt nts));
   152 
   153                         val added_tks' = token_union (new_tks, added_tks);
   154 
   155                         val nt_dependencies' = union (op =) nts nt_dependencies;
   156 
   157                         (*associate production with new starting tokens*)
   158                         fun copy ([]: Lexicon.token option list) nt_prods = nt_prods
   159                           | copy (tk :: tks) nt_prods =
   160                             let val old_prods = these (AList.lookup (op =) nt_prods tk);
   161 
   162                                 val prods' = p :: old_prods;
   163                             in nt_prods
   164                                |> AList.update (op =) (tk, prods')
   165                                |> copy tks
   166                             end;
   167 
   168                         val nt_prods' =
   169                           let val new_opt_tks = map SOME new_tks;
   170                           in copy ((if new_lambda then [NONE] else []) @
   171                                    new_opt_tks) nt_prods
   172                           end;
   173                       in examine_prods ps (add_lambda orelse new_lambda)
   174                            nt_dependencies' added_tks' nt_prods'
   175                       end
   176                       else                                  (*skip production*)
   177                         examine_prods ps add_lambda nt_dependencies
   178                                       added_tks nt_prods
   179                     end;
   180 
   181                 (*check each NT whose lookahead depends on new lambda NT*)
   182                 fun process_nts [] added_lambdas added_starts =
   183                       (added_lambdas, added_starts)
   184                   | process_nts (nt :: nts) added_lambdas added_starts =
   185                     let
   186                       val (lookahead as (old_nts, old_tks), nt_prods) =
   187                         Array.sub (prods, nt);
   188 
   189                       (*existing productions whose lookahead may depend on l*)
   190                       val tk_prods =
   191                         (these o AList.lookup (op =) nt_prods)
   192                                (SOME (hd l_starts  handle Empty => UnknownStart));
   193 
   194                       (*add_lambda is true if an existing production of the nt
   195                         produces lambda due to the new lambda NT l*)
   196                       val (add_lambda, nt_dependencies, added_tks, nt_prods') =
   197                         examine_prods tk_prods false [] [] nt_prods;
   198 
   199                       val added_nts = subtract (op =) old_nts nt_dependencies;
   200 
   201                       val added_lambdas' =
   202                         if add_lambda then nt :: added_lambdas
   203                         else added_lambdas;
   204                     in Array.update (prods, nt,
   205                                    ((added_nts @ old_nts, old_tks @ added_tks),
   206                                     nt_prods'));
   207                                           (*N.B. that because the tks component
   208                                             is used to access existing
   209                                             productions we have to add new
   210                                             tokens at the _end_ of the list*)
   211 
   212                        if null added_tks then
   213                          process_nts nts added_lambdas' added_starts
   214                        else
   215                          process_nts nts added_lambdas'
   216                                       ((nt, added_tks) :: added_starts)
   217                     end;
   218 
   219                 val (added_lambdas, added_starts') =
   220                   process_nts dependent [] added_starts;
   221 
   222                 val added_lambdas' = subtract (op =) lambdas added_lambdas;
   223               in propagate_lambda (ls @ added_lambdas') added_starts'
   224                                   (added_lambdas' @ lambdas)
   225               end;
   226         in propagate_lambda (subtract (op =) lambdas lambdas') added_starts lambdas' end;
   227 
   228       (*insert production into grammar*)
   229       val (added_starts', prod_count') =
   230         if is_some chain_from then (added_starts', prod_count)  (*don't store chain production*)
   231         else let
   232           (*lookahead tokens of new production and on which
   233             NTs lookahead depends*)
   234           val (start_tk, start_nts) = lookahead_dependency lambdas' rhs [];
   235 
   236           val start_tks = Library.foldl token_union
   237                           (if is_some start_tk then [the start_tk] else [],
   238                            map starts_for_nt start_nts);
   239 
   240           val opt_starts = (if new_lambda then [NONE]
   241                             else if null start_tks then [SOME UnknownStart]
   242                             else []) @ (map SOME start_tks);
   243 
   244           (*add lhs NT to list of dependent NTs in lookahead*)
   245           fun add_nts [] = ()
   246             | add_nts (nt :: nts) =
   247               let val ((old_nts, old_tks), ps) = Array.sub (prods, nt);
   248               in if member (op =) old_nts lhs then ()
   249                  else Array.update (prods, nt, ((lhs :: old_nts, old_tks), ps))
   250               end;
   251 
   252           (*add new start tokens to chained NTs' lookahead list;
   253             also store new production for lhs NT*)
   254           fun add_tks [] added prod_count = (added, prod_count)
   255             | add_tks (nt :: nts) added prod_count =
   256               let
   257                 val ((old_nts, old_tks), nt_prods) = Array.sub (prods, nt);
   258 
   259                 val new_tks = subtract Lexicon.matching_tokens old_tks start_tks;
   260 
   261                 (*store new production*)
   262                 fun store [] prods is_new =
   263                       (prods, if is_some prod_count andalso is_new then
   264                                 Option.map (fn x => x+1) prod_count
   265                               else prod_count, is_new)
   266                   | store (tk :: tks) prods is_new =
   267                     let val tk_prods = (these o AList.lookup (op =) prods) tk;
   268 
   269                         (*if prod_count = NONE then we can assume that
   270                           grammar does not contain new production already*)
   271                         val (tk_prods', is_new') =
   272                           if is_some prod_count then
   273                             if member (op =) tk_prods new_prod then (tk_prods, false)
   274                             else (new_prod :: tk_prods, true)
   275                           else (new_prod :: tk_prods, true);
   276 
   277                         val prods' = prods
   278                           |> is_new' ? AList.update (op =) (tk: Lexicon.token option, tk_prods');
   279                     in store tks prods' (is_new orelse is_new') end;
   280 
   281                 val (nt_prods', prod_count', changed) =
   282                   if nt = lhs then store opt_starts nt_prods false
   283                               else (nt_prods, prod_count, false);
   284               in if not changed andalso null new_tks then ()
   285                  else Array.update (prods, nt, ((old_nts, old_tks @ new_tks),
   286                                                 nt_prods'));
   287                  add_tks nts (if null new_tks then added
   288                               else (nt, new_tks) :: added) prod_count'
   289               end;
   290         in add_nts start_nts;
   291            add_tks (connected_with chains' [lhs] [lhs]) [] prod_count
   292         end;
   293 
   294       (*associate productions with new lookaheads*)
   295       val dummy =
   296         let
   297           (*propagate added start tokens*)
   298           fun add_starts [] = ()
   299             | add_starts ((changed_nt, new_tks) :: starts) =
   300               let
   301                 (*token under which old productions which
   302                   depend on changed_nt could be stored*)
   303                 val key =
   304                  case find_first (not o member (op =) new_tks)
   305                                  (starts_for_nt changed_nt) of
   306                       NONE => SOME UnknownStart
   307                     | t => t;
   308 
   309                 (*copy productions whose lookahead depends on changed_nt;
   310                   if key = SOME UnknownToken then tk_prods is used to hold
   311                   the productions not copied*)
   312                 fun update_prods [] result = result
   313                   | update_prods ((p as (rhs, _: string, _: nt_tag)) :: ps)
   314                       (tk_prods, nt_prods) =
   315                     let
   316                       (*lookahead dependency for production*)
   317                       val (tk, depends) = lookahead_dependency lambdas' rhs [];
   318 
   319                       (*test if this production has to be copied*)
   320                       val update = member (op =) depends changed_nt;
   321 
   322                       (*test if production could already be associated with
   323                         a member of new_tks*)
   324                       val lambda = length depends > 1 orelse
   325                                    not (null depends) andalso is_some tk
   326                                    andalso member (op =) new_tks (the tk);
   327 
   328                       (*associate production with new starting tokens*)
   329                       fun copy ([]: Lexicon.token list) nt_prods = nt_prods
   330                         | copy (tk :: tks) nt_prods =
   331                           let
   332                             val tk_prods = these (AList.lookup (op =) nt_prods (SOME tk));
   333 
   334                             val tk_prods' =
   335                               if not lambda then p :: tk_prods
   336                               else insert (op =) p tk_prods;
   337                                       (*if production depends on lambda NT we
   338                                         have to look for duplicates*)
   339                          in
   340                            nt_prods
   341                            |> AList.update (op =) (SOME tk, tk_prods')
   342                            |> copy tks
   343                          end;
   344                       val result =
   345                         if update then
   346                           (tk_prods, copy new_tks nt_prods)
   347                         else if key = SOME UnknownStart then
   348                           (p :: tk_prods, nt_prods)
   349                         else (tk_prods, nt_prods);
   350                     in update_prods ps result end;
   351 
   352                 (*copy existing productions for new starting tokens*)
   353                 fun process_nts [] added = added
   354                   | process_nts (nt :: nts) added =
   355                     let
   356                       val (lookahead as (old_nts, old_tks), nt_prods) =
   357                         Array.sub (prods, nt);
   358 
   359                       val tk_prods = these (AList.lookup (op =) nt_prods key);
   360 
   361                       (*associate productions with new lookahead tokens*)
   362                       val (tk_prods', nt_prods') =
   363                         update_prods tk_prods ([], nt_prods);
   364 
   365                       val nt_prods' =
   366                         nt_prods'
   367                         |> (key = SOME UnknownStart) ? AList.update (op =) (key, tk_prods')
   368 
   369                       val added_tks =
   370                         subtract Lexicon.matching_tokens old_tks new_tks;
   371                     in if null added_tks then
   372                          (Array.update (prods, nt, (lookahead, nt_prods'));
   373                           process_nts nts added)
   374                        else
   375                          (Array.update (prods, nt,
   376                             ((old_nts, added_tks @ old_tks), nt_prods'));
   377                           process_nts nts ((nt, added_tks) :: added))
   378                     end;
   379 
   380                 val ((dependent, _), _) = Array.sub (prods, changed_nt);
   381               in add_starts (starts @ process_nts dependent []) end;
   382         in add_starts added_starts' end;
   383   in add_prods prods chains' lambdas' prod_count ps end;
   384 
   385 
   386 (* pretty_gram *)
   387 
   388 fun pretty_gram (Gram {tags, prods, chains, ...}) =
   389   let
   390     fun pretty_name name = [Pretty.str (name ^ " =")];
   391 
   392     val nt_name = the o Inttab.lookup (Inttab.make (map swap (Symtab.dest tags)));
   393 
   394     fun pretty_symb (Terminal (Lexicon.Token (Lexicon.Literal, s, _))) = Pretty.quote (Pretty.str s)
   395       | pretty_symb (Terminal tok) = Pretty.str (Lexicon.str_of_token tok)
   396       | pretty_symb (Nonterminal (tag, p)) =
   397           Pretty.str (nt_name tag ^ "[" ^ signed_string_of_int p ^ "]");
   398 
   399     fun pretty_const "" = []
   400       | pretty_const c = [Pretty.str ("=> " ^ quote c)];
   401 
   402     fun pretty_pri p = [Pretty.str ("(" ^ signed_string_of_int p ^ ")")];
   403 
   404     fun pretty_prod name (symbs, const, pri) =
   405       Pretty.block (Pretty.breaks (pretty_name name @
   406         map pretty_symb symbs @ pretty_const const @ pretty_pri pri));
   407 
   408     fun pretty_nt (name, tag) =
   409       let
   410         fun prod_of_chain from = ([Nonterminal (from, ~1)], "", ~1);
   411 
   412         val nt_prods =
   413           Library.foldl (uncurry (union (op =))) ([], map snd (snd (Array.sub (prods, tag)))) @
   414           map prod_of_chain ((these o AList.lookup (op =) chains) tag);
   415       in map (pretty_prod name) nt_prods end;
   416 
   417   in maps pretty_nt (sort_wrt fst (Symtab.dest tags)) end;
   418 
   419 
   420 (** Operations on gramars **)
   421 
   422 val empty_gram = Gram {nt_count = 0, prod_count = 0,
   423                        tags = Symtab.empty, chains = [], lambdas = [],
   424                        prods = Array.array (0, (([], []), []))};
   425 
   426 
   427 (*Invert list of chain productions*)
   428 fun inverse_chains [] result = result
   429   | inverse_chains ((root, branches: nt_tag list) :: cs) result =
   430     let fun add ([]: nt_tag list) result = result
   431           | add (id :: ids) result =
   432             let val old = (these o AList.lookup (op =) result) id;
   433             in add ids (AList.update (op =) (id, root :: old) result) end;
   434     in inverse_chains cs (add branches result) end;
   435 
   436 
   437 (*Add productions to a grammar*)
   438 fun extend_gram [] gram = gram
   439   | extend_gram xprods (Gram {nt_count, prod_count, tags, chains, lambdas, prods}) =
   440     let
   441       (*Get tag for existing nonterminal or create a new one*)
   442       fun get_tag nt_count tags nt =
   443         case Symtab.lookup tags nt of
   444           SOME tag => (nt_count, tags, tag)
   445         | NONE => (nt_count+1, Symtab.update_new (nt, nt_count) tags,
   446                    nt_count);
   447 
   448       (*Convert symbols to the form used by the parser;
   449         delimiters and predefined terms are stored as terminals,
   450         nonterminals are converted to integer tags*)
   451       fun symb_of [] nt_count tags result = (nt_count, tags, rev result)
   452         | symb_of ((Syn_Ext.Delim s) :: ss) nt_count tags result =
   453             symb_of ss nt_count tags
   454               (Terminal (Lexicon.Token (Lexicon.Literal, s, Position.no_range)) :: result)
   455         | symb_of ((Syn_Ext.Argument (s, p)) :: ss) nt_count tags result =
   456             let
   457               val (nt_count', tags', new_symb) =
   458                 case Lexicon.predef_term s of
   459                   NONE =>
   460                     let val (nt_count', tags', s_tag) = get_tag nt_count tags s;
   461                     in (nt_count', tags', Nonterminal (s_tag, p)) end
   462                 | SOME tk => (nt_count, tags, Terminal tk);
   463             in symb_of ss nt_count' tags' (new_symb :: result) end
   464         | symb_of (_ :: ss) nt_count tags result =
   465             symb_of ss nt_count tags result;
   466 
   467       (*Convert list of productions by invoking symb_of for each of them*)
   468       fun prod_of [] nt_count prod_count tags result =
   469             (nt_count, prod_count, tags, result)
   470         | prod_of ((Syn_Ext.XProd (lhs, xsymbs, const, pri)) :: ps)
   471                   nt_count prod_count tags result =
   472           let val (nt_count', tags', lhs_tag) = get_tag nt_count tags lhs;
   473 
   474               val (nt_count'', tags'', prods) =
   475                 symb_of xsymbs nt_count' tags' [];
   476           in prod_of ps nt_count'' (prod_count+1) tags''
   477                      ((lhs_tag, (prods, const, pri)) :: result)
   478           end;
   479 
   480       val (nt_count', prod_count', tags', xprods') =
   481         prod_of xprods nt_count prod_count tags [];
   482 
   483       (*Copy array containing productions of old grammar;
   484         this has to be done to preserve the old grammar while being able
   485         to change the array's content*)
   486       val prods' =
   487         let fun get_prod i = if i < nt_count then Array.sub (prods, i)
   488                              else (([], []), []);
   489         in Array.tabulate (nt_count', get_prod) end;
   490 
   491       val fromto_chains = inverse_chains chains [];
   492 
   493       (*Add new productions to old ones*)
   494       val (fromto_chains', lambdas', _) =
   495         add_prods prods' fromto_chains lambdas NONE xprods';
   496 
   497       val chains' = inverse_chains fromto_chains' [];
   498     in Gram {nt_count = nt_count', prod_count = prod_count', tags = tags',
   499              chains = chains', lambdas = lambdas', prods = prods'}
   500     end;
   501 
   502 fun make_gram xprods = extend_gram xprods empty_gram;
   503 
   504 
   505 (*Merge two grammars*)
   506 fun merge_gram (gram_a, gram_b) =
   507   let
   508     (*find out which grammar is bigger*)
   509     val (Gram {nt_count = nt_count1, prod_count = prod_count1, tags = tags1,
   510                chains = chains1, lambdas = lambdas1, prods = prods1},
   511          Gram {nt_count = nt_count2, prod_count = prod_count2, tags = tags2,
   512                chains = chains2, lambdas = lambdas2, prods = prods2}) =
   513       let val Gram {prod_count = count_a, ...} = gram_a;
   514           val Gram {prod_count = count_b, ...} = gram_b;
   515       in if count_a > count_b then (gram_a, gram_b)
   516                               else (gram_b, gram_a)
   517       end;
   518 
   519     (*get existing tag from grammar1 or create a new one*)
   520     fun get_tag nt_count tags nt =
   521       case Symtab.lookup tags nt of
   522         SOME tag => (nt_count, tags, tag)
   523       | NONE => (nt_count+1, Symtab.update_new (nt, nt_count) tags,
   524                 nt_count)
   525 
   526     val ((nt_count1', tags1'), tag_table) =
   527       let val tag_list = Symtab.dest tags2;
   528 
   529           val table = Array.array (nt_count2, ~1);
   530 
   531           fun store_tag nt_count tags ~1 = (nt_count, tags)
   532             | store_tag nt_count tags tag =
   533               let val (nt_count', tags', tag') =
   534                    get_tag nt_count tags
   535                      (fst (the (find_first (fn (n, t) => t = tag) tag_list)));
   536               in Array.update (table, tag, tag');
   537                  store_tag nt_count' tags' (tag-1)
   538               end;
   539       in (store_tag nt_count1 tags1 (nt_count2-1), table) end;
   540 
   541     (*convert grammar2 tag to grammar1 tag*)
   542     fun convert_tag tag = Array.sub (tag_table, tag);
   543 
   544     (*convert chain list to raw productions*)
   545     fun mk_chain_prods [] result = result
   546       | mk_chain_prods ((to, froms) :: cs) result =
   547         let
   548           val to_tag = convert_tag to;
   549 
   550           fun make [] result = result
   551             | make (from :: froms) result = make froms ((to_tag,
   552                 ([Nonterminal (convert_tag from, ~1)], "", ~1)) :: result);
   553         in mk_chain_prods cs (make froms [] @ result) end;
   554 
   555     val chain_prods = mk_chain_prods chains2 [];
   556 
   557     (*convert prods2 array to productions*)
   558     fun process_nt ~1 result = result
   559       | process_nt nt result =
   560         let
   561           val nt_prods = Library.foldl (uncurry (union (op =)))
   562             ([], map snd (snd (Array.sub (prods2, nt))));
   563           val lhs_tag = convert_tag nt;
   564 
   565           (*convert tags in rhs*)
   566           fun process_rhs [] result = result
   567             | process_rhs (Terminal tk :: rhs) result =
   568                 process_rhs rhs (result @ [Terminal tk])
   569             | process_rhs (Nonterminal (nt, prec) :: rhs) result =
   570                 process_rhs rhs
   571                             (result @ [Nonterminal (convert_tag nt, prec)]);
   572 
   573           (*convert tags in productions*)
   574           fun process_prods [] result = result
   575             | process_prods ((rhs, id, prec) :: ps) result =
   576                 process_prods ps ((lhs_tag, (process_rhs rhs [], id, prec))
   577                                   :: result);
   578         in process_nt (nt-1) (process_prods nt_prods [] @ result) end;
   579 
   580     val raw_prods = chain_prods @ process_nt (nt_count2-1) [];
   581 
   582     val prods1' =
   583       let fun get_prod i = if i < nt_count1 then Array.sub (prods1, i)
   584                            else (([], []), []);
   585       in Array.tabulate (nt_count1', get_prod) end;
   586 
   587     val fromto_chains = inverse_chains chains1 [];
   588 
   589     val (fromto_chains', lambdas', SOME prod_count1') =
   590       add_prods prods1' fromto_chains lambdas1 (SOME prod_count1) raw_prods;
   591 
   592     val chains' = inverse_chains fromto_chains' [];
   593   in Gram {nt_count = nt_count1', prod_count = prod_count1',
   594            tags = tags1', chains = chains', lambdas = lambdas',
   595            prods = prods1'}
   596   end;
   597 
   598 
   599 (** Parser **)
   600 
   601 datatype parsetree =
   602   Node of string * parsetree list |
   603   Tip of Lexicon.token;
   604 
   605 type state =
   606   nt_tag * int *                (*identification and production precedence*)
   607   parsetree list *              (*already parsed nonterminals on rhs*)
   608   symb list *                   (*rest of rhs*)
   609   string *                      (*name of production*)
   610   int;                          (*index for previous state list*)
   611 
   612 
   613 (*Get all rhss with precedence >= minPrec*)
   614 fun getRHS minPrec = filter (fn (_, _, prec:int) => prec >= minPrec);
   615 
   616 (*Get all rhss with precedence >= minPrec and < maxPrec*)
   617 fun getRHS' minPrec maxPrec =
   618   filter (fn (_, _, prec:int) => prec >= minPrec andalso prec < maxPrec);
   619 
   620 (*Make states using a list of rhss*)
   621 fun mkStates i minPrec lhsID rhss =
   622   let fun mkState (rhs, id, prodPrec) = (lhsID, prodPrec, [], rhs, id, i);
   623   in map mkState rhss end;
   624 
   625 (*Add parse tree to list and eliminate duplicates
   626   saving the maximum precedence*)
   627 fun conc (t: parsetree list, prec:int) [] = (NONE, [(t, prec)])
   628   | conc (t, prec) ((t', prec') :: ts) =
   629       if t = t' then
   630         (SOME prec', if prec' >= prec then (t', prec') :: ts
   631                      else (t, prec) :: ts)
   632       else
   633         let val (n, ts') = conc (t, prec) ts
   634         in (n, (t', prec') :: ts') end;
   635 
   636 (*Update entry in used*)
   637 fun update_trees ((B: nt_tag, (i, ts)) :: used) (A, t) =
   638   if A = B then
   639     let val (n, ts') = conc t ts
   640     in ((A, (i, ts')) :: used, n) end
   641   else
   642     let val (used', n) = update_trees used (A, t)
   643     in ((B, (i, ts)) :: used', n) end;
   644 
   645 (*Replace entry in used*)
   646 fun update_prec (A: nt_tag, prec) used =
   647   let fun update ((hd as (B, (_, ts))) :: used, used') =
   648         if A = B
   649         then used' @ ((A, (prec, ts)) :: used)
   650         else update (used, hd :: used')
   651   in update (used, []) end;
   652 
   653 fun getS A maxPrec Si =
   654   filter
   655     (fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
   656           => A = B andalso prec <= maxPrec
   657       | _ => false) Si;
   658 
   659 fun getS' A maxPrec minPrec Si =
   660   filter
   661     (fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
   662           => A = B andalso prec > minPrec andalso prec <= maxPrec
   663       | _ => false) Si;
   664 
   665 fun getStates Estate i ii A maxPrec =
   666   filter
   667     (fn (_, _, _, Nonterminal (B, prec) :: _, _, _)
   668           => A = B andalso prec <= maxPrec
   669       | _ => false)
   670     (Array.sub (Estate, ii));
   671 
   672 
   673 fun movedot_term (A, j, ts, Terminal a :: sa, id, i) c =
   674   if Lexicon.valued_token c then
   675     (A, j, ts @ [Tip c], sa, id, i)
   676   else (A, j, ts, sa, id, i);
   677 
   678 fun movedot_nonterm ts (A, j, tss, Nonterminal _ :: sa, id, i) =
   679   (A, j, tss @ ts, sa, id, i);
   680 
   681 fun movedot_lambda _ [] = []
   682   | movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ((t, ki) :: ts) =
   683       if k <= ki then
   684         (B, j, tss @ t, sa, id, i) ::
   685           movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ts
   686       else movedot_lambda (B, j, tss, Nonterminal (A, k) :: sa, id, i) ts;
   687 
   688 
   689 val branching_level = Unsynchronized.ref 600;   (*trigger value for warnings*)
   690 
   691 (*get all productions of a NT and NTs chained to it which can
   692   be started by specified token*)
   693 fun prods_for prods chains include_none tk nts =
   694   let
   695       fun token_assoc (list, key) =
   696         let fun assoc [] result = result
   697               | assoc ((keyi, pi) :: pairs) result =
   698                   if is_some keyi andalso Lexicon.matching_tokens (the keyi, key)
   699                      orelse include_none andalso is_none keyi then
   700                     assoc pairs (pi @ result)
   701                   else assoc pairs result;
   702         in assoc list [] end;
   703 
   704       fun get_prods [] result = result
   705         | get_prods (nt :: nts) result =
   706           let val nt_prods = snd (Array.sub (prods, nt));
   707           in get_prods nts ((token_assoc (nt_prods, tk)) @ result) end;
   708   in get_prods (connected_with chains nts nts) [] end;
   709 
   710 
   711 fun PROCESSS warned prods chains Estate i c states =
   712   let
   713     fun all_prods_for nt = prods_for prods chains true c [nt];
   714 
   715     fun processS used [] (Si, Sii) = (Si, Sii)
   716       | processS used (S :: States) (Si, Sii) =
   717           (case S of
   718             (_, _, _, Nonterminal (nt, minPrec) :: _, _, _) =>
   719               let                                       (*predictor operation*)
   720                 val (used', new_states) =
   721                   (case AList.lookup (op =) used nt of
   722                     SOME (usedPrec, l) =>       (*nonterminal has been processed*)
   723                       if usedPrec <= minPrec then
   724                                           (*wanted precedence has been processed*)
   725                         (used, movedot_lambda S l)
   726                       else            (*wanted precedence hasn't been parsed yet*)
   727                         let
   728                           val tk_prods = all_prods_for nt;
   729 
   730                           val States' = mkStates i minPrec nt
   731                                           (getRHS' minPrec usedPrec tk_prods);
   732                         in (update_prec (nt, minPrec) used,
   733                             movedot_lambda S l @ States')
   734                         end
   735 
   736                   | NONE =>           (*nonterminal is parsed for the first time*)
   737                       let val tk_prods = all_prods_for nt;
   738                           val States' = mkStates i minPrec nt
   739                                           (getRHS minPrec tk_prods);
   740                       in ((nt, (minPrec, [])) :: used, States') end);
   741 
   742                 val dummy =
   743                   if not (!warned) andalso
   744                      length (new_states @ States) > (!branching_level) then
   745                     (warning "Currently parsed expression could be extremely ambiguous.";
   746                      warned := true)
   747                   else ();
   748               in
   749                 processS used' (new_states @ States) (S :: Si, Sii)
   750               end
   751           | (_, _, _, Terminal a :: _, _, _) =>               (*scanner operation*)
   752               processS used States
   753                 (S :: Si,
   754                   if Lexicon.matching_tokens (a, c) then movedot_term S c :: Sii else Sii)
   755           | (A, prec, ts, [], id, j) =>                   (*completer operation*)
   756               let val tt = if id = "" then ts else [Node (id, ts)] in
   757                 if j = i then                             (*lambda production?*)
   758                   let
   759                     val (used', O) = update_trees used (A, (tt, prec));
   760                   in
   761                     case O of
   762                       NONE =>
   763                         let val Slist = getS A prec Si;
   764                             val States' = map (movedot_nonterm tt) Slist;
   765                         in processS used' (States' @ States) (S :: Si, Sii) end
   766                     | SOME n =>
   767                         if n >= prec then processS used' States (S :: Si, Sii)
   768                         else
   769                           let val Slist = getS' A prec n Si;
   770                               val States' = map (movedot_nonterm tt) Slist;
   771                           in processS used' (States' @ States) (S :: Si, Sii) end
   772                   end
   773                 else
   774                   let val Slist = getStates Estate i j A prec
   775                   in processS used (map (movedot_nonterm tt) Slist @ States)
   776                               (S :: Si, Sii)
   777                   end
   778               end)
   779   in processS [] states ([], []) end;
   780 
   781 
   782 fun produce warned prods tags chains stateset i indata prev_token =
   783   (case Array.sub (stateset, i) of
   784     [] =>
   785       let
   786         val toks = if Lexicon.is_eof prev_token then indata else prev_token :: indata;
   787         val pos = Position.str_of (Lexicon.pos_of_token prev_token);
   788       in
   789         if null toks then error ("Inner syntax error: unexpected end of input" ^ pos)
   790         else error (Pretty.string_of (Pretty.block
   791           (Pretty.str ("Inner syntax error" ^ pos ^ " at \"") ::
   792             Pretty.breaks (map (Pretty.str o Lexicon.str_of_token) (#1 (split_last toks))) @
   793             [Pretty.str "\""])))
   794       end
   795   | s =>
   796     (case indata of
   797        [] => Array.sub (stateset, i)
   798      | c :: cs =>
   799        let val (si, sii) = PROCESSS warned prods chains stateset i c s;
   800        in Array.update (stateset, i, si);
   801           Array.update (stateset, i + 1, sii);
   802           produce warned prods tags chains stateset (i + 1) cs c
   803        end));
   804 
   805 
   806 fun get_trees l = map_filter (fn (_, _, [pt], _, _, _) => SOME pt | _ => NONE) l;
   807 
   808 fun earley prods tags chains startsymbol indata =
   809   let
   810     val start_tag =
   811       (case Symtab.lookup tags startsymbol of
   812         SOME tag => tag
   813       | NONE => error ("Inner syntax: unknown startsymbol " ^ quote startsymbol));
   814     val S0 = [(~1, 0, [], [Nonterminal (start_tag, 0), Terminal Lexicon.eof], "", 0)];
   815     val s = length indata + 1;
   816     val Estate = Array.array (s, []);
   817   in
   818     Array.update (Estate, 0, S0);
   819     get_trees (produce (Unsynchronized.ref false) prods tags chains Estate 0 indata Lexicon.eof)
   820   end;
   821 
   822 
   823 fun parse (Gram {tags, prods, chains, ...}) start toks =
   824   let
   825     val end_pos =
   826       (case try List.last toks of
   827         NONE => Position.none
   828       | SOME (Lexicon.Token (_, _, (_, end_pos))) => end_pos);
   829     val r =
   830       (case earley prods tags chains start (toks @ [Lexicon.mk_eof end_pos]) of
   831         [] => raise Fail "no parse trees"
   832       | pts => pts);
   833   in r end;
   834 
   835 
   836 fun guess_infix_lr (Gram gram) c = (*based on educated guess*)
   837   let
   838     fun freeze a = map_range (curry Array.sub a) (Array.length a);
   839     val prods = maps snd (maps snd (freeze (#prods gram)));
   840     fun guess (SOME ([Nonterminal (_, k),
   841             Terminal (Lexicon.Token (Lexicon.Literal, s, _)), Nonterminal (_, l)], _, j)) =
   842           if k = j andalso l = j + 1 then SOME (s, true, false, j)
   843           else if k = j + 1 then if l = j then SOME (s, false, true, j)
   844             else if l = j + 1 then SOME (s, false, false, j)
   845             else NONE
   846           else NONE
   847       | guess _ = NONE;
   848   in guess (find_first (fn (_, s, _) => s = c) prods) end;
   849 
   850 end;