001/* BnfParser.java */
002/* Generated By:JavaCC: Do not edit this line. BnfParser.java */
003package net.hydromatic.clapham.parser.bnf;
004
005import java.util.*;
006import net.hydromatic.clapham.parser.*;
007
008/**
009 * Parser for grammars in Backus-Naur Form (BNF) notation.
010 *
011 * <p>The supported grammar is
012 * <a href="http://en.wikipedia.org/wiki/Backus?Naur_form">Backus-Naur Form</a>,
013 * extended with '*' (closure operator), '+' (mandatory repetition), but is not
014 * the grammar officially known as 'Extended Backus-Naur Form' (EBNF).
015 *
016 * @author Julian Hyde
017 * @version $Id: BnfParser.jj 3 2009-05-11 08:11:57Z jhyde $
018 */
019public class BnfParser implements BnfParserConstants {
020    public static <E extends EbnfNode> void toString(
021        StringBuilder buf, String start, List<E> list, String end)
022    {
023        int i = 0;
024        buf.append(start);
025        for (E node : list) {
026            if (i++ > 0) {
027                buf.append(", ");
028            }
029            node.toString(buf);
030        }
031        buf.append(end);
032    }
033
034/*
035Example:
036
037Wirth's BNF, expressed in JavaCC-like BNF:
038
039SYNTAX     ::= ( PRODUCTION )*
040PRODUCTION ::= IDENTIFIER "::=" EXPRESSION "." <eol>
041EXPRESSION ::= TERM ( "|" TERM )*
042TERM       ::= FACTOR+
043FACTOR     ::= IDENTIFIER
044           | LITERAL
045           | "[" EXPRESSION "]"
046           | "(" EXPRESSION ")"
047           | "{" EXPRESSION "}"
048IDENTIFIER ::= <letter>+
049LITERAL    ::= """" <character>+ """"
050
051*/
052
053/*****************************************
054 * Syntactical Descriptions              *
055 *****************************************/
056
057// SYNTAX ::= PRODUCTION*
058  final public List<ProductionNode> Syntax() throws ParseException {List<ProductionNode> list = new ArrayList<ProductionNode>();
059    ProductionNode p;
060    label_1:
061    while (true) {
062      if (jj_2_1(4)) {
063        ;
064      } else {
065        break label_1;
066      }
067      p = Production();
068list.add(p);
069    }
070    jj_consume_token(0);
071{if ("" != null) return list;}
072    throw new Error("Missing return statement in function");
073}
074
075// PRODUCTION ::= IDENTIFIER "::=" EXPRESSION
076  final public ProductionNode Production() throws ParseException {IdentifierNode id;
077    EbnfNode expression;
078    id = Identifier();
079    jj_consume_token(COLCOLEQ);
080    expression = Expression();
081{if ("" != null) return new ProductionNode(id, expression);}
082    throw new Error("Missing return statement in function");
083}
084
085// EXPRESSION ::= TERM ( "|" TERM )*
086  final public EbnfNode Expression() throws ParseException {List<EbnfNode> list = new ArrayList<EbnfNode>();
087    EbnfNode n;
088    n = Term();
089list.add(n);
090    label_2:
091    while (true) {
092      switch ((jj_ntk==-1)?jj_ntk_f():jj_ntk) {
093      case BAR:{
094        ;
095        break;
096        }
097      default:
098        jj_la1[0] = jj_gen;
099        break label_2;
100      }
101      jj_consume_token(BAR);
102      n = Term();
103list.add(n);
104    }
105if (list.size() == 1) {
106            {if ("" != null) return list.get(0);}
107        } else {
108            {if ("" != null) return new AlternateNode(list);}
109        }
110    throw new Error("Missing return statement in function");
111}
112
113// TERM       ::= FACTOR +
114  final public EbnfNode Term() throws ParseException {EbnfNode n;
115    List<EbnfNode> list = new ArrayList<EbnfNode>();
116    label_3:
117    while (true) {
118      if (jj_2_2(2147483647) && (!(getToken(1).kind == IDENTIFIER && getToken(2).kind == COLCOLEQ))) {
119        ;
120      } else {
121        break label_3;
122      }
123      n = Factor();
124list.add(n);
125    }
126switch (list.size()) {
127        case 0:
128            {if ("" != null) return new EmptyNode();}
129        case 1:
130            {if ("" != null) return list.get(0);}
131        default:
132            {if ("" != null) return new SequenceNode(list);}
133        }
134    throw new Error("Missing return statement in function");
135}
136
137// FACTOR       ::= FACTOR2 "+" ?
138  final public EbnfNode Factor() throws ParseException {EbnfNode n;
139    n = Factor2();
140    switch ((jj_ntk==-1)?jj_ntk_f():jj_ntk) {
141    case PLUS:{
142      jj_consume_token(PLUS);
143n = new MandatoryRepeatNode(n);
144      break;
145      }
146    default:
147      jj_la1[1] = jj_gen;
148      ;
149    }
150{if ("" != null) return n;}
151    throw new Error("Missing return statement in function");
152}
153
154// FACTOR2  ::= FACTOR3
155//            | FACTOR3 "*"
156//            | FACTOR3 "?"
157  final public EbnfNode Factor2() throws ParseException {EbnfNode n;
158    n = Factor3();
159    switch ((jj_ntk==-1)?jj_ntk_f():jj_ntk) {
160    case HOOK:
161    case ASTERISK:{
162      switch ((jj_ntk==-1)?jj_ntk_f():jj_ntk) {
163      case ASTERISK:{
164        jj_consume_token(ASTERISK);
165n = new RepeatNode(n);
166        break;
167        }
168      case HOOK:{
169        jj_consume_token(HOOK);
170n = new OptionNode(n);
171        break;
172        }
173      default:
174        jj_la1[2] = jj_gen;
175        jj_consume_token(-1);
176        throw new ParseException();
177      }
178      break;
179      }
180    default:
181      jj_la1[3] = jj_gen;
182      ;
183    }
184{if ("" != null) return n;}
185    throw new Error("Missing return statement in function");
186}
187
188// FACTOR3  ::= IDENTIFIER
189//            | LITERAL
190//            | "(" EXPRESSION ")"
191  final public EbnfNode Factor3() throws ParseException {EbnfNode n;
192    switch ((jj_ntk==-1)?jj_ntk_f():jj_ntk) {
193    case IDENTIFIER:
194    case BRACKETED_IDENTIFIER:{
195      n = Identifier();
196      break;
197      }
198    case LITERAL:{
199      n = Literal();
200      break;
201      }
202    case LPAREN:{
203      jj_consume_token(LPAREN);
204      n = Expression();
205      jj_consume_token(RPAREN);
206      break;
207      }
208    default:
209      jj_la1[4] = jj_gen;
210      jj_consume_token(-1);
211      throw new ParseException();
212    }
213{if ("" != null) return n;}
214    throw new Error("Missing return statement in function");
215}
216
217// IDENTIFIER ::= <letter>+
218  final public IdentifierNode Identifier() throws ParseException {String s;
219    switch ((jj_ntk==-1)?jj_ntk_f():jj_ntk) {
220    case IDENTIFIER:{
221      s = jj_consume_token(IDENTIFIER).image;
222{if ("" != null) return new IdentifierNode(s);}
223      break;
224      }
225    case BRACKETED_IDENTIFIER:{
226      s = jj_consume_token(BRACKETED_IDENTIFIER).image;
227String stripped = s.substring(1, s.length() - 1);
228        {if ("" != null) return new IdentifierNode(stripped);}
229      break;
230      }
231    default:
232      jj_la1[5] = jj_gen;
233      jj_consume_token(-1);
234      throw new ParseException();
235    }
236    throw new Error("Missing return statement in function");
237}
238
239// LITERAL    = """" character+ """"
240  final public LiteralNode Literal() throws ParseException {String s;
241    s = jj_consume_token(LITERAL).image;
242assert s.startsWith("\"") && s.endsWith("\"") : s;
243        {if ("" != null) return new LiteralNode(s.substring(1, s.length() - 1));}
244    throw new Error("Missing return statement in function");
245}
246
247  private boolean jj_2_1(int xla)
248 {
249    jj_la = xla; jj_lastpos = jj_scanpos = token;
250    try { return (!jj_3_1()); }
251    catch(LookaheadSuccess ls) { return true; }
252    finally { jj_save(0, xla); }
253  }
254
255  private boolean jj_2_2(int xla)
256 {
257    jj_la = xla; jj_lastpos = jj_scanpos = token;
258    try { return (!jj_3_2()); }
259    catch(LookaheadSuccess ls) { return true; }
260    finally { jj_save(1, xla); }
261  }
262
263  private boolean jj_3R_5()
264 {
265    if (jj_3R_8()) return true;
266    Token xsp;
267    xsp = jj_scanpos;
268    if (jj_3R_9()) jj_scanpos = xsp;
269    return false;
270  }
271
272  private boolean jj_3R_14()
273 {
274    Token xsp;
275    xsp = jj_scanpos;
276    if (jj_3R_17()) {
277    jj_scanpos = xsp;
278    if (jj_3R_18()) {
279    jj_scanpos = xsp;
280    if (jj_3R_19()) return true;
281    }
282    }
283    return false;
284  }
285
286  private boolean jj_3R_7()
287 {
288    if (jj_3R_12()) return true;
289    Token xsp;
290    while (true) {
291      xsp = jj_scanpos;
292      if (jj_3R_13()) { jj_scanpos = xsp; break; }
293    }
294    return false;
295  }
296
297  private boolean jj_3R_22()
298 {
299    if (jj_scan_token(LITERAL)) return true;
300    return false;
301  }
302
303  private boolean jj_3R_21()
304 {
305    if (jj_scan_token(HOOK)) return true;
306    return false;
307  }
308
309  private boolean jj_3_2()
310 {
311    if (jj_3R_5()) return true;
312    return false;
313  }
314
315  private boolean jj_3R_20()
316 {
317    if (jj_scan_token(ASTERISK)) return true;
318    return false;
319  }
320
321  private boolean jj_3R_15()
322 {
323    Token xsp;
324    xsp = jj_scanpos;
325    if (jj_3R_20()) {
326    jj_scanpos = xsp;
327    if (jj_3R_21()) return true;
328    }
329    return false;
330  }
331
332  private boolean jj_3R_4()
333 {
334    if (jj_3R_6()) return true;
335    if (jj_scan_token(COLCOLEQ)) return true;
336    if (jj_3R_7()) return true;
337    return false;
338  }
339
340  private boolean jj_3R_16()
341 {
342    if (jj_3R_5()) return true;
343    return false;
344  }
345
346  private boolean jj_3R_11()
347 {
348    if (jj_scan_token(BRACKETED_IDENTIFIER)) return true;
349    return false;
350  }
351
352  private boolean jj_3R_8()
353 {
354    if (jj_3R_14()) return true;
355    Token xsp;
356    xsp = jj_scanpos;
357    if (jj_3R_15()) jj_scanpos = xsp;
358    return false;
359  }
360
361  private boolean jj_3R_12()
362 {
363    Token xsp;
364    while (true) {
365      xsp = jj_scanpos;
366      if (jj_3R_16()) { jj_scanpos = xsp; break; }
367    }
368    return false;
369  }
370
371  private boolean jj_3R_6()
372 {
373    Token xsp;
374    xsp = jj_scanpos;
375    if (jj_3R_10()) {
376    jj_scanpos = xsp;
377    if (jj_3R_11()) return true;
378    }
379    return false;
380  }
381
382  private boolean jj_3R_10()
383 {
384    if (jj_scan_token(IDENTIFIER)) return true;
385    return false;
386  }
387
388  private boolean jj_3_1()
389 {
390    if (jj_3R_4()) return true;
391    return false;
392  }
393
394  private boolean jj_3R_19()
395 {
396    if (jj_scan_token(LPAREN)) return true;
397    if (jj_3R_7()) return true;
398    if (jj_scan_token(RPAREN)) return true;
399    return false;
400  }
401
402  private boolean jj_3R_9()
403 {
404    if (jj_scan_token(PLUS)) return true;
405    return false;
406  }
407
408  private boolean jj_3R_18()
409 {
410    if (jj_3R_22()) return true;
411    return false;
412  }
413
414  private boolean jj_3R_17()
415 {
416    if (jj_3R_6()) return true;
417    return false;
418  }
419
420  private boolean jj_3R_13()
421 {
422    if (jj_scan_token(BAR)) return true;
423    if (jj_3R_12()) return true;
424    return false;
425  }
426
427  /** Generated Token Manager. */
428  public BnfParserTokenManager token_source;
429  SimpleCharStream jj_input_stream;
430  /** Current token. */
431  public Token token;
432  /** Next token. */
433  public Token jj_nt;
434  private int jj_ntk;
435  private Token jj_scanpos, jj_lastpos;
436  private int jj_la;
437  private int jj_gen;
438  final private int[] jj_la1 = new int[6];
439  static private int[] jj_la1_0;
440  static {
441           jj_la1_init_0();
442        }
443        private static void jj_la1_init_0() {
444           jj_la1_0 = new int[] {0x400,0x80,0x140,0x140,0x3012,0x1002,};
445        }
446  final private JJCalls[] jj_2_rtns = new JJCalls[2];
447  private boolean jj_rescan = false;
448  private int jj_gc = 0;
449
450  /** Constructor with InputStream. */
451  public BnfParser(java.io.InputStream stream) {
452          this(stream, null);
453  }
454  /** Constructor with InputStream and supplied encoding */
455  public BnfParser(java.io.InputStream stream, String encoding) {
456         try { jj_input_stream = new SimpleCharStream(stream, encoding, 1, 1); } catch(java.io.UnsupportedEncodingException e) { throw new RuntimeException(e); }
457         token_source = new BnfParserTokenManager(jj_input_stream);
458         token = new Token();
459         jj_ntk = -1;
460         jj_gen = 0;
461         for (int i = 0; i < 6; i++) jj_la1[i] = -1;
462         for (int i = 0; i < jj_2_rtns.length; i++) jj_2_rtns[i] = new JJCalls();
463  }
464
465  /** Reinitialise. */
466  public void ReInit(java.io.InputStream stream) {
467          ReInit(stream, null);
468  }
469  /** Reinitialise. */
470  public void ReInit(java.io.InputStream stream, String encoding) {
471         try { jj_input_stream.ReInit(stream, encoding, 1, 1); } catch(java.io.UnsupportedEncodingException e) { throw new RuntimeException(e); }
472         token_source.ReInit(jj_input_stream);
473         token = new Token();
474         jj_ntk = -1;
475         jj_gen = 0;
476         for (int i = 0; i < 6; i++) jj_la1[i] = -1;
477         for (int i = 0; i < jj_2_rtns.length; i++) jj_2_rtns[i] = new JJCalls();
478  }
479
480  /** Constructor. */
481  public BnfParser(java.io.Reader stream) {
482         jj_input_stream = new SimpleCharStream(stream, 1, 1);
483         token_source = new BnfParserTokenManager(jj_input_stream);
484         token = new Token();
485         jj_ntk = -1;
486         jj_gen = 0;
487         for (int i = 0; i < 6; i++) jj_la1[i] = -1;
488         for (int i = 0; i < jj_2_rtns.length; i++) jj_2_rtns[i] = new JJCalls();
489  }
490
491  /** Reinitialise. */
492  public void ReInit(java.io.Reader stream) {
493        if (jj_input_stream == null) {
494           jj_input_stream = new SimpleCharStream(stream, 1, 1);
495        } else {
496           jj_input_stream.ReInit(stream, 1, 1);
497        }
498        if (token_source == null) {
499 token_source = new BnfParserTokenManager(jj_input_stream);
500        }
501
502         token_source.ReInit(jj_input_stream);
503         token = new Token();
504         jj_ntk = -1;
505         jj_gen = 0;
506         for (int i = 0; i < 6; i++) jj_la1[i] = -1;
507         for (int i = 0; i < jj_2_rtns.length; i++) jj_2_rtns[i] = new JJCalls();
508  }
509
510  /** Constructor with generated Token Manager. */
511  public BnfParser(BnfParserTokenManager tm) {
512         token_source = tm;
513         token = new Token();
514         jj_ntk = -1;
515         jj_gen = 0;
516         for (int i = 0; i < 6; i++) jj_la1[i] = -1;
517         for (int i = 0; i < jj_2_rtns.length; i++) jj_2_rtns[i] = new JJCalls();
518  }
519
520  /** Reinitialise. */
521  public void ReInit(BnfParserTokenManager tm) {
522         token_source = tm;
523         token = new Token();
524         jj_ntk = -1;
525         jj_gen = 0;
526         for (int i = 0; i < 6; i++) jj_la1[i] = -1;
527         for (int i = 0; i < jj_2_rtns.length; i++) jj_2_rtns[i] = new JJCalls();
528  }
529
530  private Token jj_consume_token(int kind) throws ParseException {
531         Token oldToken;
532         if ((oldToken = token).next != null) token = token.next;
533         else token = token.next = token_source.getNextToken();
534         jj_ntk = -1;
535         if (token.kind == kind) {
536           jj_gen++;
537           if (++jj_gc > 100) {
538                 jj_gc = 0;
539                 for (int i = 0; i < jj_2_rtns.length; i++) {
540                   JJCalls c = jj_2_rtns[i];
541                   while (c != null) {
542                         if (c.gen < jj_gen) c.first = null;
543                         c = c.next;
544                   }
545                 }
546           }
547           return token;
548         }
549         token = oldToken;
550         jj_kind = kind;
551         throw generateParseException();
552  }
553
554  @SuppressWarnings("serial")
555  static private final class LookaheadSuccess extends java.lang.Error { }
556  final private LookaheadSuccess jj_ls = new LookaheadSuccess();
557  private boolean jj_scan_token(int kind) {
558         if (jj_scanpos == jj_lastpos) {
559           jj_la--;
560           if (jj_scanpos.next == null) {
561                 jj_lastpos = jj_scanpos = jj_scanpos.next = token_source.getNextToken();
562           } else {
563                 jj_lastpos = jj_scanpos = jj_scanpos.next;
564           }
565         } else {
566           jj_scanpos = jj_scanpos.next;
567         }
568         if (jj_rescan) {
569           int i = 0; Token tok = token;
570           while (tok != null && tok != jj_scanpos) { i++; tok = tok.next; }
571           if (tok != null) jj_add_error_token(kind, i);
572         }
573         if (jj_scanpos.kind != kind) return true;
574         if (jj_la == 0 && jj_scanpos == jj_lastpos) throw jj_ls;
575         return false;
576  }
577
578
579/** Get the next Token. */
580  final public Token getNextToken() {
581         if (token.next != null) token = token.next;
582         else token = token.next = token_source.getNextToken();
583         jj_ntk = -1;
584         jj_gen++;
585         return token;
586  }
587
588/** Get the specific Token. */
589  final public Token getToken(int index) {
590         Token t = token;
591         for (int i = 0; i < index; i++) {
592           if (t.next != null) t = t.next;
593           else t = t.next = token_source.getNextToken();
594         }
595         return t;
596  }
597
598  private int jj_ntk_f() {
599         if ((jj_nt=token.next) == null)
600           return (jj_ntk = (token.next=token_source.getNextToken()).kind);
601         else
602           return (jj_ntk = jj_nt.kind);
603  }
604
605  private java.util.List<int[]> jj_expentries = new java.util.ArrayList<int[]>();
606  private int[] jj_expentry;
607  private int jj_kind = -1;
608  private int[] jj_lasttokens = new int[100];
609  private int jj_endpos;
610
611  private void jj_add_error_token(int kind, int pos) {
612         if (pos >= 100) {
613                return;
614         }
615
616         if (pos == jj_endpos + 1) {
617           jj_lasttokens[jj_endpos++] = kind;
618         } else if (jj_endpos != 0) {
619           jj_expentry = new int[jj_endpos];
620
621           for (int i = 0; i < jj_endpos; i++) {
622                 jj_expentry[i] = jj_lasttokens[i];
623           }
624
625           for (int[] oldentry : jj_expentries) {
626                 if (oldentry.length == jj_expentry.length) {
627                   boolean isMatched = true;
628
629                   for (int i = 0; i < jj_expentry.length; i++) {
630                         if (oldentry[i] != jj_expentry[i]) {
631                           isMatched = false;
632                           break;
633                         }
634
635                   }
636                   if (isMatched) {
637                         jj_expentries.add(jj_expentry);
638                         break;
639                   }
640                 }
641           }
642
643           if (pos != 0) {
644                 jj_lasttokens[(jj_endpos = pos) - 1] = kind;
645           }
646         }
647  }
648
649  /** Generate ParseException. */
650  public ParseException generateParseException() {
651         jj_expentries.clear();
652         boolean[] la1tokens = new boolean[24];
653         if (jj_kind >= 0) {
654           la1tokens[jj_kind] = true;
655           jj_kind = -1;
656         }
657         for (int i = 0; i < 6; i++) {
658           if (jj_la1[i] == jj_gen) {
659                 for (int j = 0; j < 32; j++) {
660                   if ((jj_la1_0[i] & (1<<j)) != 0) {
661                         la1tokens[j] = true;
662                   }
663                 }
664           }
665         }
666         for (int i = 0; i < 24; i++) {
667           if (la1tokens[i]) {
668                 jj_expentry = new int[1];
669                 jj_expentry[0] = i;
670                 jj_expentries.add(jj_expentry);
671           }
672         }
673         jj_endpos = 0;
674         jj_rescan_token();
675         jj_add_error_token(0, 0);
676         int[][] exptokseq = new int[jj_expentries.size()][];
677         for (int i = 0; i < jj_expentries.size(); i++) {
678           exptokseq[i] = jj_expentries.get(i);
679         }
680         return new ParseException(token, exptokseq, tokenImage);
681  }
682
683  private int trace_indent = 0;
684  private boolean trace_enabled;
685
686/** Trace enabled. */
687  final public boolean trace_enabled() {
688         return trace_enabled;
689  }
690
691  /** Enable tracing. */
692  final public void enable_tracing() {
693  }
694
695  /** Disable tracing. */
696  final public void disable_tracing() {
697  }
698
699  private void jj_rescan_token() {
700         jj_rescan = true;
701         for (int i = 0; i < 2; i++) {
702           try {
703                 JJCalls p = jj_2_rtns[i];
704
705                 do {
706                   if (p.gen > jj_gen) {
707                         jj_la = p.arg; jj_lastpos = jj_scanpos = p.first;
708                         switch (i) {
709                           case 0: jj_3_1(); break;
710                           case 1: jj_3_2(); break;
711                         }
712                   }
713                   p = p.next;
714                 } while (p != null);
715
716                 } catch(LookaheadSuccess ls) { }
717         }
718         jj_rescan = false;
719  }
720
721  private void jj_save(int index, int xla) {
722         JJCalls p = jj_2_rtns[index];
723         while (p.gen > jj_gen) {
724           if (p.next == null) { p = p.next = new JJCalls(); break; }
725           p = p.next;
726         }
727
728         p.gen = jj_gen + xla - jj_la; 
729         p.first = token;
730         p.arg = xla;
731  }
732
733  static final class JJCalls {
734         int gen;
735         Token first;
736         int arg;
737         JJCalls next;
738  }
739
740}