lib-src/automata/graminfo.cc

   1 //////////////////////////////////////////////////////////////////////////////
   2 // NOTICE:
   3 //
   4 // ADLib, Prop and their related set of tools and documentation are in the
   5 // public domain.   The author(s) of this software reserve no copyrights on
   6 // the source code and any code generated using the tools.  You are encouraged
   7 // to use ADLib and Prop to develop software, in both academic and commercial
   8 // settings, and are free to incorporate any part of ADLib and Prop into
   9 // your programs.
  10 //
  11 // Although you are under no obligation to do so, we strongly recommend that
  12 // you give away all software developed using our tools.
  13 //
  14 // We also ask that credit be given to us when ADLib and/or Prop are used in
  15 // your programs, and that this notice be preserved intact in all the source
  16 // code.
  17 //
  18 // This software is still under development and we welcome any suggestions
  19 // and help from the users.
  20 //
  21 // Allen Leung
  22 // 1994
  23 //////////////////////////////////////////////////////////////////////////////
  24
  25 #include <string.h>
  26 #include <AD/automata/graminfo.h>
  27 #include <AD/sort/shellsrt.h>  // Shell sort
  28
  29 Bool add_set (register int i, register Byte * a_set, register Byte * b_set)
  30 {  register Byte changed;
  31    for (changed = 0; i > 0; i--, a_set++, b_set++) {
  32       changed |= ~ *a_set & *b_set;
  33       *a_set |= *b_set;
  34    }
  35    return changed;
  36 }
  37
  38 void GrammarInfo::compute_info(const Grammar& G)
  39 {  register Production P;
  40    register Symbol X;
  41    register int i;
  42
  43    clear_info();
  44
  45    min_non_terminal  = 32767;
  46    max_non_terminal  = -32768;
  47
  48    //
  49    // Preprocess the grammar; compute the following information:
  50    //
  51    //   max_non_terminal  -- maximal value of a non-terminal
  52    //   min_non_terminal  -- minimal value of a non-terminal
  53    //   productions[i]    -- an array of productions terminated by
  54    //                           Grammar::END_PRODUCTION
  55    //
  56
  57    productions = new Production [ G.size() ];
  58
  59    for (i = 0; i < G.size(); i++) {
  60       P = productions[i] = G[i];
  61       while ( (X = *P++) != Grammar::END_PRODUCTION) {
  62          if (G.isNonTerminal(X)) {
  63             if (X > max_non_terminal) max_non_terminal = X;
  64             if (X < min_non_terminal) min_non_terminal = X;
  65          }
  66       }
  67    }
  68    production_size = i;
  69
  70    //
  71    // Sort by left hand side non-terminal
  72    //
  73    shellSort(Production, productions, G.size(),
  74              key[0] < productions[i][0] );
  75
  76    //
  77    // compute the amount of storage needed to store the tables:
  78    //
  79    number_of_non_terminals = max_non_terminal - min_non_terminal + 1;
  80    nullable = new Bool [ number_of_non_terminals ];
  81    memset(nullable,0,number_of_non_terminals * sizeof(Bool));
  82    nullable -= min_non_terminal;
  83
  84    first.create(min_non_terminal,max_non_terminal,G.min_terminal(),G.max_terminal());
  85    follow.create(min_non_terminal,max_non_terminal,G.min_terminal(),G.max_terminal());
  86
  87    //
  88    // Iterate and compute the fix points of first and follow and nullable:
  89    //
  90    //   For each A -> X_1 X_2 ... X_n
  91    //
  92    //   nullable(A) = /\_i nullable(X_i)
  93    //   Let first(c)    = { c }
  94    //   first(A)    <- first(X_i) if nullable(X_1 X_2 ... X_{i-1} c)
  95    //   follow(X_i) <- first(X_{i+1})
  96    //
  97    //
  98    Bool changed;
  99    do {
 100       changed = false;
 101       for (i = G.size() - 1; i >= 0; i--) {
 102          register NonTerminal A;
 103          register Symbol Y = max_non_terminal + 1;  // Last symbol
 104          Bool epsilon = true;
 105          for ( P = productions[i], A = *P++; (X = *P) != END_PRODUCTION; P++) {
 106             if (G.isAction(X)) {           // X is an action symbol; skip it
 107             } else if (G.isTerminal(X)) {  // X is a terminal
 108                if (G.isNonTerminal(Y) && ! follow.has(Y,X))
 109                   { follow.insert(Y,X); changed = true; }
 110                if (epsilon && ! first.has(A,X))
 111                   { first.insert(A,X); changed = true; }
 112                epsilon = false;
 113                Y = X;
 114             } else {                       // X is a nonterminal
 115                if (G.isNonTerminal(Y) &&
 116                    add_set(first.set_size(),follow(X),first(Y))) changed = true;
 117                if (epsilon && add_set(first.set_size(),first(A),first(X)))
 118                    changed = true;
 119                if (! nullable[X]) epsilon = false;
 120                Y = X;
 121             }
 122          }
 123          if (epsilon && ! nullable[A]) { nullable[A] = true; changed = true; }
 124       }
 125    } while (changed);
 126 }
 127
 128 void GrammarInfo::clear_info()
 129 {  if (nullable) {
 130       delete [] productions;
 131       delete [] (nullable + min_non_terminal);
 132       first.destroy();
 133       follow.destroy();
 134       nullable = 0;
 135    }
 136 }
 137
 138 GrammarInfo::~GrammarInfo()
 139 {  clear_info(); }