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