Home | History | Annotate | Download | only in java_cup 
      1 package java_cup;
      2 
      3 import java.util.Enumeration;
      4 import java.util.Hashtable;
      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 
     43   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
     44 
     45   /** Constructor with default type.
     46    * @param nm  the name of the non terminal.
     47    */
     48   public non_terminal(String nm)
     49     {
     50       this(nm, null);
     51     }
     52 
     53   /*-----------------------------------------------------------*/
     54   /*--- (Access to) Static (Class) Variables ------------------*/
     55   /*-----------------------------------------------------------*/
     56 
     57   /** Table of all non-terminals -- elements are stored using name strings
     58    *  as the key
     59    */
     60   protected static Hashtable _all = new Hashtable();
     61 
     62   /** Access to all non-terminals. */
     63   public static Enumeration all() {return _all.elements();};
     64 
     65   /** lookup a non terminal by name string */
     66   public static non_terminal find(String with_name)
     67     {
     68       if (with_name == null)
     69         return null;
     70       else
     71         return (non_terminal)_all.get(with_name);
     72     }
     73 
     74   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
     75 
     76   /** Total number of non-terminals. */
     77   public static int number() {return _all.size();};
     78 
     79   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
     80 
     81   /** Static counter to assign unique indexes. */
     82   protected static int next_index = 0;
     83 
     84   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
     85 
     86   /** Static counter for creating unique non-terminal names */
     87   static protected int next_nt = 0;
     88 
     89   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
     90 
     91   /** special non-terminal for start symbol */
     92   public static final non_terminal START_nt = new non_terminal("$START");
     93 
     94   /*-----------------------------------------------------------*/
     95   /*--- Static Methods ----------------------------------------*/
     96   /*-----------------------------------------------------------*/
     97 
     98   /** Method for creating a new uniquely named hidden non-terminal using
     99    *  the given string as a base for the name (or "NT$" if null is passed).
    100    * @param prefix base name to construct unique name from.
    101    */
    102   static non_terminal create_new(String prefix) throws internal_error
    103     {
    104       if (prefix == null) prefix = "NT$";
    105       return new non_terminal(prefix + next_nt++);
    106     }
    107 
    108   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
    109 
    110   /** static routine for creating a new uniquely named hidden non-terminal */
    111   static non_terminal create_new() throws internal_error
    112     {
    113       return create_new(null);
    114     }
    115 
    116   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
    117 
    118   /** Compute nullability of all non-terminals. */
    119   public static void compute_nullability() throws internal_error
    120     {
    121       boolean      change = true;
    122       non_terminal nt;
    123       Enumeration  e;
    124       production   prod;
    125 
    126       /* repeat this process until there is no change */
    127       while (change)
    128     {
    129       /* look for a new change */
    130       change = false;
    131 
    132       /* consider each non-terminal */
    133       for (e=all(); e.hasMoreElements(); )
    134         {
    135           nt = (non_terminal)e.nextElement();
    136 
    137           /* only look at things that aren't already marked nullable */
    138           if (!nt.nullable())
    139         {
    140           if (nt.looks_nullable())
    141             {
    142               nt._nullable = true;
    143               change = true;
    144             }
    145         }
    146         }
    147     }
    148 
    149       /* do one last pass over the productions to finalize all of them */
    150       for (e=production.all(); e.hasMoreElements(); )
    151     {
    152       prod = (production)e.nextElement();
    153       prod.set_nullable(prod.check_nullable());
    154     }
    155     }
    156 
    157   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
    158 
    159   /** Compute first sets for all non-terminals.  This assumes nullability has
    160    *  already computed.
    161    */
    162   public static void compute_first_sets() throws internal_error
    163     {
    164       boolean      change = true;
    165       Enumeration  n;
    166       Enumeration  p;
    167       non_terminal nt;
    168       production   prod;
    169       terminal_set prod_first;
    170 
    171       /* repeat this process until we have no change */
    172       while (change)
    173     {
    174       /* look for a new change */
    175       change = false;
    176 
    177       /* consider each non-terminal */
    178       for (n = all(); n.hasMoreElements(); )
    179         {
    180           nt = (non_terminal)n.nextElement();
    181 
    182           /* consider every production of that non terminal */
    183           for (p = nt.productions(); p.hasMoreElements(); )
    184         {
    185           prod = (production)p.nextElement();
    186 
    187           /* get the updated first of that production */
    188           prod_first = prod.check_first_set();
    189 
    190           /* if this going to add anything, add it */
    191           if (!prod_first.is_subset_of(nt._first_set))
    192             {
    193               change = true;
    194               nt._first_set.add(prod_first);
    195             }
    196         }
    197         }
    198     }
    199     }
    200 
    201   /*-----------------------------------------------------------*/
    202   /*--- (Access to) Instance Variables ------------------------*/
    203   /*-----------------------------------------------------------*/
    204 
    205   /** Table of all productions with this non terminal on the LHS. */
    206   protected Hashtable _productions = new Hashtable(11);
    207 
    208   /** Access to productions with this non terminal on the LHS. */
    209   public Enumeration productions() {return _productions.elements();};
    210 
    211   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
    212 
    213   /** Total number of productions with this non terminal on the LHS. */
    214   public int num_productions() {return _productions.size();};
    215 
    216   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
    217 
    218   /** Add a production to our set of productions. */
    219   public void add_production(production prod) throws internal_error
    220     {
    221       /* catch improper productions */
    222       if (prod == null || prod.lhs() == null || prod.lhs().the_symbol() != this)
    223     throw new internal_error(
    224       "Attempt to add invalid production to non terminal production table");
    225 
    226       /* add it to the table, keyed with itself */
    227       _productions.put(prod,prod);
    228     }
    229 
    230   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
    231 
    232   /** Nullability of this non terminal. */
    233   protected boolean _nullable;
    234 
    235   /** Nullability of this non terminal. */
    236   public boolean nullable() {return _nullable;}
    237 
    238   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
    239 
    240   /** First set for this non-terminal. */
    241   protected terminal_set _first_set = new terminal_set();
    242 
    243   /** First set for this non-terminal. */
    244   public terminal_set first_set() {return _first_set;}
    245 
    246   /*-----------------------------------------------------------*/
    247   /*--- General Methods ---------------------------------------*/
    248   /*-----------------------------------------------------------*/
    249 
    250   /** Indicate that this symbol is a non-terminal. */
    251   public boolean is_non_term()
    252     {
    253       return true;
    254     }
    255 
    256   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
    257 
    258   /** Test to see if this non terminal currently looks nullable. */
    259   protected boolean looks_nullable() throws internal_error
    260     {
    261       /* look and see if any of the productions now look nullable */
    262       for (Enumeration e = productions(); e.hasMoreElements(); )
    263     /* if the production can go to empty, we are nullable */
    264     if (((production)e.nextElement()).check_nullable())
    265       return true;
    266 
    267       /* none of the productions can go to empty, so we are not nullable */
    268       return false;
    269     }
    270 
    271   /*. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .*/
    272 
    273   /** convert to string */
    274   public String toString()
    275     {
    276       return super.toString() + "[" + index() + "]" + (nullable() ? "*" : "");
    277     }
    278 
    279   /*-----------------------------------------------------------*/
    280 };
    281