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