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("\"") && s.endsWith("\"") : 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      final 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      final 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      final 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      final 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      final 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      final private boolean jj_3R_22() {
291        if (jj_scan_token(LITERAL)) return true;
292        return false;
293      }
294    
295      final private boolean jj_3R_21() {
296        if (jj_scan_token(HOOK)) return true;
297        return false;
298      }
299    
300      final private boolean jj_3_2() {
301        if (jj_3R_5()) return true;
302        return false;
303      }
304    
305      final private boolean jj_3R_20() {
306        if (jj_scan_token(ASTERISK)) return true;
307        return false;
308      }
309    
310      final 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      final 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      final private boolean jj_3R_16() {
328        if (jj_3R_5()) return true;
329        return false;
330      }
331    
332      final private boolean jj_3R_11() {
333        if (jj_scan_token(BRACKETED_IDENTIFIER)) return true;
334        return false;
335      }
336    
337      final 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      final 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      final 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      final private boolean jj_3R_10() {
365        if (jj_scan_token(IDENTIFIER)) return true;
366        return false;
367      }
368    
369      final private boolean jj_3_1() {
370        if (jj_3R_4()) return true;
371        return false;
372      }
373    
374      final 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      final private boolean jj_3R_9() {
382        if (jj_scan_token(PLUS)) return true;
383        return false;
384      }
385    
386      final private boolean jj_3R_18() {
387        if (jj_3R_22()) return true;
388        return false;
389      }
390    
391      final private boolean jj_3R_17() {
392        if (jj_3R_6()) return true;
393        return false;
394      }
395    
396      final 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      public BnfParserTokenManager token_source;
403      SimpleCharStream jj_input_stream;
404      public Token token, jj_nt;
405      private int jj_ntk;
406      private Token jj_scanpos, jj_lastpos;
407      private int jj_la;
408      public boolean lookingAhead = false;
409      private boolean jj_semLA;
410      private int jj_gen;
411      final private int[] jj_la1 = new int[6];
412      static private int[] jj_la1_0;
413      static {
414          jj_la1_0();
415       }
416       private static void jj_la1_0() {
417          jj_la1_0 = new int[] {0x400,0x80,0x140,0x140,0x3012,0x1002,};
418       }
419      final private JJCalls[] jj_2_rtns = new JJCalls[2];
420      private boolean jj_rescan = false;
421      private int jj_gc = 0;
422    
423      public BnfParser(java.io.InputStream stream) {
424         this(stream, null);
425      }
426      public BnfParser(java.io.InputStream stream, String encoding) {
427        try { jj_input_stream = new SimpleCharStream(stream, encoding, 1, 1); } catch(java.io.UnsupportedEncodingException e) { throw new RuntimeException(e); }
428        token_source = new BnfParserTokenManager(jj_input_stream);
429        token = new Token();
430        jj_ntk = -1;
431        jj_gen = 0;
432        for (int i = 0; i < 6; i++) jj_la1[i] = -1;
433        for (int i = 0; i < jj_2_rtns.length; i++) jj_2_rtns[i] = new JJCalls();
434      }
435    
436      public void ReInit(java.io.InputStream stream) {
437         ReInit(stream, null);
438      }
439      public void ReInit(java.io.InputStream stream, String encoding) {
440        try { jj_input_stream.ReInit(stream, encoding, 1, 1); } catch(java.io.UnsupportedEncodingException e) { throw new RuntimeException(e); }
441        token_source.ReInit(jj_input_stream);
442        token = new Token();
443        jj_ntk = -1;
444        jj_gen = 0;
445        for (int i = 0; i < 6; i++) jj_la1[i] = -1;
446        for (int i = 0; i < jj_2_rtns.length; i++) jj_2_rtns[i] = new JJCalls();
447      }
448    
449      public BnfParser(java.io.Reader stream) {
450        jj_input_stream = new SimpleCharStream(stream, 1, 1);
451        token_source = new BnfParserTokenManager(jj_input_stream);
452        token = new Token();
453        jj_ntk = -1;
454        jj_gen = 0;
455        for (int i = 0; i < 6; i++) jj_la1[i] = -1;
456        for (int i = 0; i < jj_2_rtns.length; i++) jj_2_rtns[i] = new JJCalls();
457      }
458    
459      public void ReInit(java.io.Reader stream) {
460        jj_input_stream.ReInit(stream, 1, 1);
461        token_source.ReInit(jj_input_stream);
462        token = new Token();
463        jj_ntk = -1;
464        jj_gen = 0;
465        for (int i = 0; i < 6; i++) jj_la1[i] = -1;
466        for (int i = 0; i < jj_2_rtns.length; i++) jj_2_rtns[i] = new JJCalls();
467      }
468    
469      public BnfParser(BnfParserTokenManager tm) {
470        token_source = tm;
471        token = new Token();
472        jj_ntk = -1;
473        jj_gen = 0;
474        for (int i = 0; i < 6; i++) jj_la1[i] = -1;
475        for (int i = 0; i < jj_2_rtns.length; i++) jj_2_rtns[i] = new JJCalls();
476      }
477    
478      public void ReInit(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      final private Token jj_consume_token(int kind) throws ParseException {
488        Token oldToken;
489        if ((oldToken = token).next != null) token = token.next;
490        else token = token.next = token_source.getNextToken();
491        jj_ntk = -1;
492        if (token.kind == kind) {
493          jj_gen++;
494          if (++jj_gc > 100) {
495            jj_gc = 0;
496            for (int i = 0; i < jj_2_rtns.length; i++) {
497              JJCalls c = jj_2_rtns[i];
498              while (c != null) {
499                if (c.gen < jj_gen) c.first = null;
500                c = c.next;
501              }
502            }
503          }
504          return token;
505        }
506        token = oldToken;
507        jj_kind = kind;
508        throw generateParseException();
509      }
510    
511      static private final class LookaheadSuccess extends java.lang.Error { }
512      final private LookaheadSuccess jj_ls = new LookaheadSuccess();
513      final private boolean jj_scan_token(int kind) {
514        if (jj_scanpos == jj_lastpos) {
515          jj_la--;
516          if (jj_scanpos.next == null) {
517            jj_lastpos = jj_scanpos = jj_scanpos.next = token_source.getNextToken();
518          } else {
519            jj_lastpos = jj_scanpos = jj_scanpos.next;
520          }
521        } else {
522          jj_scanpos = jj_scanpos.next;
523        }
524        if (jj_rescan) {
525          int i = 0; Token tok = token;
526          while (tok != null && tok != jj_scanpos) { i++; tok = tok.next; }
527          if (tok != null) jj_add_error_token(kind, i);
528        }
529        if (jj_scanpos.kind != kind) return true;
530        if (jj_la == 0 && jj_scanpos == jj_lastpos) throw jj_ls;
531        return false;
532      }
533    
534      final public Token getNextToken() {
535        if (token.next != null) token = token.next;
536        else token = token.next = token_source.getNextToken();
537        jj_ntk = -1;
538        jj_gen++;
539        return token;
540      }
541    
542      final public Token getToken(int index) {
543        Token t = lookingAhead ? jj_scanpos : token;
544        for (int i = 0; i < index; i++) {
545          if (t.next != null) t = t.next;
546          else t = t.next = token_source.getNextToken();
547        }
548        return t;
549      }
550    
551      final private int jj_ntk() {
552        if ((jj_nt=token.next) == null)
553          return (jj_ntk = (token.next=token_source.getNextToken()).kind);
554        else
555          return (jj_ntk = jj_nt.kind);
556      }
557    
558      private java.util.Vector jj_expentries = new java.util.Vector();
559      private int[] jj_expentry;
560      private int jj_kind = -1;
561      private int[] jj_lasttokens = new int[100];
562      private int jj_endpos;
563    
564      private void jj_add_error_token(int kind, int pos) {
565        if (pos >= 100) return;
566        if (pos == jj_endpos + 1) {
567          jj_lasttokens[jj_endpos++] = kind;
568        } else if (jj_endpos != 0) {
569          jj_expentry = new int[jj_endpos];
570          for (int i = 0; i < jj_endpos; i++) {
571            jj_expentry[i] = jj_lasttokens[i];
572          }
573          boolean exists = false;
574          for (java.util.Enumeration e = jj_expentries.elements(); e.hasMoreElements();) {
575            int[] oldentry = (int[])(e.nextElement());
576            if (oldentry.length == jj_expentry.length) {
577              exists = true;
578              for (int i = 0; i < jj_expentry.length; i++) {
579                if (oldentry[i] != jj_expentry[i]) {
580                  exists = false;
581                  break;
582                }
583              }
584              if (exists) break;
585            }
586          }
587          if (!exists) jj_expentries.addElement(jj_expentry);
588          if (pos != 0) jj_lasttokens[(jj_endpos = pos) - 1] = kind;
589        }
590      }
591    
592      public ParseException generateParseException() {
593        jj_expentries.removeAllElements();
594        boolean[] la1tokens = new boolean[24];
595        for (int i = 0; i < 24; i++) {
596          la1tokens[i] = false;
597        }
598        if (jj_kind >= 0) {
599          la1tokens[jj_kind] = true;
600          jj_kind = -1;
601        }
602        for (int i = 0; i < 6; i++) {
603          if (jj_la1[i] == jj_gen) {
604            for (int j = 0; j < 32; j++) {
605              if ((jj_la1_0[i] & (1<<j)) != 0) {
606                la1tokens[j] = true;
607              }
608            }
609          }
610        }
611        for (int i = 0; i < 24; i++) {
612          if (la1tokens[i]) {
613            jj_expentry = new int[1];
614            jj_expentry[0] = i;
615            jj_expentries.addElement(jj_expentry);
616          }
617        }
618        jj_endpos = 0;
619        jj_rescan_token();
620        jj_add_error_token(0, 0);
621        int[][] exptokseq = new int[jj_expentries.size()][];
622        for (int i = 0; i < jj_expentries.size(); i++) {
623          exptokseq[i] = (int[])jj_expentries.elementAt(i);
624        }
625        return new ParseException(token, exptokseq, tokenImage);
626      }
627    
628      final public void enable_tracing() {
629      }
630    
631      final public void disable_tracing() {
632      }
633    
634      final private void jj_rescan_token() {
635        jj_rescan = true;
636        for (int i = 0; i < 2; i++) {
637        try {
638          JJCalls p = jj_2_rtns[i];
639          do {
640            if (p.gen > jj_gen) {
641              jj_la = p.arg; jj_lastpos = jj_scanpos = p.first;
642              switch (i) {
643                case 0: jj_3_1(); break;
644                case 1: jj_3_2(); break;
645              }
646            }
647            p = p.next;
648          } while (p != null);
649          } catch(LookaheadSuccess ls) { }
650        }
651        jj_rescan = false;
652      }
653    
654      final private void jj_save(int index, int xla) {
655        JJCalls p = jj_2_rtns[index];
656        while (p.gen > jj_gen) {
657          if (p.next == null) { p = p.next = new JJCalls(); break; }
658          p = p.next;
659        }
660        p.gen = jj_gen + xla - jj_la; p.first = token; p.arg = xla;
661      }
662    
663      static final class JJCalls {
664        int gen;
665        Token first;
666        int arg;
667        JJCalls next;
668      }
669    
670    }