Grammar


1   /*
2    *  Copyright (C) Chaperon. All rights reserved.
3    *  -------------------------------------------------------------------------
4    *  This software is published under the terms of the Apache Software License
5    *  version 1.1, a copy of which has been included  with this distribution in
6    *  the LICENSE file.
7    */
8   
9   package net.sourceforge.chaperon.model.grammar;
10  
11  import net.sourceforge.chaperon.common.IntegerList;
12  import net.sourceforge.chaperon.model.Violations;
13  import net.sourceforge.chaperon.model.symbol.Nonterminal;
14  import net.sourceforge.chaperon.model.symbol.Symbol;
15  import net.sourceforge.chaperon.model.symbol.SymbolList;
16  import net.sourceforge.chaperon.model.symbol.SymbolSet;
17  import net.sourceforge.chaperon.model.symbol.Terminal;
18  
19  import java.io.Serializable  ;
20  
21  import java.util.Enumeration  ;
22  import java.util.Hashtable  ;
23  import java.util.Vector  ;
24  
25  /**
26   * This class represents a model for a grammar. The content of the grammar includes the
27   * productions, start symbol, associativities and priorities.
28   *
29   * @author <a HREF="mailto:stephan@apache.org">Stephan Michels </a>
30   * @version CVS $Id: Grammar.java,v 1.16 2003/12/09 19:55:52 benedikta Exp $
31   */
32  public class Grammar implements Serializable  , Cloneable  
33  {
34    // Start symbol
35    private Nonterminal startsymbol = null;
36  
37    // Productions
38    private Vector   productions = new Vector  ();
39    private Hashtable   priorities = new Hashtable  ();
40    private Hashtable   associativities = new Hashtable  ();
41    private String   location = null;
42  
43    /**
44     * Creates an empty grammar.
45     */
46    public Grammar() {}
47  
48    /**
49     * Add a production to this grammar.
50     *
51     * @param production Production, which should be added.
52     *
53     * @return Index of the production in this grammar.
54     */
55    public int addProduction(Production production)
56    {
57      if (production==null)
58        throw new NullPointerException  ();
59  
60      productions.addElement(production);
61      return productions.size()-1;
62    }
63  
64    /**
65     * Add a list of productions to this grammar.
66     *
67     * @param list Array of productions.
68     */
69    public void addProduction(Production[] list)
70    {
71      for (int i = 0; i<list.length; i++)
72        addProduction((Production)list[i].clone());
73    }
74  
75    /**
76     * Removes a production by an index from this grammar.
77     *
78     * @param index Index of the production, which should be removed.
79     */
80    public void removeProduction(int index)
81    {
82      productions.removeElementAt(index);
83    }
84  
85    /**
86     * Replace a production by an index in this grammar.
87     *
88     * @param index The index, at which the productionshould be replaced.
89     * @param production The production.
90     */
91    public void setProduction(int index, Production production)
92    {
93      if ((index<0) || (index>productions.size()))
94        throw new IndexOutOfBoundsException  ();
95  
96      productions.setElementAt(production, index);
97    }
98  
99    /**
100    * Return a production giving by an index.
101    *
102    * @param index Index of the Production.
103    *
104    * @return The production.
105    */
106   public Production getProduction(int index)
107   {
108 /*    if ((index<0) || (index>productions.size()))
109       throw new IndexOutOfBoundsException(index);*/
110     return (Production)productions.elementAt(index);
111   }
112 
113   /**
114    * Returns all production for given nonterminal symbol as a list of indices.
115    *
116    * @param ntsymbol Nonterminal symbol
117    *
118    * @return List of indices from the productions
119    */
120   public IntegerList getProductionList(Symbol ntsymbol)
121   {
122     IntegerList list = new IntegerList();
123     int i;
124 
125     for (i = 0; i<getProductionCount(); i++)
126     {
127       if (getProduction(i).getSymbol().equals(ntsymbol))
128         list.add(i);
129     }
130 
131     return list;
132   }
133 
134   public Production[] getProductions(Symbol ntsymbol)
135   {
136     int count = 0;
137     for (int i = 0; i<getProductionCount(); i++)
138       if (getProduction(i).getSymbol().equals(ntsymbol))
139         count++;
140 
141     Production[] productions = new Production[count];
142     for (int i = 0; i<getProductionCount(); i++)
143       if (getProduction(i).getSymbol().equals(ntsymbol))
144         productions[--count] = getProduction(i);
145 
146     return productions;
147   }
148 
149   /**
150    * Returns the count of productions in this grammar.
151    *
152    * @return Count of productions.
153    */
154   public int getProductionCount()
155   {
156     return productions.size();
157   }
158 
159   /**
160    * Return the index of a production.
161    *
162    * @param production The production.
163    *
164    * @return Index of the Production.
165    */
166   public int indexOf(Production production)
167   {
168     for (int i = 0; i<productions.size(); i++)
169       if (((Production)productions.elementAt(i)).equals(production))
170         return i;
171 
172     return -1;
173   }
174 
175   /**
176    * Return the index of the next production, which found by a nonterminal symbol.
177    *
178    * @param ntsymbol Nonterminal symbol
179    *
180    * @return Index of the production.
181    */
182   public int indexOf(Symbol ntsymbol)
183   {
184     for (int i = 0; i<productions.size(); i++)
185       if (((Production)productions.elementAt(i)).getSymbol().equals(ntsymbol))
186         return i;
187 
188     return -1;
189   }
190 
191   /**
192    * If the grammar contains a production.
193    *
194    * @param production The production, which the grammar should contain.
195    *
196    * @return True, if the grammar contains the production.
197    */
198   public boolean contains(Production production)
199   {
200     return (indexOf(production)!=-1);
201   }
202 
203   /**
204    * If the grammar contains a production with this nonterminal symbol.
205    *
206    * @param ntsymbol Nonterminal symbol.
207    *
208    * @return True, if the grammar contains a production with the symbol.
209    */
210   public boolean contains(Symbol ntsymbol)
211   {
212     return (indexOf(ntsymbol)!=-1);
213   }
214 
215   /**
216    * Removes all productions from this grammar.
217    */
218   public void removeAllProduction()
219   {
220     productions.removeAllElements();
221   }
222 
223   /**
224    * Returns the production, which this grammar contains, as an array.
225    *
226    * @return Array if productions.
227    */
228   public Production[] getProduction()
229   {
230     int size = productions.size();
231     Production[] mArray = new Production[size];
232 
233     for (int index = 0; index<size; index++)
234       mArray[index] = (Production)productions.elementAt(index);
235 
236     return mArray;
237   }
238 
239   /**
240    * Replace the productions of this grammar by an array of productions.
241    *
242    * @param productionArray Array of productions.
243    */
244   public void setProduction(Production[] productionArray)
245   {
246     productions.removeAllElements();
247     for (int i = 0; i<productionArray.length; i++)
248       productions.addElement(productionArray[i]);
249   }
250 
251   /**
252    * Set a priority of a terminal symbol.
253    *
254    * @param terminal Terminal symbol.
255    * @param priority Priority of the symbol.
256    */
257   public void setPriority(Terminal terminal, int priority)
258   {
259     if (terminal==null)
260       throw new NullPointerException  ();
261 
262     priorities.put(terminal, new Integer  (priority));
263   }
264 
265   /**
266    * Returns the priority of a terminal symbol.
267    *
268    * @param terminal Terminal symbol.
269    *
270    * @return Priority of the symbol.
271    */
272   public int getPriority(Terminal terminal)
273   {
274     Integer   priority = (Integer  )priorities.get(terminal);
275 
276     if (priority==null)
277       return 0;
278 
279     return priority.intValue();
280   }
281 
282   /**
283    * Return the priority of a production in this grammar.
284    *
285    * @param production Production.
286    *
287    * @return Priority of the production.
288    */
289   public int getPriority(Production production)
290   {
291     if (!contains(production))
292       return 0;
293 
294     if (production.getPrecedence()!=null)
295       return getPriority(production.getPrecedence());
296 
297     SymbolList definition = production.getDefinition();
298 
299     for (int i = definition.getSymbolCount()-1; i>=0; i--)
300       if (definition.getSymbol(i) instanceof Terminal)
301       {
302         int priority = getPriority((Terminal)definition.getSymbol(i));
303 
304         return priority;
305       }
306 
307     //return getProductionCount()-indexOf(production);
308     return 0;
309   }
310 
311   /**
312    * Set the associativity of a terminal symbol.
313    *
314    * @param terminal Terminal symbol.
315    * @param assoc Associativity of the symbol.
316    */
317   public void setAssociativity(Terminal terminal, Associativity assoc)
318   {
319     if (terminal==null)
320       throw new NullPointerException  ();
321 
322     associativities.put(terminal, assoc);
323   }
324 
325   /**
326    * Return the associativity of a terminal symbol.
327    *
328    * @param terminal Terminal symbol.
329    *
330    * @return Associativity of the symbol.
331    */
332   public Associativity getAssociativity(Terminal terminal)
333   {
334     Associativity assoc = (Associativity)associativities.get(terminal);
335 
336     if (assoc==null)
337       return Associativity.NONASSOC;
338 
339     return assoc;
340   }
341 
342   /**
343    * Return the associativity of a production in this grammar.
344    *
345    * @param production Production.
346    *
347    * @return Associativity of the production.
348    */
349   public Associativity getAssociativity(Production production)
350   {
351     if (!contains(production))
352       return Associativity.NONASSOC;
353 
354     if (production.getPrecedence()!=null)
355       return getAssociativity(production.getPrecedence());
356 
357     SymbolList definition = production.getDefinition();
358 
359     for (int i = definition.getSymbolCount()-1; i>=0; i--)
360       if (definition.getSymbol(i) instanceof Terminal)
361         return getAssociativity((Terminal)definition.getSymbol(i));
362 
363     return Associativity.NONASSOC;
364   }
365 
366   /**
367    * Return all used symbol in this grammar.
368    *
369    * @return Set of symbols, which were used.
370    */
371   public SymbolSet getSymbols()
372   {
373     SymbolSet set = new SymbolSet();
374 
375     for (int i = 0; i<getProductionCount(); i++)
376       set.addSymbol(getProduction(i).getSymbols());
377 
378     return set;
379   }
380 
381   /**
382    * Set the start symbol for this grammar.
383    *
384    * @param startsymbol Start symbol.
385    */
386   public void setStartSymbol(Nonterminal startsymbol)
387   {
388     this.startsymbol = startsymbol;
389   }
390 
391   /**
392    * Return the start symbol.
393    *
394    * @return Start symbol.
395    */
396   public Nonterminal getStartSymbol()
397   {
398     return startsymbol;
399   }
400 
401   /**
402    * Set the location from the input source.
403    *
404    * @param location Location in the input source.
405    */
406   public void setLocation(String   location)
407   {
408     this.location = location;
409   }
410 
411   /**
412    * Returns the location from the input source.
413    *
414    * @return Location in the input source.
415    */
416   public String   getLocation()
417   {
418     return location;
419   }
420 
421   /**
422    * Validated the grammar.
423    *
424    * @return Return a list of violations, if this object isn't valid.
425    */
426   public Violations validate()
427   {
428     Violations violations = new Violations();
429 
430     if (startsymbol==null)
431       violations.addViolation("Start symbol is not defined", location);
432     else if (!contains(startsymbol))
433       violations.addViolation("Start symbol \""+startsymbol+"\""+
434                               "is not defined through a production", location);
435 
436     if (getProductionCount()<=0)
437       violations.addViolation("No productions are defined", location);
438 
439     for (Enumeration   e = productions.elements(); e.hasMoreElements();)
440       violations.addViolations(((Production)e.nextElement()).validate());
441 
442     SymbolSet ntsymbols = getSymbols().getNonterminals();
443 
444     for (int i = 0; i<ntsymbols.getSymbolCount(); i++)
445     {
446       if (!contains(ntsymbols.getSymbol(i)))
447         violations.addViolation("Nonterminal symbol \""+ntsymbols.getSymbol(i)+"\""+
448                                 "is not defined through a production", location);
449 
450       if (ntsymbols.getSymbol(i).getName().equals("error"))
451         violations.addViolation("Nonterminal symbol with name \"error\" is not allowed", location);
452     }
453 
454     SymbolSet tsymbols = getSymbols().getTerminals();
455 
456     for (int i = 0; i<tsymbols.getSymbolCount(); i++)
457     {
458       if ((!(tsymbols.getSymbol(i) instanceof Error  )) &&
459           (tsymbols.getSymbol(i).getName().equals("error")))
460         violations.addViolation("Terminal symbol with name \"error\" is not allowed", location);
461     }
462 
463     return violations;
464   }
465 
466   /**
467    * Return a string representation of the grammar.
468    *
469    * @return String representation.
470    */
471   public String   toString()
472   {
473     StringBuffer   buffer = new StringBuffer  ();
474 
475     buffer.append("Terminal symbols:\n");
476 
477     SymbolSet tsymbols = getSymbols().getTerminals();
478 
479     for (int i = 0; i<tsymbols.getSymbolCount(); i++)
480     {
481       buffer.append(String.valueOf(i));
482       buffer.append(".Terminal: ");
483       buffer.append(tsymbols.getSymbol(i));
484       buffer.append(" Priority=");
485       buffer.append(String.valueOf(getPriority((Terminal)tsymbols.getSymbol(i))));
486       buffer.append(" Associativity=");
487       buffer.append(String.valueOf(getAssociativity((Terminal)tsymbols.getSymbol(i))));
488       buffer.append("\n");
489     }
490 
491     buffer.append("Produktions:\n");
492     for (int i = 0; i<getProductionCount(); i++)
493     {
494       buffer.append(String.valueOf(i));
495       buffer.append(".Production: ");
496       buffer.append(getProduction(i).toString());
497       buffer.append("\n");
498     }
499 
500     buffer.append("\n");
501 
502     return buffer.toString();
503   }
504 
505   /**
506    * Creates a clone of this grammar.
507    *
508    * @return Clone of this grammar.
509    *
510    * @throws CloneNotSupportedException If an exception occurs during the cloning.
511    */
512   public Object   clone()
513   {
514     Grammar clone = new Grammar();
515 
516     clone.startsymbol = startsymbol;
517     for (int i = 0; i<productions.size(); i++)
518       clone.addProduction((Production)((Production)productions.elementAt(i)).clone());
519 
520     clone.location = location;
521 
522     return clone;
523   }
524 }
525
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags