Robust/cup/java_cup/non_terminal.java

   1 package java_cup;
   2
   3 import java.util.Hashtable;
   4 import java.util.Enumeration;
   5
   6 /** This class represents a non-terminal symbol in the grammar.  Each
   7  *  non terminal has a textual name, an index, and a string which indicates
   8  *  the type of object it will be implemented with at runtime (i.e. the class
   9  *  of object that will be pushed on the parse stack to represent it).
  10  *
  11  * @version last updated: 11/25/95
  12  * @author  Scott Hudson
  13  */
  14
  15 public class non_terminal extends symbol {
  16
  17   /*-----------------------------------------------------------*/
  18   /*--- Constructor(s) ----------------------------------------*/
  19   /*-----------------------------------------------------------*/
  20
  21   /** Full constructor.
  22    * @param nm  the name of the non terminal.
  23    * @param tp  the type string for the non terminal.
  24    */
  25   public non_terminal(String nm, String tp)
  26     {
  27       /* super class does most of the work */
  28       super(nm, tp);
  29
  30       /* add to set of all non terminals and check for duplicates */
  31       Object conflict = _all.put(nm,this);
  32       if (conflict != null)
  33         // can't throw an exception here because these are used in static
  34         // initializers, so we crash instead
  35         // was:
  36         // throw new internal_error("Duplicate non-terminal ("+nm+") created");
  37         (new internal_error("Duplicate non-terminal ("+nm+") created")).crash();
  38
  39       /* assign a unique index */
  40       _index = next_index++;
  41
  42       /* add to by_index set */
  43       _all_by_index.put(new Integer(_index), this);
  44     }
  45
  46   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  47
  48   /** Constructor with default type.
  49    * @param nm  the name of the non terminal.
  50    */
  51   public non_terminal(String nm)
  52     {
  53       this(nm, null);
  54     }
  55
  56   /*-----------------------------------------------------------*/
  57   /*--- (Access to) Static (Class) Variables ------------------*/
  58   /*-----------------------------------------------------------*/
  59
  60   /** Table of all non-terminals -- elements are stored using name strings
  61    *  as the key
  62    */
  63   protected static Hashtable _all = new Hashtable();
  64
  65   /** Access to all non-terminals. */
  66   public static Enumeration all() {return _all.elements();}
  67
  68   /** lookup a non terminal by name string */
  69   public static non_terminal find(String with_name)
  70     {
  71       if (with_name == null)
  72         return null;
  73       else
  74         return (non_terminal)_all.get(with_name);
  75     }
  76
  77   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  78
  79   /** Table of all non terminals indexed by their index number. */
  80   protected static Hashtable _all_by_index = new Hashtable();
  81
  82   /** Lookup a non terminal by index. */
  83   public static non_terminal find(int indx)
  84     {
  85       Integer the_indx = new Integer(indx);
  86
  87       return (non_terminal)_all_by_index.get(the_indx);
  88     }
  89
  90   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  91
  92   /** Total number of non-terminals. */
  93   public static int number() {return _all.size();}
  94
  95   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
  96
  97   /** Static counter to assign unique indexes. */
  98   protected static int next_index = 0;
  99
 100   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 101
 102   /** Static counter for creating unique non-terminal names */
 103   static protected int next_nt = 0;
 104
 105   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 106
 107   /** special non-terminal for start symbol */
 108   public static final non_terminal START_nt = new non_terminal("$START");
 109
 110   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 111
 112   /** flag non-terminals created to embed action productions */
 113   public boolean is_embedded_action = false; /* added 24-Mar-1998, CSA */
 114
 115   /*-----------------------------------------------------------*/
 116   /*--- Static Methods ----------------------------------------*/
 117   /*-----------------------------------------------------------*/
 118
 119   /** Method for creating a new uniquely named hidden non-terminal using
 120    *  the given string as a base for the name (or "NT$" if null is passed).
 121    * @param prefix base name to construct unique name from.
 122    */
 123   static non_terminal create_new(String prefix) throws internal_error
 124     {
 125       if (prefix == null) prefix = "NT$";
 126       return new non_terminal(prefix + next_nt++);
 127     }
 128
 129   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 130
 131   /** static routine for creating a new uniquely named hidden non-terminal */
 132   static non_terminal create_new() throws internal_error
 133     {
 134       return create_new(null);
 135     }
 136
 137   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 138
 139   /** Compute nullability of all non-terminals. */
 140   public static void compute_nullability() throws internal_error
 141     {
 142       boolean      change = true;
 143       non_terminal nt;
 144       Enumeration  e;
 145       production   prod;
 146
 147       /* repeat this process until there is no change */
 148       while (change)
 149         {
 150           /* look for a new change */
 151           change = false;
 152
 153           /* consider each non-terminal */
 154           for (e=all(); e.hasMoreElements(); )
 155             {
 156               nt = (non_terminal)e.nextElement();
 157
 158               /* only look at things that aren't already marked nullable */
 159               if (!nt.nullable())
 160                 {
 161                   if (nt.looks_nullable())
 162                     {
 163                       nt._nullable = true;
 164                       change = true;
 165                     }
 166                 }
 167             }
 168         }
 169
 170       /* do one last pass over the productions to finalize all of them */
 171       for (e=production.all(); e.hasMoreElements(); )
 172         {
 173           prod = (production)e.nextElement();
 174           prod.set_nullable(prod.check_nullable());
 175         }
 176     }
 177
 178   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 179
 180   /** Compute first sets for all non-terminals.  This assumes nullability has
 181    *  already computed.
 182    */
 183   public static void compute_first_sets() throws internal_error
 184     {
 185       boolean      change = true;
 186       Enumeration  n;
 187       Enumeration  p;
 188       non_terminal nt;
 189       production   prod;
 190       terminal_set prod_first;
 191
 192       /* repeat this process until we have no change */
 193       while (change)
 194         {
 195           /* look for a new change */
 196           change = false;
 197
 198           /* consider each non-terminal */
 199           for (n = all(); n.hasMoreElements(); )
 200             {
 201               nt = (non_terminal)n.nextElement();
 202
 203               /* consider every production of that non terminal */
 204               for (p = nt.productions(); p.hasMoreElements(); )
 205                 {
 206                   prod = (production)p.nextElement();
 207
 208                   /* get the updated first of that production */
 209                   prod_first = prod.check_first_set();
 210
 211                   /* if this going to add anything, add it */
 212                   if (!prod_first.is_subset_of(nt._first_set))
 213                     {
 214                       change = true;
 215                       nt._first_set.add(prod_first);
 216                     }
 217                 }
 218             }
 219         }
 220     }
 221
 222   /*-----------------------------------------------------------*/
 223   /*--- (Access to) Instance Variables ------------------------*/
 224   /*-----------------------------------------------------------*/
 225
 226   /** Table of all productions with this non terminal on the LHS. */
 227   protected Hashtable _productions = new Hashtable(11);
 228
 229   /** Access to productions with this non terminal on the LHS. */
 230   public Enumeration productions() {return _productions.elements();}
 231
 232   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 233
 234   /** Total number of productions with this non terminal on the LHS. */
 235   public int num_productions() {return _productions.size();}
 236
 237   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 238
 239   /** Add a production to our set of productions. */
 240   public void add_production(production prod) throws internal_error
 241     {
 242       /* catch improper productions */
 243       if (prod == null || prod.lhs() == null || prod.lhs().the_symbol() != this)
 244         throw new internal_error(
 245           "Attempt to add invalid production to non terminal production table");
 246
 247       /* add it to the table, keyed with itself */
 248       _productions.put(prod,prod);
 249     }
 250
 251   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 252
 253   /** Nullability of this non terminal. */
 254   protected boolean _nullable;
 255
 256   /** Nullability of this non terminal. */
 257   public boolean nullable() {return _nullable;}
 258
 259   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 260
 261   /** First set for this non-terminal. */
 262   protected terminal_set _first_set = new terminal_set();
 263
 264   /** First set for this non-terminal. */
 265   public terminal_set first_set() {return _first_set;}
 266
 267   /*-----------------------------------------------------------*/
 268   /*--- General Methods ---------------------------------------*/
 269   /*-----------------------------------------------------------*/
 270
 271   /** Indicate that this symbol is a non-terminal. */
 272   public boolean is_non_term()
 273     {
 274       return true;
 275     }
 276
 277   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 278
 279   /** Test to see if this non terminal currently looks nullable. */
 280   protected boolean looks_nullable() throws internal_error
 281     {
 282       /* look and see if any of the productions now look nullable */
 283       for (Enumeration e = productions(); e.hasMoreElements(); )
 284         /* if the production can go to empty, we are nullable */
 285         if (((production)e.nextElement()).check_nullable())
 286           return true;
 287
 288       /* none of the productions can go to empty, so we are not nullable */
 289       return false;
 290     }
 291
 292   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
 293
 294   /** convert to string */
 295   public String toString()
 296     {
 297       return super.toString() + "[" + index() + "]" + (nullable() ? "*" : "");
 298     }
 299
 300   /*-----------------------------------------------------------*/
 301 }