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