lib-src/automata/follow.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 <AD/automata/follow.h>
  26
  27 //////////////////////////////////////////////////////////////////////////////
  28 //  Constructor
  29 //////////////////////////////////////////////////////////////////////////////
  30 FollowSet::FollowSet(const Grammar& g, Mem& m) : FirstSet(g,m)
  31 {  // int  min      = G.min_terminal();
  32    int  max      = G.max_non_terminal();
  33    int  set_size = G.max_terminal() + 1;
  34
  35    ///////////////////////////////////////////////////////////////////////////
  36    //  Allocate memory for the follow set
  37    ///////////////////////////////////////////////////////////////////////////
  38    follow_set = (BitSet**)m.c_alloc(sizeof(BitSet*) * (max + 1));
  39    {  for (int i = G.min_non_terminal(); i <= G.max_non_terminal(); i++) {
  40          follow_set[i] = new (m, set_size) BitSet;
  41       }
  42    }
  43
  44    ///////////////////////////////////////////////////////////////////////////
  45    //  Compute the follow set.
  46    //  Iterate until fixed point is reached
  47    ///////////////////////////////////////////////////////////////////////////
  48    Bool changed;
  49    do {
  50       changed = false;
  51       ////////////////////////////////////////////////////////////////////////
  52       //  For each production A -> xyz.
  53       //  For each non-terminal X in    A -> a X b
  54       //    (1)   new follow(X) = follow(X) union first(b)
  55       //    (2)   new follow(X) = follow(X) union follow(A)  if nullable(b)
  56       ////////////////////////////////////////////////////////////////////////
  57       for (int i = g.size() - 1; i >= 0; i--) {
  58          register Symbol     X;
  59          register Production P = g[i];
  60                   Symbol     A = P[0]; // A -> a X b
  61          for (P++; (X = *P++) != Grammar::END_PRODUCTION; ) {
  62             if (g.isNonTerminal(X)              &&
  63                 first(*follow_set[X],P,changed) &&
  64                 X != A                          && // a slight optimization
  65                 follow_set[X]->Union_if_changed(*follow_set[A]))
  66                changed = true;
  67          }
  68       }
  69    } while (changed);
  70 }
  71
  72 //////////////////////////////////////////////////////////////////////////////
  73 //  Destructor.  Do nothing since memory is handled by the memory pool
  74 //////////////////////////////////////////////////////////////////////////////
  75 FollowSet::~FollowSet() {}