Semanticize


1   /*
2    * Copyright © 2002 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
3    * California 95054, U.S.A. All rights reserved.  Sun Microsystems, Inc. has
4    * intellectual property rights relating to technology embodied in the product
5    * that is described in this document. In particular, and without limitation,
6    * these intellectual property rights may include one or more of the U.S.
7    * patents listed at http://www.sun.com/patents and one or more additional
8    * patents or pending patent applications in the U.S. and in other countries.
9    * U.S. Government Rights - Commercial software. Government users are subject
10   * to the Sun Microsystems, Inc. standard license agreement and applicable
11   * provisions of the FAR and its supplements.  Use is subject to license terms.
12   * Sun,  Sun Microsystems,  the Sun logo and  Java are trademarks or registered
13   * trademarks of Sun Microsystems, Inc. in the U.S. and other countries.  This
14   * product is covered and controlled by U.S. Export Control laws and may be
15   * subject to the export or import laws in other countries.  Nuclear, missile,
16   * chemical biological weapons or nuclear maritime end uses or end users,
17   * whether direct or indirect, are strictly prohibited.  Export or reexport
18   * to countries subject to U.S. embargo or to entities identified on U.S.
19   * export exclusion lists, including, but not limited to, the denied persons
20   * and specially designated nationals lists is strictly prohibited.
21   */
22  
23  package org.javacc.parser;
24  
25  public class Semanticize extends JavaCCGlobals {
26  
27    static java.util.Vector removeList = new java.util.Vector();
28    static java.util.Vector itemList = new java.util.Vector();
29  
30    static void prepareToRemove(java.util.Vector vec, Object item) {
31      removeList.addElement(vec);
32      itemList.addElement(item);
33    }
34  
35    static void removePreparedItems() {
36      for (int i = 0; i < removeList.size(); i++) {
37        java.util.Vector vec = (java.util.Vector)(removeList.elementAt(i));
38        vec.removeElement(itemList.elementAt(i));
39      }
40      removeList.removeAllElements();
41      itemList.removeAllElements();
42    }
43  
44    static public void start() throws MetaParseException {
45  
46      if (JavaCCErrors.get_error_count() != 0) throw new MetaParseException();
47  
48      if (Options.I("LOOKAHEAD") > 1 && !Options.B("FORCE_LA_CHECK") && Options.B("SANITY_CHECK")) {
49        JavaCCErrors.warning("Lookahead adequacy checking not being performed since option LOOKAHEAD is more than 1.  Set option FORCE_LA_CHECK to true to force checking.");
50      }
51  
52      /*
53       * The following walks the entire parse tree to convert all LOOKAHEAD's
54       * that are not at choice points (but at beginning of sequences) and converts
55       * them to trivial choices.  This way, their semantic lookahead specification
56       * can be evaluated during other lookahead evaluations.
57       */
58      for (java.util.Enumeration enum = bnfproductions.elements(); enum.hasMoreElements();) {
59        ExpansionTreeWalker.postOrderWalk(((NormalProduction)enum.nextElement()).expansion, new LookaheadFixer());
60      }
61  
62      /*
63       * The following loop populates "production_table"
64       */
65      for (java.util.Enumeration enum = bnfproductions.elements(); enum.hasMoreElements();) {
66        NormalProduction p = (NormalProduction)enum.nextElement();
67        if (production_table.put(p.lhs, p) != null) {
68          JavaCCErrors.semantic_error(p, p.lhs + " occurs on the left hand side of more than one production.");
69        }
70      }
71  
72      /*
73       * The following walks the entire parse tree to make sure that all
74       * non-terminals on RHS's are defined on the LHS.
75       */
76      for (java.util.Enumeration enum = bnfproductions.elements(); enum.hasMoreElements();) {
77        ExpansionTreeWalker.preOrderWalk(((NormalProduction)enum.nextElement()).expansion, new ProductionDefinedChecker());
78      }
79  
80      /*
81       * The following loop ensures that all target lexical states are
82       * defined.  Also piggybacking on this loop is the detection of
83       * <EOF> and <name> in token productions.  After reporting an
84       * error, these entries are removed.  Also checked are definitions
85       * on inline private regular expressions.
86       * This loop works slightly differently when USER_TOKEN_MANAGER
87       * is set to true.  In this case, <name> occurrences are OK, while
88       * regular expression specs generate a warning.
89       */
90      for (java.util.Enumeration enum = rexprlist.elements(); enum.hasMoreElements();) {
91        TokenProduction tp = (TokenProduction)(enum.nextElement());
92        java.util.Vector respecs = tp.respecs;
93        for (java.util.Enumeration enum1 = respecs.elements(); enum1.hasMoreElements();) {
94          RegExprSpec res = (RegExprSpec)(enum1.nextElement());
95          if (res.nextState != null) {
96            if (lexstate_S2I.get(res.nextState) == null) {
97              JavaCCErrors.semantic_error(res.nsTok, "Lexical state \"" + res.nextState + "\" has not been defined.");
98            }
99          }
100         if (res.rexp instanceof REndOfFile) {
101           //JavaCCErrors.semantic_error(res.rexp, "Badly placed <EOF>.");
102           if (tp.lexStates != null)
103             JavaCCErrors.semantic_error(res.rexp, "EOF action/state change must be specified for all states, i.e., <*>TOKEN:.");
104           if (tp.kind != TokenProduction.TOKEN)
105             JavaCCErrors.semantic_error(res.rexp, "EOF action/state change can be specified only in a TOKEN specification.");
106           if (nextStateForEof != null || actForEof != null)
107             JavaCCErrors.semantic_error(res.rexp, "Duplicate action/state change specification for <EOF>.");
108           actForEof = res.act;
109           nextStateForEof = res.nextState;
110           prepareToRemove(respecs, res);
111         } else if (tp.isExplicit && Options.B("USER_TOKEN_MANAGER")) {
112           JavaCCErrors.warning(res.rexp, "Ignoring regular expression specification since option USER_TOKEN_MANAGER has been set to true.");
113         } else if (tp.isExplicit && !Options.B("USER_TOKEN_MANAGER") && res.rexp instanceof RJustName) {
114             JavaCCErrors.warning(res.rexp, "Ignoring free-standing regular expression reference.  If you really want this, you must give it a different label as <NEWLABEL:<" + res.rexp.label + ">>.");
115             prepareToRemove(respecs, res);
116         } else if (!tp.isExplicit && res.rexp.private_rexp) {
117           JavaCCErrors.semantic_error(res.rexp, "Private (#) regular expression cannot be defined within grammar productions.");
118         }
119       }
120     }
121 
122     removePreparedItems();
123 
124     /*
125      * The following loop inserts all names of regular expressions into
126      * "named_tokens_table" and "ordered_named_tokens".
127      * Duplications are flagged as errors.
128      */
129     for (java.util.Enumeration enum = rexprlist.elements(); enum.hasMoreElements();) {
130       TokenProduction tp = (TokenProduction)(enum.nextElement());
131       java.util.Vector respecs = tp.respecs;
132       for (java.util.Enumeration enum1 = respecs.elements(); enum1.hasMoreElements();) {
133         RegExprSpec res = (RegExprSpec)(enum1.nextElement());
134         if (!(res.rexp instanceof RJustName) && !res.rexp.label.equals("")) {
135           String s = res.rexp.label;
136           Object obj = named_tokens_table.put(s, res.rexp);
137           if (obj != null) {
138             JavaCCErrors.semantic_error(res.rexp, "Multiply defined lexical token name \"" + s + "\".");
139           } else {
140             ordered_named_tokens.addElement(res.rexp);
141           }
142           if (lexstate_S2I.get(s) != null) {
143             JavaCCErrors.semantic_error(res.rexp, "Lexical token name \"" + s + "\" is the same as that of a lexical state.");
144           }
145         }
146       }
147     }
148 
149     /*
150      * The following code merges multiple uses of the same string in the same
151      * lexical state and produces error messages when there are multiple
152      * explicit occurrences (outside the BNF) of the string in the same
153      * lexical state, or when within BNF occurrences of a string are duplicates
154      * of those that occur as non-TOKEN's (SKIP, MORE, SPECIAL_TOKEN) or private
155      * regular expressions.  While doing this, this code also numbers all
156      * regular expressions (by setting their ordinal values), and populates the
157      * table "names_of_tokens".
158      */
159 
160     tokenCount = 1;
161     for (java.util.Enumeration enum = rexprlist.elements(); enum.hasMoreElements();) {
162       TokenProduction tp = (TokenProduction)(enum.nextElement());
163       java.util.Vector respecs = tp.respecs;
164       if (tp.lexStates == null) {
165         tp.lexStates = new String[lexstate_I2S.size()];
166         int i = 0;
167         for (java.util.Enumeration enum1 = lexstate_I2S.elements(); enum1.hasMoreElements();) {
168           tp.lexStates[i++] = (String)(enum1.nextElement());
169         }
170       }
171       java.util.Hashtable table[] = new java.util.Hashtable[tp.lexStates.length];
172       for (int i = 0; i < tp.lexStates.length; i++) {
173         table[i] = (java.util.Hashtable)simple_tokens_table.get(tp.lexStates[i]);
174       }
175       for (java.util.Enumeration enum1 = respecs.elements(); enum1.hasMoreElements();) {
176         RegExprSpec res = (RegExprSpec)(enum1.nextElement());
177         if (res.rexp instanceof RStringLiteral) {
178           RStringLiteral sl = (RStringLiteral)res.rexp;
179           // This loop performs the checks and actions with respect to each lexical state.
180           for (int i = 0; i < table.length; i++) {
181             // Get table of all case variants of "sl.image" into table2.
182             java.util.Hashtable table2 = (java.util.Hashtable)(table[i].get(sl.image.toUpperCase()));
183             if (table2 == null) {
184               // There are no case variants of "sl.image" earlier than the current one.
185               // So go ahead and insert this item.
186               if (sl.ordinal == 0) {
187                 sl.ordinal = tokenCount++;
188               }
189               table2 = new java.util.Hashtable();
190               table2.put(sl.image, sl);
191               table[i].put(sl.image.toUpperCase(), table2);
192             } else if (hasIgnoreCase(table2, sl.image)) { // hasIgnoreCase sets "other" if it is found.
193               // Since IGNORE_CASE version exists, current one is useless and bad.
194               if (!sl.tpContext.isExplicit) {
195                 // inline BNF string is used earlier with an IGNORE_CASE.
196                 JavaCCErrors.semantic_error(sl, "String \"" + sl.image + "\" can never be matched due to presence of more general (IGNORE_CASE) regular expression at line " + other.line + ", column " + other.column + ".");
197               } else {
198                 // give the standard error message.
199                 JavaCCErrors.semantic_error(sl, "Duplicate definition of string token \"" + sl.image + "\" can never be matched.");
200               }
201             } else if (sl.tpContext.ignoreCase) {
202               // This has to be explicit.  A warning needs to be given with respect
203               // to all previous strings.
204               String pos = ""; int count = 0;
205               for (java.util.Enumeration enum2 = table2.elements(); enum2.hasMoreElements();) {
206                 RegularExpression rexp = (RegularExpression)(enum2.nextElement());
207                 if (count != 0) pos += ",";
208                 pos += " line " + rexp.line;
209                 count++;
210               }
211               if (count == 1) {
212                 JavaCCErrors.warning(sl, "String with IGNORE_CASE is partially superceded by string at" + pos + ".");
213               } else {
214                 JavaCCErrors.warning(sl, "String with IGNORE_CASE is partially superceded by strings at" + pos + ".");
215               }
216               // This entry is legitimate.  So insert it.
217               if (sl.ordinal == 0) {
218                 sl.ordinal = tokenCount++;
219               }
220               table2.put(sl.image, sl);
221               // The above "put" may override an existing entry (that is not IGNORE_CASE) and that's
222               // the desired behavior.
223             } else {
224               // The rest of the cases do not involve IGNORE_CASE.
225               RegularExpression re = (RegularExpression)table2.get(sl.image);
226               if (re == null) {
227                 if (sl.ordinal == 0) {
228                   sl.ordinal = tokenCount++;
229                 }
230                 table2.put(sl.image, sl);
231               } else if (tp.isExplicit) {
232                 // This is an error even if the first occurrence was implicit.
233                 if (tp.lexStates[i].equals("DEFAULT")) {
234                   JavaCCErrors.semantic_error(sl, "Duplicate definition of string token \"" + sl.image + "\".");
235                 } else {
236                   JavaCCErrors.semantic_error(sl, "Duplicate definition of string token \"" + sl.image + "\" in lexical state \"" + tp.lexStates[i] + "\".");
237                 }
238               } else if (re.tpContext.kind != TokenProduction.TOKEN) {
239                 JavaCCErrors.semantic_error(sl, "String token \"" + sl.image + "\" has been defined as a \"" + TokenProduction.kindImage[re.tpContext.kind] + "\" token.");
240               } else if (re.private_rexp) {
241                 JavaCCErrors.semantic_error(sl, "String token \"" + sl.image + "\" has been defined as a private regular expression.");
242               } else {
243                 // This is now a legitimate reference to an existing RStringLiteral.
244                 // So we assign it a number and take it out of "rexprlist".
245                 // Therefore, if all is OK (no errors), then there will be only unequal
246                 // string literals in each lexical state.  Note that the only way
247                 // this can be legal is if this is a string declared inline within the
248                 // BNF.  Hence, it belongs to only one lexical state - namely "DEFAULT".
249                 sl.ordinal = re.ordinal;
250                 prepareToRemove(respecs, res);
251               }
252             }
253           }
254         } else if (!(res.rexp instanceof RJustName)) {
255           res.rexp.ordinal = tokenCount++;
256         }
257         if (!(res.rexp instanceof RJustName) && !res.rexp.label.equals("")) {
258           names_of_tokens.put(new Integer(res.rexp.ordinal), res.rexp.label);
259         }
260         if (!(res.rexp instanceof RJustName)) {
261           rexps_of_tokens.put(new Integer(res.rexp.ordinal), res.rexp);
262         }
263       }
264     }
265 
266     removePreparedItems();
267 
268     /*
269      * The following code performs a tree walk on all regular expressions
270      * attaching links to "RJustName"s.  Error messages are given if
271      * undeclared names are used, or if "RJustNames" refer to private
272      * regular expressions or to regular expressions of any kind other
273      * than TOKEN.  In addition, this loop also removes top level
274      * "RJustName"s from "rexprlist".
275      * This code is not executed if Options.B("USER_TOKEN_MANAGER") is set to
276      * true.  Instead the following block of code is executed.
277      */
278 
279     if (!Options.B("USER_TOKEN_MANAGER")) {
280       FixRJustNames frjn = new FixRJustNames();
281       for (java.util.Enumeration enum = rexprlist.elements(); enum.hasMoreElements();) {
282         TokenProduction tp = (TokenProduction)(enum.nextElement());
283         java.util.Vector respecs = tp.respecs;
284         for (java.util.Enumeration enum1 = respecs.elements(); enum1.hasMoreElements();) {
285           RegExprSpec res = (RegExprSpec)(enum1.nextElement());
286           frjn.root = res.rexp;
287           ExpansionTreeWalker.preOrderWalk(res.rexp, frjn);
288           if (res.rexp instanceof RJustName) {
289             prepareToRemove(respecs, res);
290           }
291         }
292       }
293     }
294 
295     removePreparedItems();
296 
297     /*
298      * The following code is executed only if Options.B("USER_TOKEN_MANAGER") is
299      * set to true.  This code visits all top-level "RJustName"s (ignores
300      * "RJustName"s nested within regular expressions).  Since regular expressions
301      * are optional in this case, "RJustName"s without corresponding regular
302      * expressions are given ordinal values here.  If "RJustName"s refer to
303      * a named regular expression, their ordinal values are set to reflect this.
304      * All but one "RJustName" node is removed from the lists by the end of
305      * execution of this code.
306      */
307 
308     if (Options.B("USER_TOKEN_MANAGER")) {
309       for (java.util.Enumeration enum = rexprlist.elements(); enum.hasMoreElements();) {
310         TokenProduction tp = (TokenProduction)(enum.nextElement());
311         java.util.Vector respecs = tp.respecs;
312         for (java.util.Enumeration enum1 = respecs.elements(); enum1.hasMoreElements();) {
313           RegExprSpec res = (RegExprSpec)(enum1.nextElement());
314           if (res.rexp instanceof RJustName) {
315 
316             RJustName jn = (RJustName)res.rexp;
317             RegularExpression rexp = (RegularExpression)named_tokens_table.get(jn.label);
318             if (rexp == null) {
319               jn.ordinal = tokenCount++;
320               named_tokens_table.put(jn.label, jn);
321               ordered_named_tokens.addElement(jn);
322               names_of_tokens.put(new Integer(jn.ordinal), jn.label);
323             } else {
324               jn.ordinal = rexp.ordinal;
325               prepareToRemove(respecs, res);
326             }
327           }
328         }
329       }
330     }
331 
332     removePreparedItems();
333 
334     /*
335      * The following code is executed only if Options.B("USER_TOKEN_MANAGER") is
336      * set to true.  This loop labels any unlabeled regular expression and
337      * prints a warning that it is doing so.  These labels are added to
338      * "ordered_named_tokens" so that they may be generated into the ...Constants
339      * file.
340      */
341     if (Options.B("USER_TOKEN_MANAGER")) {
342       for (java.util.Enumeration enum = rexprlist.elements(); enum.hasMoreElements();) {
343         TokenProduction tp = (TokenProduction)(enum.nextElement());
344         java.util.Vector respecs = tp.respecs;
345         for (java.util.Enumeration enum1 = respecs.elements(); enum1.hasMoreElements();) {
346           RegExprSpec res = (RegExprSpec)(enum1.nextElement());
347           Integer ii = new Integer(res.rexp.ordinal);
348           if (names_of_tokens.get(ii) == null) {
349             JavaCCErrors.warning(res.rexp, "Unlabeled regular expression cannot be referred to by user generated token manager.");
350           }
351         }
352       }
353     }
354 
355     if (JavaCCErrors.get_error_count() != 0) throw new MetaParseException();
356 
357     // The following code sets the value of the "emptyPossible" field of NormalProduction
358     // nodes.  This field is initialized to false, and then the entire list of
359     // productions is processed.  This is repeated as long as at least one item
360     // got updated from false to true in the pass.
361     boolean emptyUpdate = true;
362     while (emptyUpdate) {
363       emptyUpdate = false;
364       for (java.util.Enumeration enum = bnfproductions.elements(); enum.hasMoreElements();) {
365         NormalProduction prod = (NormalProduction)enum.nextElement();
366         if (emptyExpansionExists(prod.expansion)) {
367           if (!prod.emptyPossible) {
368             emptyUpdate = prod.emptyPossible = true;
369           }
370         }
371       }
372     }
373 
374     if (Options.B("SANITY_CHECK") && JavaCCErrors.get_error_count() == 0) {
375 
376       // The following code checks that all ZeroOrMore, ZeroOrOne, and OneOrMore nodes
377       // do not contain expansions that can expand to the empty token list.
378       for (java.util.Enumeration enum = bnfproductions.elements(); enum.hasMoreElements();) {
379         ExpansionTreeWalker.preOrderWalk(((NormalProduction)enum.nextElement()).expansion, new EmptyChecker());
380       }
381 
382       // The following code goes through the productions and adds pointers to other
383       // productions that it can expand to without consuming any tokens.  Once this is
384       // done, a left-recursion check can be performed.
385       for (java.util.Enumeration enum = bnfproductions.elements(); enum.hasMoreElements();) {
386         NormalProduction prod = (NormalProduction)enum.nextElement();
387         addLeftMost(prod, prod.expansion);
388       }
389 
390       // Now the following loop calls a recursive walk routine that searches for
391       // actual left recursions.  The way the algorithm is coded, once a node has
392       // been determined to participate in a left recursive loop, it is not tried
393       // in any other loop.
394       for (java.util.Enumeration enum = bnfproductions.elements(); enum.hasMoreElements();) {
395         NormalProduction prod = (NormalProduction)enum.nextElement();
396         if (prod.walkStatus == 0) {
397           prodWalk(prod);
398         }
399       }
400 
401       // Now we do a similar, but much simpler walk for the regular expression part of
402       // the grammar.  Here we are looking for any kind of loop, not just left recursions,
403       // so we only need to do the equivalent of the above walk.
404       // This is not done if option USER_TOKEN_MANAGER is set to true.
405       if (!Options.B("USER_TOKEN_MANAGER")) {
406         for (java.util.Enumeration enum = rexprlist.elements(); enum.hasMoreElements();) {
407           TokenProduction tp = (TokenProduction)(enum.nextElement());
408           java.util.Vector respecs = tp.respecs;
409           for (java.util.Enumeration enum1 = respecs.elements(); enum1.hasMoreElements();) {
410             RegExprSpec res = (RegExprSpec)(enum1.nextElement());
411             RegularExpression rexp = res.rexp;
412             if (rexp.walkStatus == 0) {
413               rexp.walkStatus = -1;
414               if (rexpWalk(rexp)) {
415                 loopString = "..." + rexp.label + "... --> " + loopString;
416                 JavaCCErrors.semantic_error(rexp, "Loop in regular expression detected: \"" + loopString + "\"");
417               }
418               rexp.walkStatus = 1;
419             }
420           }
421         }
422       }
423 
424       /*
425        * The following code performs the lookahead ambiguity checking.
426        */
427       if (JavaCCErrors.get_error_count() == 0) {
428         for (java.util.Enumeration enum = bnfproductions.elements(); enum.hasMoreElements();) {
429           ExpansionTreeWalker.preOrderWalk(((NormalProduction)enum.nextElement()).expansion, new LookaheadChecker());
430         }
431       }
432 
433     } // matches "if (Options.B("SANITY_CHECK")) {"
434 
435     if (JavaCCErrors.get_error_count() != 0) throw new MetaParseException();
436 
437   }
438 
439   public static RegularExpression other;
440 
441   // Checks to see if the "str" is superceded by another equal (except case) string
442   // in table.
443   public static boolean hasIgnoreCase(java.util.Hashtable table, String str) {
444     RegularExpression rexp;
445     rexp = (RegularExpression)(table.get(str));
446     if (rexp != null && !rexp.tpContext.ignoreCase) {
447       return false;
448     }
449     for (java.util.Enumeration enum = table.elements(); enum.hasMoreElements();) {
450       rexp = (RegularExpression)(enum.nextElement());
451       if (rexp.tpContext.ignoreCase) {
452         other = rexp;
453         return true;
454       }
455     }
456     return false;
457   }
458 
459   // returns true if "exp" can expand to the empty string, returns false otherwise.
460   public static boolean emptyExpansionExists(Expansion exp) {
461     if (exp instanceof NonTerminal) {
462       return ((NonTerminal)exp).prod.emptyPossible;
463     } else if (exp instanceof Action) {
464       return true;
465     } else if (exp instanceof RegularExpression) {
466       return false;
467     } else if (exp instanceof OneOrMore) {
468       return emptyExpansionExists(((OneOrMore)exp).expansion);
469     } else if (exp instanceof ZeroOrMore || exp instanceof ZeroOrOne) {
470       return true;
471     } else if (exp instanceof Lookahead) {
472       return true;
473     } else if (exp instanceof Choice) {
474       for (java.util.Enumeration enum = ((Choice)exp).choices.elements(); enum.hasMoreElements();) {
475         if (emptyExpansionExists((Expansion)enum.nextElement())) {
476           return true;
477         }
478       }
479       return false;
480     } else if (exp instanceof Sequence) {
481       for (java.util.Enumeration enum = ((Sequence)exp).units.elements(); enum.hasMoreElements();) {
482         if (!emptyExpansionExists((Expansion)enum.nextElement())) {
483           return false;
484         }
485       }
486       return true;
487     } else if (exp instanceof TryBlock) {
488       return emptyExpansionExists(((TryBlock)exp).exp);
489     } else {
490       return false; // This should be dead code.
491     }
492   }
493 
494   // Updates prod.leftExpansions based on a walk of exp.
495   static private void addLeftMost(NormalProduction prod, Expansion exp) {
496     if (exp instanceof NonTerminal) {
497       for (int i=0; i<prod.leIndex; i++) {
498         if (prod.leftExpansions[i] == ((NonTerminal)exp).prod) {
499           return;
500         }
501       }
502       if (prod.leIndex == prod.leftExpansions.length) {
503     NormalProduction[] newle = new NormalProduction[prod.leIndex*2];
504     System.arraycopy(prod.leftExpansions, 0, newle, 0, prod.leIndex);
505     prod.leftExpansions = newle;
506       }
507       prod.leftExpansions[prod.leIndex++] = ((NonTerminal)exp).prod;
508     } else if (exp instanceof OneOrMore) {
509       addLeftMost(prod, ((OneOrMore)exp).expansion);
510     } else if (exp instanceof ZeroOrMore) {
511       addLeftMost(prod, ((ZeroOrMore)exp).expansion);
512     } else if (exp instanceof ZeroOrOne) {
513       addLeftMost(prod, ((ZeroOrOne)exp).expansion);
514     } else if (exp instanceof Choice) {
515       for (java.util.Enumeration enum = ((Choice)exp).choices.elements(); enum.hasMoreElements();) {
516         addLeftMost(prod, (Expansion)enum.nextElement());
517       }
518     } else if (exp instanceof Sequence) {
519       for (java.util.Enumeration enum = ((Sequence)exp).units.elements(); enum.hasMoreElements();) {
520         Expansion e = (Expansion)enum.nextElement();
521         addLeftMost(prod, e);
522         if (!emptyExpansionExists(e)) {
523           break;
524         }
525       }
526     } else if (exp instanceof TryBlock) {
527       addLeftMost(prod, ((TryBlock)exp).exp);
528     }
529   }
530 
531   // The string in which the following methods store information.
532   static private String loopString;
533 
534   // Returns true to indicate an unraveling of a detected left recursion loop,
535   // and returns false otherwise.
536   static private boolean prodWalk(NormalProduction prod) {
537     prod.walkStatus = -1;
538     for (int i = 0; i < prod.leIndex; i++) {
539       if (prod.leftExpansions[i].walkStatus == -1) {
540         prod.leftExpansions[i].walkStatus = -2;
541         loopString = prod.lhs + "... --> " + prod.leftExpansions[i].lhs + "...";
542         if (prod.walkStatus == -2) {
543           prod.walkStatus = 1;
544           JavaCCErrors.semantic_error(prod, "Left recursion detected: \"" + loopString + "\"");
545           return false;
546         } else {
547           prod.walkStatus = 1;
548           return true;
549         }
550       } else if (prod.leftExpansions[i].walkStatus == 0) {
551         if (prodWalk(prod.leftExpansions[i])) {
552           loopString = prod.lhs + "... --> " + loopString;
553           if (prod.walkStatus == -2) {
554             prod.walkStatus = 1;
555             JavaCCErrors.semantic_error(prod, "Left recursion detected: \"" + loopString + "\"");
556             return false;
557           } else {
558             prod.walkStatus = 1;
559             return true;
560           }
561         }
562       }
563     }
564     prod.walkStatus = 1;
565     return false;
566   }
567 
568   // Returns true to indicate an unraveling of a detected loop,
569   // and returns false otherwise.
570   static private boolean rexpWalk(RegularExpression rexp) {
571     if (rexp instanceof RJustName) {
572       RJustName jn = (RJustName)rexp;
573       if (jn.regexpr.walkStatus == -1) {
574         jn.regexpr.walkStatus = -2;
575         loopString = "..." + jn.regexpr.label + "...";
576         // Note: Only the regexpr's of RJustName nodes and the top leve
577         // regexpr's can have labels.  Hence it is only in these cases that
578         // the labels are checked for to be added to the loopString.
579         return true;
580       } else if (jn.regexpr.walkStatus == 0) {
581         jn.regexpr.walkStatus = -1;
582         if (rexpWalk(jn.regexpr)) {
583           loopString = "..." + jn.regexpr.label + "... --> " + loopString;
584           if (jn.regexpr.walkStatus == -2) {
585             jn.regexpr.walkStatus = 1;
586             JavaCCErrors.semantic_error(jn.regexpr, "Loop in regular expression detected: \"" + loopString + "\"");
587             return false;
588           } else {
589             jn.regexpr.walkStatus = 1;
590             return true;
591           }
592         } else {
593           jn.regexpr.walkStatus = 1;
594           return false;
595         }
596       }
597     } else if (rexp instanceof RChoice) {
598       for (java.util.Enumeration enum = ((RChoice)rexp).choices.elements(); enum.hasMoreElements();) {
599         if (rexpWalk((RegularExpression)enum.nextElement())) {
600           return true;
601         }
602       }
603       return false;
604     } else if (rexp instanceof RSequence) {
605       for (java.util.Enumeration enum = ((RSequence)rexp).units.elements(); enum.hasMoreElements();) {
606         if (rexpWalk((RegularExpression)enum.nextElement())) {
607           return true;
608         }
609       }
610       return false;
611     } else if (rexp instanceof ROneOrMore) {
612       return rexpWalk(((ROneOrMore)rexp).regexpr);
613     } else if (rexp instanceof RZeroOrMore) {
614       return rexpWalk(((RZeroOrMore)rexp).regexpr);
615     } else if (rexp instanceof RZeroOrOne) {
616       return rexpWalk(((RZeroOrOne)rexp).regexpr);
617     } else if (rexp instanceof RRepetitionRange) {
618       return rexpWalk(((RRepetitionRange)rexp).regexpr);
619     }
620     return false;
621   }
622 
623   /**
624    * Objects of this class are created from class Semanticize to work on
625    * references to regular expressions from RJustName's.
626    */
627   static class FixRJustNames extends JavaCCGlobals implements TreeWalkerOp {
628 
629     public RegularExpression root;
630 
631     public boolean goDeeper(Expansion e) {
632       return true;
633     }
634 
635     public void action(Expansion e) {
636       if (e instanceof RJustName) {
637     RJustName jn = (RJustName)e;
638     RegularExpression rexp = (RegularExpression)named_tokens_table.get(jn.label);
639     if (rexp == null) {
640       JavaCCErrors.semantic_error(e, "Undefined lexical token name \"" + jn.label + "\".");
641     } else if (jn == root && !jn.tpContext.isExplicit && rexp.private_rexp) {
642       JavaCCErrors.semantic_error(e, "Token name \"" + jn.label + "\" refers to a private (with a #) regular expression.");
643     } else if (jn == root && !jn.tpContext.isExplicit && rexp.tpContext.kind != TokenProduction.TOKEN) {
644       JavaCCErrors.semantic_error(e, "Token name \"" + jn.label + "\" refers to a non-token (SKIP, MORE, IGNORE_IN_BNF) regular expression.");
645     } else {
646       jn.ordinal = rexp.ordinal;
647       jn.regexpr = rexp;
648     }
649       }
650     }
651 
652   }
653 
654   static class LookaheadFixer extends JavaCCGlobals implements TreeWalkerOp {
655 
656     public boolean goDeeper(Expansion e) {
657       if (e instanceof RegularExpression) {
658     return false;
659       } else {
660     return true;
661       }
662     }
663 
664     public void action(Expansion e) {
665       if (e instanceof Sequence) {
666     if (e.parent instanceof Choice || e.parent instanceof ZeroOrMore ||
667         e.parent instanceof OneOrMore || e.parent instanceof ZeroOrOne) {
668       return;
669     }
670     Sequence seq = (Sequence)e;
671     Lookahead la = (Lookahead)(seq.units.elementAt(0));
672     if (!la.isExplicit) {
673       return;
674     }
675     // Create a singleton choice with an empty action.
676     Choice ch = new Choice();
677     ch.line = la.line; ch.column = la.column;
678     ch.parent = seq;
679     Sequence seq1 = new Sequence();
680     seq1.line = la.line; seq1.column = la.column;
681     seq1.parent = ch;
682     seq1.units.addElement(la);
683     la.parent = seq1;
684     Action act = new Action();
685     act.line = la.line; act.column = la.column;
686     act.parent = seq1;
687     seq1.units.addElement(act);
688     ch.choices.addElement(seq1);
689     if (la.amount != 0) {
690       if (la.action_tokens.size() != 0) {
691         JavaCCErrors.warning(la, "Encountered LOOKAHEAD(...) at a non-choice location.  Only semantic lookahead will be considered here.");
692       } else {
693         JavaCCErrors.warning(la, "Encountered LOOKAHEAD(...) at a non-choice location.  This will be ignored.");
694       }
695     }
696     // Now we have moved the lookahead into the singleton choice.  Now create
697     // a new dummy lookahead node to replace this one at its original location.
698     Lookahead la1 = new Lookahead();
699     la1.isExplicit = false;
700     la1.line = la.line; la1.column = la.column;
701     la1.parent = seq;
702     // Now set the la_expansion field of la and la1 with a dummy expansion (we use EOF).
703     la.la_expansion = new REndOfFile();
704     la1.la_expansion = new REndOfFile();
705     seq.units.setElementAt(la1, 0);
706     seq.units.insertElementAt(ch, 1);
707       }
708     }
709 
710   }
711 
712   static class ProductionDefinedChecker extends JavaCCGlobals implements TreeWalkerOp {
713 
714     public boolean goDeeper(Expansion e) {
715       if (e instanceof RegularExpression) {
716     return false;
717       } else {
718     return true;
719       }
720     }
721 
722     public void action(Expansion e) {
723       if (e instanceof NonTerminal) {
724     NonTerminal nt = (NonTerminal)e;
725     if ((nt.prod = (NormalProduction)production_table.get(nt.name)) == null) {
726       JavaCCErrors.semantic_error(e, "Non-terminal " + nt.name + " has not been defined.");
727     } else {
728       nt.prod.parents.addElement(nt);
729     }
730       }
731     }
732 
733   }
734 
735   static class EmptyChecker extends JavaCCGlobals implements TreeWalkerOp {
736 
737     public boolean goDeeper(Expansion e) {
738       if (e instanceof RegularExpression) {
739     return false;
740       } else {
741     return true;
742       }
743     }
744 
745     public void action(Expansion e) {
746       if (e instanceof OneOrMore) {
747     if (Semanticize.emptyExpansionExists(((OneOrMore)e).expansion)) {
748       JavaCCErrors.semantic_error(e, "Expansion within \"(...)+\" can be matched by empty string.");
749     }
750       } else if (e instanceof ZeroOrMore) {
751     if (Semanticize.emptyExpansionExists(((ZeroOrMore)e).expansion)) {
752       JavaCCErrors.semantic_error(e, "Expansion within \"(...)*\" can be matched by empty string.");
753     }
754       } else if (e instanceof ZeroOrOne) {
755     if (Semanticize.emptyExpansionExists(((ZeroOrOne)e).expansion)) {
756       JavaCCErrors.semantic_error(e, "Expansion within \"(...)?\" can be matched by empty string.");
757     }
758       }
759     }
760 
761   }
762 
763   static class LookaheadChecker extends JavaCCGlobals implements TreeWalkerOp {
764 
765     public boolean goDeeper(Expansion e) {
766       if (e instanceof RegularExpression) {
767     return false;
768       } else if (e instanceof Lookahead) {
769     return false;
770       } else {
771     return true;
772       }
773     }
774 
775     public void action(Expansion e) {
776       if (e instanceof Choice) {
777     if (Options.I("LOOKAHEAD") == 1 || Options.B("FORCE_LA_CHECK")) {
778       LookaheadCalc.choiceCalc((Choice)e);
779     }
780       } else if (e instanceof OneOrMore) {
781     OneOrMore exp = (OneOrMore)e;
782     if (Options.B("FORCE_LA_CHECK") || (implicitLA(exp.expansion) && Options.I("LOOKAHEAD") == 1)) {
783       LookaheadCalc.ebnfCalc(exp, exp.expansion);
784     }
785       } else if (e instanceof ZeroOrMore) {
786     ZeroOrMore exp = (ZeroOrMore)e;
787     if (Options.B("FORCE_LA_CHECK") || (implicitLA(exp.expansion) && Options.I("LOOKAHEAD") == 1)) {
788       LookaheadCalc.ebnfCalc(exp, exp.expansion);
789     }
790       } else if (e instanceof ZeroOrOne) {
791     ZeroOrOne exp = (ZeroOrOne)e;
792     if (Options.B("FORCE_LA_CHECK") || (implicitLA(exp.expansion) && Options.I("LOOKAHEAD") == 1)) {
793       LookaheadCalc.ebnfCalc(exp, exp.expansion);
794     }
795       }
796     }
797 
798     static boolean implicitLA(Expansion exp) {
799       if (!(exp instanceof Sequence)) {
800     return true;
801       }
802       Sequence seq = (Sequence)exp;
803       Object obj = seq.units.elementAt(0);
804       if (!(obj instanceof Lookahead)) {
805     return true;
806       }
807       Lookahead la = (Lookahead)obj;
808       return !la.isExplicit;
809     }
810 
811   }
812 
813    public static void reInit()
814    {
815       removeList = new java.util.Vector();
816       itemList = new java.util.Vector();
817       other = null;
818       loopString = null;
819    }
820 
821 }
822
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Java Books Remove Frame
Popular Tags