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