Syntax


1   package fri.patterns.interpreter.parsergenerator.syntax;
2   
3   import java.io.Serializable  ;
4   import java.util.*;
5   import fri.patterns.interpreter.parsergenerator.Token;
6   
7   /**
8       A Syntax is a Rule list that can be converted to a parser table.
9       It provides several methods to check and simplify the grammar.
10      Syntax accepts no duplicate rules (ignores any addition except
11      the first by using a backing hashtable).
12      
13      @author (c) 2004 Fritz Ritzberger
14  */
15  
16  public class Syntax implements Serializable  
17  {
18      private List rules;
19      private Hashtable ruleHash;
20      
21      public Syntax() {
22          this(new ArrayList());
23      }
24      
25      public Syntax(int size) {
26          this(new ArrayList(size));
27      }
28      
29      public Syntax(String   [][] rules)    {
30          this(SyntaxUtil.ruleArrayToList(rules));
31      }
32      
33      public Syntax(String   [][][] ruleSets)   {
34          this(SyntaxUtil.catenizeRulesUnique(ruleSets));
35      }
36  
37      public Syntax(List rules)   {
38          appendRules(rules);
39      }
40  
41  
42      /** Append rules to this syntax. List elements can be Rule or List, second will be converted to Rule. */
43      public void appendRules(List rules) {
44          if (rules != null)  {
45              if (rules.size() > 0)   {
46                  if (this.rules == null) {
47                      allocateRules(rules);
48                  }
49                      
50                  for (int i = 0; i < rules.size(); i++)  {
51                      Object   o = rules.get(i);
52                      if (o instanceof Rule)
53                          addRule((Rule) o);
54                      else    // must convert from List to Rule
55                          addRule(new Rule((List) o));
56                  }
57              }
58              else    {
59                  if (this.rules == null) {
60                      allocateRules(rules);
61                  }
62              }
63          }
64      }
65      
66      /** Returns the number of rules of this Syntax. */
67      public int size()   {
68          return rules != null ? rules.size() : 0;
69      }
70      
71      /** Returns the rule at the given position. */
72      public Rule getRule(int i)  {
73          return (Rule) rules.get(i);
74      }
75      
76      /** Appends a new rule to this Syntax. */
77      public void addRule(Rule rule)  {
78          insertRule(size(), rule);
79      }
80      
81      /** Inserts a new rule into this Syntax (needed to set artificial START rule at position 0). */
82      public void insertRule(int i, Rule rule)    {
83          if (rules == null)  {
84              allocateRules(null);
85          }
86          
87          if (ruleHash.get(rule) != null)
88              return; // already contained
89          
90          ruleHash.put(rule, rule);
91          rules.add(i, rule);
92      }
93      
94      /** Removes the rule at passed index from this Syntax. */
95      public void removeRule(int index)   {
96          rules.remove(index);
97      }
98      
99  
100     private void allocateRules(List rules)  {
101         int size = rules == null || rules.size() <= 0 ? 64 : rules.size();
102         this.rules = new ArrayList(size);
103         this.ruleHash = new Hashtable(size);
104     }
105 
106 
107     /** Returns a List of top level Rules (that do not appear on right side of any contained rule). */
108     public List findStartRules()    {
109         List roots = new ArrayList(1);
110         
111         for (int i = 0; i < size(); i++)    {
112             Rule rule = getRule(i);
113             String   nonterm = rule.getNonterminal();
114 
115             // search this left side nonterminal on right sides of all rules
116             boolean found = nonterm.equals(Token.TOKEN) || nonterm.equals(Token.IGNORED);
117             for (int j = 0; found == false && j < size(); j++)  {
118                 Rule r = getRule(j);
119                 if (j != i && r.getNonterminal().equals(nonterm) == false)  // start rule is allowed to be recursive
120                     for (int k = 0; found == false && k < r.rightSize(); k++)
121                         if (r.getRightSymbol(k).equals(nonterm) && false == r.getNonterminal().equals(Token.TOKEN) && false == r.getNonterminal().equals(Token.IGNORED))
122                             found = true;
123             }
124             
125             if (found == false) // must be a top level rule
126                 roots.add(rule);
127         }
128         
129         return roots;
130     }
131 
132 
133     /**
134         Simplify the syntax. Search rules that have a nonterminal that is defined only once
135         and contains exactly one symbol on right side. Such a rule gets deleted and its references
136         get substituted by the symbol on right side of that rule.
137         <p>
138         This method is called by default from SerializedObject (base class for all builders).
139         <p>
140         CAUTION: Such symbols will not be called within Semantic!
141     */
142     public void resolveSingulars()  {
143         Rule singular;
144         while ((singular = removeSingular()) != null)   {
145             String   substitute = singular.getNonterminal();
146 
147             for (int i = 0; i < size(); i++)    {   // substitute rules containing the singular
148                 Rule rule = getRule(i);
149 
150                 for (int j = 0; j < rule.rightSize(); j++)
151                     if (rule.getRightSymbol(j).equals(substitute))
152                         rule.setRightSymbol(singular.getRightSymbol(0), j);
153             }
154         }
155     }
156 
157     private Rule removeSingular()   {
158         for (int i = size() - 1; i >= 0; i--)   {
159             Rule rule = getRule(i);
160             String   nonterminal = rule.getNonterminal();
161             
162             // check if rule has only one symbol on right side and nonterminal is artificial symbol
163             boolean singular = 
164                 rule.rightSize() == 1 &&
165                 nonterminal.startsWith(Token.ARTIFICIAL_NONTERMINAL_START_CHARACTER) &&
166                 nonterminal.equals(Token.TOKEN) == false && nonterminal.equals(Token.IGNORED) == false;
167 
168             // check if defined only once on any left side
169             for (int j = 0; singular && j < size(); j++)
170                 if (j != i && getRule(j).getNonterminal().equals(nonterminal))
171                     singular = false;   // nonterm has been found once more on left side: rule has alternative rules
172             
173             // check if this is not a semantic splitting of a nonterminal in different contexts:
174             // is right symbol defined only once on any right side with rightSize() == 1 ?
175             String   rightSymbol = singular ? rule.getRightSymbol(0) : null;
176             for (int j = 0; singular && j < size(); j++)
177                 if (j != i && getRule(j).rightSize() == 1 && getRule(j).getRightSymbol(0).equals(rightSymbol))
178                     singular = false;   // nonterm has been found once more on a right side with exactly one symbol
179             
180             if (singular)   {
181                 if (rule.indexOnRightSide(nonterminal) >= 0)    // check if recursive rule
182                     System.err.println("WARNING: removing recursive singular rule: "+rule);
183 
184                 this.rules.remove(i);
185                 return rule;
186             }
187         }
188         return null;
189     }
190 
191 
192 
193     /**
194         Resolves undefined rules in this syntax from another syntax.
195         @param resolvingSyntax the syntax to copy rules from
196     */
197     public void resolveFrom(Syntax resolvingSyntax) {
198         Set unresolved = getUnresolvedNonterminals();
199         Map done = new Hashtable();
200         for (Iterator it = unresolved.iterator(); it.hasNext(); )   {
201             getRulesUnderSymbol((String  ) it.next(), resolvingSyntax, done);
202         }
203     }
204 
205     /**
206         Returns a set of nonterminals that have no rule within this syntax.
207     */
208     public Set getUnresolvedNonterminals()  {
209         Set unresolved = new HashSet();
210         for (int j = 0; j < size(); j++)    {
211             Rule rule = getRule(j);
212             for (int i = 0; i < rule.rightSize(); i++)  {
213                 String   sym = rule.getRightSymbol(i);
214                 if (Token.isTerminal(sym) == false && sym.equals(Token.BUTNOT) == false && sym.equals(Token.UPTO) == false && hasRule(sym) == false)
215                     unresolved.add(sym);
216             }
217         }
218         return unresolved;
219     }
220 
221     private void getRulesUnderSymbol(String   nonterminal, Syntax sourceSyntax, Map done) {
222         if (done.get(nonterminal) != null)
223             return;
224         done.put(nonterminal, nonterminal);
225 
226         for (int i = 0; i < sourceSyntax.size(); i++)   {
227             Rule rule = sourceSyntax.getRule(i);
228             if (rule.getNonterminal().equals(nonterminal))  {
229                 addRule(rule);
230                 for (int j = 0; j < rule.rightSize(); j++)  {   // cascade to other rules
231                     String   sym = rule.getRightSymbol(j);
232                     if (Token.isTerminal(sym) == false && sym.equals(Token.BUTNOT) == false && sym.equals(Token.UPTO) == false)
233                         getRulesUnderSymbol(sym, sourceSyntax, done);
234                 }
235             }
236         }
237     }
238 
239     /**
240         Returns true if the passed nonterminal is on the left side of at least one contained rule.
241     */
242     public boolean hasRule(String   nonterminal)  {
243         for (int i = 0; i < size(); i++)
244             if (getRule(i).getNonterminal().equals(nonterminal))
245                 return true;
246         return false;
247     }       
248 
249 
250 
251 
252     /** Returns the syntax as a human readable multiline text. */
253     public String   toString()    {
254         StringBuffer   sb = new StringBuffer  ();
255         for (int i = 0; i < size(); i++)    {
256             sb.append(getRule(i).toString());
257             sb.append("\n");
258         }
259         return sb.toString();
260     }
261 
262 }
263
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags