Production


1   /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2    * This file is part of Beaver Parser Generator.                       *
3    * Copyright (C) 2003,2004 Alexander Demenchuk <alder@softanvil.com>.  *
4    * All rights reserved.                                                *
5    * See the file "LICENSE" for the terms and conditions for copying,    *
6    * distribution and modification of Beaver.                            *
7    * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
8   
9   package beaver.spec;
10  
11  import java.util.Comparator  ;
12  
13  import beaver.Symbol;
14  
15  /**
16   * Represents production rules in the grammar.
17   */
18  public class Production
19  {
20      static final Comparator   NUM_TERM_CMP = new Comparator  ()
21      {
22          public int compare(Object   o1, Object   o2)
23          {
24              return ((Production) o2).rhs.n_term - ((Production) o1).rhs.n_term;
25          }
26      };
27      static final Comparator   NUM_NONTERM_CMP = new Comparator  ()
28      {
29          public int compare(Object   o1, Object   o2)
30          {
31              return ((Production) o2).rhs.n_nonterm - ((Production) o1).rhs.n_nonterm;
32          }
33      };
34      
35      static public class List
36      {
37          private Production first, last;
38          private int size;
39          
40          public void add(Production rule)
41          {
42              if (last == null)
43                  last = first = rule;
44              else
45                  last = last.next_definition = rule;
46              size++;
47          }
48          
49          public Production start()
50          {
51              return first;
52          }
53          
54          public int size()
55          {
56              return size;
57          }
58      }
59      
60      static public class RHS
61      {
62          /**
63           * Components of the right-hand side of a production.
64           */
65          static public class Item
66          {
67              /** Grammar symbol */
68              public final GrammarSymbol symbol;
69          
70              /** Alias for the symbol (NULL if none) */
71              public final String   alias;
72          
73              Item(GrammarSymbol sym)
74              {
75                  symbol = sym;
76                  alias = null;
77              }
78          
79              Item(GrammarSymbol sym, String   alias)
80              {
81                  this.symbol = sym;
82                  this.alias = alias;
83              }
84              
85              public String   toString()
86              {
87                  return alias == null
88                      ? symbol.name
89                      : new StringBuffer  (symbol.name.length() + 1 + alias.length())
90                          .append(symbol.name).append('.').append(alias)
91                          .toString();
92              }
93              
94              void appendTo(StringBuffer   str)
95              {
96                  str.append(symbol.name);
97                  if (alias != null)
98                  {
99                      str.append('.').append(alias);
100                 }
101             }
102         }
103         
104         static public final Item[] NONE = {};
105 
106         public final Item[] items;
107         Item first_term;
108         int n_term, n_nonterm;
109         
110         RHS()
111         {
112             items = NONE;
113         }
114         
115         RHS(Item[] items)
116         {
117             this.items = items;
118             for (int i = 0; i < items.length; i++)
119             {
120                 Item rhs_item = items[i];
121                 if (rhs_item.symbol instanceof Terminal)
122                 {
123                     if (first_term == null)
124                     {
125                         first_term = rhs_item;
126                     }
127                     n_term++;
128                 }
129                 else
130                 {
131                     n_nonterm++;
132                 }
133             }
134         }
135         
136         RHS(GrammarSymbol sym)
137         {
138             this(new Item[] { new Item(sym) });
139         }
140         
141         RHS(GrammarSymbol symA, GrammarSymbol symB)
142         {
143             this(new Item[] { new Item(symA), new Item(symB) });
144         }
145         
146         public Item start()
147         {
148             return items.length > 0 ? items[0] : null;
149         }
150         
151         public Item end()
152         {
153             return items.length > 0 ? items[items.length - 1] : null;
154         }
155         
156         public int size()
157         {
158             return items.length;
159         }
160         
161         public String   toString()
162         {
163             if (items.length == 0)
164                 return "";
165             
166             if (items.length == 1)
167                 return items[0].toString();
168             
169             int len = -1;
170             for (int i = 0; i < items.length; i++)
171             {
172                 len += 1 + items[i].symbol.name.length();
173                 if (items[i].alias != null)
174                 {
175                     len += 1 + items[i].alias.length();
176                 }
177             }
178             StringBuffer   str = new StringBuffer  (len);
179             items[0].appendTo(str);
180             for (int i = 1; i < items.length; i++)
181             {
182                 str.append(' ');
183                 items[i].appendTo(str);
184             }
185             return str.toString();
186         }
187     }
188 
189     static private final Terminal DEFAULT_PRECEDENCE_SYMBOL = new Terminal("DEFAULT_PRECEDENCE", -1, Terminal.Associativity.NONE);
190 
191     /** Next definition of this rule LHS nonterminal */
192     public Production next_definition;
193     
194     /** This rule ID */
195     public final int id;
196 
197     /** Left-hand side of the rule */
198     public final NonTerminal lhs;
199 
200     /** Right hand side of the production */
201     public final RHS rhs;
202 
203     /** Precedence symbol for this rule */
204     public final Terminal prec_sym;
205 
206     /** Code executed when this rule is reduced */
207     public String   code;
208 
209     /** Position of this rule in the source */
210     public int start_pos, end_pos;
211 
212     /** True if this rule can be reduced. */
213     public boolean is_reducible;
214 
215 
216     Production(int id, NonTerminal lhs, RHS rhs, Terminal prec_sym)
217     {
218         this.id = id;
219         this.lhs = lhs;
220         this.rhs = rhs;
221         if (prec_sym == null)
222         {
223             /* Set production precedence.
224              * 
225              * Unless a precedence symbol is provided explicitly in the input grammar rules take as their
226              * precedence symbol the rightmost RHS symbol with a defined precedence. The idea is that if
227              * the lookahead has higher precedence than the production currently used, we shift.
228              * 
229              * If there are no RHS symbols with a _defined_ precedence, a production will have the lowest
230              * precedence.
231              */
232             prec_sym = DEFAULT_PRECEDENCE_SYMBOL;
233             
234             for (int i = rhs.items.length - 1; i >= 0; i--)
235             {
236                 if (rhs.items[i].symbol instanceof Terminal)
237                 {
238                     Terminal term = (Terminal) rhs.items[i].symbol;
239                     if (term.prec > 0)
240                     {
241                         prec_sym = term;
242                         break;
243                     }
244                 }
245             }
246         }
247         this.prec_sym = prec_sym;
248         if (rhs.items.length == 0)
249         {
250             lhs.is_nullable = true;
251         }
252         lhs.definitions.add(this);
253     }
254     
255     Production(int id, NonTerminal lhs, RHS rhs)
256     {
257         this(id, lhs, rhs, null);
258     }
259     
260     /**
261      * Checks whether the production can derive an empty string.
262      *
263      * @return true if this production can match an empty string.
264      */
265     boolean isNullable()
266     {
267         if (rhs.first_term != null)
268             return false;
269 
270         for (int i = 0; i < rhs.items.length; i++)
271         {
272             if (!((NonTerminal) rhs.items[i].symbol).is_nullable)
273                 return false;
274         }
275         return true;
276     }
277 
278     /**
279      * Runs the first iteration of first set construction.
280      */
281     void startFirstSet()
282     {
283         for (int i = 0; i < rhs.items.length; i++)
284         {
285             if (rhs.items[i].symbol instanceof Terminal)
286             {
287                 lhs.first_set.add(rhs.items[i].symbol.id);
288                 break;
289             }
290             NonTerminal rhs_nt = (NonTerminal) rhs.items[i].symbol;
291             if (rhs_nt != lhs && rhs_nt.first_set != null)
292             {
293                 lhs.first_set.add(rhs_nt.first_set);
294             }
295             if (!rhs_nt.is_nullable) break;
296         }
297     }
298 
299     /**
300      * Adds other terminals that may start this production.
301      *
302      * @return true if this cycle contributed more terminals to the first set
303      */
304     boolean extendFirstSet()
305     {
306         boolean more_added = false;
307         for (int i = 0; i < rhs.items.length; i++)
308         {
309             if (rhs.items[i].symbol instanceof Terminal)
310                 break;
311             
312             NonTerminal rhs_nt = (NonTerminal) rhs.items[i].symbol;
313             if (rhs_nt != lhs && rhs_nt.first_set != null)
314             {
315                 if (lhs.first_set.add(rhs_nt.first_set))
316                 {
317                     more_added = true;
318                 }
319             }
320             if (!rhs_nt.is_nullable) break;
321         }
322         return more_added;
323     }
324     
325     public int getFirstLine()
326     {
327         return Symbol.getLine(start_pos);
328     }
329 
330     public String   toString()
331     {
332         return new StringBuffer  (100)
333             .append(lhs).append(" = ").append(rhs)
334             .toString();
335     }
336 }
337
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags