1 /* 2 * [The "BSD license"] 3 * Copyright (c) 2010 Terence Parr 4 * All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 1. Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 2. Redistributions in binary form must reproduce the above copyright 12 * notice, this list of conditions and the following disclaimer in the 13 * documentation and/or other materials provided with the distribution. 14 * 3. The name of the author may not be used to endorse or promote products 15 * derived from this software without specific prior written permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 package org.antlr.test; 29 30 import org.antlr.Tool; 31 import org.antlr.analysis.DFA; 32 import org.antlr.analysis.DecisionProbe; 33 import org.antlr.codegen.CodeGenerator; 34 import org.antlr.misc.BitSet; 35 import org.antlr.tool.*; 36 import org.junit.Test; 37 38 import java.util.*; 39 40 public class TestDFAConversion extends BaseTest { 41 testA()42 @Test public void testA() throws Exception { 43 Grammar g = new Grammar( 44 "parser grammar t;\n"+ 45 "a : A C | B;"); 46 String expecting = 47 ".s0-A->:s1=>1\n" + 48 ".s0-B->:s2=>2\n"; 49 checkDecision(g, 1, expecting, null, null, null, null, 0); 50 } 51 testAB_or_AC()52 @Test public void testAB_or_AC() throws Exception { 53 Grammar g = new Grammar( 54 "parser grammar t;\n"+ 55 "a : A B | A C;"); 56 String expecting = 57 ".s0-A->.s1\n" + 58 ".s1-B->:s2=>1\n" + 59 ".s1-C->:s3=>2\n"; 60 checkDecision(g, 1, expecting, null, null, null, null, 0); 61 } 62 testAB_or_AC_k2()63 @Test public void testAB_or_AC_k2() throws Exception { 64 Grammar g = new Grammar( 65 "parser grammar t;\n" + 66 "options {k=2;}\n"+ 67 "a : A B | A C;"); 68 String expecting = 69 ".s0-A->.s1\n" + 70 ".s1-B->:s2=>1\n" + 71 ".s1-C->:s3=>2\n"; 72 checkDecision(g, 1, expecting, null, null, null, null, 0); 73 } 74 testAB_or_AC_k1()75 @Test public void testAB_or_AC_k1() throws Exception { 76 Grammar g = new Grammar( 77 "parser grammar t;\n" + 78 "options {k=1;}\n"+ 79 "a : A B | A C;"); 80 String expecting = 81 ".s0-A->:s1=>1\n"; 82 int[] unreachableAlts = new int[] {2}; 83 int[] nonDetAlts = new int[] {1,2}; 84 String ambigInput = "A" ; 85 int[] danglingAlts = new int[] {2}; 86 int numWarnings = 2; // ambig upon A 87 checkDecision(g, 1, expecting, unreachableAlts, 88 nonDetAlts, ambigInput, danglingAlts, numWarnings); 89 } 90 testselfRecurseNonDet()91 @Test public void testselfRecurseNonDet() throws Exception { 92 Grammar g = new Grammar( 93 "parser grammar t;\n"+ 94 "s : a ;\n" + 95 "a : A a X | A a Y;"); 96 List altsWithRecursion = Arrays.asList(new Object[] {1,2}); 97 assertNonLLStar(g, altsWithRecursion); 98 } 99 testRecursionOverflow()100 @Test public void testRecursionOverflow() throws Exception { 101 Grammar g = new Grammar( 102 "parser grammar t;\n"+ 103 "s : a Y | A A A A A X ;\n" + // force recursion past m=4 104 "a : A a | Q;"); 105 List expectedTargetRules = Arrays.asList(new Object[] {"a"}); 106 int expectedAlt = 1; 107 assertRecursionOverflow(g, expectedTargetRules, expectedAlt); 108 } 109 testRecursionOverflow2()110 @Test public void testRecursionOverflow2() throws Exception { 111 Grammar g = new Grammar( 112 "parser grammar t;\n"+ 113 "s : a Y | A+ X ;\n" + // force recursion past m=4 114 "a : A a | Q;"); 115 List expectedTargetRules = Arrays.asList(new Object[] {"a"}); 116 int expectedAlt = 1; 117 assertRecursionOverflow(g, expectedTargetRules, expectedAlt); 118 } 119 testRecursionOverflowWithPredOk()120 @Test public void testRecursionOverflowWithPredOk() throws Exception { 121 // overflows with k=*, but resolves with pred 122 // no warnings/errors 123 Grammar g = new Grammar( 124 "parser grammar t;\n"+ 125 "s : (a Y)=> a Y | A A A A A X ;\n" + // force recursion past m=4 126 "a : A a | Q;"); 127 String expecting = 128 ".s0-A->.s1\n" + 129 ".s0-Q&&{synpred1_t}?->:s11=>1\n" + 130 ".s1-A->.s2\n" + 131 ".s1-Q&&{synpred1_t}?->:s10=>1\n" + 132 ".s2-A->.s3\n" + 133 ".s2-Q&&{synpred1_t}?->:s9=>1\n" + 134 ".s3-A->.s4\n" + 135 ".s3-Q&&{synpred1_t}?->:s8=>1\n" + 136 ".s4-A->.s5\n" + 137 ".s4-Q&&{synpred1_t}?->:s6=>1\n" + 138 ".s5-{synpred1_t}?->:s6=>1\n" + 139 ".s5-{true}?->:s7=>2\n"; 140 int[] unreachableAlts = null; 141 int[] nonDetAlts = null; 142 String ambigInput = null; 143 int[] danglingAlts = null; 144 int numWarnings = 0; 145 checkDecision(g, 1, expecting, unreachableAlts, 146 nonDetAlts, ambigInput, danglingAlts, numWarnings); 147 } 148 testRecursionOverflowWithPredOk2()149 @Test public void testRecursionOverflowWithPredOk2() throws Exception { 150 // must predict Z w/o predicate 151 Grammar g = new Grammar( 152 "parser grammar t;\n"+ 153 "s : (a Y)=> a Y | A A A A A X | Z;\n" + // force recursion past m=4 154 "a : A a | Q;"); 155 String expecting = 156 ".s0-A->.s1\n" + 157 ".s0-Q&&{synpred1_t}?->:s11=>1\n" + 158 ".s0-Z->:s12=>3\n" + 159 ".s1-A->.s2\n" + 160 ".s1-Q&&{synpred1_t}?->:s10=>1\n" + 161 ".s2-A->.s3\n" + 162 ".s2-Q&&{synpred1_t}?->:s9=>1\n" + 163 ".s3-A->.s4\n" + 164 ".s3-Q&&{synpred1_t}?->:s8=>1\n" + 165 ".s4-A->.s5\n" + 166 ".s4-Q&&{synpred1_t}?->:s6=>1\n" + 167 ".s5-{synpred1_t}?->:s6=>1\n" + 168 ".s5-{true}?->:s7=>2\n"; 169 int[] unreachableAlts = null; 170 int[] nonDetAlts = null; 171 String ambigInput = null; 172 int[] danglingAlts = null; 173 int numWarnings = 0; 174 checkDecision(g, 1, expecting, unreachableAlts, 175 nonDetAlts, ambigInput, danglingAlts, numWarnings); 176 } 177 testCannotSeePastRecursion()178 @Test public void testCannotSeePastRecursion() throws Exception { 179 Grammar g = new Grammar( 180 "parser grammar t;\n"+ 181 "x : y X\n" + 182 " | y Y\n" + 183 " ;\n" + 184 "y : L y R\n" + 185 " | B\n" + 186 " ;"); 187 List altsWithRecursion = Arrays.asList(new Object[] {1,2}); 188 assertNonLLStar(g, altsWithRecursion); 189 } 190 testSynPredResolvesRecursion()191 @Test public void testSynPredResolvesRecursion() throws Exception { 192 Grammar g = new Grammar( 193 "parser grammar t;\n"+ 194 "x : (y X)=> y X\n" + 195 " | y Y\n" + 196 " ;\n" + 197 "y : L y R\n" + 198 " | B\n" + 199 " ;"); 200 String expecting = 201 ".s0-B->.s4\n" + 202 ".s0-L->.s1\n" + 203 ".s1-{synpred1_t}?->:s2=>1\n" + 204 ".s1-{true}?->:s3=>2\n" + 205 ".s4-{synpred1_t}?->:s2=>1\n" + 206 ".s4-{true}?->:s3=>2\n"; 207 int[] unreachableAlts = null; 208 int[] nonDetAlts = null; 209 String ambigInput = null; 210 int[] danglingAlts = null; 211 int numWarnings = 0; 212 checkDecision(g, 1, expecting, unreachableAlts, 213 nonDetAlts, ambigInput, danglingAlts, numWarnings); 214 } 215 testSynPredMissingInMiddle()216 @Test public void testSynPredMissingInMiddle() throws Exception { 217 Grammar g = new Grammar( 218 "parser grammar t;\n"+ 219 "x : (A)=> X\n" + 220 " | X\n" + // assume missing synpred is true also 221 " | (C)=> X" + 222 " ;\n"); 223 String expecting = 224 ".s0-X->.s1\n" + 225 ".s1-{synpred1_t}?->:s2=>1\n" + 226 ".s1-{synpred2_t}?->:s4=>3\n" + 227 ".s1-{true}?->:s3=>2\n"; 228 int[] unreachableAlts = null; 229 int[] nonDetAlts = null; 230 String ambigInput = null; 231 int[] danglingAlts = null; 232 int numWarnings = 0; 233 checkDecision(g, 1, expecting, unreachableAlts, 234 nonDetAlts, ambigInput, danglingAlts, numWarnings); 235 } 236 testAutoBacktrackAndPredMissingInMiddle()237 @Test public void testAutoBacktrackAndPredMissingInMiddle() throws Exception { 238 Grammar g = new Grammar( 239 "parser grammar t;\n" + 240 "options {backtrack=true;}\n"+ 241 "x : (A)=> X\n" + 242 " | X\n" + // assume missing synpred is true also 243 " | (C)=> X" + 244 " ;\n"); 245 String expecting = 246 ".s0-X->.s1\n" + 247 ".s1-{synpred1_t}?->:s2=>1\n" + // gen code should have this as (A)=> 248 ".s1-{synpred2_t}?->:s3=>2\n" + // gen code should have this as (X)=> 249 ".s1-{synpred3_t}?->:s4=>3\n"; // gen code should have this as (C)=> 250 int[] unreachableAlts = null; 251 int[] nonDetAlts = null; 252 String ambigInput = null; 253 int[] danglingAlts = null; 254 int numWarnings = 0; 255 checkDecision(g, 1, expecting, unreachableAlts, 256 nonDetAlts, ambigInput, danglingAlts, numWarnings); 257 } 258 testSemPredResolvesRecursion()259 @Test public void testSemPredResolvesRecursion() throws Exception { 260 Grammar g = new Grammar( 261 "parser grammar t;\n"+ 262 "x : {p}? y X\n" + 263 " | y Y\n" + 264 " ;\n" + 265 "y : L y R\n" + 266 " | B\n" + 267 " ;"); 268 String expecting = 269 ".s0-B->.s4\n" + 270 ".s0-L->.s1\n" + 271 ".s1-{p}?->:s2=>1\n" + 272 ".s1-{true}?->:s3=>2\n" + 273 ".s4-{p}?->:s2=>1\n" + 274 ".s4-{true}?->:s3=>2\n"; 275 int[] unreachableAlts = null; 276 int[] nonDetAlts = null; 277 String ambigInput = null; 278 int[] danglingAlts = null; 279 int numWarnings = 0; 280 checkDecision(g, 1, expecting, unreachableAlts, 281 nonDetAlts, ambigInput, danglingAlts, numWarnings); 282 } 283 testSemPredResolvesRecursion2()284 @Test public void testSemPredResolvesRecursion2() throws Exception { 285 Grammar g = new Grammar( 286 "parser grammar t;\n"+ 287 "x\n" + 288 "options {k=1;}\n" + 289 " : {p}? y X\n" + 290 " | y Y\n" + 291 " ;\n" + 292 "y : L y R\n" + 293 " | B\n" + 294 " ;"); 295 String expecting = 296 ".s0-B->.s4\n" + 297 ".s0-L->.s1\n" + 298 ".s1-{p}?->:s2=>1\n" + 299 ".s1-{true}?->:s3=>2\n" + 300 ".s4-{p}?->:s2=>1\n" + 301 ".s4-{true}?->:s3=>2\n"; 302 int[] unreachableAlts = null; 303 int[] nonDetAlts = null; 304 String ambigInput = null; 305 int[] danglingAlts = null; 306 int numWarnings = 0; 307 checkDecision(g, 1, expecting, unreachableAlts, 308 nonDetAlts, ambigInput, danglingAlts, numWarnings); 309 } 310 testSemPredResolvesRecursion3()311 @Test public void testSemPredResolvesRecursion3() throws Exception { 312 Grammar g = new Grammar( 313 "parser grammar t;\n"+ 314 "x\n" + 315 "options {k=2;}\n" + // just makes bigger DFA 316 " : {p}? y X\n" + 317 " | y Y\n" + 318 " ;\n" + 319 "y : L y R\n" + 320 " | B\n" + 321 " ;"); 322 String expecting = 323 ".s0-B->.s6\n" + 324 ".s0-L->.s1\n" + 325 ".s1-B->.s5\n" + 326 ".s1-L->.s2\n" + 327 ".s2-{p}?->:s3=>1\n" + 328 ".s2-{true}?->:s4=>2\n" + 329 ".s5-{p}?->:s3=>1\n" + 330 ".s5-{true}?->:s4=>2\n" + 331 ".s6-X->:s3=>1\n" + 332 ".s6-Y->:s4=>2\n"; 333 int[] unreachableAlts = null; 334 int[] nonDetAlts = null; 335 String ambigInput = null; 336 int[] danglingAlts = null; 337 int numWarnings = 0; 338 checkDecision(g, 1, expecting, unreachableAlts, 339 nonDetAlts, ambigInput, danglingAlts, numWarnings); 340 } 341 testSynPredResolvesRecursion2()342 @Test public void testSynPredResolvesRecursion2() throws Exception { 343 // k=* fails and it retries/succeeds with k=1 silently 344 // because of predicate 345 Grammar g = new Grammar( 346 "parser grammar t;\n"+ 347 "statement\n" + 348 " : (reference ASSIGN)=> reference ASSIGN expr\n" + 349 " | expr\n" + 350 " ;\n" + 351 "expr: reference\n" + 352 " | INT\n" + 353 " | FLOAT\n" + 354 " ;\n" + 355 "reference\n" + 356 " : ID L argument_list R\n" + 357 " ;\n" + 358 "argument_list\n" + 359 " : expr COMMA expr\n" + 360 " ;"); 361 String expecting = 362 ".s0-ID->.s1\n" + 363 ".s0-{FLOAT, INT}->:s3=>2\n" + 364 ".s1-{synpred1_t}?->:s2=>1\n" + 365 ".s1-{true}?->:s3=>2\n"; 366 int[] unreachableAlts = null; 367 int[] nonDetAlts = null; 368 String ambigInput = null; 369 int[] danglingAlts = null; 370 int numWarnings = 0; 371 checkDecision(g, 1, expecting, unreachableAlts, 372 nonDetAlts, ambigInput, danglingAlts, numWarnings); 373 } 374 testSynPredResolvesRecursion3()375 @Test public void testSynPredResolvesRecursion3() throws Exception { 376 // No errors with k=1; don't try k=* first 377 Grammar g = new Grammar( 378 "parser grammar t;\n"+ 379 "statement\n" + 380 "options {k=1;}\n" + 381 " : (reference ASSIGN)=> reference ASSIGN expr\n" + 382 " | expr\n" + 383 " ;\n" + 384 "expr: reference\n" + 385 " | INT\n" + 386 " | FLOAT\n" + 387 " ;\n" + 388 "reference\n" + 389 " : ID L argument_list R\n" + 390 " ;\n" + 391 "argument_list\n" + 392 " : expr COMMA expr\n" + 393 " ;"); 394 String expecting = 395 ".s0-ID->.s1\n" + 396 ".s0-{FLOAT, INT}->:s3=>2\n" + 397 ".s1-{synpred1_t}?->:s2=>1\n" + 398 ".s1-{true}?->:s3=>2\n"; 399 int[] unreachableAlts = null; 400 int[] nonDetAlts = null; 401 String ambigInput = null; 402 int[] danglingAlts = null; 403 int numWarnings = 0; 404 checkDecision(g, 1, expecting, unreachableAlts, 405 nonDetAlts, ambigInput, danglingAlts, numWarnings); 406 } 407 testSynPredResolvesRecursion4()408 @Test public void testSynPredResolvesRecursion4() throws Exception { 409 // No errors with k=2; don't try k=* first 410 // Should be ok like k=1 'except bigger DFA 411 Grammar g = new Grammar( 412 "parser grammar t;\n"+ 413 "statement\n" + 414 "options {k=2;}\n" + 415 " : (reference ASSIGN)=> reference ASSIGN expr\n" + 416 " | expr\n" + 417 " ;\n" + 418 "expr: reference\n" + 419 " | INT\n" + 420 " | FLOAT\n" + 421 " ;\n" + 422 "reference\n" + 423 " : ID L argument_list R\n" + 424 " ;\n" + 425 "argument_list\n" + 426 " : expr COMMA expr\n" + 427 " ;"); 428 String expecting = 429 ".s0-ID->.s1\n" + 430 ".s0-{FLOAT, INT}->:s4=>2\n" + 431 ".s1-L->.s2\n" + 432 ".s2-{synpred1_t}?->:s3=>1\n" + 433 ".s2-{true}?->:s4=>2\n"; 434 int[] unreachableAlts = null; 435 int[] nonDetAlts = null; 436 String ambigInput = null; 437 int[] danglingAlts = null; 438 int numWarnings = 0; 439 checkDecision(g, 1, expecting, unreachableAlts, 440 nonDetAlts, ambigInput, danglingAlts, numWarnings); 441 } 442 testSynPredResolvesRecursionInLexer()443 @Test public void testSynPredResolvesRecursionInLexer() throws Exception { 444 Grammar g = new Grammar( 445 "lexer grammar t;\n"+ 446 "A : (B ';')=> B ';'\n" + 447 " | B '.'\n" + 448 " ;\n" + 449 "fragment\n" + 450 "B : '(' B ')'\n" + 451 " | 'x'\n" + 452 " ;\n"); 453 String expecting = 454 ".s0-'('->.s1\n" + 455 ".s0-'x'->.s4\n" + 456 ".s1-{synpred1_t}?->:s2=>1\n" + 457 ".s1-{true}?->:s3=>2\n" + 458 ".s4-{synpred1_t}?->:s2=>1\n" + 459 ".s4-{true}?->:s3=>2\n"; 460 int[] unreachableAlts = null; 461 int[] nonDetAlts = null; 462 String ambigInput = null; 463 int[] danglingAlts = null; 464 int numWarnings = 0; 465 checkDecision(g, 1, expecting, unreachableAlts, 466 nonDetAlts, ambigInput, danglingAlts, numWarnings); 467 } 468 testAutoBacktrackResolvesRecursionInLexer()469 @Test public void testAutoBacktrackResolvesRecursionInLexer() throws Exception { 470 Grammar g = new Grammar( 471 "lexer grammar t;\n"+ 472 "options {backtrack=true;}\n"+ 473 "A : B ';'\n" + 474 " | B '.'\n" + 475 " ;\n" + 476 "fragment\n" + 477 "B : '(' B ')'\n" + 478 " | 'x'\n" + 479 " ;\n"); 480 String expecting = 481 ".s0-'('->.s1\n" + 482 ".s0-'x'->.s4\n" + 483 ".s1-{synpred1_t}?->:s2=>1\n" + 484 ".s1-{true}?->:s3=>2\n" + 485 ".s4-{synpred1_t}?->:s2=>1\n" + 486 ".s4-{true}?->:s3=>2\n"; 487 int[] unreachableAlts = null; 488 int[] nonDetAlts = null; 489 String ambigInput = null; 490 int[] danglingAlts = null; 491 int numWarnings = 0; 492 checkDecision(g, 1, expecting, unreachableAlts, 493 nonDetAlts, ambigInput, danglingAlts, numWarnings); 494 } 495 testAutoBacktrackResolvesRecursion()496 @Test public void testAutoBacktrackResolvesRecursion() throws Exception { 497 Grammar g = new Grammar( 498 "parser grammar t;\n" + 499 "options {backtrack=true;}\n"+ 500 "x : y X\n" + 501 " | y Y\n" + 502 " ;\n" + 503 "y : L y R\n" + 504 " | B\n" + 505 " ;"); 506 String expecting = 507 ".s0-B->.s4\n" + 508 ".s0-L->.s1\n" + 509 ".s1-{synpred1_t}?->:s2=>1\n" + 510 ".s1-{true}?->:s3=>2\n" + 511 ".s4-{synpred1_t}?->:s2=>1\n" + 512 ".s4-{true}?->:s3=>2\n"; 513 int[] unreachableAlts = null; 514 int[] nonDetAlts = null; 515 String ambigInput = null; 516 int[] danglingAlts = null; 517 int numWarnings = 0; 518 checkDecision(g, 1, expecting, unreachableAlts, 519 nonDetAlts, ambigInput, danglingAlts, numWarnings); 520 } 521 testselfRecurseNonDet2()522 @Test public void testselfRecurseNonDet2() throws Exception { 523 Grammar g = new Grammar( 524 "parser grammar t;\n"+ 525 "s : a ;\n" + 526 "a : P a P | P;"); 527 // nondeterministic from left edge 528 String expecting = 529 ".s0-P->.s1\n" + 530 ".s1-EOF->:s3=>2\n"+ 531 ".s1-P->:s2=>1\n"; 532 int[] unreachableAlts = null; 533 int[] nonDetAlts = new int[] {1,2}; 534 String ambigInput = "P P"; 535 int[] danglingAlts = null; 536 int numWarnings = 1; 537 checkDecision(g, 1, expecting, unreachableAlts, 538 nonDetAlts, ambigInput, danglingAlts, numWarnings); 539 } 540 testIndirectRecursionLoop()541 @Test public void testIndirectRecursionLoop() throws Exception { 542 Grammar g = new Grammar( 543 "parser grammar t;\n"+ 544 "s : a ;\n" + 545 "a : b X ;\n"+ 546 "b : a B ;\n"); 547 548 DecisionProbe.verbose=true; // make sure we get all error info 549 ErrorQueue equeue = new ErrorQueue(); 550 ErrorManager.setErrorListener(equeue); 551 552 Set<Rule> leftRecursive = g.getLeftRecursiveRules(); 553 Set expectedRules = 554 new HashSet() {{add("a"); add("b");}}; 555 assertEquals(expectedRules, ruleNames(leftRecursive)); 556 557 assertEquals(1, equeue.errors.size()); 558 Message msg = (Message)equeue.errors.get(0); 559 assertTrue("expecting left recursion cycles; found "+msg.getClass().getName(), 560 msg instanceof LeftRecursionCyclesMessage); 561 LeftRecursionCyclesMessage cyclesMsg = (LeftRecursionCyclesMessage)msg; 562 563 // cycle of [a, b] 564 Collection result = cyclesMsg.cycles; 565 Set expecting = new HashSet() {{add("a"); add("b");}}; 566 assertEquals(expecting, ruleNames2(result)); 567 } 568 testIndirectRecursionLoop2()569 @Test public void testIndirectRecursionLoop2() throws Exception { 570 Grammar g = new Grammar( 571 "parser grammar t;\n"+ 572 "s : a ;\n" + 573 "a : i b X ;\n"+ // should see through i 574 "b : a B ;\n" + 575 "i : ;\n"); 576 577 DecisionProbe.verbose=true; // make sure we get all error info 578 ErrorQueue equeue = new ErrorQueue(); 579 ErrorManager.setErrorListener(equeue); 580 581 Set leftRecursive = g.getLeftRecursiveRules(); 582 Set expectedRules = 583 new HashSet() {{add("a"); add("b");}}; 584 assertEquals(expectedRules, ruleNames(leftRecursive)); 585 586 assertEquals(1, equeue.errors.size()); 587 Message msg = (Message)equeue.errors.get(0); 588 assertTrue("expecting left recursion cycles; found "+msg.getClass().getName(), 589 msg instanceof LeftRecursionCyclesMessage); 590 LeftRecursionCyclesMessage cyclesMsg = (LeftRecursionCyclesMessage)msg; 591 592 // cycle of [a, b] 593 Collection result = cyclesMsg.cycles; 594 Set expecting = new HashSet() {{add("a"); add("b");}}; 595 assertEquals(expecting, ruleNames2(result)); 596 } 597 testIndirectRecursionLoop3()598 @Test public void testIndirectRecursionLoop3() throws Exception { 599 Grammar g = new Grammar( 600 "parser grammar t;\n"+ 601 "s : a ;\n" + 602 "a : i b X ;\n"+ // should see through i 603 "b : a B ;\n" + 604 "i : ;\n" + 605 "d : e ;\n" + 606 "e : d ;\n"); 607 608 DecisionProbe.verbose=true; // make sure we get all error info 609 ErrorQueue equeue = new ErrorQueue(); 610 ErrorManager.setErrorListener(equeue); 611 612 Set leftRecursive = g.getLeftRecursiveRules(); 613 Set expectedRules = 614 new HashSet() {{add("a"); add("b"); add("e"); add("d");}}; 615 assertEquals(expectedRules, ruleNames(leftRecursive)); 616 617 assertEquals(1, equeue.errors.size()); 618 Message msg = (Message)equeue.errors.get(0); 619 assertTrue("expecting left recursion cycles; found "+msg.getClass().getName(), 620 msg instanceof LeftRecursionCyclesMessage); 621 LeftRecursionCyclesMessage cyclesMsg = (LeftRecursionCyclesMessage)msg; 622 623 // cycle of [a, b] 624 Collection result = cyclesMsg.cycles; 625 Set expecting = new HashSet() {{add("a"); add("b"); add("d"); add("e");}}; 626 assertEquals(expecting, ruleNames2(result)); 627 } 628 testifThenElse()629 @Test public void testifThenElse() throws Exception { 630 Grammar g = new Grammar( 631 "parser grammar t;\n"+ 632 "s : IF s (E s)? | B;\n" + 633 "slist: s SEMI ;"); 634 String expecting = 635 ".s0-E->:s1=>1\n" + 636 ".s0-SEMI->:s2=>2\n"; 637 int[] unreachableAlts = null; 638 int[] nonDetAlts = new int[] {1,2}; 639 String ambigInput = "E"; 640 int[] danglingAlts = null; 641 int numWarnings = 1; 642 checkDecision(g, 1, expecting, unreachableAlts, 643 nonDetAlts, ambigInput, danglingAlts, numWarnings); 644 expecting = 645 ".s0-B->:s2=>2\n" + 646 ".s0-IF->:s1=>1\n"; 647 checkDecision(g, 2, expecting, null, null, null, null, 0); 648 } 649 testifThenElseChecksStackSuffixConflict()650 @Test public void testifThenElseChecksStackSuffixConflict() throws Exception { 651 // if you don't check stack soon enough, this finds E B not just E 652 // as ambig input 653 Grammar g = new Grammar( 654 "parser grammar t;\n"+ 655 "slist: s SEMI ;\n"+ 656 "s : IF s el | B;\n" + 657 "el: (E s)? ;\n"); 658 String expecting = 659 ".s0-E->:s1=>1\n" + 660 ".s0-SEMI->:s2=>2\n"; 661 int[] unreachableAlts = null; 662 int[] nonDetAlts = new int[] {1,2}; 663 String ambigInput = "E"; 664 int[] danglingAlts = null; 665 int numWarnings = 1; 666 checkDecision(g, 2, expecting, unreachableAlts, 667 nonDetAlts, ambigInput, danglingAlts, numWarnings); 668 expecting = 669 ".s0-B->:s2=>2\n" + 670 ".s0-IF->:s1=>1\n"; 671 checkDecision(g, 1, expecting, null, null, null, null, 0); 672 } 673 674 @Test testInvokeRule()675 public void testInvokeRule() throws Exception { 676 Grammar g = new Grammar( 677 "parser grammar t;\n"+ 678 "a : b A\n" + 679 " | b B\n" + 680 " | C\n" + 681 " ;\n" + 682 "b : X\n" + 683 " ;\n"); 684 String expecting = 685 ".s0-C->:s4=>3\n" + 686 ".s0-X->.s1\n" + 687 ".s1-A->:s2=>1\n" + 688 ".s1-B->:s3=>2\n"; 689 checkDecision(g, 1, expecting, null, null, null, null, 0); 690 } 691 692 @Test testDoubleInvokeRuleLeftEdge()693 public void testDoubleInvokeRuleLeftEdge() throws Exception { 694 Grammar g = new Grammar( 695 "parser grammar t;\n"+ 696 "a : b X\n" + 697 " | b Y\n" + 698 " ;\n" + 699 "b : c B\n" + 700 " | c\n" + 701 " ;\n" + 702 "c : C ;\n"); 703 String expecting = 704 ".s0-C->.s1\n" + 705 ".s1-B->.s2\n" + 706 ".s1-X->:s3=>1\n" + 707 ".s1-Y->:s4=>2\n" + 708 ".s2-X->:s3=>1\n" + 709 ".s2-Y->:s4=>2\n"; 710 checkDecision(g, 1, expecting, null, null, null, null, 0); 711 expecting = 712 ".s0-C->.s1\n" + 713 ".s1-B->:s2=>1\n" + 714 ".s1-X..Y->:s3=>2\n"; 715 checkDecision(g, 2, expecting, null, null, null, null, 0); 716 } 717 testimmediateTailRecursion()718 @Test public void testimmediateTailRecursion() throws Exception { 719 Grammar g = new Grammar( 720 "parser grammar t;\n"+ 721 "s : a ;\n" + 722 "a : A a | A B;"); 723 String expecting = 724 ".s0-A->.s1\n" + 725 ".s1-A->:s3=>1\n" + 726 ".s1-B->:s2=>2\n"; 727 checkDecision(g, 1, expecting, null, null, null, null, 0); 728 } 729 730 @Test testAStar_immediateTailRecursion()731 public void testAStar_immediateTailRecursion() throws Exception { 732 Grammar g = new Grammar( 733 "parser grammar t;\n"+ 734 "s : a ;\n" + 735 "a : A a | ;"); 736 String expecting = 737 ".s0-A->:s1=>1\n" + 738 ".s0-EOF->:s2=>2\n"; 739 int[] unreachableAlts = null; // without 740 int[] nonDetAlts = null; 741 String ambigInput = null; 742 int[] danglingAlts = null; 743 int numWarnings = 0; 744 checkDecision(g, 1, expecting, unreachableAlts, 745 nonDetAlts, ambigInput, danglingAlts, numWarnings); 746 } 747 testNoStartRule()748 @Test public void testNoStartRule() throws Exception { 749 ErrorQueue equeue = new ErrorQueue(); 750 ErrorManager.setErrorListener(equeue); 751 Grammar g = new Grammar( 752 "parser grammar t;\n"+ 753 "a : A a | X;"); // single rule 'a' refers to itself; no start rule 754 755 Tool antlr = newTool(); 756 antlr.setOutputDirectory(null); // write to /dev/null 757 CodeGenerator generator = new CodeGenerator(antlr, g, "Java"); 758 g.setCodeGenerator(generator); 759 generator.genRecognizer(); 760 761 Message msg = (Message)equeue.warnings.get(0); 762 assertTrue("expecting no start rules; found "+msg.getClass().getName(), 763 msg instanceof GrammarSemanticsMessage); 764 } 765 766 @Test testAStar_immediateTailRecursion2()767 public void testAStar_immediateTailRecursion2() throws Exception { 768 Grammar g = new Grammar( 769 "parser grammar t;\n"+ 770 "s : a ;\n" + 771 "a : A a | A ;"); 772 String expecting = 773 ".s0-A->.s1\n" + 774 ".s1-A->:s2=>1\n" + 775 ".s1-EOF->:s3=>2\n"; 776 int[] unreachableAlts = null; 777 int[] nonDetAlts = null; 778 String ambigInput = null; 779 int[] danglingAlts = null; 780 int numWarnings = 0; 781 checkDecision(g, 1, expecting, unreachableAlts, 782 nonDetAlts, ambigInput, danglingAlts, numWarnings); 783 } 784 testimmediateLeftRecursion()785 @Test public void testimmediateLeftRecursion() throws Exception { 786 Grammar g = new Grammar( 787 "parser grammar t;\n"+ 788 "s : a ;\n" + 789 "a : a A | B;"); 790 Set leftRecursive = g.getLeftRecursiveRules(); 791 Set expectedRules = new HashSet() {{add("a");}}; 792 assertEquals(expectedRules, ruleNames(leftRecursive)); 793 } 794 testIndirectLeftRecursion()795 @Test public void testIndirectLeftRecursion() throws Exception { 796 Grammar g = new Grammar( 797 "parser grammar t;\n"+ 798 "s : a ;\n" + 799 "a : b | A ;\n" + 800 "b : c ;\n" + 801 "c : a | C ;\n"); 802 Set leftRecursive = g.getLeftRecursiveRules(); 803 Set expectedRules = new HashSet() {{add("a"); add("b"); add("c");}}; 804 assertEquals(expectedRules, ruleNames(leftRecursive)); 805 } 806 testLeftRecursionInMultipleCycles()807 @Test public void testLeftRecursionInMultipleCycles() throws Exception { 808 Grammar g = new Grammar( 809 "parser grammar t;\n"+ 810 "s : a x ;\n" + 811 "a : b | A ;\n" + 812 "b : c ;\n" + 813 "c : a | C ;\n" + 814 "x : y | X ;\n" + 815 "y : x ;\n"); 816 Set leftRecursive = g.getLeftRecursiveRules(); 817 Set expectedRules = 818 new HashSet() {{add("a"); add("b"); add("c"); add("x"); add("y");}}; 819 assertEquals(expectedRules, ruleNames(leftRecursive)); 820 } 821 testCycleInsideRuleDoesNotForceInfiniteRecursion()822 @Test public void testCycleInsideRuleDoesNotForceInfiniteRecursion() throws Exception { 823 Grammar g = new Grammar( 824 "parser grammar t;\n"+ 825 "s : a ;\n" + 826 "a : (A|)+ B;\n"); 827 // before I added a visitedStates thing, it was possible to loop 828 // forever inside of a rule if there was an epsilon loop. 829 Set leftRecursive = g.getLeftRecursiveRules(); 830 Set expectedRules = new HashSet(); 831 assertEquals(expectedRules, leftRecursive); 832 } 833 834 // L O O P S 835 testAStar()836 @Test public void testAStar() throws Exception { 837 Grammar g = new Grammar( 838 "parser grammar t;\n"+ 839 "a : ( A )* ;"); 840 String expecting = 841 ".s0-A->:s1=>1\n" + 842 ".s0-EOF->:s2=>2\n"; 843 checkDecision(g, 1, expecting, null, null, null, null, 0); 844 } 845 testAorBorCStar()846 @Test public void testAorBorCStar() throws Exception { 847 Grammar g = new Grammar( 848 "parser grammar t;\n"+ 849 "a : ( A | B | C )* ;"); 850 String expecting = 851 ".s0-A..C->:s1=>1\n" + 852 ".s0-EOF->:s2=>2\n"; 853 checkDecision(g, 1, expecting, null, null, null, null, 0); 854 } 855 testAPlus()856 @Test public void testAPlus() throws Exception { 857 Grammar g = new Grammar( 858 "parser grammar t;\n"+ 859 "a : ( A )+ ;"); 860 String expecting = 861 ".s0-A->:s1=>1\n" + 862 ".s0-EOF->:s2=>2\n"; 863 checkDecision(g, 1, expecting, null, null, null, null, 0); // loopback decision 864 } 865 testAPlusNonGreedyWhenDeterministic()866 @Test public void testAPlusNonGreedyWhenDeterministic() throws Exception { 867 Grammar g = new Grammar( 868 "parser grammar t;\n"+ 869 "a : (options {greedy=false;}:A)+ ;\n"); 870 // should look the same as A+ since no ambiguity 871 String expecting = 872 ".s0-A->:s1=>1\n" + 873 ".s0-EOF->:s2=>2\n"; 874 checkDecision(g, 1, expecting, null, null, null, null, 0); 875 } 876 testAPlusNonGreedyWhenNonDeterministic()877 @Test public void testAPlusNonGreedyWhenNonDeterministic() throws Exception { 878 Grammar g = new Grammar( 879 "parser grammar t;\n"+ 880 "a : (options {greedy=false;}:A)+ A+ ;\n"); 881 // should look the same as A+ since no ambiguity 882 String expecting = 883 ".s0-A->:s1=>2\n"; // always chooses to exit 884 int[] unreachableAlts = new int[] {1}; 885 int[] nonDetAlts = new int[] {1,2}; 886 String ambigInput = "A"; 887 int[] danglingAlts = null; 888 int numWarnings = 2; 889 checkDecision(g, 1, expecting, unreachableAlts, 890 nonDetAlts, ambigInput, danglingAlts, numWarnings); 891 } 892 testAPlusGreedyWhenNonDeterministic()893 @Test public void testAPlusGreedyWhenNonDeterministic() throws Exception { 894 Grammar g = new Grammar( 895 "parser grammar t;\n"+ 896 "a : (options {greedy=true;}:A)+ A+ ;\n"); 897 // should look the same as A+ since no ambiguity 898 String expecting = 899 ".s0-A->:s1=>1\n"; // always chooses to enter loop upon A 900 // turns off 1 of warnings. A can never exit loop now 901 int[] unreachableAlts = new int[] {2}; 902 int[] nonDetAlts = null; 903 String ambigInput = null; 904 int[] danglingAlts = null; 905 int numWarnings = 1; 906 checkDecision(g, 1, expecting, unreachableAlts, 907 nonDetAlts, ambigInput, danglingAlts, numWarnings); 908 } 909 testAorBorCPlus()910 @Test public void testAorBorCPlus() throws Exception { 911 Grammar g = new Grammar( 912 "parser grammar t;\n"+ 913 "a : ( A | B | C )+ ;"); 914 String expecting = 915 ".s0-A..C->:s1=>1\n" + 916 ".s0-EOF->:s2=>2\n"; 917 checkDecision(g, 1, expecting, null, null, null, null, 0); 918 } 919 testAOptional()920 @Test public void testAOptional() throws Exception { 921 Grammar g = new Grammar( 922 "parser grammar t;\n"+ 923 "a : ( A )? B ;"); 924 String expecting = 925 ".s0-A->:s1=>1\n" + 926 ".s0-B->:s2=>2\n"; 927 checkDecision(g, 1, expecting, null, null, null, null, 0); // loopback decision 928 } 929 testAorBorCOptional()930 @Test public void testAorBorCOptional() throws Exception { 931 Grammar g = new Grammar( 932 "parser grammar t;\n"+ 933 "a : ( A | B | C )? Z ;"); 934 String expecting = 935 ".s0-A..C->:s1=>1\n" + 936 ".s0-Z->:s2=>2\n"; 937 checkDecision(g, 1, expecting, null, null, null, null, 0); // loopback decision 938 } 939 940 // A R B I T R A R Y L O O K A H E A D 941 942 @Test testAStarBOrAStarC()943 public void testAStarBOrAStarC() throws Exception { 944 Grammar g = new Grammar( 945 "parser grammar t;\n"+ 946 "a : (A)* B | (A)* C;"); 947 String expecting = 948 ".s0-A->:s1=>1\n" + 949 ".s0-B->:s2=>2\n"; 950 checkDecision(g, 1, expecting, null, null, null, null, 0); // loopback 951 expecting = 952 ".s0-A->:s1=>1\n" + 953 ".s0-C->:s2=>2\n"; 954 checkDecision(g, 2, expecting, null, null, null, null, 0); // loopback 955 expecting = 956 ".s0-A->.s1\n" + 957 ".s0-B->:s2=>1\n" + 958 ".s0-C->:s3=>2\n" + 959 ".s1-A->.s1\n" + 960 ".s1-B->:s2=>1\n" + 961 ".s1-C->:s3=>2\n"; 962 checkDecision(g, 3, expecting, null, null, null, null, 0); // rule block 963 } 964 965 @Test testAStarBOrAPlusC()966 public void testAStarBOrAPlusC() throws Exception { 967 Grammar g = new Grammar( 968 "parser grammar t;\n"+ 969 "a : (A)* B | (A)+ C;"); 970 String expecting = 971 ".s0-A->:s1=>1\n" + 972 ".s0-B->:s2=>2\n"; 973 checkDecision(g, 1, expecting, null, null, null, null, 0); // loopback 974 expecting = 975 ".s0-A->:s1=>1\n" + 976 ".s0-C->:s2=>2\n"; 977 checkDecision(g, 2, expecting, null, null, null, null, 0); // loopback 978 expecting = 979 ".s0-A->.s1\n" + 980 ".s0-B->:s2=>1\n" + 981 ".s1-A->.s1\n" + 982 ".s1-B->:s2=>1\n" + 983 ".s1-C->:s3=>2\n"; 984 checkDecision(g, 3, expecting, null, null, null, null, 0); // rule block 985 } 986 987 988 @Test testAOrBPlusOrAPlus()989 public void testAOrBPlusOrAPlus() throws Exception { 990 Grammar g = new Grammar( 991 "parser grammar t;\n"+ 992 "a : (A|B)* X | (A)+ Y;"); 993 String expecting = 994 ".s0-A..B->:s1=>1\n" + 995 ".s0-X->:s2=>2\n"; 996 checkDecision(g, 1, expecting, null, null, null, null, 0); // loopback (A|B)* 997 expecting = 998 ".s0-A->:s1=>1\n" + 999 ".s0-Y->:s2=>2\n"; 1000 checkDecision(g, 2, expecting, null, null, null, null, 0); // loopback (A)+ 1001 expecting = 1002 ".s0-A->.s1\n" + 1003 ".s0-B..X->:s2=>1\n" + 1004 ".s1-A->.s1\n" + 1005 ".s1-B..X->:s2=>1\n" + 1006 ".s1-Y->:s3=>2\n"; 1007 checkDecision(g, 3, expecting, null, null, null, null, 0); // rule 1008 } 1009 testLoopbackAndExit()1010 @Test public void testLoopbackAndExit() throws Exception { 1011 Grammar g = new Grammar( 1012 "parser grammar t;\n"+ 1013 "a : (A|B)+ B;"); 1014 String expecting = 1015 ".s0-A->:s3=>1\n" + 1016 ".s0-B->.s1\n" + 1017 ".s1-A..B->:s3=>1\n" + 1018 ".s1-EOF->:s2=>2\n"; // sees A|B as a set 1019 checkDecision(g, 1, expecting, null, null, null, null, 0); 1020 } 1021 testOptionalAltAndBypass()1022 @Test public void testOptionalAltAndBypass() throws Exception { 1023 Grammar g = new Grammar( 1024 "parser grammar t;\n"+ 1025 "a : (A|B)? B;"); 1026 String expecting = 1027 ".s0-A->:s2=>1\n" + 1028 ".s0-B->.s1\n" + 1029 ".s1-B->:s2=>1\n" + 1030 ".s1-EOF->:s3=>2\n"; 1031 checkDecision(g, 1, expecting, null, null, null, null, 0); 1032 } 1033 1034 // R E S O L V E S Y N C O N F L I C T S 1035 testResolveLL1ByChoosingFirst()1036 @Test public void testResolveLL1ByChoosingFirst() throws Exception { 1037 Grammar g = new Grammar( 1038 "parser grammar t;\n"+ 1039 "a : A C | A C;"); 1040 String expecting = 1041 ".s0-A->.s1\n" + 1042 ".s1-C->:s2=>1\n"; 1043 int[] unreachableAlts = new int[] {2}; 1044 int[] nonDetAlts = new int[] {1,2}; 1045 String ambigInput = "A C"; 1046 int[] danglingAlts = null; 1047 int numWarnings = 2; 1048 checkDecision(g, 1, expecting, unreachableAlts, 1049 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1050 } 1051 testResolveLL2ByChoosingFirst()1052 @Test public void testResolveLL2ByChoosingFirst() throws Exception { 1053 Grammar g = new Grammar( 1054 "parser grammar t;\n"+ 1055 "a : A B | A B;"); 1056 String expecting = 1057 ".s0-A->.s1\n" + 1058 ".s1-B->:s2=>1\n"; 1059 int[] unreachableAlts = new int[] {2}; 1060 int[] nonDetAlts = new int[] {1,2}; 1061 String ambigInput = "A B"; 1062 int[] danglingAlts = null; 1063 int numWarnings = 2; 1064 checkDecision(g, 1, expecting, unreachableAlts, 1065 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1066 } 1067 testResolveLL2MixAlt()1068 @Test public void testResolveLL2MixAlt() throws Exception { 1069 Grammar g = new Grammar( 1070 "parser grammar t;\n"+ 1071 "a : A B | A C | A B | Z;"); 1072 String expecting = 1073 ".s0-A->.s1\n" + 1074 ".s0-Z->:s4=>4\n" + 1075 ".s1-B->:s2=>1\n" + 1076 ".s1-C->:s3=>2\n"; 1077 int[] unreachableAlts = new int[] {3}; 1078 int[] nonDetAlts = new int[] {1,3}; 1079 String ambigInput = "A B"; 1080 int[] danglingAlts = null; 1081 int numWarnings = 2; 1082 checkDecision(g, 1, expecting, unreachableAlts, 1083 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1084 } 1085 testIndirectIFThenElseStyleAmbig()1086 @Test public void testIndirectIFThenElseStyleAmbig() throws Exception { 1087 // the (c)+ loopback is ambig because it could match "CASE" 1088 // by entering the loop or by falling out and ignoring (s)* 1089 // back falling back into (cg)* loop which stats over and 1090 // calls cg again. Either choice allows it to get back to 1091 // the same node. The software catches it as: 1092 // "avoid infinite closure computation emanating from alt 1 1093 // of ():27|2|[8 $]" where state 27 is the first alt of (c)+ 1094 // and 8 is the first alt of the (cg)* loop. 1095 Grammar g = new Grammar( 1096 "parser grammar t;\n" + 1097 "s : stat ;\n" + 1098 "stat : LCURLY ( cg )* RCURLY | E SEMI ;\n" + 1099 "cg : (c)+ (stat)* ;\n" + 1100 "c : CASE E ;\n"); 1101 String expecting = 1102 ".s0-CASE->:s2=>1\n" + 1103 ".s0-E..RCURLY->:s1=>2\n"; 1104 int[] unreachableAlts = null; 1105 int[] nonDetAlts = new int[] {1,2}; 1106 String ambigInput = "CASE"; 1107 int[] danglingAlts = null; 1108 int numWarnings = 1; 1109 checkDecision(g, 3, expecting, unreachableAlts, 1110 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1111 } 1112 1113 // S E T S 1114 testComplement()1115 @Test public void testComplement() throws Exception { 1116 Grammar g = new Grammar( 1117 "parser grammar t;\n"+ 1118 "a : ~(A | B | C) | C {;} ;\n" + 1119 "b : X Y Z ;"); 1120 String expecting = 1121 ".s0-C->:s2=>2\n" + 1122 ".s0-X..Z->:s1=>1\n"; 1123 checkDecision(g, 1, expecting, null, null, null, null, 0); 1124 } 1125 testComplementToken()1126 @Test public void testComplementToken() throws Exception { 1127 Grammar g = new Grammar( 1128 "parser grammar t;\n"+ 1129 "a : ~C | C {;} ;\n" + 1130 "b : X Y Z ;"); 1131 String expecting = 1132 ".s0-C->:s2=>2\n" + 1133 ".s0-X..Z->:s1=>1\n"; 1134 checkDecision(g, 1, expecting, null, null, null, null, 0); 1135 } 1136 testComplementChar()1137 @Test public void testComplementChar() throws Exception { 1138 Grammar g = new Grammar( 1139 "lexer grammar t;\n"+ 1140 "A : ~'x' | 'x' {;} ;\n"); 1141 String expecting = 1142 ".s0-'x'->:s2=>2\n" + 1143 ".s0-{'\\u0000'..'w', 'y'..'\\uFFFF'}->:s1=>1\n"; 1144 checkDecision(g, 1, expecting, null, null, null, null, 0); 1145 } 1146 testComplementCharSet()1147 @Test public void testComplementCharSet() throws Exception { 1148 Grammar g = new Grammar( 1149 "lexer grammar t;\n"+ 1150 "A : ~(' '|'\t'|'x'|'y') | 'x';\n" + // collapse into single set 1151 "B : 'y' ;"); 1152 String expecting = 1153 ".s0-'y'->:s2=>2\n" + 1154 ".s0-{'\\u0000'..'\\b', '\\n'..'\\u001F', '!'..'x', 'z'..'\\uFFFF'}->:s1=>1\n"; 1155 checkDecision(g, 1, expecting, null, null, null, null, 0); 1156 } 1157 testNoSetCollapseWithActions()1158 @Test public void testNoSetCollapseWithActions() throws Exception { 1159 Grammar g = new Grammar( 1160 "parser grammar t;\n"+ 1161 "a : (A | B {foo}) | C;"); 1162 String expecting = 1163 ".s0-A->:s1=>1\n" + 1164 ".s0-B->:s2=>2\n"; 1165 checkDecision(g, 1, expecting, null, null, null, null, 0); 1166 } 1167 testRuleAltsSetCollapse()1168 @Test public void testRuleAltsSetCollapse() throws Exception { 1169 Grammar g = new Grammar( 1170 "parser grammar t;\n"+ 1171 "a : A | B | C ;" 1172 ); 1173 String expecting = // still looks like block 1174 "(grammar t (rule a ARG RET scope (BLOCK (ALT A <end-of-alt>) (ALT B <end-of-alt>) (ALT C <end-of-alt>) <end-of-block>) <end-of-rule>))"; 1175 assertEquals(expecting, g.getGrammarTree().toStringTree()); 1176 } 1177 testTokensRuleAltsDoNotCollapse()1178 @Test public void testTokensRuleAltsDoNotCollapse() throws Exception { 1179 Grammar g = new Grammar( 1180 "lexer grammar t;\n"+ 1181 "A : 'a';" + 1182 "B : 'b';\n" 1183 ); 1184 String expecting = 1185 ".s0-'a'->:s1=>1\n" + 1186 ".s0-'b'->:s2=>2\n"; 1187 checkDecision(g, 1, expecting, null, null, null, null, 0); 1188 } 1189 testMultipleSequenceCollision()1190 @Test public void testMultipleSequenceCollision() throws Exception { 1191 Grammar g = new Grammar( 1192 "parser grammar t;\n" + 1193 "a : (A{;}|B)\n" + 1194 " | (A{;}|B)\n" + 1195 " | A\n" + 1196 " ;"); 1197 String expecting = 1198 ".s0-A->:s1=>1\n" + 1199 ".s0-B->:s2=>1\n"; // not optimized because states are nondet 1200 int[] unreachableAlts = new int[] {2,3}; 1201 int[] nonDetAlts = new int[] {1,2,3}; 1202 String ambigInput = "A"; 1203 int[] danglingAlts = null; 1204 int numWarnings = 3; 1205 checkDecision(g, 3, expecting, unreachableAlts, 1206 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1207 /* There are 2 nondet errors, but the checkDecision only checks first one :( 1208 The "B" conflicting input is not checked except by virtue of the 1209 result DFA. 1210 <string>:2:5: Decision can match input such as "A" using multiple alternatives: 1211 alt 1 via NFA path 7,2,3 1212 alt 2 via NFA path 14,9,10 1213 alt 3 via NFA path 16,17 1214 As a result, alternative(s) 2,3 were disabled for that input, 1215 <string>:2:5: Decision can match input such as "B" using multiple alternatives: 1216 alt 1 via NFA path 7,8,4,5 1217 alt 2 via NFA path 14,15,11,12 1218 As a result, alternative(s) 2 were disabled for that input 1219 <string>:2:5: The following alternatives are unreachable: 2,3 1220 */ 1221 } 1222 testMultipleAltsSameSequenceCollision()1223 @Test public void testMultipleAltsSameSequenceCollision() throws Exception { 1224 Grammar g = new Grammar( 1225 "parser grammar t;\n" + 1226 "a : type ID \n" + 1227 " | type ID\n" + 1228 " | type ID\n" + 1229 " | type ID\n" + 1230 " ;\n" + 1231 "\n" + 1232 "type : I | F;"); 1233 // nondeterministic from left edge; no stop state 1234 String expecting = 1235 ".s0-F..I->.s1\n" + 1236 ".s1-ID->:s2=>1\n"; 1237 int[] unreachableAlts = new int[] {2,3,4}; 1238 int[] nonDetAlts = new int[] {1,2,3,4}; 1239 String ambigInput = "F..I ID"; 1240 int[] danglingAlts = null; 1241 int numWarnings = 2; 1242 checkDecision(g, 1, expecting, unreachableAlts, 1243 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1244 } 1245 testFollowReturnsToLoopReenteringSameRule()1246 @Test public void testFollowReturnsToLoopReenteringSameRule() throws Exception { 1247 // D07 can be matched in the (...)? or fall out of esc back into (..)* 1248 // loop in sl. Note that D07 is matched by ~(R|SLASH). No good 1249 // way to write that grammar I guess 1250 Grammar g = new Grammar( 1251 "parser grammar t;\n"+ 1252 "sl : L ( esc | ~(R|SLASH) )* R ;\n" + 1253 "\n" + 1254 "esc : SLASH ( N | D03 (D07)? ) ;"); 1255 String expecting = 1256 ".s0-D03..N->:s2=>2\n" + 1257 ".s0-R->:s3=>3\n" + 1258 ".s0-SLASH->:s1=>1\n"; 1259 int[] unreachableAlts = null; 1260 int[] nonDetAlts = new int[] {1,2}; 1261 String ambigInput = "D07"; 1262 int[] danglingAlts = null; 1263 int numWarnings = 1; 1264 checkDecision(g, 1, expecting, unreachableAlts, 1265 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1266 } 1267 testTokenCallsAnotherOnLeftEdge()1268 @Test public void testTokenCallsAnotherOnLeftEdge() throws Exception { 1269 Grammar g = new Grammar( 1270 "lexer grammar t;\n"+ 1271 "F : I '.'\n" + 1272 " ;\n" + 1273 "I : '0'\n" + 1274 " ;\n" 1275 ); 1276 String expecting = 1277 ".s0-'0'->.s1\n" + 1278 ".s1-'.'->:s3=>1\n" + 1279 ".s1-<EOT>->:s2=>2\n"; 1280 checkDecision(g, 1, expecting, null, null, null, null, 0); 1281 } 1282 1283 testSelfRecursionAmbigAlts()1284 @Test public void testSelfRecursionAmbigAlts() throws Exception { 1285 // ambiguous grammar for "L ID R" (alts 1,2 of a) 1286 Grammar g = new Grammar( 1287 "parser grammar t;\n"+ 1288 "s : a;\n" + 1289 "a : L ID R\n" + 1290 " | L a R\n" + // disabled for L ID R 1291 " | b\n" + 1292 " ;\n" + 1293 "\n" + 1294 "b : ID\n" + 1295 " ;\n"); 1296 String expecting = 1297 ".s0-ID->:s5=>3\n" + 1298 ".s0-L->.s1\n" + 1299 ".s1-ID->.s2\n" + 1300 ".s1-L->:s4=>2\n" + 1301 ".s2-R->:s3=>1\n"; 1302 int[] unreachableAlts = null; 1303 int[] nonDetAlts = new int[] {1,2}; 1304 String ambigInput = "L ID R"; 1305 int[] danglingAlts = null; 1306 int numWarnings = 1; 1307 checkDecision(g, 1, expecting, unreachableAlts, 1308 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1309 } 1310 testIndirectRecursionAmbigAlts()1311 @Test public void testIndirectRecursionAmbigAlts() throws Exception { 1312 // ambiguous grammar for "L ID R" (alts 1,2 of a) 1313 // This was derived from the java grammar 12/4/2004 when it 1314 // was not handling a unaryExpression properly. I traced it 1315 // to incorrect closure-busy condition. It thought that the trace 1316 // of a->b->a->b again for "L ID" was an infinite loop, but actually 1317 // the repeat call to b only happens *after* an L has been matched. 1318 // I added a check to see what the initial stack looks like and it 1319 // seems to work now. 1320 Grammar g = new Grammar( 1321 "parser grammar t;\n"+ 1322 "s : a ;\n" + 1323 "a : L ID R\n" + 1324 " | b\n" + 1325 " ;\n" + 1326 "\n" + 1327 "b : ID\n" + 1328 " | L a R\n" + 1329 " ;"); 1330 String expecting = 1331 ".s0-ID->:s4=>2\n" + 1332 ".s0-L->.s1\n" + 1333 ".s1-ID->.s2\n" + 1334 ".s1-L->:s4=>2\n" + 1335 ".s2-R->:s3=>1\n"; 1336 int[] unreachableAlts = null; 1337 int[] nonDetAlts = new int[] {1,2}; 1338 String ambigInput = "L ID R"; 1339 int[] danglingAlts = null; 1340 int numWarnings = 1; 1341 checkDecision(g, 1, expecting, unreachableAlts, 1342 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1343 } 1344 testTailRecursionInvokedFromArbitraryLookaheadDecision()1345 @Test public void testTailRecursionInvokedFromArbitraryLookaheadDecision() throws Exception { 1346 Grammar g = new Grammar( 1347 "parser grammar t;\n"+ 1348 "a : b X\n" + 1349 " | b Y\n" + 1350 " ;\n" + 1351 "\n" + 1352 "b : A\n" + 1353 " | A b\n" + 1354 " ;\n"); 1355 List altsWithRecursion = Arrays.asList(new Object[] {1,2}); 1356 assertNonLLStar(g, altsWithRecursion); 1357 } 1358 testWildcardStarK1AndNonGreedyByDefaultInParser()1359 @Test public void testWildcardStarK1AndNonGreedyByDefaultInParser() throws Exception { 1360 // no error because .* assumes it should finish when it sees R 1361 Grammar g = new Grammar( 1362 "parser grammar t;\n" + 1363 "s : A block EOF ;\n" + 1364 "block : L .* R ;"); 1365 String expecting = 1366 ".s0-A..L->:s2=>1\n" + 1367 ".s0-R->:s1=>2\n"; 1368 int[] unreachableAlts = null; 1369 int[] nonDetAlts = null; 1370 String ambigInput = null; 1371 int[] danglingAlts = null; 1372 int numWarnings = 0; 1373 checkDecision(g, 1, expecting, unreachableAlts, 1374 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1375 } 1376 testWildcardPlusK1AndNonGreedyByDefaultInParser()1377 @Test public void testWildcardPlusK1AndNonGreedyByDefaultInParser() throws Exception { 1378 Grammar g = new Grammar( 1379 "parser grammar t;\n" + 1380 "s : A block EOF ;\n" + 1381 "block : L .+ R ;"); 1382 String expecting = 1383 ".s0-A..L->:s2=>1\n" + 1384 ".s0-R->:s1=>2\n"; 1385 int[] unreachableAlts = null; 1386 int[] nonDetAlts = null; 1387 String ambigInput = null; 1388 int[] danglingAlts = null; 1389 int numWarnings = 0; 1390 checkDecision(g, 1, expecting, unreachableAlts, 1391 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1392 } 1393 testGatedSynPred()1394 @Test public void testGatedSynPred() throws Exception { 1395 Grammar g = new Grammar( 1396 "parser grammar t;\n"+ 1397 "x : (X)=> X\n" + 1398 " | Y\n" + 1399 " ;\n"); 1400 String expecting = 1401 ".s0-X&&{synpred1_t}?->:s1=>1\n" + // does not hoist; it gates edges 1402 ".s0-Y->:s2=>2\n"; 1403 int[] unreachableAlts = null; 1404 int[] nonDetAlts = null; 1405 String ambigInput = null; 1406 int[] danglingAlts = null; 1407 int numWarnings = 0; 1408 checkDecision(g, 1, expecting, unreachableAlts, 1409 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1410 1411 Set<String> preds = g.synPredNamesUsedInDFA; 1412 Set<String> expectedPreds = new HashSet<String>() {{add("synpred1_t");}}; 1413 assertEquals("predicate names not recorded properly in grammar", expectedPreds, preds); 1414 } 1415 testHoistedGatedSynPred()1416 @Test public void testHoistedGatedSynPred() throws Exception { 1417 Grammar g = new Grammar( 1418 "parser grammar t;\n"+ 1419 "x : (X)=> X\n" + 1420 " | X\n" + 1421 " ;\n"); 1422 String expecting = 1423 ".s0-X->.s1\n" + 1424 ".s1-{synpred1_t}?->:s2=>1\n" + // hoists into decision 1425 ".s1-{true}?->:s3=>2\n"; 1426 int[] unreachableAlts = null; 1427 int[] nonDetAlts = null; 1428 String ambigInput = null; 1429 int[] danglingAlts = null; 1430 int numWarnings = 0; 1431 checkDecision(g, 1, expecting, unreachableAlts, 1432 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1433 1434 Set<String> preds = g.synPredNamesUsedInDFA; 1435 Set<String> expectedPreds = new HashSet<String>() {{add("synpred1_t");}}; 1436 assertEquals("predicate names not recorded properly in grammar", expectedPreds, preds); 1437 } 1438 testHoistedGatedSynPred2()1439 @Test public void testHoistedGatedSynPred2() throws Exception { 1440 Grammar g = new Grammar( 1441 "parser grammar t;\n"+ 1442 "x : (X)=> (X|Y)\n" + 1443 " | X\n" + 1444 " ;\n"); 1445 String expecting = 1446 ".s0-X->.s1\n" + 1447 ".s0-Y&&{synpred1_t}?->:s2=>1\n" + 1448 ".s1-{synpred1_t}?->:s2=>1\n" + 1449 ".s1-{true}?->:s3=>2\n"; 1450 int[] unreachableAlts = null; 1451 int[] nonDetAlts = null; 1452 String ambigInput = null; 1453 int[] danglingAlts = null; 1454 int numWarnings = 0; 1455 checkDecision(g, 1, expecting, unreachableAlts, 1456 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1457 1458 Set<String> preds = g.synPredNamesUsedInDFA; 1459 Set<String> expectedPreds = new HashSet<String>() {{add("synpred1_t");}}; 1460 assertEquals("predicate names not recorded properly in grammar", expectedPreds, preds); 1461 } 1462 testGreedyGetsNoErrorForAmbig()1463 @Test public void testGreedyGetsNoErrorForAmbig() throws Exception { 1464 Grammar g = new Grammar( 1465 "parser grammar t;\n"+ 1466 "s : IF s (options {greedy=true;} : E s)? | B;\n" + 1467 "slist: s SEMI ;"); 1468 String expecting = 1469 ".s0-E->:s1=>1\n" + 1470 ".s0-SEMI->:s2=>2\n"; 1471 int[] unreachableAlts = null; 1472 int[] nonDetAlts = null; 1473 String ambigInput = null; 1474 int[] danglingAlts = null; 1475 int numWarnings = 0; 1476 checkDecision(g, 1, expecting, unreachableAlts, 1477 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1478 expecting = 1479 ".s0-B->:s2=>2\n" + 1480 ".s0-IF->:s1=>1\n"; 1481 checkDecision(g, 2, expecting, null, null, null, null, 0); 1482 } 1483 testGreedyNonLLStarStillGetsError()1484 @Test public void testGreedyNonLLStarStillGetsError() throws Exception { 1485 Grammar g = new Grammar( 1486 "parser grammar t;\n"+ 1487 "x : ( options {greedy=true;}\n" + 1488 " : y X\n" + 1489 " | y Y\n" + 1490 " )\n" + 1491 " ;\n" + 1492 "y : L y R\n" + 1493 " | B\n" + 1494 " ;"); 1495 List altsWithRecursion = Arrays.asList(new Object[] {1,2}); 1496 assertNonLLStar(g, altsWithRecursion); 1497 } 1498 testGreedyRecOverflowStillGetsError()1499 @Test public void testGreedyRecOverflowStillGetsError() throws Exception { 1500 Grammar g = new Grammar( 1501 "parser grammar t;\n"+ 1502 "s : (options {greedy=true;} : a Y | A A A A A X) ;\n" + // force recursion past m=4 1503 "a : A a | Q;"); 1504 List expectedTargetRules = Arrays.asList(new Object[] {"a"}); 1505 int expectedAlt = 1; 1506 assertRecursionOverflow(g, expectedTargetRules, expectedAlt); 1507 } 1508 1509 1510 // Check state table creation 1511 testCyclicTableCreation()1512 @Test public void testCyclicTableCreation() throws Exception { 1513 Grammar g = new Grammar( 1514 "parser grammar t;\n"+ 1515 "a : A+ X | A+ Y ;"); 1516 String expecting = 1517 ".s0-A->:s1=>1\n" + 1518 ".s0-B->:s2=>2\n"; 1519 } 1520 1521 1522 // S U P P O R T 1523 _template()1524 public void _template() throws Exception { 1525 Grammar g = new Grammar( 1526 "parser grammar t;\n"+ 1527 "a : A | B;"); 1528 String expecting = 1529 "\n"; 1530 checkDecision(g, 1, expecting, null, null, null, null, 0); 1531 } 1532 assertNonLLStar(Grammar g, List expectedBadAlts)1533 protected void assertNonLLStar(Grammar g, List expectedBadAlts) { 1534 DecisionProbe.verbose=true; // make sure we get all error info 1535 ErrorQueue equeue = new ErrorQueue(); 1536 ErrorManager.setErrorListener(equeue); 1537 1538 // mimic actions of org.antlr.Tool first time for grammar g 1539 if ( g.getNumberOfDecisions()==0 ) { 1540 g.buildNFA(); 1541 g.createLookaheadDFAs(false); 1542 } 1543 NonRegularDecisionMessage msg = getNonRegularDecisionMessage(equeue.errors); 1544 assertTrue("expected fatal non-LL(*) msg", msg!=null); 1545 List<Integer> alts = new ArrayList(); 1546 alts.addAll(msg.altsWithRecursion); 1547 Collections.sort(alts); 1548 assertEquals(expectedBadAlts,alts); 1549 } 1550 assertRecursionOverflow(Grammar g, List expectedTargetRules, int expectedAlt)1551 protected void assertRecursionOverflow(Grammar g, 1552 List expectedTargetRules, 1553 int expectedAlt) { 1554 DecisionProbe.verbose=true; // make sure we get all error info 1555 ErrorQueue equeue = new ErrorQueue(); 1556 ErrorManager.setErrorListener(equeue); 1557 1558 // mimic actions of org.antlr.Tool first time for grammar g 1559 if ( g.getNumberOfDecisions()==0 ) { 1560 g.buildNFA(); 1561 g.createLookaheadDFAs(false); 1562 } 1563 RecursionOverflowMessage msg = getRecursionOverflowMessage(equeue.errors); 1564 assertTrue("missing expected recursion overflow msg"+msg, msg!=null); 1565 assertEquals("target rules mismatch", 1566 expectedTargetRules.toString(), msg.targetRules.toString()); 1567 assertEquals("mismatched alt", expectedAlt, msg.alt); 1568 } 1569 1570 @Test testWildcardInTreeGrammar()1571 public void testWildcardInTreeGrammar() throws Exception { 1572 Grammar g = new Grammar( 1573 "tree grammar t;\n" + 1574 "a : A B | A . ;\n"); 1575 String expecting = 1576 ".s0-A->.s1\n" + 1577 ".s1-A->:s3=>2\n" + 1578 ".s1-B->:s2=>1\n"; 1579 int[] unreachableAlts = null; 1580 int[] nonDetAlts = new int[] {1,2}; 1581 String ambigInput = null; 1582 int[] danglingAlts = null; 1583 int numWarnings = 1; 1584 checkDecision(g, 1, expecting, unreachableAlts, 1585 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1586 } 1587 1588 @Test testWildcardInTreeGrammar2()1589 public void testWildcardInTreeGrammar2() throws Exception { 1590 Grammar g = new Grammar( 1591 "tree grammar t;\n" + 1592 "a : ^(A X Y) | ^(A . .) ;\n"); 1593 String expecting = 1594 ".s0-A->.s1\n" + 1595 ".s1-DOWN->.s2\n" + 1596 ".s2-X->.s3\n" + 1597 ".s2-{A, Y}->:s6=>2\n" + 1598 ".s3-Y->.s4\n" + 1599 ".s3-{DOWN, A..X}->:s6=>2\n" + 1600 ".s4-DOWN->:s6=>2\n" + 1601 ".s4-UP->:s5=>1\n"; 1602 int[] unreachableAlts = null; 1603 int[] nonDetAlts = new int[] {1,2}; 1604 String ambigInput = null; 1605 int[] danglingAlts = null; 1606 int numWarnings = 1; 1607 checkDecision(g, 1, expecting, unreachableAlts, 1608 nonDetAlts, ambigInput, danglingAlts, numWarnings); 1609 } 1610 checkDecision(Grammar g, int decision, String expecting, int[] expectingUnreachableAlts, int[] expectingNonDetAlts, String expectingAmbigInput, int[] expectingDanglingAlts, int expectingNumWarnings)1611 protected void checkDecision(Grammar g, 1612 int decision, 1613 String expecting, 1614 int[] expectingUnreachableAlts, 1615 int[] expectingNonDetAlts, 1616 String expectingAmbigInput, 1617 int[] expectingDanglingAlts, 1618 int expectingNumWarnings) 1619 throws Exception 1620 { 1621 DecisionProbe.verbose=true; // make sure we get all error info 1622 ErrorQueue equeue = new ErrorQueue(); 1623 ErrorManager.setErrorListener(equeue); 1624 1625 // mimic actions of org.antlr.Tool first time for grammar g 1626 if ( g.getNumberOfDecisions()==0 ) { 1627 g.buildNFA(); 1628 g.createLookaheadDFAs(false); 1629 } 1630 CodeGenerator generator = new CodeGenerator(newTool(), g, "Java"); 1631 g.setCodeGenerator(generator); 1632 1633 if ( equeue.size()!=expectingNumWarnings ) { 1634 System.err.println("Warnings issued: "+equeue); 1635 } 1636 1637 assertEquals("unexpected number of expected problems", 1638 expectingNumWarnings, equeue.size()); 1639 1640 DFA dfa = g.getLookaheadDFA(decision); 1641 assertNotNull("no DFA for decision "+decision, dfa); 1642 FASerializer serializer = new FASerializer(g); 1643 String result = serializer.serialize(dfa.startState); 1644 1645 List unreachableAlts = dfa.getUnreachableAlts(); 1646 1647 // make sure unreachable alts are as expected 1648 if ( expectingUnreachableAlts!=null ) { 1649 BitSet s = new BitSet(); 1650 s.addAll(expectingUnreachableAlts); 1651 BitSet s2 = new BitSet(); 1652 s2.addAll(unreachableAlts); 1653 assertEquals("unreachable alts mismatch", s, s2); 1654 } 1655 else { 1656 assertEquals("number of unreachable alts", 0, 1657 unreachableAlts!=null?unreachableAlts.size():0); 1658 } 1659 1660 // check conflicting input 1661 if ( expectingAmbigInput!=null ) { 1662 // first, find nondet message 1663 Message msg = (Message)equeue.warnings.get(0); 1664 assertTrue("expecting nondeterminism; found "+msg.getClass().getName(), 1665 msg instanceof GrammarNonDeterminismMessage); 1666 GrammarNonDeterminismMessage nondetMsg = 1667 getNonDeterminismMessage(equeue.warnings); 1668 List labels = 1669 nondetMsg.probe.getSampleNonDeterministicInputSequence(nondetMsg.problemState); 1670 String input = nondetMsg.probe.getInputSequenceDisplay(labels); 1671 assertEquals(expectingAmbigInput, input); 1672 } 1673 1674 // check nondet alts 1675 if ( expectingNonDetAlts!=null ) { 1676 RecursionOverflowMessage recMsg = null; 1677 GrammarNonDeterminismMessage nondetMsg = 1678 getNonDeterminismMessage(equeue.warnings); 1679 List nonDetAlts = null; 1680 if ( nondetMsg!=null ) { 1681 nonDetAlts = 1682 nondetMsg.probe.getNonDeterministicAltsForState(nondetMsg.problemState); 1683 } 1684 else { 1685 recMsg = getRecursionOverflowMessage(equeue.warnings); 1686 if ( recMsg!=null ) { 1687 //nonDetAlts = new ArrayList(recMsg.alts); 1688 } 1689 } 1690 // compare nonDetAlts with expectingNonDetAlts 1691 BitSet s = new BitSet(); 1692 s.addAll(expectingNonDetAlts); 1693 BitSet s2 = new BitSet(); 1694 s2.addAll(nonDetAlts); 1695 assertEquals("nondet alts mismatch", s, s2); 1696 assertTrue("found no nondet alts; expecting: "+ 1697 str(expectingNonDetAlts), 1698 nondetMsg!=null||recMsg!=null); 1699 } 1700 else { 1701 // not expecting any nondet alts, make sure there are none 1702 GrammarNonDeterminismMessage nondetMsg = 1703 getNonDeterminismMessage(equeue.warnings); 1704 assertNull("found nondet alts, but expecting none", nondetMsg); 1705 } 1706 1707 assertEquals(expecting, result); 1708 } 1709 getNonDeterminismMessage(List warnings)1710 protected GrammarNonDeterminismMessage getNonDeterminismMessage(List warnings) { 1711 for (int i = 0; i < warnings.size(); i++) { 1712 Message m = (Message) warnings.get(i); 1713 if ( m instanceof GrammarNonDeterminismMessage ) { 1714 return (GrammarNonDeterminismMessage)m; 1715 } 1716 } 1717 return null; 1718 } 1719 getNonRegularDecisionMessage(List errors)1720 protected NonRegularDecisionMessage getNonRegularDecisionMessage(List errors) { 1721 for (int i = 0; i < errors.size(); i++) { 1722 Message m = (Message) errors.get(i); 1723 if ( m instanceof NonRegularDecisionMessage ) { 1724 return (NonRegularDecisionMessage)m; 1725 } 1726 } 1727 return null; 1728 } 1729 getRecursionOverflowMessage(List warnings)1730 protected RecursionOverflowMessage getRecursionOverflowMessage(List warnings) { 1731 for (int i = 0; i < warnings.size(); i++) { 1732 Message m = (Message) warnings.get(i); 1733 if ( m instanceof RecursionOverflowMessage ) { 1734 return (RecursionOverflowMessage)m; 1735 } 1736 } 1737 return null; 1738 } 1739 getLeftRecursionCyclesMessage(List warnings)1740 protected LeftRecursionCyclesMessage getLeftRecursionCyclesMessage(List warnings) { 1741 for (int i = 0; i < warnings.size(); i++) { 1742 Message m = (Message) warnings.get(i); 1743 if ( m instanceof LeftRecursionCyclesMessage ) { 1744 return (LeftRecursionCyclesMessage)m; 1745 } 1746 } 1747 return null; 1748 } 1749 getDanglingStateMessage(List warnings)1750 protected GrammarDanglingStateMessage getDanglingStateMessage(List warnings) { 1751 for (int i = 0; i < warnings.size(); i++) { 1752 Message m = (Message) warnings.get(i); 1753 if ( m instanceof GrammarDanglingStateMessage ) { 1754 return (GrammarDanglingStateMessage)m; 1755 } 1756 } 1757 return null; 1758 } 1759 str(int[] elements)1760 protected String str(int[] elements) { 1761 StringBuffer buf = new StringBuffer(); 1762 for (int i = 0; i < elements.length; i++) { 1763 if ( i>0 ) { 1764 buf.append(", "); 1765 } 1766 int element = elements[i]; 1767 buf.append(element); 1768 } 1769 return buf.toString(); 1770 } 1771 ruleNames(Set<Rule> rules)1772 protected Set<String> ruleNames(Set<Rule> rules) { 1773 Set<String> x = new HashSet<String>(); 1774 for (Rule r : rules) { 1775 x.add(r.name); 1776 } 1777 return x; 1778 } 1779 ruleNames2(Collection<HashSet> rules)1780 protected Set<String> ruleNames2(Collection<HashSet> rules) { 1781 Set<String> x = new HashSet<String>(); 1782 for (HashSet s : rules) { 1783 x.addAll(ruleNames(s)); 1784 } 1785 return x; 1786 } 1787 } 1788