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