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.analysis.DFA; 31 import org.antlr.analysis.DecisionProbe; 32 import org.antlr.codegen.CodeGenerator; 33 import org.antlr.misc.BitSet; 34 import org.antlr.runtime.Token; 35 import org.antlr.tool.*; 36 import org.junit.Test; 37 38 import java.util.List; 39 import java.util.Map; 40 import java.util.Set; 41 42 public class TestSemanticPredicates extends BaseTest { 43 44 /** Public default constructor used by TestRig */ TestSemanticPredicates()45 public TestSemanticPredicates() { 46 } 47 testPredsButSyntaxResolves()48 @Test public void testPredsButSyntaxResolves() throws Exception { 49 Grammar g = new Grammar( 50 "parser grammar P;\n"+ 51 "a : {p1}? A | {p2}? B ;"); 52 String expecting = 53 ".s0-A->:s1=>1\n" + 54 ".s0-B->:s2=>2\n"; 55 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 56 } 57 testLL_1_Pred()58 @Test public void testLL_1_Pred() throws Exception { 59 Grammar g = new Grammar( 60 "parser grammar P;\n"+ 61 "a : {p1}? A | {p2}? A ;"); 62 String expecting = 63 ".s0-A->.s1\n" + 64 ".s1-{p1}?->:s2=>1\n" + 65 ".s1-{p2}?->:s3=>2\n"; 66 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 67 } 68 testLL_1_Pred_forced_k_1()69 @Test public void testLL_1_Pred_forced_k_1() throws Exception { 70 // should stop just like before w/o k set. 71 Grammar g = new Grammar( 72 "parser grammar P;\n"+ 73 "a options {k=1;} : {p1}? A | {p2}? A ;"); 74 String expecting = 75 ".s0-A->.s1\n" + 76 ".s1-{p1}?->:s2=>1\n" + 77 ".s1-{p2}?->:s3=>2\n"; 78 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 79 } 80 testLL_2_Pred()81 @Test public void testLL_2_Pred() throws Exception { 82 Grammar g = new Grammar( 83 "parser grammar P;\n"+ 84 "a : {p1}? A B | {p2}? A B ;"); 85 String expecting = 86 ".s0-A->.s1\n" + 87 ".s1-B->.s2\n" + 88 ".s2-{p1}?->:s3=>1\n" + 89 ".s2-{p2}?->:s4=>2\n"; 90 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 91 } 92 testPredicatedLoop()93 @Test public void testPredicatedLoop() throws Exception { 94 Grammar g = new Grammar( 95 "parser grammar P;\n"+ 96 "a : ( {p1}? A | {p2}? A )+;"); 97 String expecting = // loop back 98 ".s0-A->.s2\n" + 99 ".s0-EOF->:s1=>3\n" + 100 ".s2-{p1}?->:s3=>1\n" + 101 ".s2-{p2}?->:s4=>2\n"; 102 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 103 } 104 testPredicatedToStayInLoop()105 @Test public void testPredicatedToStayInLoop() throws Exception { 106 Grammar g = new Grammar( 107 "parser grammar P;\n"+ 108 "a : ( {p1}? A )+ (A)+;"); 109 String expecting = 110 ".s0-A->.s1\n" + 111 ".s1-{p1}?->:s2=>1\n" + 112 ".s1-{true}?->:s3=>2\n"; // loop back 113 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 114 } 115 testAndPredicates()116 @Test public void testAndPredicates() throws Exception { 117 Grammar g = new Grammar( 118 "parser grammar P;\n"+ 119 "a : {p1}? {p1a}? A | {p2}? A ;"); 120 String expecting = 121 ".s0-A->.s1\n" + 122 ".s1-{(p1&&p1a)}?->:s2=>1\n" + 123 ".s1-{p2}?->:s3=>2\n"; 124 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 125 } 126 127 @Test testOrPredicates()128 public void testOrPredicates() throws Exception { 129 Grammar g = new Grammar( 130 "parser grammar P;\n"+ 131 "a : b | {p2}? A ;\n" + 132 "b : {p1}? A | {p1a}? A ;"); 133 String expecting = 134 ".s0-A->.s1\n" + 135 ".s1-{(p1a||p1)}?->:s2=>1\n" + 136 ".s1-{p2}?->:s3=>2\n"; 137 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 138 } 139 testIgnoresHoistingDepthGreaterThanZero()140 @Test public void testIgnoresHoistingDepthGreaterThanZero() throws Exception { 141 Grammar g = new Grammar( 142 "parser grammar P;\n"+ 143 "a : A {p1}? | A {p2}?;"); 144 String expecting = 145 ".s0-A->:s1=>1\n"; 146 checkDecision(g, 1, expecting, new int[] {2}, 147 new int[] {1,2}, "A", null, null, 2, false); 148 } 149 testIgnoresPredsHiddenByActions()150 @Test public void testIgnoresPredsHiddenByActions() throws Exception { 151 Grammar g = new Grammar( 152 "parser grammar P;\n"+ 153 "a : {a1} {p1}? A | {a2} {p2}? A ;"); 154 String expecting = 155 ".s0-A->:s1=>1\n"; 156 checkDecision(g, 1, expecting, new int[] {2}, 157 new int[] {1,2}, "A", null, null, 2, true); 158 } 159 testIgnoresPredsHiddenByActionsOneAlt()160 @Test public void testIgnoresPredsHiddenByActionsOneAlt() throws Exception { 161 Grammar g = new Grammar( 162 "parser grammar P;\n"+ 163 "a : {p1}? A | {a2} {p2}? A ;"); // ok since 1 pred visible 164 String expecting = 165 ".s0-A->.s1\n" + 166 ".s1-{p1}?->:s2=>1\n" + 167 ".s1-{true}?->:s3=>2\n"; 168 checkDecision(g, 1, expecting, null, 169 null, null, null, null, 0, true); 170 } 171 172 /* 173 @Test public void testIncompleteSemanticHoistedContextk2() throws Exception { 174 ErrorQueue equeue = new ErrorQueue(); 175 ErrorManager.setErrorListener(equeue); 176 Grammar g = new Grammar( 177 "parser grammar t;\n"+ 178 "a : b | A B;\n" + 179 "b : {p1}? A B | A B ;"); 180 String expecting = 181 ".s0-A->.s1\n" + 182 ".s1-B->:s2=>1\n"; 183 checkDecision(g, 1, expecting, new int[] {2}, 184 new int[] {1,2}, "A B", new int[] {1}, null, 3); 185 } 186 */ 187 testHoist2()188 @Test public void testHoist2() throws Exception { 189 Grammar g = new Grammar( 190 "parser grammar P;\n"+ 191 "a : b | c ;\n" + 192 "b : {p1}? A ;\n" + 193 "c : {p2}? A ;\n"); 194 String expecting = 195 ".s0-A->.s1\n" + 196 ".s1-{p1}?->:s2=>1\n" + 197 ".s1-{p2}?->:s3=>2\n"; 198 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 199 } 200 testHoistCorrectContext()201 @Test public void testHoistCorrectContext() throws Exception { 202 Grammar g = new Grammar( 203 "parser grammar P;\n"+ 204 "a : b | {p2}? ID ;\n" + 205 "b : {p1}? ID | INT ;\n"); 206 String expecting = // only tests after ID, not INT :) 207 ".s0-ID->.s1\n" + 208 ".s0-INT->:s2=>1\n" + 209 ".s1-{p1}?->:s2=>1\n" + 210 ".s1-{p2}?->:s3=>2\n"; 211 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 212 } 213 testDefaultPredNakedAltIsLast()214 @Test public void testDefaultPredNakedAltIsLast() throws Exception { 215 Grammar g = new Grammar( 216 "parser grammar P;\n"+ 217 "a : b | ID ;\n" + 218 "b : {p1}? ID | INT ;\n"); 219 String expecting = 220 ".s0-ID->.s1\n" + 221 ".s0-INT->:s2=>1\n" + 222 ".s1-{p1}?->:s2=>1\n" + 223 ".s1-{true}?->:s3=>2\n"; 224 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 225 } 226 testDefaultPredNakedAltNotLast()227 @Test public void testDefaultPredNakedAltNotLast() throws Exception { 228 Grammar g = new Grammar( 229 "parser grammar P;\n"+ 230 "a : ID | b ;\n" + 231 "b : {p1}? ID | INT ;\n"); 232 String expecting = 233 ".s0-ID->.s1\n" + 234 ".s0-INT->:s3=>2\n" + 235 ".s1-{!(p1)}?->:s2=>1\n" + 236 ".s1-{p1}?->:s3=>2\n"; 237 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 238 } 239 testLeftRecursivePred()240 @Test public void testLeftRecursivePred() throws Exception { 241 // No analysis possible. but probably good to fail. Not sure we really want 242 // left-recursion even if guarded with pred. 243 Grammar g = new Grammar( 244 "parser grammar P;\n"+ 245 "s : a ;\n" + 246 "a : {p1}? a | ID ;\n"); 247 String expecting = 248 ".s0-ID->.s1\n" + 249 ".s1-{p1}?->:s2=>1\n" + 250 ".s1-{true}?->:s3=>2\n"; 251 252 DecisionProbe.verbose=true; // make sure we get all error info 253 ErrorQueue equeue = new ErrorQueue(); 254 ErrorManager.setErrorListener(equeue); 255 CodeGenerator generator = new CodeGenerator(newTool(), g, "Java"); 256 g.setCodeGenerator(generator); 257 if ( g.getNumberOfDecisions()==0 ) { 258 g.buildNFA(); 259 g.createLookaheadDFAs(false); 260 } 261 262 DFA dfa = g.getLookaheadDFA(1); 263 assertEquals(null, dfa); // can't analyze. 264 265 /* 266 String result = serializer.serialize(dfa.startState); 267 assertEquals(expecting, result); 268 */ 269 270 assertEquals("unexpected number of expected problems", 1, equeue.size()); 271 Message msg = (Message)equeue.errors.get(0); 272 assertTrue("warning must be a left recursion msg", 273 msg instanceof LeftRecursionCyclesMessage); 274 } 275 testIgnorePredFromLL2AltLastAltIsDefaultTrue()276 @Test public void testIgnorePredFromLL2AltLastAltIsDefaultTrue() throws Exception { 277 Grammar g = new Grammar( 278 "parser grammar P;\n"+ 279 "a : {p1}? A B | A C | {p2}? A | {p3}? A | A ;\n"); 280 // two situations of note: 281 // 1. A B syntax is enough to predict that alt, so p1 is not used 282 // to distinguish it from alts 2..5 283 // 2. Alts 3, 4, 5 are nondeterministic with upon A. p2, p3 and the 284 // complement of p2||p3 is sufficient to resolve the conflict. Do 285 // not include alt 1's p1 pred in the "complement of other alts" 286 // because it is not considered nondeterministic with alts 3..5 287 String expecting = 288 ".s0-A->.s1\n" + 289 ".s1-B->:s2=>1\n" + 290 ".s1-C->:s3=>2\n" + 291 ".s1-{p2}?->:s4=>3\n" + 292 ".s1-{p3}?->:s5=>4\n" + 293 ".s1-{true}?->:s6=>5\n"; 294 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 295 } 296 testIgnorePredFromLL2AltPredUnionNeeded()297 @Test public void testIgnorePredFromLL2AltPredUnionNeeded() throws Exception { 298 Grammar g = new Grammar( 299 "parser grammar P;\n"+ 300 "a : {p1}? A B | A C | {p2}? A | A | {p3}? A ;\n"); 301 // two situations of note: 302 // 1. A B syntax is enough to predict that alt, so p1 is not used 303 // to distinguish it from alts 2..5 304 // 2. Alts 3, 4, 5 are nondeterministic with upon A. p2, p3 and the 305 // complement of p2||p3 is sufficient to resolve the conflict. Do 306 // not include alt 1's p1 pred in the "complement of other alts" 307 // because it is not considered nondeterministic with alts 3..5 308 String expecting = 309 ".s0-A->.s1\n" + 310 ".s1-B->:s2=>1\n" + 311 ".s1-C->:s3=>2\n" + 312 ".s1-{!((p3||p2))}?->:s5=>4\n" + 313 ".s1-{p2}?->:s4=>3\n" + 314 ".s1-{p3}?->:s6=>5\n"; 315 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 316 } 317 testPredGets2SymbolSyntacticContext()318 @Test public void testPredGets2SymbolSyntacticContext() throws Exception { 319 Grammar g = new Grammar( 320 "parser grammar P;\n"+ 321 "a : b | A B | C ;\n" + 322 "b : {p1}? A B ;\n"); 323 String expecting = 324 ".s0-A->.s1\n" + 325 ".s0-C->:s5=>3\n" + 326 ".s1-B->.s2\n" + 327 ".s2-{p1}?->:s3=>1\n" + 328 ".s2-{true}?->:s4=>2\n"; 329 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 330 } 331 testMatchesLongestThenTestPred()332 @Test public void testMatchesLongestThenTestPred() throws Exception { 333 Grammar g = new Grammar( 334 "parser grammar P;\n"+ 335 "a : b | c ;\n" + 336 "b : {p}? A ;\n" + 337 "c : {q}? (A|B)+ ;"); 338 String expecting = 339 ".s0-A->.s1\n" + 340 ".s0-B->:s3=>2\n" + 341 ".s1-{p}?->:s2=>1\n" + 342 ".s1-{q}?->:s3=>2\n"; 343 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 344 } 345 testPredsUsedAfterRecursionOverflow()346 @Test public void testPredsUsedAfterRecursionOverflow() throws Exception { 347 // analysis must bail out due to non-LL(*) nature (ovf) 348 // retries with k=1 (but with LL(*) algorithm not optimized version 349 // as it has preds) 350 Grammar g = new Grammar( 351 "parser grammar P;\n"+ 352 "s : {p1}? e '.' | {p2}? e ':' ;\n" + 353 "e : '(' e ')' | INT ;\n"); 354 String expecting = 355 ".s0-'('->.s1\n" + 356 ".s0-INT->.s4\n" + 357 ".s1-{p1}?->:s2=>1\n" + 358 ".s1-{p2}?->:s3=>2\n" + 359 ".s4-{p1}?->:s2=>1\n" + 360 ".s4-{p2}?->:s3=>2\n"; 361 DecisionProbe.verbose=true; // make sure we get all error info 362 ErrorQueue equeue = new ErrorQueue(); 363 ErrorManager.setErrorListener(equeue); 364 CodeGenerator generator = new CodeGenerator(newTool(), g, "Java"); 365 g.setCodeGenerator(generator); 366 if ( g.getNumberOfDecisions()==0 ) { 367 g.buildNFA(); 368 g.createLookaheadDFAs(false); 369 } 370 371 assertEquals("unexpected number of expected problems", 0, equeue.size()); 372 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 373 } 374 testPredsUsedAfterK2FailsNoRecursionOverflow()375 @Test public void testPredsUsedAfterK2FailsNoRecursionOverflow() throws Exception { 376 // analysis must bail out due to non-LL(*) nature (ovf) 377 // retries with k=1 (but with LL(*) algorithm not optimized version 378 // as it has preds) 379 Grammar g = new Grammar( 380 "grammar P;\n" + 381 "options {k=2;}\n"+ 382 "s : {p1}? e '.' | {p2}? e ':' ;\n" + 383 "e : '(' e ')' | INT ;\n"); 384 String expecting = 385 ".s0-'('->.s1\n" + 386 ".s0-INT->.s6\n" + 387 ".s1-'('->.s2\n" + 388 ".s1-INT->.s5\n" + 389 ".s2-{p1}?->:s3=>1\n" + 390 ".s2-{p2}?->:s4=>2\n" + 391 ".s5-{p1}?->:s3=>1\n" + 392 ".s5-{p2}?->:s4=>2\n" + 393 ".s6-'.'->:s3=>1\n" + 394 ".s6-':'->:s4=>2\n"; 395 DecisionProbe.verbose=true; // make sure we get all error info 396 ErrorQueue equeue = new ErrorQueue(); 397 ErrorManager.setErrorListener(equeue); 398 CodeGenerator generator = new CodeGenerator(newTool(), g, "Java"); 399 g.setCodeGenerator(generator); 400 if ( g.getNumberOfDecisions()==0 ) { 401 g.buildNFA(); 402 g.createLookaheadDFAs(false); 403 } 404 405 assertEquals("unexpected number of expected problems", 0, equeue.size()); 406 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 407 } 408 testLexerMatchesLongestThenTestPred()409 @Test public void testLexerMatchesLongestThenTestPred() throws Exception { 410 Grammar g = new Grammar( 411 "lexer grammar P;\n"+ 412 "B : {p}? 'a' ;\n" + 413 "C : {q}? ('a'|'b')+ ;"); 414 String expecting = 415 ".s0-'a'->.s1\n" + 416 ".s0-'b'->:s4=>2\n" + 417 ".s1-'a'..'b'->:s4=>2\n" + 418 ".s1-<EOT>->.s2\n" + 419 ".s2-{p}?->:s3=>1\n" + 420 ".s2-{q}?->:s4=>2\n"; 421 checkDecision(g, 2, expecting, null, null, null, null, null, 0, false); 422 } 423 testLexerMatchesLongestMinusPred()424 @Test public void testLexerMatchesLongestMinusPred() throws Exception { 425 Grammar g = new Grammar( 426 "lexer grammar P;\n"+ 427 "B : 'a' ;\n" + 428 "C : ('a'|'b')+ ;"); 429 String expecting = 430 ".s0-'a'->.s1\n" + 431 ".s0-'b'->:s3=>2\n" + 432 ".s1-'a'..'b'->:s3=>2\n" + 433 ".s1-<EOT>->:s2=>1\n"; 434 checkDecision(g, 2, expecting, null, null, null, null, null, 0, false); 435 } 436 437 @Test testGatedPred()438 public void testGatedPred() throws Exception { 439 // gated preds are present on all arcs in predictor 440 Grammar g = new Grammar( 441 "lexer grammar P;\n"+ 442 "B : {p}? => 'a' ;\n" + 443 "C : {q}? => ('a'|'b')+ ;"); 444 String expecting = 445 ".s0-'a'&&{(q||p)}?->.s1\n" + 446 ".s0-'b'&&{q}?->:s4=>2\n" + 447 ".s1-'a'..'b'&&{q}?->:s4=>2\n" + 448 ".s1-<EOT>&&{(q||p)}?->.s2\n" + 449 ".s2-{p}?->:s3=>1\n" + 450 ".s2-{q}?->:s4=>2\n"; 451 checkDecision(g, 2, expecting, null, null, null, null, null, 0, false); 452 } 453 testGatedPredHoistsAndCanBeInStopState()454 @Test public void testGatedPredHoistsAndCanBeInStopState() throws Exception { 455 // I found a bug where merging stop states made us throw away 456 // a stop state with a gated pred! 457 Grammar g = new Grammar( 458 "grammar u;\n" + 459 "a : b+ ;\n" + 460 "b : 'x' | {p}?=> 'y' ;"); 461 String expecting = 462 ".s0-'x'->:s2=>1\n" + 463 ".s0-'y'&&{p}?->:s3=>1\n" + 464 ".s0-EOF->:s1=>2\n"; 465 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 466 } 467 468 @Test testGatedPredInCyclicDFA()469 public void testGatedPredInCyclicDFA() throws Exception { 470 Grammar g = new Grammar( 471 "lexer grammar P;\n"+ 472 "A : {p}?=> ('a')+ 'x' ;\n" + 473 "B : {q}?=> ('a'|'b')+ 'x' ;"); 474 String expecting = 475 ".s0-'a'&&{(q||p)}?->.s1\n" + 476 ".s0-'b'&&{q}?->:s5=>2\n" + 477 ".s1-'a'&&{(q||p)}?->.s1\n" + 478 ".s1-'b'&&{q}?->:s5=>2\n" + 479 ".s1-'x'&&{(q||p)}?->.s2\n" + 480 ".s2-<EOT>&&{(q||p)}?->.s3\n" + 481 ".s3-{p}?->:s4=>1\n" + 482 ".s3-{q}?->:s5=>2\n"; 483 checkDecision(g, 3, expecting, null, null, null, null, null, 0, false); 484 } 485 testGatedPredNotActuallyUsedOnEdges()486 @Test public void testGatedPredNotActuallyUsedOnEdges() throws Exception { 487 Grammar g = new Grammar( 488 "lexer grammar P;\n"+ 489 "A : ('a' | {p}?=> 'a')\n" + 490 " | 'a' 'b'\n" + 491 " ;"); 492 String expecting1 = 493 ".s0-'a'->.s1\n" + 494 ".s1-{!(p)}?->:s2=>1\n" + // Used to disambig subrule 495 ".s1-{p}?->:s3=>2\n"; 496 // rule A decision can't test p from s0->1 because 'a' is valid 497 // for alt1 *and* alt2 w/o p. Can't test p from s1 to s3 because 498 // we might have passed the first alt of subrule. The same state 499 // is listed in s2 in 2 different configurations: one with and one 500 // w/o p. Can't test therefore. p||true == true. 501 String expecting2 = 502 ".s0-'a'->.s1\n" + 503 ".s1-'b'->:s2=>2\n" + 504 ".s1-<EOT>->:s3=>1\n"; 505 checkDecision(g, 1, expecting1, null, null, null, null, null, 0, false); 506 checkDecision(g, 2, expecting2, null, null, null, null, null, 0, false); 507 } 508 testGatedPredDoesNotForceAllToBeGated()509 @Test public void testGatedPredDoesNotForceAllToBeGated() throws Exception { 510 Grammar g = new Grammar( 511 "grammar w;\n" + 512 "a : b | c ;\n" + 513 "b : {p}? B ;\n" + 514 "c : {q}?=> d ;\n" + 515 "d : {r}? C ;\n"); 516 String expecting = 517 ".s0-B->:s1=>1\n" + 518 ".s0-C&&{q}?->:s2=>2\n"; 519 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 520 } 521 testGatedPredDoesNotForceAllToBeGated2()522 @Test public void testGatedPredDoesNotForceAllToBeGated2() throws Exception { 523 Grammar g = new Grammar( 524 "grammar w;\n" + 525 "a : b | c ;\n" + 526 "b : {p}? B ;\n" + 527 "c : {q}?=> d ;\n" + 528 "d : {r}?=> C\n" + 529 " | B\n" + 530 " ;\n"); 531 String expecting = 532 ".s0-B->.s1\n" + 533 ".s0-C&&{(q&&r)}?->:s3=>2\n" + 534 ".s1-{p}?->:s2=>1\n" + 535 ".s1-{q}?->:s3=>2\n"; 536 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 537 } 538 testORGatedPred()539 @Test public void testORGatedPred() throws Exception { 540 Grammar g = new Grammar( 541 "grammar w;\n" + 542 "a : b | c ;\n" + 543 "b : {p}? B ;\n" + 544 "c : {q}?=> d ;\n" + 545 "d : {r}?=> C\n" + 546 " | {s}?=> B\n" + 547 " ;\n"); 548 String expecting = 549 ".s0-B->.s1\n" + 550 ".s0-C&&{(q&&r)}?->:s3=>2\n" + 551 ".s1-{(q&&s)}?->:s3=>2\n" + 552 ".s1-{p}?->:s2=>1\n"; 553 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 554 } 555 556 /** The following grammar should yield an error that rule 'a' has 557 * insufficient semantic info pulled from 'b'. 558 */ testIncompleteSemanticHoistedContext()559 @Test public void testIncompleteSemanticHoistedContext() throws Exception { 560 ErrorQueue equeue = new ErrorQueue(); 561 ErrorManager.setErrorListener(equeue); 562 Grammar g = new Grammar( 563 "parser grammar t;\n"+ 564 "a : b | B;\n" + 565 "b : {p1}? B | B ;"); 566 String expecting = 567 ".s0-B->:s1=>1\n"; 568 checkDecision(g, 1, expecting, new int[] {2}, 569 new int[] {1,2}, "B", new int[] {1}, null, 3, false); 570 } 571 testIncompleteSemanticHoistedContextk2()572 @Test public void testIncompleteSemanticHoistedContextk2() throws Exception { 573 ErrorQueue equeue = new ErrorQueue(); 574 ErrorManager.setErrorListener(equeue); 575 Grammar g = new Grammar( 576 "parser grammar t;\n"+ 577 "a : b | A B;\n" + 578 "b : {p1}? A B | A B ;"); 579 String expecting = 580 ".s0-A->.s1\n" + 581 ".s1-B->:s2=>1\n"; 582 checkDecision(g, 1, expecting, new int[] {2}, 583 new int[] {1,2}, "A B", new int[] {1}, null, 3, false); 584 } 585 testIncompleteSemanticHoistedContextInFOLLOW()586 @Test public void testIncompleteSemanticHoistedContextInFOLLOW() throws Exception { 587 ErrorQueue equeue = new ErrorQueue(); 588 ErrorManager.setErrorListener(equeue); 589 Grammar g = new Grammar( 590 "parser grammar t;\n"+ 591 "options {k=1;}\n" + // limit to k=1 because it's LL(2); force pred hoist 592 "a : A? ;\n" + // need FOLLOW 593 "b : X a {p1}? A | Y a A ;"); // only one A is covered 594 String expecting = 595 ".s0-A->:s1=>1\n"; // s0-EOF->s2 branch pruned during optimization 596 checkDecision(g, 1, expecting, new int[] {2}, 597 new int[] {1,2}, "A", new int[] {2}, null, 3, false); 598 } 599 testIncompleteSemanticHoistedContextInFOLLOWk2()600 @Test public void testIncompleteSemanticHoistedContextInFOLLOWk2() throws Exception { 601 ErrorQueue equeue = new ErrorQueue(); 602 ErrorManager.setErrorListener(equeue); 603 Grammar g = new Grammar( 604 "parser grammar t;\n"+ 605 "a : (A B)? ;\n" + // need FOLLOW 606 "b : X a {p1}? A B | Y a A B | Z a ;"); // only first alt is covered 607 String expecting = 608 ".s0-A->.s1\n" + 609 ".s0-EOF->:s3=>2\n" + 610 ".s1-B->:s2=>1\n"; 611 checkDecision(g, 1, expecting, null, 612 new int[] {1,2}, "A B", new int[] {2}, null, 2, false); 613 } 614 testIncompleteSemanticHoistedContextInFOLLOWDueToHiddenPred()615 @Test public void testIncompleteSemanticHoistedContextInFOLLOWDueToHiddenPred() throws Exception { 616 ErrorQueue equeue = new ErrorQueue(); 617 ErrorManager.setErrorListener(equeue); 618 Grammar g = new Grammar( 619 "parser grammar t;\n"+ 620 "a : (A B)? ;\n" + // need FOLLOW 621 "b : X a {p1}? A B | Y a {a1} {p2}? A B | Z a ;"); // only first alt is covered 622 String expecting = 623 ".s0-A->.s1\n" + 624 ".s0-EOF->:s3=>2\n" + 625 ".s1-B->:s2=>1\n"; 626 checkDecision(g, 1, expecting, null, 627 new int[] {1,2}, "A B", new int[] {2}, null, 2, true); 628 } 629 630 /** The following grammar should yield an error that rule 'a' has 631 * insufficient semantic info pulled from 'b'. This is the same 632 * as the previous case except that the D prevents the B path from 633 * "pinching" together into a single NFA state. 634 * 635 * This test also demonstrates that just because B D could predict 636 * alt 1 in rule 'a', it is unnecessary to continue NFA->DFA 637 * conversion to include an edge for D. Alt 1 is the only possible 638 * prediction because we resolve the ambiguity by choosing alt 1. 639 */ testIncompleteSemanticHoistedContext2()640 @Test public void testIncompleteSemanticHoistedContext2() throws Exception { 641 ErrorQueue equeue = new ErrorQueue(); 642 ErrorManager.setErrorListener(equeue); 643 Grammar g = new Grammar( 644 "parser grammar t;\n"+ 645 "a : b | B;\n" + 646 "b : {p1}? B | B D ;"); 647 String expecting = 648 ".s0-B->:s1=>1\n"; 649 checkDecision(g, 1, expecting, new int[] {2}, 650 new int[] {1,2}, "B", new int[] {1}, 651 null, 3, false); 652 } 653 testTooFewSemanticPredicates()654 @Test public void testTooFewSemanticPredicates() throws Exception { 655 Grammar g = new Grammar( 656 "parser grammar t;\n"+ 657 "a : {p1}? A | A | A ;"); 658 String expecting = 659 ".s0-A->:s1=>1\n"; 660 checkDecision(g, 1, expecting, new int[] {2,3}, 661 new int[] {1,2,3}, "A", 662 null, null, 2, false); 663 } 664 testPredWithK1()665 @Test public void testPredWithK1() throws Exception { 666 Grammar g = new Grammar( 667 "\tlexer grammar TLexer;\n" + 668 "A\n" + 669 "options {\n" + 670 " k=1;\n" + 671 "}\n" + 672 " : {p1}? ('x')+ '.'\n" + 673 " | {p2}? ('x')+ '.'\n" + 674 " ;\n"); 675 String expecting = 676 ".s0-'x'->.s1\n" + 677 ".s1-{p1}?->:s2=>1\n" + 678 ".s1-{p2}?->:s3=>2\n"; 679 int[] unreachableAlts = null; 680 int[] nonDetAlts = null; 681 String ambigInput = null; 682 int[] insufficientPredAlts = null; 683 int[] danglingAlts = null; 684 int numWarnings = 0; 685 checkDecision(g, 3, expecting, unreachableAlts, 686 nonDetAlts, ambigInput, insufficientPredAlts, 687 danglingAlts, numWarnings, false); 688 } 689 testPredWithArbitraryLookahead()690 @Test public void testPredWithArbitraryLookahead() throws Exception { 691 Grammar g = new Grammar( 692 "\tlexer grammar TLexer;\n" + 693 "A : {p1}? ('x')+ '.'\n" + 694 " | {p2}? ('x')+ '.'\n" + 695 " ;\n"); 696 String expecting = 697 ".s0-'x'->.s1\n" + 698 ".s1-'.'->.s2\n" + 699 ".s1-'x'->.s1\n" + 700 ".s2-{p1}?->:s3=>1\n" + 701 ".s2-{p2}?->:s4=>2\n"; 702 int[] unreachableAlts = null; 703 int[] nonDetAlts = null; 704 String ambigInput = null; 705 int[] insufficientPredAlts = null; 706 int[] danglingAlts = null; 707 int numWarnings = 0; 708 checkDecision(g, 3, expecting, unreachableAlts, 709 nonDetAlts, ambigInput, insufficientPredAlts, 710 danglingAlts, numWarnings, false); 711 } 712 713 @Test 714 /** For a DFA state with lots of configurations that have the same 715 * predicate, don't just OR them all together as it's a waste to 716 * test a||a||b||a||a etc... ANTLR makes a unique set and THEN 717 * OR's them together. 718 */ testUniquePredicateOR()719 public void testUniquePredicateOR() throws Exception { 720 Grammar g = new Grammar( 721 "parser grammar v;\n" + 722 "\n" + 723 "a : {a}? b\n" + 724 " | {b}? b\n" + 725 " ;\n" + 726 "\n" + 727 "b : {c}? (X)+ ;\n" + 728 "\n" + 729 "c : a\n" + 730 " | b\n" + 731 " ;\n"); 732 String expecting = 733 ".s0-X->.s1\n" + 734 ".s1-{((a&&c)||(b&&c))}?->:s2=>1\n" + 735 ".s1-{c}?->:s3=>2\n"; 736 int[] unreachableAlts = null; 737 int[] nonDetAlts = null; 738 String ambigInput = null; 739 int[] insufficientPredAlts = null; 740 int[] danglingAlts = null; 741 int numWarnings = 0; 742 checkDecision(g, 3, expecting, unreachableAlts, 743 nonDetAlts, ambigInput, insufficientPredAlts, 744 danglingAlts, numWarnings, false); 745 } 746 747 @Test testSemanticContextPreventsEarlyTerminationOfClosure()748 public void testSemanticContextPreventsEarlyTerminationOfClosure() throws Exception { 749 Grammar g = new Grammar( 750 "parser grammar T;\n" + 751 "a : loop SEMI | ID SEMI\n" + 752 " ;\n" + 753 "loop\n" + 754 " : {while}? ID\n" + 755 " | {do}? ID\n" + 756 " | {for}? ID\n" + 757 " ;"); 758 String expecting = 759 ".s0-ID->.s1\n" + 760 ".s1-SEMI->.s2\n" + 761 ".s2-{(for||do||while)}?->:s3=>1\n" + 762 ".s2-{true}?->:s4=>2\n"; 763 checkDecision(g, 1, expecting, null, null, null, null, null, 0, false); 764 } 765 766 // S U P P O R T 767 _template()768 public void _template() throws Exception { 769 Grammar g = new Grammar( 770 "parser grammar t;\n"+ 771 "a : A | B;"); 772 String expecting = 773 "\n"; 774 int[] unreachableAlts = null; 775 int[] nonDetAlts = new int[] {1,2}; 776 String ambigInput = "L ID R"; 777 int[] insufficientPredAlts = new int[] {1}; 778 int[] danglingAlts = null; 779 int numWarnings = 1; 780 checkDecision(g, 1, expecting, unreachableAlts, 781 nonDetAlts, ambigInput, insufficientPredAlts, 782 danglingAlts, numWarnings, false); 783 } 784 checkDecision(Grammar g, int decision, String expecting, int[] expectingUnreachableAlts, int[] expectingNonDetAlts, String expectingAmbigInput, int[] expectingInsufficientPredAlts, int[] expectingDanglingAlts, int expectingNumWarnings, boolean hasPredHiddenByAction)785 protected void checkDecision(Grammar g, 786 int decision, 787 String expecting, 788 int[] expectingUnreachableAlts, 789 int[] expectingNonDetAlts, 790 String expectingAmbigInput, 791 int[] expectingInsufficientPredAlts, 792 int[] expectingDanglingAlts, 793 int expectingNumWarnings, 794 boolean hasPredHiddenByAction) 795 throws Exception 796 { 797 DecisionProbe.verbose=true; // make sure we get all error info 798 ErrorQueue equeue = new ErrorQueue(); 799 ErrorManager.setErrorListener(equeue); 800 CodeGenerator generator = new CodeGenerator(newTool(), g, "Java"); 801 g.setCodeGenerator(generator); 802 // mimic actions of org.antlr.Tool first time for grammar g 803 if ( g.getNumberOfDecisions()==0 ) { 804 g.buildNFA(); 805 g.createLookaheadDFAs(false); 806 } 807 808 if ( equeue.size()!=expectingNumWarnings ) { 809 System.err.println("Warnings issued: "+equeue); 810 } 811 812 assertEquals("unexpected number of expected problems", 813 expectingNumWarnings, equeue.size()); 814 815 DFA dfa = g.getLookaheadDFA(decision); 816 FASerializer serializer = new FASerializer(g); 817 String result = serializer.serialize(dfa.startState); 818 //System.out.print(result); 819 List unreachableAlts = dfa.getUnreachableAlts(); 820 821 // make sure unreachable alts are as expected 822 if ( expectingUnreachableAlts!=null ) { 823 BitSet s = new BitSet(); 824 s.addAll(expectingUnreachableAlts); 825 BitSet s2 = new BitSet(); 826 s2.addAll(unreachableAlts); 827 assertEquals("unreachable alts mismatch", s, s2); 828 } 829 else { 830 assertEquals("unreachable alts mismatch", 0, 831 unreachableAlts!=null?unreachableAlts.size():0); 832 } 833 834 // check conflicting input 835 if ( expectingAmbigInput!=null ) { 836 // first, find nondet message 837 Message msg = getNonDeterminismMessage(equeue.warnings); 838 assertNotNull("no nondeterminism warning?", msg); 839 assertTrue("expecting nondeterminism; found "+msg.getClass().getName(), 840 msg instanceof GrammarNonDeterminismMessage); 841 GrammarNonDeterminismMessage nondetMsg = 842 getNonDeterminismMessage(equeue.warnings); 843 List labels = 844 nondetMsg.probe.getSampleNonDeterministicInputSequence(nondetMsg.problemState); 845 String input = nondetMsg.probe.getInputSequenceDisplay(labels); 846 assertEquals(expectingAmbigInput, input); 847 } 848 849 // check nondet alts 850 if ( expectingNonDetAlts!=null ) { 851 GrammarNonDeterminismMessage nondetMsg = 852 getNonDeterminismMessage(equeue.warnings); 853 assertNotNull("found no nondet alts; expecting: "+ 854 str(expectingNonDetAlts), nondetMsg); 855 List nonDetAlts = 856 nondetMsg.probe.getNonDeterministicAltsForState(nondetMsg.problemState); 857 // compare nonDetAlts with expectingNonDetAlts 858 BitSet s = new BitSet(); 859 s.addAll(expectingNonDetAlts); 860 BitSet s2 = new BitSet(); 861 s2.addAll(nonDetAlts); 862 assertEquals("nondet alts mismatch", s, s2); 863 assertEquals("mismatch between expected hasPredHiddenByAction", hasPredHiddenByAction, 864 nondetMsg.problemState.dfa.hasPredicateBlockedByAction); 865 } 866 else { 867 // not expecting any nondet alts, make sure there are none 868 GrammarNonDeterminismMessage nondetMsg = 869 getNonDeterminismMessage(equeue.warnings); 870 assertNull("found nondet alts, but expecting none", nondetMsg); 871 } 872 873 if ( expectingInsufficientPredAlts!=null ) { 874 GrammarInsufficientPredicatesMessage insuffPredMsg = 875 getGrammarInsufficientPredicatesMessage(equeue.warnings); 876 assertNotNull("found no GrammarInsufficientPredicatesMessage alts; expecting: "+ 877 str(expectingNonDetAlts), insuffPredMsg); 878 Map<Integer, Set<Token>> locations = insuffPredMsg.altToLocations; 879 Set actualAlts = locations.keySet(); 880 BitSet s = new BitSet(); 881 s.addAll(expectingInsufficientPredAlts); 882 BitSet s2 = new BitSet(); 883 s2.addAll(actualAlts); 884 assertEquals("mismatch between insufficiently covered alts", s, s2); 885 assertEquals("mismatch between expected hasPredHiddenByAction", hasPredHiddenByAction, 886 insuffPredMsg.problemState.dfa.hasPredicateBlockedByAction); 887 } 888 else { 889 // not expecting any nondet alts, make sure there are none 890 GrammarInsufficientPredicatesMessage nondetMsg = 891 getGrammarInsufficientPredicatesMessage(equeue.warnings); 892 if ( nondetMsg!=null ) { 893 System.out.println(equeue.warnings); 894 } 895 assertNull("found insufficiently covered alts, but expecting none", nondetMsg); 896 } 897 898 assertEquals(expecting, result); 899 } 900 getNonDeterminismMessage(List warnings)901 protected GrammarNonDeterminismMessage getNonDeterminismMessage(List warnings) { 902 for (int i = 0; i < warnings.size(); i++) { 903 Message m = (Message) warnings.get(i); 904 if ( m instanceof GrammarNonDeterminismMessage ) { 905 return (GrammarNonDeterminismMessage)m; 906 } 907 } 908 return null; 909 } 910 getGrammarInsufficientPredicatesMessage(List warnings)911 protected GrammarInsufficientPredicatesMessage getGrammarInsufficientPredicatesMessage(List warnings) { 912 for (int i = 0; i < warnings.size(); i++) { 913 Message m = (Message) warnings.get(i); 914 if ( m instanceof GrammarInsufficientPredicatesMessage ) { 915 return (GrammarInsufficientPredicatesMessage)m; 916 } 917 } 918 return null; 919 } 920 str(int[] elements)921 protected String str(int[] elements) { 922 StringBuffer buf = new StringBuffer(); 923 for (int i = 0; i < elements.length; i++) { 924 if ( i>0 ) { 925 buf.append(", "); 926 } 927 int element = elements[i]; 928 buf.append(element); 929 } 930 return buf.toString(); 931 } 932 } 933