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