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.State; 31 import org.antlr.tool.FASerializer; 32 import org.antlr.tool.Grammar; 33 import org.junit.Test; 34 35 public class TestNFAConstruction extends BaseTest { 36 37 /** Public default constructor used by TestRig */ 38 public TestNFAConstruction() { 39 } 40 41 @Test public void testA() throws Exception { 42 Grammar g = new Grammar( 43 "parser grammar P;\n"+ 44 "a : A;"); 45 String expecting = 46 ".s0->.s1\n" + 47 ".s1->.s2\n" + 48 ".s2-A->.s3\n" + 49 ".s3->:s4\n" + 50 ":s4-EOF->.s5\n"; 51 checkRule(g, "a", expecting); 52 } 53 54 @Test public void testAB() throws Exception { 55 Grammar g = new Grammar( 56 "parser grammar P;\n"+ 57 "a : A B ;"); 58 String expecting = 59 ".s0->.s1\n" + 60 ".s1->.s2\n" + 61 ".s2-A->.s3\n" + 62 ".s3-B->.s4\n" + 63 ".s4->:s5\n" + 64 ":s5-EOF->.s6\n"; 65 checkRule(g, "a", expecting); 66 } 67 68 @Test public void testAorB() throws Exception { 69 Grammar g = new Grammar( 70 "parser grammar P;\n"+ 71 "a : A | B {;} ;"); 72 /* expecting (0)--Ep-->(1)--Ep-->(2)--A-->(3)--Ep-->(4)--Ep-->(5,end) 73 | ^ 74 (6)--Ep-->(7)--B-->(8)--------| 75 */ 76 String expecting = 77 ".s0->.s1\n" + 78 ".s1->.s2\n" + 79 ".s1->.s7\n" + 80 ".s10->.s4\n" + 81 ".s2-A->.s3\n" + 82 ".s3->.s4\n" + 83 ".s4->:s5\n" + 84 ".s7->.s8\n" + 85 ".s8-B->.s9\n" + 86 ".s9-{}->.s10\n" + 87 ":s5-EOF->.s6\n"; 88 checkRule(g, "a", expecting); 89 } 90 91 @Test public void testRangeOrRange() throws Exception { 92 Grammar g = new Grammar( 93 "lexer grammar P;\n"+ 94 "A : ('a'..'c' 'h' | 'q' 'j'..'l') ;" 95 ); 96 String expecting = 97 ".s0->.s1\n" + 98 ".s1->.s2\n" + 99 ".s10-'q'->.s11\n" + 100 ".s11-'j'..'l'->.s12\n" + 101 ".s12->.s6\n" + 102 ".s2->.s3\n" + 103 ".s2->.s9\n" + 104 ".s3-'a'..'c'->.s4\n" + 105 ".s4-'h'->.s5\n" + 106 ".s5->.s6\n" + 107 ".s6->:s7\n" + 108 ".s9->.s10\n" + 109 ":s7-<EOT>->.s8\n"; 110 checkRule(g, "A", expecting); 111 } 112 113 @Test public void testRange() throws Exception { 114 Grammar g = new Grammar( 115 "lexer grammar P;\n"+ 116 "A : 'a'..'c' ;" 117 ); 118 String expecting = 119 ".s0->.s1\n" + 120 ".s1->.s2\n" + 121 ".s2-'a'..'c'->.s3\n" + 122 ".s3->:s4\n" + 123 ":s4-<EOT>->.s5\n"; 124 checkRule(g, "A", expecting); 125 } 126 127 @Test public void testCharSetInParser() throws Exception { 128 Grammar g = new Grammar( 129 "grammar P;\n"+ 130 "a : A|'b' ;" 131 ); 132 String expecting = 133 ".s0->.s1\n" + 134 ".s1->.s2\n" + 135 ".s2-A..'b'->.s3\n" + 136 ".s3->:s4\n" + 137 ":s4-EOF->.s5\n"; 138 checkRule(g, "a", expecting); 139 } 140 141 @Test public void testABorCD() throws Exception { 142 Grammar g = new Grammar( 143 "parser grammar P;\n"+ 144 "a : A B | C D;"); 145 String expecting = 146 ".s0->.s1\n" + 147 ".s1->.s2\n" + 148 ".s1->.s8\n" + 149 ".s10-D->.s11\n" + 150 ".s11->.s5\n" + 151 ".s2-A->.s3\n" + 152 ".s3-B->.s4\n" + 153 ".s4->.s5\n" + 154 ".s5->:s6\n" + 155 ".s8->.s9\n" + 156 ".s9-C->.s10\n" + 157 ":s6-EOF->.s7\n"; 158 checkRule(g, "a", expecting); 159 } 160 161 @Test public void testbA() throws Exception { 162 Grammar g = new Grammar( 163 "parser grammar P;\n"+ 164 "a : b A ;\n"+ 165 "b : B ;"); 166 String expecting = 167 ".s0->.s1\n" + 168 ".s1->.s2\n" + 169 ".s2->.s3\n" + 170 ".s3->.s4\n" + 171 ".s4->.s5\n" + 172 ".s5-B->.s6\n" + 173 ".s6->:s7\n" + 174 ".s8-A->.s9\n" + 175 ".s9->:s10\n" + 176 ":s10-EOF->.s11\n" + 177 ":s7->.s8\n"; 178 checkRule(g, "a", expecting); 179 } 180 181 @Test public void testbA_bC() throws Exception { 182 Grammar g = new Grammar( 183 "parser grammar P;\n"+ 184 "a : b A ;\n"+ 185 "b : B ;\n"+ 186 "c : b C;"); 187 String expecting = 188 ".s0->.s1\n" + 189 ".s1->.s2\n" + 190 ".s12->.s13\n" + 191 ".s13-C->.s14\n" + 192 ".s14->:s15\n" + 193 ".s2->.s3\n" + 194 ".s3->.s4\n" + 195 ".s4->.s5\n" + 196 ".s5-B->.s6\n" + 197 ".s6->:s7\n" + 198 ".s8-A->.s9\n" + 199 ".s9->:s10\n" + 200 ":s10-EOF->.s11\n" + 201 ":s15-EOF->.s16\n" + 202 ":s7->.s12\n" + 203 ":s7->.s8\n"; 204 checkRule(g, "a", expecting); 205 } 206 207 @Test public void testAorEpsilon() throws Exception { 208 Grammar g = new Grammar( 209 "parser grammar P;\n"+ 210 "a : A | ;"); 211 /* expecting (0)--Ep-->(1)--Ep-->(2)--A-->(3)--Ep-->(4)--Ep-->(5,end) 212 | ^ 213 (6)--Ep-->(7)--Ep-->(8)-------| 214 */ 215 String expecting = 216 ".s0->.s1\n" + 217 ".s1->.s2\n" + 218 ".s1->.s7\n" + 219 ".s2-A->.s3\n" + 220 ".s3->.s4\n" + 221 ".s4->:s5\n" + 222 ".s7->.s8\n" + 223 ".s8->.s9\n" + 224 ".s9->.s4\n" + 225 ":s5-EOF->.s6\n"; 226 checkRule(g, "a", expecting); 227 } 228 229 @Test public void testAOptional() throws Exception { 230 Grammar g = new Grammar( 231 "parser grammar P;\n"+ 232 "a : (A)?;"); 233 String expecting = 234 ".s0->.s1\n" + 235 ".s1->.s2\n" + 236 ".s2->.s3\n" + 237 ".s2->.s8\n" + 238 ".s3-A->.s4\n" + 239 ".s4->.s5\n" + 240 ".s5->:s6\n" + 241 ".s8->.s5\n" + 242 ":s6-EOF->.s7\n"; 243 checkRule(g, "a", expecting); 244 } 245 246 @Test public void testNakedAoptional() throws Exception { 247 Grammar g = new Grammar( 248 "parser grammar P;\n"+ 249 "a : A?;"); 250 String expecting = 251 ".s0->.s1\n" + 252 ".s1->.s2\n" + 253 ".s2->.s3\n" + 254 ".s2->.s8\n" + 255 ".s3-A->.s4\n" + 256 ".s4->.s5\n" + 257 ".s5->:s6\n" + 258 ".s8->.s5\n" + 259 ":s6-EOF->.s7\n"; 260 checkRule(g, "a", expecting); 261 } 262 263 @Test public void testAorBthenC() throws Exception { 264 Grammar g = new Grammar( 265 "parser grammar P;\n"+ 266 "a : (A | B) C;"); 267 /* expecting 268 269 (0)--Ep-->(1)--Ep-->(2)--A-->(3)--Ep-->(4)--Ep-->(5)--C-->(6)--Ep-->(7,end) 270 | ^ 271 (8)--Ep-->(9)--B-->(10)-------| 272 */ 273 } 274 275 @Test public void testAplus() throws Exception { 276 Grammar g = new Grammar( 277 "parser grammar P;\n"+ 278 "a : (A)+;"); 279 String expecting = 280 ".s0->.s1\n" + 281 ".s1->.s2\n" + 282 ".s2->.s3\n" + 283 ".s3->.s4\n" + 284 ".s4-A->.s5\n" + 285 ".s5->.s3\n" + 286 ".s5->.s6\n" + 287 ".s6->:s7\n" + 288 ":s7-EOF->.s8\n"; 289 checkRule(g, "a", expecting); 290 } 291 292 @Test public void testNakedAplus() throws Exception { 293 Grammar g = new Grammar( 294 "parser grammar P;\n"+ 295 "a : A+;"); 296 String expecting = 297 ".s0->.s1\n" + 298 ".s1->.s2\n" + 299 ".s2->.s3\n" + 300 ".s3->.s4\n" + 301 ".s4-A->.s5\n" + 302 ".s5->.s3\n" + 303 ".s5->.s6\n" + 304 ".s6->:s7\n" + 305 ":s7-EOF->.s8\n"; 306 checkRule(g, "a", expecting); 307 } 308 309 @Test public void testAplusNonGreedy() throws Exception { 310 Grammar g = new Grammar( 311 "lexer grammar t;\n"+ 312 "A : (options {greedy=false;}:'0'..'9')+ ;\n"); 313 String expecting = 314 ".s0->.s1\n" + 315 ".s1->.s2\n" + 316 ".s2->.s3\n" + 317 ".s3->.s4\n" + 318 ".s4-'0'..'9'->.s5\n" + 319 ".s5->.s3\n" + 320 ".s5->.s6\n" + 321 ".s6->:s7\n" + 322 ":s7-<EOT>->.s8\n"; 323 checkRule(g, "A", expecting); 324 } 325 326 @Test public void testAorBplus() throws Exception { 327 Grammar g = new Grammar( 328 "parser grammar P;\n"+ 329 "a : (A | B{action})+ ;"); 330 String expecting = 331 ".s0->.s1\n" + 332 ".s1->.s2\n" + 333 ".s10->.s11\n" + 334 ".s11-B->.s12\n" + 335 ".s12-{}->.s13\n" + 336 ".s13->.s6\n" + 337 ".s2->.s3\n" + 338 ".s3->.s10\n" + 339 ".s3->.s4\n" + 340 ".s4-A->.s5\n" + 341 ".s5->.s6\n" + 342 ".s6->.s3\n" + 343 ".s6->.s7\n" + 344 ".s7->:s8\n" + 345 ":s8-EOF->.s9\n"; 346 checkRule(g, "a", expecting); 347 } 348 349 @Test public void testAorBorEmptyPlus() throws Exception { 350 Grammar g = new Grammar( 351 "parser grammar P;\n"+ 352 "a : (A | B | )+ ;"); 353 String expecting = 354 ".s0->.s1\n" + 355 ".s1->.s2\n" + 356 ".s10->.s11\n" + 357 ".s10->.s13\n" + 358 ".s11-B->.s12\n" + 359 ".s12->.s6\n" + 360 ".s13->.s14\n" + 361 ".s14->.s15\n" + 362 ".s15->.s6\n" + 363 ".s2->.s3\n" + 364 ".s3->.s10\n" + 365 ".s3->.s4\n" + 366 ".s4-A->.s5\n" + 367 ".s5->.s6\n" + 368 ".s6->.s3\n" + 369 ".s6->.s7\n" + 370 ".s7->:s8\n" + 371 ":s8-EOF->.s9\n"; 372 checkRule(g, "a", expecting); 373 } 374 375 @Test public void testAStar() throws Exception { 376 Grammar g = new Grammar( 377 "parser grammar P;\n"+ 378 "a : (A)*;"); 379 String expecting = 380 ".s0->.s1\n" + 381 ".s1->.s2\n" + 382 ".s2->.s3\n" + 383 ".s2->.s9\n" + 384 ".s3->.s4\n" + 385 ".s4-A->.s5\n" + 386 ".s5->.s3\n" + 387 ".s5->.s6\n" + 388 ".s6->:s7\n" + 389 ".s9->.s6\n" + 390 ":s7-EOF->.s8\n"; 391 checkRule(g, "a", expecting); 392 } 393 394 @Test public void testNestedAstar() throws Exception { 395 Grammar g = new Grammar( 396 "parser grammar P;\n"+ 397 "a : (A*)*;"); 398 String expecting = 399 ".s0->.s1\n" + 400 ".s1->.s2\n" + 401 ".s10->:s11\n" + 402 ".s13->.s8\n" + 403 ".s14->.s10\n" + 404 ".s2->.s14\n" + 405 ".s2->.s3\n" + 406 ".s3->.s4\n" + 407 ".s4->.s13\n" + 408 ".s4->.s5\n" + 409 ".s5->.s6\n" + 410 ".s6-A->.s7\n" + 411 ".s7->.s5\n" + 412 ".s7->.s8\n" + 413 ".s8->.s9\n" + 414 ".s9->.s10\n" + 415 ".s9->.s3\n" + 416 ":s11-EOF->.s12\n"; 417 checkRule(g, "a", expecting); 418 } 419 420 @Test public void testPlusNestedInStar() throws Exception { 421 Grammar g = new Grammar( 422 "parser grammar P;\n"+ 423 "a : (A+)*;"); 424 String expecting = 425 ".s0->.s1\n" + 426 ".s1->.s2\n" + 427 ".s10->:s11\n" + 428 ".s13->.s10\n" + 429 ".s2->.s13\n" + 430 ".s2->.s3\n" + 431 ".s3->.s4\n" + 432 ".s4->.s5\n" + 433 ".s5->.s6\n" + 434 ".s6-A->.s7\n" + 435 ".s7->.s5\n" + 436 ".s7->.s8\n" + 437 ".s8->.s9\n" + 438 ".s9->.s10\n" + 439 ".s9->.s3\n" + 440 ":s11-EOF->.s12\n"; 441 checkRule(g, "a", expecting); 442 } 443 444 @Test public void testStarNestedInPlus() throws Exception { 445 Grammar g = new Grammar( 446 "parser grammar P;\n"+ 447 "a : (A*)+;"); 448 String expecting = 449 ".s0->.s1\n" + 450 ".s1->.s2\n" + 451 ".s10->:s11\n" + 452 ".s13->.s8\n" + 453 ".s2->.s3\n" + 454 ".s3->.s4\n" + 455 ".s4->.s13\n" + 456 ".s4->.s5\n" + 457 ".s5->.s6\n" + 458 ".s6-A->.s7\n" + 459 ".s7->.s5\n" + 460 ".s7->.s8\n" + 461 ".s8->.s9\n" + 462 ".s9->.s10\n" + 463 ".s9->.s3\n" + 464 ":s11-EOF->.s12\n"; 465 checkRule(g, "a", expecting); 466 } 467 468 @Test public void testNakedAstar() throws Exception { 469 Grammar g = new Grammar( 470 "parser grammar P;\n"+ 471 "a : A*;"); 472 String expecting = 473 ".s0->.s1\n" + 474 ".s1->.s2\n" + 475 ".s2->.s3\n" + 476 ".s2->.s9\n" + 477 ".s3->.s4\n" + 478 ".s4-A->.s5\n" + 479 ".s5->.s3\n" + 480 ".s5->.s6\n" + 481 ".s6->:s7\n" + 482 ".s9->.s6\n" + 483 ":s7-EOF->.s8\n"; 484 checkRule(g, "a", expecting); 485 } 486 487 @Test public void testAorBstar() throws Exception { 488 Grammar g = new Grammar( 489 "parser grammar P;\n"+ 490 "a : (A | B{action})* ;"); 491 String expecting = 492 ".s0->.s1\n" + 493 ".s1->.s2\n" + 494 ".s10->.s11\n" + 495 ".s11-B->.s12\n" + 496 ".s12-{}->.s13\n" + 497 ".s13->.s6\n" + 498 ".s14->.s7\n" + 499 ".s2->.s14\n" + 500 ".s2->.s3\n" + 501 ".s3->.s10\n" + 502 ".s3->.s4\n" + 503 ".s4-A->.s5\n" + 504 ".s5->.s6\n" + 505 ".s6->.s3\n" + 506 ".s6->.s7\n" + 507 ".s7->:s8\n" + 508 ":s8-EOF->.s9\n"; 509 checkRule(g, "a", expecting); 510 } 511 512 @Test public void testAorBOptionalSubrule() throws Exception { 513 Grammar g = new Grammar( 514 "parser grammar P;\n"+ 515 "a : ( A | B )? ;"); 516 String expecting = 517 ".s0->.s1\n" + 518 ".s1->.s2\n" + 519 ".s2->.s3\n" + 520 ".s2->.s8\n" + 521 ".s3-A..B->.s4\n" + 522 ".s4->.s5\n" + 523 ".s5->:s6\n" + 524 ".s8->.s5\n" + 525 ":s6-EOF->.s7\n"; 526 checkRule(g, "a", expecting); 527 } 528 529 @Test public void testPredicatedAorB() throws Exception { 530 Grammar g = new Grammar( 531 "parser grammar P;\n"+ 532 "a : {p1}? A | {p2}? B ;"); 533 String expecting = 534 ".s0->.s1\n" + 535 ".s1->.s2\n" + 536 ".s1->.s8\n" + 537 ".s10-B->.s11\n" + 538 ".s11->.s5\n" + 539 ".s2-{p1}?->.s3\n" + 540 ".s3-A->.s4\n" + 541 ".s4->.s5\n" + 542 ".s5->:s6\n" + 543 ".s8->.s9\n" + 544 ".s9-{p2}?->.s10\n" + 545 ":s6-EOF->.s7\n"; 546 checkRule(g, "a", expecting); 547 } 548 549 @Test public void testMultiplePredicates() throws Exception { 550 Grammar g = new Grammar( 551 "parser grammar P;\n"+ 552 "a : {p1}? {p1a}? A | {p2}? B | {p3} b;\n" + 553 "b : {p4}? B ;"); 554 String expecting = 555 ".s0->.s1\n" + 556 ".s1->.s2\n" + 557 ".s1->.s9\n" + 558 ".s10-{p2}?->.s11\n" + 559 ".s11-B->.s12\n" + 560 ".s12->.s6\n" + 561 ".s13->.s14\n" + 562 ".s14-{}->.s15\n" + 563 ".s15->.s16\n" + 564 ".s16->.s17\n" + 565 ".s17->.s18\n" + 566 ".s18-{p4}?->.s19\n" + 567 ".s19-B->.s20\n" + 568 ".s2-{p1}?->.s3\n" + 569 ".s20->:s21\n" + 570 ".s22->.s6\n" + 571 ".s3-{p1a}?->.s4\n" + 572 ".s4-A->.s5\n" + 573 ".s5->.s6\n" + 574 ".s6->:s7\n" + 575 ".s9->.s10\n" + 576 ".s9->.s13\n" + 577 ":s21->.s22\n" + 578 ":s7-EOF->.s8\n"; 579 checkRule(g, "a", expecting); 580 } 581 582 @Test public void testSets() throws Exception { 583 Grammar g = new Grammar( 584 "parser grammar P;\n"+ 585 "a : ( A | B )+ ;\n" + 586 "b : ( A | B{;} )+ ;\n" + 587 "c : (A|B) (A|B) ;\n" + 588 "d : ( A | B )* ;\n" + 589 "e : ( A | B )? ;"); 590 String expecting = 591 ".s0->.s1\n" + 592 ".s1->.s2\n" + 593 ".s2->.s3\n" + 594 ".s3->.s4\n" + 595 ".s4-A..B->.s5\n" + 596 ".s5->.s3\n" + 597 ".s5->.s6\n" + 598 ".s6->:s7\n" + 599 ":s7-EOF->.s8\n"; 600 checkRule(g, "a", expecting); 601 expecting = 602 ".s0->.s1\n" + 603 ".s1->.s2\n" + 604 ".s10->.s11\n" + 605 ".s11-B->.s12\n" + 606 ".s12-{}->.s13\n" + 607 ".s13->.s6\n" + 608 ".s2->.s3\n" + 609 ".s3->.s10\n" + 610 ".s3->.s4\n" + 611 ".s4-A->.s5\n" + 612 ".s5->.s6\n" + 613 ".s6->.s3\n" + 614 ".s6->.s7\n" + 615 ".s7->:s8\n" + 616 ":s8-EOF->.s9\n"; 617 checkRule(g, "b", expecting); 618 expecting = 619 ".s0->.s1\n" + 620 ".s1->.s2\n" + 621 ".s2-A..B->.s3\n" + 622 ".s3-A..B->.s4\n" + 623 ".s4->:s5\n" + 624 ":s5-EOF->.s6\n"; 625 checkRule(g, "c", expecting); 626 expecting = 627 ".s0->.s1\n" + 628 ".s1->.s2\n" + 629 ".s2->.s3\n" + 630 ".s2->.s9\n" + 631 ".s3->.s4\n" + 632 ".s4-A..B->.s5\n" + 633 ".s5->.s3\n" + 634 ".s5->.s6\n" + 635 ".s6->:s7\n" + 636 ".s9->.s6\n" + 637 ":s7-EOF->.s8\n"; 638 checkRule(g, "d", expecting); 639 expecting = 640 ".s0->.s1\n" + 641 ".s1->.s2\n" + 642 ".s2->.s3\n" + 643 ".s2->.s8\n" + 644 ".s3-A..B->.s4\n" + 645 ".s4->.s5\n" + 646 ".s5->:s6\n" + 647 ".s8->.s5\n" + 648 ":s6-EOF->.s7\n"; 649 checkRule(g, "e", expecting); 650 } 651 652 @Test public void testNotSet() throws Exception { 653 Grammar g = new Grammar( 654 "parser grammar P;\n"+ 655 "tokens { A; B; C; }\n"+ 656 "a : ~A ;\n"); 657 String expecting = 658 ".s0->.s1\n" + 659 ".s1->.s2\n" + 660 ".s2-B..C->.s3\n" + 661 ".s3->:s4\n" + 662 ":s4-EOF->.s5\n"; 663 checkRule(g, "a", expecting); 664 665 String expectingGrammarStr = 666 "1:8: parser grammar P;\n" + 667 "a : ~ A ;"; 668 assertEquals(expectingGrammarStr, g.toString()); 669 } 670 671 @Test public void testNotSingletonBlockSet() throws Exception { 672 Grammar g = new Grammar( 673 "parser grammar P;\n"+ 674 "tokens { A; B; C; }\n"+ 675 "a : ~(A) ;\n"); 676 String expecting = 677 ".s0->.s1\n" + 678 ".s1->.s2\n" + 679 ".s2-B..C->.s3\n" + 680 ".s3->:s4\n" + 681 ":s4-EOF->.s5\n"; 682 checkRule(g, "a", expecting); 683 684 String expectingGrammarStr = 685 "1:8: parser grammar P;\n" + 686 "a : ~ ( A ) ;"; 687 assertEquals(expectingGrammarStr, g.toString()); 688 } 689 690 @Test public void testNotCharSet() throws Exception { 691 Grammar g = new Grammar( 692 "lexer grammar P;\n"+ 693 "A : ~'3' ;\n"); 694 String expecting = 695 ".s0->.s1\n" + 696 ".s1->.s2\n" + 697 ".s2-{'\\u0000'..'2', '4'..'\\uFFFF'}->.s3\n" + 698 ".s3->:s4\n" + 699 ":s4-<EOT>->.s5\n"; 700 checkRule(g, "A", expecting); 701 702 String expectingGrammarStr = 703 "1:7: lexer grammar P;\n" + 704 "A : ~ '3' ;\n"+ 705 "Tokens : A ;"; 706 assertEquals(expectingGrammarStr, g.toString()); 707 } 708 709 @Test public void testNotBlockSet() throws Exception { 710 Grammar g = new Grammar( 711 "lexer grammar P;\n"+ 712 "A : ~('3'|'b') ;\n"); 713 String expecting = 714 ".s0->.s1\n" + 715 ".s1->.s2\n" + 716 ".s2-{'\\u0000'..'2', '4'..'a', 'c'..'\\uFFFF'}->.s3\n" + 717 ".s3->:s4\n" + 718 ":s4-<EOT>->.s5\n"; 719 checkRule(g, "A", expecting); 720 721 String expectingGrammarStr = 722 "1:7: lexer grammar P;\n" + 723 "A : ~ ( '3' | 'b' ) ;\n" + 724 "Tokens : A ;"; 725 assertEquals(expectingGrammarStr, g.toString()); 726 } 727 728 @Test public void testNotSetLoop() throws Exception { 729 Grammar g = new Grammar( 730 "lexer grammar P;\n"+ 731 "A : ~('3')* ;\n"); 732 String expecting = 733 ".s0->.s1\n" + 734 ".s1->.s2\n" + 735 ".s2->.s3\n" + 736 ".s2->.s9\n" + 737 ".s3->.s4\n" + 738 ".s4-{'\\u0000'..'2', '4'..'\\uFFFF'}->.s5\n" + 739 ".s5->.s3\n" + 740 ".s5->.s6\n" + 741 ".s6->:s7\n" + 742 ".s9->.s6\n" + 743 ":s7-<EOT>->.s8\n"; 744 checkRule(g, "A", expecting); 745 746 String expectingGrammarStr = 747 "1:7: lexer grammar P;\n" + 748 "A : (~ ( '3' ) )* ;\n" + 749 "Tokens : A ;"; 750 assertEquals(expectingGrammarStr, g.toString()); 751 } 752 753 @Test public void testNotBlockSetLoop() throws Exception { 754 Grammar g = new Grammar( 755 "lexer grammar P;\n"+ 756 "A : ~('3'|'b')* ;\n"); 757 String expecting = 758 ".s0->.s1\n" + 759 ".s1->.s2\n" + 760 ".s2->.s3\n" + 761 ".s2->.s9\n" + 762 ".s3->.s4\n" + 763 ".s4-{'\\u0000'..'2', '4'..'a', 'c'..'\\uFFFF'}->.s5\n" + 764 ".s5->.s3\n" + 765 ".s5->.s6\n" + 766 ".s6->:s7\n" + 767 ".s9->.s6\n" + 768 ":s7-<EOT>->.s8\n"; 769 checkRule(g, "A", expecting); 770 771 String expectingGrammarStr = 772 "1:7: lexer grammar P;\n" + 773 "A : (~ ( '3' | 'b' ) )* ;\n" + 774 "Tokens : A ;"; 775 assertEquals(expectingGrammarStr, g.toString()); 776 } 777 778 @Test public void testSetsInCombinedGrammarSentToLexer() throws Exception { 779 // not sure this belongs in this test suite, but whatever. 780 Grammar g = new Grammar( 781 "grammar t;\n"+ 782 "A : '{' ~('}')* '}';\n"); 783 String result = g.getLexerGrammar(); 784 String expecting = 785 "lexer grammar t;" +newline + 786 "// $ANTLR src \"<string>\" 2"+newline+ 787 "A : '{' ~('}')* '}';"; 788 assertEquals(result, expecting); 789 } 790 791 @Test public void testLabeledNotSet() throws Exception { 792 Grammar g = new Grammar( 793 "parser grammar P;\n"+ 794 "tokens { A; B; C; }\n"+ 795 "a : t=~A ;\n"); 796 String expecting = 797 ".s0->.s1\n" + 798 ".s1->.s2\n" + 799 ".s2-B..C->.s3\n" + 800 ".s3->:s4\n" + 801 ":s4-EOF->.s5\n"; 802 checkRule(g, "a", expecting); 803 804 String expectingGrammarStr = 805 "1:8: parser grammar P;\n" + 806 "a : t=~ A ;"; 807 assertEquals(expectingGrammarStr, g.toString()); 808 } 809 810 @Test public void testLabeledNotCharSet() throws Exception { 811 Grammar g = new Grammar( 812 "lexer grammar P;\n"+ 813 "A : t=~'3' ;\n"); 814 String expecting = 815 ".s0->.s1\n" + 816 ".s1->.s2\n" + 817 ".s2-{'\\u0000'..'2', '4'..'\\uFFFF'}->.s3\n" + 818 ".s3->:s4\n" + 819 ":s4-<EOT>->.s5\n"; 820 checkRule(g, "A", expecting); 821 822 String expectingGrammarStr = 823 "1:7: lexer grammar P;\n" + 824 "A : t=~ '3' ;\n"+ 825 "Tokens : A ;"; 826 assertEquals(expectingGrammarStr, g.toString()); 827 } 828 829 @Test public void testLabeledNotBlockSet() throws Exception { 830 Grammar g = new Grammar( 831 "lexer grammar P;\n"+ 832 "A : t=~('3'|'b') ;\n"); 833 String expecting = 834 ".s0->.s1\n" + 835 ".s1->.s2\n" + 836 ".s2-{'\\u0000'..'2', '4'..'a', 'c'..'\\uFFFF'}->.s3\n" + 837 ".s3->:s4\n" + 838 ":s4-<EOT>->.s5\n"; 839 checkRule(g, "A", expecting); 840 841 String expectingGrammarStr = 842 "1:7: lexer grammar P;\n" + 843 "A : t=~ ( '3' | 'b' ) ;\n" + 844 "Tokens : A ;"; 845 assertEquals(expectingGrammarStr, g.toString()); 846 } 847 848 @Test public void testEscapedCharLiteral() throws Exception { 849 Grammar g = new Grammar( 850 "grammar P;\n"+ 851 "a : '\\n';"); 852 String expecting = 853 ".s0->.s1\n" + 854 ".s1->.s2\n" + 855 ".s2-'\\n'->.s3\n" + 856 ".s3->:s4\n" + 857 ":s4-EOF->.s5\n"; 858 checkRule(g, "a", expecting); 859 } 860 861 @Test public void testEscapedStringLiteral() throws Exception { 862 Grammar g = new Grammar( 863 "grammar P;\n"+ 864 "a : 'a\\nb\\u0030c\\'';"); 865 String expecting = 866 ".s0->.s1\n" + 867 ".s1->.s2\n" + 868 ".s2-'a\\nb\\u0030c\\''->.s3\n" + 869 ".s3->:s4\n" + 870 ":s4-EOF->.s5\n"; 871 checkRule(g, "a", expecting); 872 } 873 874 // AUTO BACKTRACKING STUFF 875 876 @Test public void testAutoBacktracking_RuleBlock() throws Exception { 877 Grammar g = new Grammar( 878 "grammar t;\n" + 879 "options {backtrack=true;}\n"+ 880 "a : 'a'{;}|'b';" 881 ); 882 String expecting = 883 ".s0->.s1\n" + 884 ".s1->.s2\n" + 885 ".s1->.s9\n" + 886 ".s10-'b'->.s11\n" + 887 ".s11->.s6\n" + 888 ".s2-{synpred1_t}?->.s3\n" + 889 ".s3-'a'->.s4\n" + 890 ".s4-{}->.s5\n" + 891 ".s5->.s6\n" + 892 ".s6->:s7\n" + 893 ".s9->.s10\n" + 894 ":s7-EOF->.s8\n"; 895 checkRule(g, "a", expecting); 896 } 897 898 @Test public void testAutoBacktracking_RuleSetBlock() throws Exception { 899 Grammar g = new Grammar( 900 "grammar t;\n" + 901 "options {backtrack=true;}\n"+ 902 "a : 'a'|'b';" 903 ); 904 String expecting = 905 ".s0->.s1\n" + 906 ".s1->.s2\n" + 907 ".s2-'a'..'b'->.s3\n" + 908 ".s3->:s4\n" + 909 ":s4-EOF->.s5\n"; 910 checkRule(g, "a", expecting); 911 } 912 913 @Test public void testAutoBacktracking_SimpleBlock() throws Exception { 914 Grammar g = new Grammar( 915 "grammar t;\n" + 916 "options {backtrack=true;}\n"+ 917 "a : ('a'{;}|'b') ;" 918 ); 919 String expecting = 920 ".s0->.s1\n" + 921 ".s1->.s2\n" + 922 ".s10->.s11\n" + 923 ".s11-'b'->.s12\n" + 924 ".s12->.s7\n" + 925 ".s2->.s10\n" + 926 ".s2->.s3\n" + 927 ".s3-{synpred1_t}?->.s4\n" + 928 ".s4-'a'->.s5\n" + 929 ".s5-{}->.s6\n" + 930 ".s6->.s7\n" + 931 ".s7->:s8\n" + 932 ":s8-EOF->.s9\n"; 933 checkRule(g, "a", expecting); 934 } 935 936 @Test public void testAutoBacktracking_SetBlock() throws Exception { 937 Grammar g = new Grammar( 938 "grammar t;\n" + 939 "options {backtrack=true;}\n"+ 940 "a : ('a'|'b') ;" 941 ); 942 String expecting = 943 ".s0->.s1\n" + 944 ".s1->.s2\n" + 945 ".s2-'a'..'b'->.s3\n" + 946 ".s3->:s4\n" + 947 ":s4-EOF->.s5\n"; 948 checkRule(g, "a", expecting); 949 } 950 951 @Test public void testAutoBacktracking_StarBlock() throws Exception { 952 Grammar g = new Grammar( 953 "grammar t;\n" + 954 "options {backtrack=true;}\n"+ 955 "a : ('a'{;}|'b')* ;" 956 ); 957 String expecting = 958 ".s0->.s1\n" + 959 ".s1->.s2\n" + 960 ".s12->.s13\n" + 961 ".s13-{synpred2_t}?->.s14\n" + 962 ".s14-'b'->.s15\n" + 963 ".s15->.s8\n" + 964 ".s16->.s9\n" + 965 ".s2->.s16\n" + 966 ".s2->.s3\n" + 967 ".s3->.s12\n" + 968 ".s3->.s4\n" + 969 ".s4-{synpred1_t}?->.s5\n" + 970 ".s5-'a'->.s6\n" + 971 ".s6-{}->.s7\n" + 972 ".s7->.s8\n" + 973 ".s8->.s3\n" + 974 ".s8->.s9\n" + 975 ".s9->:s10\n" + 976 ":s10-EOF->.s11\n"; 977 checkRule(g, "a", expecting); 978 } 979 980 @Test public void testAutoBacktracking_StarSetBlock_IgnoresPreds() throws Exception { 981 Grammar g = new Grammar( 982 "grammar t;\n" + 983 "options {backtrack=true;}\n"+ 984 "a : ('a'|'b')* ;" 985 ); 986 String expecting = 987 ".s0->.s1\n" + 988 ".s1->.s2\n" + 989 ".s2->.s3\n" + 990 ".s2->.s9\n" + 991 ".s3->.s4\n" + 992 ".s4-'a'..'b'->.s5\n" + 993 ".s5->.s3\n" + 994 ".s5->.s6\n" + 995 ".s6->:s7\n" + 996 ".s9->.s6\n" + 997 ":s7-EOF->.s8\n"; 998 checkRule(g, "a", expecting); 999 } 1000 1001 @Test public void testAutoBacktracking_StarSetBlock() throws Exception { 1002 Grammar g = new Grammar( 1003 "grammar t;\n" + 1004 "options {backtrack=true;}\n"+ 1005 "a : ('a'|'b'{;})* ;" 1006 ); 1007 String expecting = 1008 ".s0->.s1\n" + 1009 ".s1->.s2\n" + 1010 ".s11->.s12\n" + 1011 ".s12-{synpred2_t}?->.s13\n" + 1012 ".s13-'b'->.s14\n" + 1013 ".s14-{}->.s15\n" + 1014 ".s15->.s7\n" + 1015 ".s16->.s8\n" + 1016 ".s2->.s16\n" + 1017 ".s2->.s3\n" + 1018 ".s3->.s11\n" + 1019 ".s3->.s4\n" + 1020 ".s4-{synpred1_t}?->.s5\n" + 1021 ".s5-'a'->.s6\n" + 1022 ".s6->.s7\n" + 1023 ".s7->.s3\n" + 1024 ".s7->.s8\n" + 1025 ".s8->:s9\n" + 1026 ":s9-EOF->.s10\n"; 1027 checkRule(g, "a", expecting); 1028 } 1029 1030 @Test public void testAutoBacktracking_StarBlock1Alt() throws Exception { 1031 Grammar g = new Grammar( 1032 "grammar t;\n" + 1033 "options {backtrack=true;}\n"+ 1034 "a : ('a')* ;" 1035 ); 1036 String expecting = 1037 ".s0->.s1\n" + 1038 ".s1->.s2\n" + 1039 ".s10->.s7\n" + 1040 ".s2->.s10\n" + 1041 ".s2->.s3\n" + 1042 ".s3->.s4\n" + 1043 ".s4-{synpred1_t}?->.s5\n" + 1044 ".s5-'a'->.s6\n" + 1045 ".s6->.s3\n" + 1046 ".s6->.s7\n" + 1047 ".s7->:s8\n" + 1048 ":s8-EOF->.s9\n"; 1049 checkRule(g, "a", expecting); 1050 } 1051 1052 @Test public void testAutoBacktracking_PlusBlock() throws Exception { 1053 Grammar g = new Grammar( 1054 "grammar t;\n" + 1055 "options {backtrack=true;}\n"+ 1056 "a : ('a'{;}|'b')+ ;" 1057 ); 1058 String expecting = 1059 ".s0->.s1\n" + 1060 ".s1->.s2\n" + 1061 ".s12->.s13\n" + 1062 ".s13-{synpred2_t}?->.s14\n" + 1063 ".s14-'b'->.s15\n" + 1064 ".s15->.s8\n" + 1065 ".s2->.s3\n" + 1066 ".s3->.s12\n" + 1067 ".s3->.s4\n" + 1068 ".s4-{synpred1_t}?->.s5\n" + 1069 ".s5-'a'->.s6\n" + 1070 ".s6-{}->.s7\n" + 1071 ".s7->.s8\n" + 1072 ".s8->.s3\n" + 1073 ".s8->.s9\n" + 1074 ".s9->:s10\n" + 1075 ":s10-EOF->.s11\n"; 1076 checkRule(g, "a", expecting); 1077 } 1078 1079 @Test public void testAutoBacktracking_PlusSetBlock() throws Exception { 1080 Grammar g = new Grammar( 1081 "grammar t;\n" + 1082 "options {backtrack=true;}\n"+ 1083 "a : ('a'|'b'{;})+ ;" 1084 ); 1085 String expecting = 1086 ".s0->.s1\n" + 1087 ".s1->.s2\n" + 1088 ".s11->.s12\n" + 1089 ".s12-{synpred2_t}?->.s13\n" + 1090 ".s13-'b'->.s14\n" + 1091 ".s14-{}->.s15\n" + 1092 ".s15->.s7\n" + 1093 ".s2->.s3\n" + 1094 ".s3->.s11\n" + 1095 ".s3->.s4\n" + 1096 ".s4-{synpred1_t}?->.s5\n" + 1097 ".s5-'a'->.s6\n" + 1098 ".s6->.s7\n" + 1099 ".s7->.s3\n" + 1100 ".s7->.s8\n" + 1101 ".s8->:s9\n" + 1102 ":s9-EOF->.s10\n"; 1103 checkRule(g, "a", expecting); 1104 } 1105 1106 @Test public void testAutoBacktracking_PlusBlock1Alt() throws Exception { 1107 Grammar g = new Grammar( 1108 "grammar t;\n" + 1109 "options {backtrack=true;}\n"+ 1110 "a : ('a')+ ;" 1111 ); 1112 String expecting = 1113 ".s0->.s1\n" + 1114 ".s1->.s2\n" + 1115 ".s2->.s3\n" + 1116 ".s3->.s4\n" + 1117 ".s4-{synpred1_t}?->.s5\n" + 1118 ".s5-'a'->.s6\n" + 1119 ".s6->.s3\n" + 1120 ".s6->.s7\n" + 1121 ".s7->:s8\n" + 1122 ":s8-EOF->.s9\n"; 1123 checkRule(g, "a", expecting); 1124 } 1125 1126 @Test public void testAutoBacktracking_OptionalBlock2Alts() throws Exception { 1127 Grammar g = new Grammar( 1128 "grammar t;\n" + 1129 "options {backtrack=true;}\n"+ 1130 "a : ('a'{;}|'b')?;" 1131 ); 1132 String expecting = 1133 ".s0->.s1\n" + 1134 ".s1->.s2\n" + 1135 ".s10->.s11\n" + 1136 ".s10->.s14\n" + 1137 ".s11-{synpred2_t}?->.s12\n" + 1138 ".s12-'b'->.s13\n" + 1139 ".s13->.s7\n" + 1140 ".s14->.s7\n" + 1141 ".s2->.s10\n" + 1142 ".s2->.s3\n" + 1143 ".s3-{synpred1_t}?->.s4\n" + 1144 ".s4-'a'->.s5\n" + 1145 ".s5-{}->.s6\n" + 1146 ".s6->.s7\n" + 1147 ".s7->:s8\n" + 1148 ":s8-EOF->.s9\n"; 1149 checkRule(g, "a", expecting); 1150 } 1151 1152 @Test public void testAutoBacktracking_OptionalBlock1Alt() throws Exception { 1153 Grammar g = new Grammar( 1154 "grammar t;\n" + 1155 "options {backtrack=true;}\n"+ 1156 "a : ('a')?;" 1157 ); 1158 String expecting = 1159 ".s0->.s1\n" + 1160 ".s1->.s2\n" + 1161 ".s2->.s3\n" + 1162 ".s2->.s9\n" + 1163 ".s3-{synpred1_t}?->.s4\n" + 1164 ".s4-'a'->.s5\n" + 1165 ".s5->.s6\n" + 1166 ".s6->:s7\n" + 1167 ".s9->.s6\n" + 1168 ":s7-EOF->.s8\n"; 1169 checkRule(g, "a", expecting); 1170 } 1171 1172 @Test public void testAutoBacktracking_ExistingPred() throws Exception { 1173 Grammar g = new Grammar( 1174 "grammar t;\n" + 1175 "options {backtrack=true;}\n"+ 1176 "a : ('a')=> 'a' | 'b';" 1177 ); 1178 String expecting = 1179 ".s0->.s1\n" + 1180 ".s1->.s2\n" + 1181 ".s1->.s8\n" + 1182 ".s10->.s5\n" + 1183 ".s2-{synpred1_t}?->.s3\n" + 1184 ".s3-'a'->.s4\n" + 1185 ".s4->.s5\n" + 1186 ".s5->:s6\n" + 1187 ".s8->.s9\n" + 1188 ".s9-'b'->.s10\n" + 1189 ":s6-EOF->.s7\n"; 1190 checkRule(g, "a", expecting); 1191 } 1192 1193 private void checkRule(Grammar g, String rule, String expecting) 1194 { 1195 g.buildNFA(); 1196 State startState = g.getRuleStartState(rule); 1197 FASerializer serializer = new FASerializer(g); 1198 String result = serializer.serialize(startState); 1199 1200 //System.out.print(result); 1201 assertEquals(expecting, result); 1202 } 1203 1204 } 1205