non_terminal


1   package com.sun.java_cup.internal;
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 }
302
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags