001    /* Generated By:JavaCC: Do not edit this line. BnfParser.java */
002    package net.hydromatic.clapham.parser.bnf;
003    
004    import java.util.*;
005    import 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     */
018    public 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    /*
034    Example:
035    
036    Wirth's BNF, expressed in JavaCC-like BNF:
037    
038    SYNTAX     ::= ( PRODUCTION )*
039    PRODUCTION ::= IDENTIFIER "::=" EXPRESSION "." <eol>
040    EXPRESSION ::= TERM ( "|" TERM )*
041    TERM       ::= FACTOR+
042    FACTOR     ::= IDENTIFIER
043               | LITERAL
044               | "[" EXPRESSION "]"
045               | "(" EXPRESSION ")"
046               | "{" EXPRESSION "}"
047    IDENTIFIER ::= <letter>+
048    LITERAL    ::= """" <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    }