ParseEngine


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  import java.util.Hashtable;
26  import java.util.*;
27  
28  public class ParseEngine extends JavaCCGlobals {
29  
30    static private java.io.PrintWriter ostr;
31    static private int gensymindex = 0;
32    static private int indentamt;
33    static private boolean jj2LA;
34  
35    /**
36     * These lists are used to maintain expansions for which code generation
37     * in phase 2 and phase 3 is required.  Whenever a call is generated to
38     * a phase 2 or phase 3 routine, a corresponding entry is added here if
39     * it has not already been added.
40     * The phase 3 routines have been optimized in version 0.7pre2.  Essentially
41     * only those methods (and only those portions of these methods) are
42     * generated that are required.  The lookahead amount is used to determine
43     * this.  This change requires the use of a hash table because it is now
44     * possible for the same phase 3 routine to be requested multiple times
45     * with different lookaheads.  The hash table provides a easily searchable
46     * capability to determine the previous requests.
47     * The phase 3 routines now are performed in a two step process - the first
48     * step gathers the requests (replacing requests with lower lookaheads with
49     * those requiring larger lookaheads).  The second step then generates these
50     * methods.
51     * This optimization and the hashtable makes it look like we do not need
52     * the flag "phase3done" any more.  But this has not been removed yet.
53     */
54    static private java.util.Vector phase2list = new java.util.Vector();
55    static private java.util.Vector phase3list = new java.util.Vector();
56    static private java.util.Hashtable phase3table = new java.util.Hashtable();
57  
58    /**
59     * The phase 1 routines generates their output into String's and dumps
60     * these String's once for each method.  These String's contain the
61     * special characters '' to indicate a positive indent, and ''
62     * to indicate a negative indent.  '\n' is used to indicate a line terminator.
63     * The characters '' and '' are used to delineate portions of
64     * text where '\n's should not be followed by an indentation.
65     */
66  
67    /**
68     * Returns true if there is a JAVACODE production that the argument expansion
69     * may directly expand to (without consuming tokens).
70     */
71    static private boolean javaCodeCheck(Expansion exp) {
72      if (exp instanceof RegularExpression) {
73        return false;
74      } else if (exp instanceof NonTerminal) {
75        NormalProduction prod = ((NonTerminal)exp).prod;
76        if (prod instanceof JavaCodeProduction) {
77          return true;
78        } else {
79          return javaCodeCheck(prod.expansion);
80        }
81      } else if (exp instanceof Choice) {
82        Choice ch = (Choice)exp;
83        for (int i = 0; i < ch.choices.size(); i++) {
84          if (javaCodeCheck((Expansion)(ch.choices.elementAt(i)))) {
85            return true;
86          }
87        }
88        return false;
89      } else if (exp instanceof Sequence) {
90        Sequence seq = (Sequence)exp;
91        for (int i = 0; i < seq.units.size(); i++) {
92          if (javaCodeCheck((Expansion)(seq.units.elementAt(i)))) {
93            return true;
94          } else if (!Semanticize.emptyExpansionExists((Expansion)(seq.units.elementAt(i)))) {
95            return false;
96          }
97        }
98        return false;
99      } else if (exp instanceof OneOrMore) {
100       OneOrMore om = (OneOrMore)exp;
101       return javaCodeCheck(om.expansion);
102     } else if (exp instanceof ZeroOrMore) {
103       ZeroOrMore zm = (ZeroOrMore)exp;
104       return javaCodeCheck(zm.expansion);
105     } else if (exp instanceof ZeroOrOne) {
106       ZeroOrOne zo = (ZeroOrOne)exp;
107       return javaCodeCheck(zo.expansion);
108     } else if (exp instanceof TryBlock) {
109       TryBlock tb = (TryBlock)exp;
110       return javaCodeCheck(tb.exp);
111     } else {
112       return false;
113     }
114   }
115 
116   /**
117    * An array used to store the first sets generated by the following method.
118    * A true entry means that the corresponding token is in the first set.
119    */
120   static private boolean[] firstSet;
121 
122   /**
123    * Sets up the array "firstSet" above based on the Expansion argument
124    * passed to it.  Since this is a recursive function, it assumes that
125    * "firstSet" has been reset before the first call.
126    */
127   static private void genFirstSet(Expansion exp) {
128     if (exp instanceof RegularExpression) {
129       firstSet[((RegularExpression)exp).ordinal] = true;
130     } else if (exp instanceof NonTerminal) {
131       genFirstSet(((BNFProduction)(((NonTerminal)exp).prod)).expansion);
132     } else if (exp instanceof Choice) {
133       Choice ch = (Choice)exp;
134       for (int i = 0; i < ch.choices.size(); i++) {
135         genFirstSet((Expansion)(ch.choices.elementAt(i)));
136       }
137     } else if (exp instanceof Sequence) {
138       Sequence seq = (Sequence)exp;
139       Object obj = seq.units.elementAt(0);
140       if ((obj instanceof Lookahead) && (((Lookahead)obj).action_tokens.size() != 0)) {
141         jj2LA = true;
142       }
143       for (int i = 0; i < seq.units.size(); i++) {
144         genFirstSet((Expansion)(seq.units.elementAt(i)));
145         if (!Semanticize.emptyExpansionExists((Expansion)(seq.units.elementAt(i)))) {
146           break;
147         }
148       }
149     } else if (exp instanceof OneOrMore) {
150       OneOrMore om = (OneOrMore)exp;
151       genFirstSet(om.expansion);
152     } else if (exp instanceof ZeroOrMore) {
153       ZeroOrMore zm = (ZeroOrMore)exp;
154       genFirstSet(zm.expansion);
155     } else if (exp instanceof ZeroOrOne) {
156       ZeroOrOne zo = (ZeroOrOne)exp;
157       genFirstSet(zo.expansion);
158     } else if (exp instanceof TryBlock) {
159       TryBlock tb = (TryBlock)exp;
160       genFirstSet(tb.exp);
161     }
162   }
163 
164   /**
165    * Constants used in the following method "buildLookaheadChecker".
166    */
167   static final int NOOPENSTM = 0;
168   static final int OPENIF = 1;
169   static final int OPENSWITCH = 2;
170 
171   /**
172    * This method takes two parameters - an array of Lookahead's
173    * "conds", and an array of String's "actions".  "actions" contains
174    * exactly one element more than "conds".  "actions" are Java source
175    * code, and "conds" translate to conditions - so lets say
176    * "f(conds[i])" is true if the lookahead required by "conds[i]" is
177    * indeed the case.  This method returns a string corresponding to
178    * the Java code for:
179    *
180    *   if (f(conds[0]) actions[0]
181    *   else if (f(conds[1]) actions[1]
182    *   . . .
183    *   else actions[action.length-1]
184    *
185    * A particular action entry ("actions[i]") can be null, in which
186    * case, a noop is generated for that action.
187    */
188   static String buildLookaheadChecker(Lookahead[] conds, String[] actions) {
189 
190     // The state variables.
191     int state = NOOPENSTM;
192     int indentAmt = 0;
193     boolean[] casedValues = new boolean[tokenCount];
194     String retval = "";
195     Lookahead la;
196     Token t = null;
197     int tokenMaskSize = (tokenCount-1)/32 + 1;
198     int[] tokenMask = null;
199 
200     // Iterate over all the conditions.
201     int index = 0;
202     while (index < conds.length) {
203 
204       la = conds[index];
205       jj2LA = false;
206 
207       if ((la.amount == 0) ||
208       Semanticize.emptyExpansionExists(la.la_expansion) ||
209       javaCodeCheck(la.la_expansion)
210      ) {
211 
212     // This handles the following cases:
213     // . If syntactic lookahead is not wanted (and hence explicitly specified
214     //   as 0).
215     // . If it is possible for the lookahead expansion to recognize the empty
216     //   string - in which case the lookahead trivially passes.
217     // . If the lookahead expansion has a JAVACODE production that it directly
218     //   expands to - in which case the lookahead trivially passes.
219     if (la.action_tokens.size() == 0) {
220       // In addition, if there is no semantic lookahead, then the
221       // lookahead trivially succeeds.  So break the main loop and
222       // treat this case as the default last action.
223       break;
224     } else {
225       // This case is when there is only semantic lookahead
226       // (without any preceding syntactic lookahead).  In this
227       // case, an "if" statement is generated.
228       switch (state) {
229       case NOOPENSTM:
230         retval += "\n" + "if (";
231         indentAmt++;
232         break;
233       case OPENIF:
234         retval += "\u0002\n" + "} else if (";
235         break;
236       case OPENSWITCH:
237         retval += "\u0002\n" + "default:" + "\u0001";
238         if (Options.B("ERROR_REPORTING")) {
239           retval += "\njj_la1[" + maskindex + "] = jj_gen;";
240           maskindex++;
241         }
242         maskVals.addElement(tokenMask);
243         retval += "\n" + "if (";
244         indentAmt++;
245       }
246       printTokenSetup((Token)(la.action_tokens.elementAt(0)));
247       for (java.util.Enumeration enum = la.action_tokens.elements(); enum.hasMoreElements();) {
248         t = (Token)enum.nextElement();
249         retval += printToken(t);
250       }
251       retval += printTrailingComments(t);
252       retval += ") {\u0001" + actions[index];
253       state = OPENIF;
254     }
255 
256       } else if (la.amount == 1 && la.action_tokens.size() == 0) {
257     // Special optimal processing when the lookahead is exactly 1, and there
258     // is no semantic lookahead.
259 
260     if (firstSet == null) {
261       firstSet = new boolean[tokenCount];
262     }
263     for (int i = 0; i < tokenCount; i++) {
264       firstSet[i] = false;
265     }
266     // jj2LA is set to false at the beginning of the containing "if" statement.
267     // It is checked immediately after the end of the same statement to determine
268     // if lookaheads are to be performed using calls to the jj2 methods.
269     genFirstSet(la.la_expansion);
270     // genFirstSet may find that semantic attributes are appropriate for the next
271     // token.  In which case, it sets jj2LA to true.
272     if (!jj2LA) {
273 
274       // This case is if there is no applicable semantic lookahead and the lookahead
275       // is one (excluding the earlier cases such as JAVACODE, etc.).
276       switch (state) {
277       case OPENIF:
278         retval += "\u0002\n" + "} else {\u0001";
279         // Control flows through to next case.
280       case NOOPENSTM:
281         retval += "\n" + "switch (";
282         if (Options.B("CACHE_TOKENS")) {
283           retval += "jj_nt.kind) {\u0001";
284         } else {
285           retval += "(jj_ntk==-1)?jj_ntk():jj_ntk) {\u0001";
286         }
287         for (int i = 0; i < tokenCount; i++) {
288           casedValues[i] = false;
289         }
290         indentAmt++;
291         tokenMask = new int[tokenMaskSize];
292         for (int i = 0; i < tokenMaskSize; i++) {
293           tokenMask[i] = 0;
294         }
295           // Don't need to do anything if state is OPENSWITCH.
296       }
297       for (int i = 0; i < tokenCount; i++) {
298         if (firstSet[i]) {
299           if (!casedValues[i]) {
300         casedValues[i] = true;
301         retval += "\u0002\ncase ";
302         int j1 = i/32;
303         int j2 = i%32;
304         tokenMask[j1] |= 1 << j2;
305         String s = (String)(names_of_tokens.get(new Integer(i)));
306         if (s == null) {
307           retval += i;
308         } else {
309           retval += s;
310         }
311         retval += ":\u0001";
312           }
313         }
314       }
315       retval += actions[index];
316       retval += "\nbreak;";
317       state = OPENSWITCH;
318 
319     }
320 
321       } else {
322     // This is the case when lookahead is determined through calls to
323     // jj2 methods.  The other case is when lookahead is 1, but semantic
324     // attributes need to be evaluated.  Hence this crazy control structure.
325 
326     jj2LA = true;
327 
328       }
329 
330       if (jj2LA) {
331     // In this case lookahead is determined by the jj2 methods.
332 
333     switch (state) {
334     case NOOPENSTM:
335       retval += "\n" + "if (";
336       indentAmt++;
337       break;
338     case OPENIF:
339       retval += "\u0002\n" + "} else if (";
340       break;
341     case OPENSWITCH:
342       retval += "\u0002\n" + "default:" + "\u0001";
343       if (Options.B("ERROR_REPORTING")) {
344         retval += "\njj_la1[" + maskindex + "] = jj_gen;";
345         maskindex++;
346       }
347       maskVals.addElement(tokenMask);
348       retval += "\n" + "if (";
349       indentAmt++;
350     }
351     jj2index++;
352     // At this point, la.la_expansion.internal_name must be "".
353     la.la_expansion.internal_name = "_" + jj2index;
354     phase2list.addElement(la);
355     retval += "jj_2" + la.la_expansion.internal_name + "(" + la.amount + ")";
356     if (la.action_tokens.size() != 0) {
357       // In addition, there is also a semantic lookahead.  So concatenate
358       // the semantic check with the syntactic one.
359       retval += " && (";
360       printTokenSetup((Token)(la.action_tokens.elementAt(0)));
361       for (java.util.Enumeration enum = la.action_tokens.elements(); enum.hasMoreElements();) {
362         t = (Token)enum.nextElement();
363         retval += printToken(t);
364       }
365       retval += printTrailingComments(t);
366       retval += ")";
367     }
368     retval += ") {\u0001" + actions[index];
369     state = OPENIF;
370       }
371 
372       index++;
373     }
374 
375     // Generate code for the default case.  Note this may not
376     // be the last entry of "actions" if any condition can be
377     // statically determined to be always "true".
378 
379     switch (state) {
380     case NOOPENSTM:
381       retval += actions[index];
382       break;
383     case OPENIF:
384       retval += "\u0002\n" + "} else {\u0001" + actions[index];
385       break;
386     case OPENSWITCH:
387       retval += "\u0002\n" + "default:" + "\u0001";
388       if (Options.B("ERROR_REPORTING")) {
389     retval += "\njj_la1[" + maskindex + "] = jj_gen;";
390     maskVals.addElement(tokenMask);
391     maskindex++;
392       }
393       retval += actions[index];
394     }
395     for (int i = 0; i < indentAmt; i++) {
396       retval += "\u0002\n}";
397     }
398 
399     return retval;
400 
401   }
402 
403   static void dumpFormattedString(String str) {
404     char ch = ' ';
405     char prevChar;
406     boolean indentOn = true;
407     for (int i = 0; i < str.length(); i++) {
408       prevChar = ch;
409       ch = str.charAt(i);
410       if (ch == '\n' && prevChar == '\r') {
411         // do nothing - we've already printed a new line for the '\r'
412         // during the previous iteration.
413       } else if (ch == '\n' || ch == '\r') {
414         if (indentOn) {
415           phase1NewLine();
416         } else {
417           ostr.println("");
418         }
419       } else if (ch == '\u0001') {
420         indentamt += 2;
421       } else if (ch == '\u0002') {
422         indentamt -= 2;
423       } else if (ch == '\u0003') {
424         indentOn = false;
425       } else if (ch == '\u0004') {
426         indentOn = true;
427       } else {
428         ostr.print(ch);
429       }
430     }
431   }
432 
433   static void buildPhase1Routine(BNFProduction p) {
434     Token t;
435     t = (Token)(p.return_type_tokens.elementAt(0));
436     boolean voidReturn = false;
437     if (t.kind == JavaCCParserConstants.VOID) {
438       voidReturn = true;
439     }
440     printTokenSetup(t); ccol = 1;
441     printLeadingComments(t, ostr);
442     ostr.print("  " + staticOpt() + "final public ");
443     cline = t.beginLine; ccol = t.beginColumn;
444     printTokenOnly(t, ostr);
445     for (int i = 1; i < p.return_type_tokens.size(); i++) {
446       t = (Token)(p.return_type_tokens.elementAt(i));
447       printToken(t, ostr);
448     }
449     printTrailingComments(t, ostr);
450     ostr.print(" " + p.lhs + "(");
451     if (p.parameter_list_tokens.size() != 0) {
452       printTokenSetup((Token)(p.parameter_list_tokens.elementAt(0)));
453       for (java.util.Enumeration enum = p.parameter_list_tokens.elements(); enum.hasMoreElements();) {
454         t = (Token)enum.nextElement();
455         printToken(t, ostr);
456       }
457       printTrailingComments(t, ostr);
458     }
459     ostr.print(") throws ParseException");
460     for (java.util.Enumeration enum = p.throws_list.elements(); enum.hasMoreElements();) {
461       ostr.print(", ");
462       java.util.Vector name = (java.util.Vector)enum.nextElement();
463       for (java.util.Enumeration enum1 = name.elements(); enum1.hasMoreElements();) {
464         t = (Token)enum1.nextElement();
465         ostr.print(t.image);
466       }
467     }
468     ostr.print(" {");
469     indentamt = 4;
470     if (Options.B("DEBUG_PARSER")) {
471       ostr.println("");
472       ostr.println("    trace_call(\"" + p.lhs + "\");");
473       ostr.print("    try {");
474       indentamt = 6;
475     }
476     if (p.declaration_tokens.size() != 0) {
477       printTokenSetup((Token)(p.declaration_tokens.elementAt(0))); cline--;
478       for (java.util.Enumeration enum = p.declaration_tokens.elements(); enum.hasMoreElements();) {
479         t = (Token)enum.nextElement();
480         printToken(t, ostr);
481       }
482       printTrailingComments(t, ostr);
483     }
484     String code = phase1ExpansionGen(p.expansion);
485     dumpFormattedString(code);
486     ostr.println("");
487     if (p.jumpPatched && !voidReturn) {
488       ostr.println("    throw new Error(\"Missing return statement in function\");");
489     }
490     if (Options.B("DEBUG_PARSER")) {
491       ostr.println("    } finally {");
492       ostr.println("      trace_return(\"" + p.lhs + "\");");
493       ostr.println("    }");
494     }
495     ostr.println("  }");
496     ostr.println("");
497   }
498 
499   static void phase1NewLine() {
500     ostr.println("");
501     for (int i = 0; i < indentamt; i++) {
502       ostr.print(" ");
503     }
504   }
505 
506   static String phase1ExpansionGen(Expansion e) {
507     String retval = "";
508     Token t = null;
509     Lookahead[] conds;
510     String[] actions;
511     if (e instanceof RegularExpression) {
512       RegularExpression e_nrw = (RegularExpression)e;
513       retval += "\n";
514       if (e_nrw.lhsTokens.size() != 0) {
515         printTokenSetup((Token)(e_nrw.lhsTokens.elementAt(0)));
516         for (java.util.Enumeration enum = e_nrw.lhsTokens.elements(); enum.hasMoreElements();) {
517           t = (Token)enum.nextElement();
518           retval += printToken(t);
519         }
520         retval += printTrailingComments(t);
521         retval += " = ";
522       }
523       if (e_nrw.label.equals("")) {
524         Object label = names_of_tokens.get(new Integer(e_nrw.ordinal));
525         if (label != null) {
526           retval += "jj_consume_token(" + (String)label + ");";
527         } else {
528           retval += "jj_consume_token(" + e_nrw.ordinal + ");";
529         }
530       } else {
531         retval += "jj_consume_token(" + e_nrw.label + ");";
532       }
533     } else if (e instanceof NonTerminal) {
534       NonTerminal e_nrw = (NonTerminal)e;
535       retval += "\n";
536       if (e_nrw.lhsTokens.size() != 0) {
537         printTokenSetup((Token)(e_nrw.lhsTokens.elementAt(0)));
538         for (java.util.Enumeration enum = e_nrw.lhsTokens.elements(); enum.hasMoreElements();) {
539           t = (Token)enum.nextElement();
540           retval += printToken(t);
541         }
542         retval += printTrailingComments(t);
543         retval += " = ";
544       }
545       retval += e_nrw.name + "(";
546       if (e_nrw.argument_tokens.size() != 0) {
547         printTokenSetup((Token)(e_nrw.argument_tokens.elementAt(0)));
548         for (java.util.Enumeration enum = e_nrw.argument_tokens.elements(); enum.hasMoreElements();) {
549           t = (Token)enum.nextElement();
550           retval += printToken(t);
551         }
552         retval += printTrailingComments(t);
553       }
554       retval += ");";
555     } else if (e instanceof Action) {
556       Action e_nrw = (Action)e;
557       retval += "\u0003\n";
558       if (e_nrw.action_tokens.size() != 0) {
559         printTokenSetup((Token)(e_nrw.action_tokens.elementAt(0))); ccol = 1;
560         for (java.util.Enumeration enum = e_nrw.action_tokens.elements(); enum.hasMoreElements();) {
561           t = (Token)enum.nextElement();
562           retval += printToken(t);
563         }
564         retval += printTrailingComments(t);
565       }
566       retval += "\u0004";
567     } else if (e instanceof Choice) {
568       Choice e_nrw = (Choice)e;
569       conds = new Lookahead[e_nrw.choices.size()];
570       actions = new String[e_nrw.choices.size() + 1];
571       actions[e_nrw.choices.size()] = "\n" + "jj_consume_token(-1);\n" + "throw new ParseException();";
572       // In previous line, the "throw" never throws an exception since the
573       // evaluation of jj_consume_token(-1) causes ParseException to be
574       // thrown first.
575       Sequence nestedSeq;
576       for (int i = 0; i < e_nrw.choices.size(); i++) {
577         nestedSeq = (Sequence)(e_nrw.choices.elementAt(i));
578         actions[i] = phase1ExpansionGen(nestedSeq);
579         conds[i] = (Lookahead)(nestedSeq.units.elementAt(0));
580       }
581       retval = buildLookaheadChecker(conds, actions);
582     } else if (e instanceof Sequence) {
583       Sequence e_nrw = (Sequence)e;
584       // We skip the first element in the following iteration since it is the
585       // Lookahead object.
586       for (int i = 1; i < e_nrw.units.size(); i++) {
587         retval += phase1ExpansionGen((Expansion)(e_nrw.units.elementAt(i)));
588       }
589     } else if (e instanceof OneOrMore) {
590       OneOrMore e_nrw = (OneOrMore)e;
591       Expansion nested_e = e_nrw.expansion;
592       Lookahead la;
593       if (nested_e instanceof Sequence) {
594         la = (Lookahead)(((Sequence)nested_e).units.elementAt(0));
595       } else {
596         la = new Lookahead();
597         la.amount = Options.I("LOOKAHEAD");
598         la.la_expansion = nested_e;
599       }
600       retval += "\n";
601       int labelIndex = ++gensymindex;
602       retval += "label_" + labelIndex + ":\n";
603       retval += "while (true) {\u0001";
604       retval += phase1ExpansionGen(nested_e);
605       conds = new Lookahead[1];
606       conds[0] = la;
607       actions = new String[2];
608       actions[0] = "\n;";
609       actions[1] = "\nbreak label_" + labelIndex + ";";
610       retval += buildLookaheadChecker(conds, actions);
611       retval += "\u0002\n" + "}";
612     } else if (e instanceof ZeroOrMore) {
613       ZeroOrMore e_nrw = (ZeroOrMore)e;
614       Expansion nested_e = e_nrw.expansion;
615       Lookahead la;
616       if (nested_e instanceof Sequence) {
617         la = (Lookahead)(((Sequence)nested_e).units.elementAt(0));
618       } else {
619         la = new Lookahead();
620         la.amount = Options.I("LOOKAHEAD");
621         la.la_expansion = nested_e;
622       }
623       retval += "\n";
624       int labelIndex = ++gensymindex;
625       retval += "label_" + labelIndex + ":\n";
626       retval += "while (true) {\u0001";
627       conds = new Lookahead[1];
628       conds[0] = la;
629       actions = new String[2];
630       actions[0] = "\n;";
631       actions[1] = "\nbreak label_" + labelIndex + ";";
632       retval += buildLookaheadChecker(conds, actions);
633       retval += phase1ExpansionGen(nested_e);
634       retval += "\u0002\n" + "}";
635     } else if (e instanceof ZeroOrOne) {
636       ZeroOrOne e_nrw = (ZeroOrOne)e;
637       Expansion nested_e = e_nrw.expansion;
638       Lookahead la;
639       if (nested_e instanceof Sequence) {
640         la = (Lookahead)(((Sequence)nested_e).units.elementAt(0));
641       } else {
642         la = new Lookahead();
643         la.amount = Options.I("LOOKAHEAD");
644         la.la_expansion = nested_e;
645       }
646       conds = new Lookahead[1];
647       conds[0] = la;
648       actions = new String[2];
649       actions[0] = phase1ExpansionGen(nested_e);
650       actions[1] = "\n;";
651       retval += buildLookaheadChecker(conds, actions);
652     } else if (e instanceof TryBlock) {
653       TryBlock e_nrw = (TryBlock)e;
654       Expansion nested_e = e_nrw.exp;
655       java.util.Vector v;
656       retval += "\n";
657       retval += "try {\u0001";
658       retval += phase1ExpansionGen(nested_e);
659       retval += "\u0002\n" + "}";
660       for (int i = 0; i < e_nrw.catchblks.size(); i++) {
661         retval += " catch (";
662         v = (java.util.Vector)(e_nrw.types.elementAt(i));
663         if (v.size() != 0) {
664           printTokenSetup((Token)(v.elementAt(0)));
665           for (java.util.Enumeration enum = v.elements(); enum.hasMoreElements();) {
666             t = (Token)enum.nextElement();
667             retval += printToken(t);
668           }
669           retval += printTrailingComments(t);
670         }
671         retval += " ";
672         t = (Token)(e_nrw.ids.elementAt(i));
673         printTokenSetup(t);
674         retval += printToken(t);
675         retval += printTrailingComments(t);
676         retval += ") {\u0003\n";
677         v = (java.util.Vector)(e_nrw.catchblks.elementAt(i));
678         if (v.size() != 0) {
679           printTokenSetup((Token)(v.elementAt(0))); ccol = 1;
680           for (java.util.Enumeration enum = v.elements(); enum.hasMoreElements();) {
681             t = (Token)enum.nextElement();
682             retval += printToken(t);
683           }
684           retval += printTrailingComments(t);
685         }
686         retval += "\u0004\n" + "}";
687       }
688       if (e_nrw.finallyblk != null) {
689         retval += " finally {\u0003\n";
690         if (e_nrw.finallyblk.size() != 0) {
691           printTokenSetup((Token)(e_nrw.finallyblk.elementAt(0))); ccol = 1;
692           for (java.util.Enumeration enum = e_nrw.finallyblk.elements(); enum.hasMoreElements();) {
693             t = (Token)enum.nextElement();
694             retval += printToken(t);
695           }
696           retval += printTrailingComments(t);
697         }
698         retval += "\u0004\n" + "}";
699       }
700     }
701     return retval;
702   }
703 
704   static void buildPhase2Routine(Lookahead la) {
705     Expansion e = la.la_expansion;
706     ostr.println("  " + staticOpt() + "final private boolean jj_2" + e.internal_name + "(int xla) {");
707     ostr.println("    jj_la = xla; jj_lastpos = jj_scanpos = token;");
708     ostr.println("    try { return !jj_3" + e.internal_name + "(); }");
709     ostr.println("    catch(LookaheadSuccess ls) { return true; }");
710     if (Options.B("ERROR_REPORTING"))
711       ostr.println("    finally { jj_save(" + (Integer.parseInt(e.internal_name.substring(1))-1) + ", xla); }");
712     ostr.println("  }");
713     ostr.println("");
714     Phase3Data p3d = new Phase3Data(e, la.amount);
715     phase3list.addElement(p3d);
716     phase3table.put(e, p3d);
717   }
718 
719   static private boolean xsp_declared;
720 
721   static Expansion jj3_expansion;
722 
723   static String genReturn(boolean value) {
724     String retval = (value ? "true" : "false");
725     if (Options.B("DEBUG_LOOKAHEAD") && jj3_expansion != null) {
726       String tracecode = "trace_return(\"" + ((NormalProduction)jj3_expansion.parent).lhs +
727                          "(LOOKAHEAD " + (value ? "FAILED" : "SUCCEEDED") + ")\");";
728       if (Options.B("ERROR_REPORTING")) {
729         tracecode = "if (!jj_rescan) " + tracecode;
730       }
731       return "{ " + tracecode + " return " + retval + "; }";
732     } else {
733       return "return " + retval + ";";
734     }
735   }
736 
737   private static void generate3R(Expansion e, Phase3Data inf)
738   {
739     Expansion seq = e;
740     if (e.internal_name.equals(""))
741     {
742       while (true)
743       {
744          if (seq instanceof Sequence && ((Sequence)seq).units.size() == 2)
745          {
746             seq = (Expansion)((Sequence)seq).units.elementAt(1);
747          }
748          else if (seq instanceof NonTerminal)
749          {
750             NonTerminal e_nrw = (NonTerminal)seq;
751             NormalProduction ntprod = (NormalProduction)(production_table.get(e_nrw.name));
752             if (ntprod instanceof JavaCodeProduction)
753             {
754               break; // nothing to do here
755             }
756             else
757             {
758               seq = ntprod.expansion;
759             }
760          }
761          else
762             break;
763       }
764 
765       if (seq instanceof RegularExpression)
766       {
767          e.internal_name = "jj_scan_token(" + ((RegularExpression)seq).ordinal + ")";
768          return;
769       }
770 
771       gensymindex++;
772 //if (gensymindex == 100)
773 //{
774 //new Error().printStackTrace();
775 //System.out.println(" ***** seq: " + seq.internal_name + "; size: " + ((Sequence)seq).units.size());
776 //}
777       e.internal_name = "R_" + gensymindex;
778     }
779     Phase3Data p3d = (Phase3Data)(phase3table.get(e));
780     if (p3d == null || p3d.count < inf.count) {
781       p3d = new Phase3Data(e, inf.count);
782       phase3list.addElement(p3d);
783       phase3table.put(e, p3d);
784     }
785   }
786 
787   static void setupPhase3Builds(Phase3Data inf) {
788     Expansion e = inf.exp;
789     if (e instanceof RegularExpression) {
790       ; // nothing to here
791     } else if (e instanceof NonTerminal) {
792       // All expansions of non-terminals have the "name" fields set.  So
793       // there's no need to check it below for "e_nrw" and "ntexp".  In
794       // fact, we rely here on the fact that the "name" fields of both these
795       // variables are the same.
796       NonTerminal e_nrw = (NonTerminal)e;
797       NormalProduction ntprod = (NormalProduction)(production_table.get(e_nrw.name));
798       if (ntprod instanceof JavaCodeProduction) {
799         ; // nothing to do here
800       } else {
801         generate3R(ntprod.expansion, inf);
802       }
803     } else if (e instanceof Choice) {
804       Choice e_nrw = (Choice)e;
805       for (int i = 0; i < e_nrw.choices.size(); i++) {
806         generate3R((Expansion)(e_nrw.choices.elementAt(i)), inf);
807       }
808     } else if (e instanceof Sequence) {
809       Sequence e_nrw = (Sequence)e;
810       // We skip the first element in the following iteration since it is the
811       // Lookahead object.
812       int cnt = inf.count;
813       for (int i = 1; i < e_nrw.units.size(); i++) {
814         Expansion eseq = (Expansion)(e_nrw.units.elementAt(i));
815         setupPhase3Builds(new Phase3Data(eseq, cnt));
816         cnt -= minimumSize(eseq);
817         if (cnt <= 0) break;
818       }
819     } else if (e instanceof TryBlock) {
820       TryBlock e_nrw = (TryBlock)e;
821       setupPhase3Builds(new Phase3Data(e_nrw.exp, inf.count));
822     } else if (e instanceof OneOrMore) {
823       OneOrMore e_nrw = (OneOrMore)e;
824       generate3R(e_nrw.expansion, inf);
825     } else if (e instanceof ZeroOrMore) {
826       ZeroOrMore e_nrw = (ZeroOrMore)e;
827       generate3R(e_nrw.expansion, inf);
828     } else if (e instanceof ZeroOrOne) {
829       ZeroOrOne e_nrw = (ZeroOrOne)e;
830       generate3R(e_nrw.expansion, inf);
831     }
832   }
833 
834   private static String genjj_3Call(Expansion e)
835   {
836      if (e.internal_name.startsWith("jj_scan_token"))
837         return e.internal_name;
838      else
839         return "jj_3" + e.internal_name + "()";
840   }
841 
842   static Hashtable generated = new Hashtable();
843   static void buildPhase3Routine(Phase3Data inf, boolean recursive_call) {
844     Expansion e = inf.exp;
845     Token t = null;
846     if (e.internal_name.startsWith("jj_scan_token"))
847        return;
848 
849     if (!recursive_call) {
850       ostr.println("  " + staticOpt() + "final private boolean jj_3" + e.internal_name + "() {");
851       xsp_declared = false;
852       if (Options.B("DEBUG_LOOKAHEAD") && e.parent instanceof NormalProduction) {
853         ostr.print("    ");
854         if (Options.B("ERROR_REPORTING")) {
855           ostr.print("if (!jj_rescan) ");
856         }
857         ostr.println("trace_call(\"" + ((NormalProduction)e.parent).lhs + "(LOOKING AHEAD...)\");");
858         jj3_expansion = e;
859       } else {
860         jj3_expansion = null;
861       }
862     }
863     if (e instanceof RegularExpression) {
864       RegularExpression e_nrw = (RegularExpression)e;
865       if (e_nrw.label.equals("")) {
866         Object label = names_of_tokens.get(new Integer(e_nrw.ordinal));
867         if (label != null) {
868           ostr.println("    if (jj_scan_token(" + (String)label + ")) " + genReturn(true));
869         } else {
870           ostr.println("    if (jj_scan_token(" + e_nrw.ordinal + ")) " + genReturn(true));
871         }
872       } else {
873         ostr.println("    if (jj_scan_token(" + e_nrw.label + ")) " + genReturn(true));
874       }
875       //ostr.println("    if (jj_la == 0 && jj_scanpos == jj_lastpos) " + genReturn(false));
876     } else if (e instanceof NonTerminal) {
877       // All expansions of non-terminals have the "name" fields set.  So
878       // there's no need to check it below for "e_nrw" and "ntexp".  In
879       // fact, we rely here on the fact that the "name" fields of both these
880       // variables are the same.
881       NonTerminal e_nrw = (NonTerminal)e;
882       NormalProduction ntprod = (NormalProduction)(production_table.get(e_nrw.name));
883       if (ntprod instanceof JavaCodeProduction) {
884         ostr.println("    if (true) { jj_la = 0; jj_scanpos = jj_lastpos; " + genReturn(false) + "}");
885       } else {
886         Expansion ntexp = ntprod.expansion;
887         //ostr.println("    if (jj_3" + ntexp.internal_name + "()) " + genReturn(true));
888         ostr.println("    if (" + genjj_3Call(ntexp)+ ") " + genReturn(true));
889         //ostr.println("    if (jj_la == 0 && jj_scanpos == jj_lastpos) " + genReturn(false));
890       }
891     } else if (e instanceof Choice) {
892       if (!xsp_declared) {
893         xsp_declared = true;
894         ostr.println("    Token xsp;");
895       }
896       ostr.println("    xsp = jj_scanpos;");
897       Sequence nested_seq;
898       Choice e_nrw = (Choice)e;
899       for (int i = 0; i < e_nrw.choices.size(); i++) {
900         nested_seq = (Sequence)(e_nrw.choices.elementAt(i));
901         Lookahead la = (Lookahead)(nested_seq.units.elementAt(0));
902         if (la.action_tokens.size() != 0) {
903           // We have semantic lookahead that must be evaluated.
904           ostr.println("    lookingAhead = true;");
905           ostr.print("    jj_semLA = ");
906           printTokenSetup((Token)(la.action_tokens.elementAt(0)));
907           for (java.util.Enumeration enum = la.action_tokens.elements(); enum.hasMoreElements();) {
908             t = (Token)enum.nextElement();
909             printToken(t, ostr);
910           }
911           printTrailingComments(t, ostr);
912           ostr.println(";");
913           ostr.println("    lookingAhead = false;");
914         }
915         ostr.print("    if (");
916         if (la.action_tokens.size() != 0) {
917           ostr.print("!jj_semLA || ");
918         }
919         if (i != e_nrw.choices.size() - 1) {
920           //ostr.println("jj_3" + nested_seq.internal_name + "()) {");
921           ostr.println(genjj_3Call(nested_seq) + ") {");
922           ostr.println("    jj_scanpos = xsp;");
923         } else {
924           //ostr.println("jj_3" + nested_seq.internal_name + "()) " + genReturn(true));
925           ostr.println(genjj_3Call(nested_seq) + ") " + genReturn(true));
926           //ostr.println("    if (jj_la == 0 && jj_scanpos == jj_lastpos) " + genReturn(false));
927         }
928       }
929       for (int i = 1; i < e_nrw.choices.size(); i++) {
930         //ostr.println("    } else if (jj_la == 0 && jj_scanpos == jj_lastpos) " + genReturn(false));
931         ostr.println("    }");
932       }
933     } else if (e instanceof Sequence) {
934       Sequence e_nrw = (Sequence)e;
935       // We skip the first element in the following iteration since it is the
936       // Lookahead object.
937       int cnt = inf.count;
938       for (int i = 1; i < e_nrw.units.size(); i++) {
939         Expansion eseq = (Expansion)(e_nrw.units.elementAt(i));
940         buildPhase3Routine(new Phase3Data(eseq, cnt), true);
941 
942 //System.out.println("minimumSize: line: " + eseq.line + ", column: " + eseq.column + ": " + minimumSize(eseq));//Test Code
943 
944         cnt -= minimumSize(eseq);
945         if (cnt <= 0) break;
946       }
947     } else if (e instanceof TryBlock) {
948       TryBlock e_nrw = (TryBlock)e;
949       buildPhase3Routine(new Phase3Data(e_nrw.exp, inf.count), true);
950     } else if (e instanceof OneOrMore) {
951       if (!xsp_declared) {
952         xsp_declared = true;
953         ostr.println("    Token xsp;");
954       }
955       OneOrMore e_nrw = (OneOrMore)e;
956       Expansion nested_e = e_nrw.expansion;
957       //ostr.println("    if (jj_3" + nested_e.internal_name + "()) " + genReturn(true));
958       ostr.println("    if (" + genjj_3Call(nested_e) + ") " + genReturn(true));
959       //ostr.println("    if (jj_la == 0 && jj_scanpos == jj_lastpos) " + genReturn(false));
960       ostr.println("    while (true) {");
961       ostr.println("      xsp = jj_scanpos;");
962       //ostr.println("      if (jj_3" + nested_e.internal_name + "()) { jj_scanpos = xsp; break; }");
963       ostr.println("      if (" + genjj_3Call(nested_e) + ") { jj_scanpos = xsp; break; }");
964       //ostr.println("      if (jj_la == 0 && jj_scanpos == jj_lastpos) " + genReturn(false));
965       ostr.println("    }");
966     } else if (e instanceof ZeroOrMore) {
967       if (!xsp_declared) {
968         xsp_declared = true;
969         ostr.println("    Token xsp;");
970       }
971       ZeroOrMore e_nrw = (ZeroOrMore)e;
972       Expansion nested_e = e_nrw.expansion;
973       ostr.println("    while (true) {");
974       ostr.println("      xsp = jj_scanpos;");
975       //ostr.println("      if (jj_3" + nested_e.internal_name + "()) { jj_scanpos = xsp; break; }");
976       ostr.println("      if (" + genjj_3Call(nested_e) + ") { jj_scanpos = xsp; break; }");
977       //ostr.println("      if (jj_la == 0 && jj_scanpos == jj_lastpos) " + genReturn(false));
978       ostr.println("    }");
979     } else if (e instanceof ZeroOrOne) {
980       if (!xsp_declared) {
981         xsp_declared = true;
982         ostr.println("    Token xsp;");
983       }
984       ZeroOrOne e_nrw = (ZeroOrOne)e;
985       Expansion nested_e = e_nrw.expansion;
986       ostr.println("    xsp = jj_scanpos;");
987       //ostr.println("    if (jj_3" + nested_e.internal_name + "()) jj_scanpos = xsp;");
988       ostr.println("    if (" + genjj_3Call(nested_e) + ") jj_scanpos = xsp;");
989       //ostr.println("    else if (jj_la == 0 && jj_scanpos == jj_lastpos) " + genReturn(false));
990     }
991     if (!recursive_call) {
992       ostr.println("    " + genReturn(false));
993       ostr.println("  }");
994       ostr.println("");
995     }
996   }
997 
998   /*
999    * Returns the minimum number of tokens that can parse to this expansion.
1000   */
1001  static int minimumSize(Expansion e) {
1002    int retval = 0;  // should never be used.  Will be bad if it is.
1003    if (e.inMinimumSize) {
1004      // recursive search for minimum size unnecessary.
1005      return Integer.MAX_VALUE;
1006    }
1007    e.inMinimumSize = true;
1008    if (e instanceof RegularExpression) {
1009      retval = 1;
1010    } else if (e instanceof NonTerminal) {
1011      NonTerminal e_nrw = (NonTerminal)e;
1012      NormalProduction ntprod = (NormalProduction)(production_table.get(e_nrw.name));
1013      if (ntprod instanceof JavaCodeProduction) {
1014        retval = Integer.MAX_VALUE;
1015        // Make caller think this is unending (for we do not go beyond JAVACODE during
1016        // phase3 execution).
1017      } else {
1018        Expansion ntexp = ntprod.expansion;
1019        retval = minimumSize(ntexp);
1020      }
1021    } else if (e instanceof Choice) {
1022      int min = Integer.MAX_VALUE;
1023      Expansion nested_e;
1024      Choice e_nrw = (Choice)e;
1025      for (int i = 0; i < e_nrw.choices.size(); i++) {
1026        nested_e = (Expansion)(e_nrw.choices.elementAt(i));
1027        int min1 = minimumSize(nested_e);
1028        if (min > min1) min = min1;
1029      }
1030      retval = min;
1031    } else if (e instanceof Sequence) {
1032      int min = 0;
1033      Sequence e_nrw = (Sequence)e;
1034      // We skip the first element in the following iteration since it is the
1035      // Lookahead object.
1036      for (int i = 1; i < e_nrw.units.size(); i++) {
1037        Expansion eseq = (Expansion)(e_nrw.units.elementAt(i));
1038        int mineseq = minimumSize(eseq);
1039        if (min == Integer.MAX_VALUE || mineseq == Integer.MAX_VALUE) {
1040          min = Integer.MAX_VALUE; // Adding infinity to something results in infinity.
1041        } else {
1042          min += mineseq;
1043        }
1044      }
1045      retval = min;
1046    } else if (e instanceof TryBlock) {
1047      TryBlock e_nrw = (TryBlock)e;
1048      retval = minimumSize(e_nrw.exp);
1049    } else if (e instanceof OneOrMore) {
1050      OneOrMore e_nrw = (OneOrMore)e;
1051      retval = minimumSize(e_nrw.expansion);
1052    } else if (e instanceof ZeroOrMore) {
1053      retval = 0;
1054    } else if (e instanceof ZeroOrOne) {
1055      retval = 0;
1056    } else if (e instanceof Lookahead) {
1057      retval = 0;
1058    } else if (e instanceof Action) {
1059      retval = 0;
1060    }
1061    e.inMinimumSize = false;
1062    return retval;
1063  }
1064
1065  static void build(java.io.PrintWriter ps) {
1066    NormalProduction p;
1067    JavaCodeProduction jp;
1068    Token t = null;
1069
1070    ostr = ps;
1071
1072    for (java.util.Enumeration enum = bnfproductions.elements(); enum.hasMoreElements();) {
1073      p = (NormalProduction)enum.nextElement();
1074      if (p instanceof JavaCodeProduction) {
1075        jp = (JavaCodeProduction)p;
1076        t = (Token)(jp.return_type_tokens.elementAt(0));
1077        printTokenSetup(t); ccol = 1;
1078        printLeadingComments(t, ostr);
1079        ostr.print("  " + staticOpt());
1080        cline = t.beginLine; ccol = t.beginColumn;
1081        printTokenOnly(t, ostr);
1082        for (int i = 1; i < jp.return_type_tokens.size(); i++) {
1083          t = (Token)(jp.return_type_tokens.elementAt(i));
1084          printToken(t, ostr);
1085        }
1086        printTrailingComments(t, ostr);
1087        ostr.print(" " + jp.lhs + "(");
1088        if (jp.parameter_list_tokens.size() != 0) {
1089          printTokenSetup((Token)(jp.parameter_list_tokens.elementAt(0)));
1090          for (java.util.Enumeration enum1 = jp.parameter_list_tokens.elements(); enum1.hasMoreElements();) {
1091            t = (Token)enum1.nextElement();
1092            printToken(t, ostr);
1093          }
1094          printTrailingComments(t, ostr);
1095        }
1096        ostr.print(") throws ParseException");
1097        for (java.util.Enumeration enum1 = jp.throws_list.elements(); enum1.hasMoreElements();) {
1098          ostr.print(", ");
1099          java.util.Vector name = (java.util.Vector)enum1.nextElement();
1100          for (java.util.Enumeration enum2 = name.elements(); enum2.hasMoreElements();) {
1101            t = (Token)enum2.nextElement();
1102            ostr.print(t.image);
1103          }
1104        }
1105        ostr.print(" {");
1106        if (Options.B("DEBUG_PARSER")) {
1107          ostr.println("");
1108          ostr.println("    trace_call(\"" + jp.lhs + "\");");
1109          ostr.print("    try {");
1110        }
1111        if (jp.code_tokens.size() != 0) {
1112          printTokenSetup((Token)(jp.code_tokens.elementAt(0))); cline--;
1113          for (java.util.Enumeration enum1 = jp.code_tokens.elements(); enum1.hasMoreElements();) {
1114            t = (Token)enum1.nextElement();
1115            printToken(t, ostr);
1116          }
1117          printTrailingComments(t, ostr);
1118        }
1119        ostr.println("");
1120        if (Options.B("DEBUG_PARSER")) {
1121          ostr.println("    } finally {");
1122          ostr.println("      trace_return(\"" + jp.lhs + "\");");
1123          ostr.println("    }");
1124        }
1125        ostr.println("  }");
1126        ostr.println("");
1127      } else {
1128        buildPhase1Routine((BNFProduction)p);
1129      }
1130    }
1131
1132    for (int phase2index = 0; phase2index < phase2list.size(); phase2index++) {
1133      buildPhase2Routine((Lookahead)(phase2list.elementAt(phase2index)));
1134    }
1135
1136    int phase3index = 0;
1137
1138    while (phase3index < phase3list.size()) {
1139      for (; phase3index < phase3list.size(); phase3index++) {
1140        setupPhase3Builds((Phase3Data)(phase3list.elementAt(phase3index)));
1141      }
1142    }
1143
1144    for (java.util.Enumeration enum = phase3table.elements(); enum.hasMoreElements();) {
1145      buildPhase3Routine((Phase3Data)(enum.nextElement()), false);
1146    }
1147
1148  }
1149
1150   public static void reInit()
1151   {
1152      ostr = null;
1153      gensymindex = 0;
1154      indentamt = (int)0;
1155      jj2LA = false;
1156      phase2list = new java.util.Vector();
1157      phase3list = new java.util.Vector();
1158      phase3table = new java.util.Hashtable();
1159      firstSet = null;
1160      xsp_declared = false;
1161      jj3_expansion = null;
1162   }
1163
1164}
1165
1166/*
1167 * This class stored information to pass from phase 2 to phase 3.
1168 */
1169class Phase3Data {
1170
1171  /*
1172   * This is the expansion to generate the jj3 method for.
1173   */
1174  Expansion exp;
1175
1176  /*
1177   * This is the number of tokens that can still be consumed.  This
1178   * number is used to limit the number of jj3 methods generated.
1179   */
1180  int count;
1181
1182  Phase3Data(Expansion e, int c) {
1183    exp = e;
1184    count = c;
1185  }
1186
1187}
1188
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Java Books Remove Frame
Popular Tags