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 }