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.junit.Test; 31 32 public class TestSyntacticPredicateEvaluation extends BaseTest { testTwoPredsWithNakedAlt()33 @Test public void testTwoPredsWithNakedAlt() throws Exception { 34 String grammar = 35 "grammar T;\n" + 36 "s : (a ';')+ ;\n" + 37 "a\n" + 38 "options {\n" + 39 " k=1;\n" + 40 "}\n" + 41 " : (b '.')=> b '.' {System.out.println(\"alt 1\");}\n" + 42 " | (b)=> b {System.out.println(\"alt 2\");}\n" + 43 " | c {System.out.println(\"alt 3\");}\n" + 44 " ;\n" + 45 "b\n" + 46 "@init {System.out.println(\"enter b\");}\n" + 47 " : '(' 'x' ')' ;\n" + 48 "c\n" + 49 "@init {System.out.println(\"enter c\");}\n" + 50 " : '(' c ')' | 'x' ;\n" + 51 "WS : (' '|'\\n')+ {$channel=HIDDEN;}\n" + 52 " ;\n" ; 53 String found = execParser("T.g", grammar, "TParser", "TLexer", 54 "a", "(x) ;", false); 55 String expecting = 56 "enter b\n" + 57 "enter b\n" + 58 "enter b\n" + 59 "alt 2\n"; 60 assertEquals(expecting, found); 61 62 found = execParser("T.g", grammar, "TParser", "TLexer", 63 "a", "(x). ;", false); 64 expecting = 65 "enter b\n" + 66 "enter b\n" + 67 "alt 1\n"; 68 assertEquals(expecting, found); 69 70 found = execParser("T.g", grammar, "TParser", "TLexer", 71 "a", "((x)) ;", false); 72 expecting = 73 "enter b\n" + 74 "enter b\n" + 75 "enter c\n" + 76 "enter c\n" + 77 "enter c\n" + 78 "alt 3\n"; 79 assertEquals(expecting, found); 80 } 81 testTwoPredsWithNakedAltNotLast()82 @Test public void testTwoPredsWithNakedAltNotLast() throws Exception { 83 String grammar = 84 "grammar T;\n" + 85 "s : (a ';')+ ;\n" + 86 "a\n" + 87 "options {\n" + 88 " k=1;\n" + 89 "}\n" + 90 " : (b '.')=> b '.' {System.out.println(\"alt 1\");}\n" + 91 " | c {System.out.println(\"alt 2\");}\n" + 92 " | (b)=> b {System.out.println(\"alt 3\");}\n" + 93 " ;\n" + 94 "b\n" + 95 "@init {System.out.println(\"enter b\");}\n" + 96 " : '(' 'x' ')' ;\n" + 97 "c\n" + 98 "@init {System.out.println(\"enter c\");}\n" + 99 " : '(' c ')' | 'x' ;\n" + 100 "WS : (' '|'\\n')+ {$channel=HIDDEN;}\n" + 101 " ;\n" ; 102 String found = execParser("T.g", grammar, "TParser", "TLexer", 103 "a", "(x) ;", false); 104 String expecting = 105 "enter b\n" + 106 "enter c\n" + 107 "enter c\n" + 108 "alt 2\n"; 109 assertEquals(expecting, found); 110 111 found = execParser("T.g", grammar, "TParser", "TLexer", 112 "a", "(x). ;", false); 113 expecting = 114 "enter b\n" + 115 "enter b\n" + 116 "alt 1\n"; 117 assertEquals(expecting, found); 118 119 found = execParser("T.g", grammar, "TParser", "TLexer", 120 "a", "((x)) ;", false); 121 expecting = 122 "enter b\n" + 123 "enter c\n" + 124 "enter c\n" + 125 "enter c\n" + 126 "alt 2\n"; 127 assertEquals(expecting, found); 128 } 129 testLexerPred()130 @Test public void testLexerPred() throws Exception { 131 String grammar = 132 "grammar T;\n" + 133 "s : A ;\n" + 134 "A options {k=1;}\n" + // force backtracking 135 " : (B '.')=>B '.' {System.out.println(\"alt1\");}\n" + 136 " | B {System.out.println(\"alt2\");}" + 137 " ;\n" + 138 "fragment\n" + 139 "B : 'x'+ ;\n" ; 140 String found = execParser("T.g", grammar, "TParser", "TLexer", 141 "s", "xxx", false); 142 143 assertEquals("alt2\n", found); 144 145 found = execParser("T.g", grammar, "TParser", "TLexer", 146 "s", "xxx.", false); 147 148 assertEquals("alt1\n", found); 149 } 150 testLexerWithPredLongerThanAlt()151 @Test public void testLexerWithPredLongerThanAlt() throws Exception { 152 String grammar = 153 "grammar T;\n" + 154 "s : A ;\n" + 155 "A options {k=1;}\n" + // force backtracking 156 " : (B '.')=>B {System.out.println(\"alt1\");}\n" + 157 " | B {System.out.println(\"alt2\");}" + 158 " ;\n" + 159 "D : '.' {System.out.println(\"D\");} ;\n" + 160 "fragment\n" + 161 "B : 'x'+ ;\n" ; 162 String found = execParser("T.g", grammar, "TParser", "TLexer", 163 "s", "xxx", false); 164 165 assertEquals("alt2\n", found); 166 167 found = execParser("T.g", grammar, "TParser", "TLexer", 168 "s", "xxx.", false); 169 170 assertEquals("alt1\nD\n", found); 171 } 172 testLexerPredCyclicPrediction()173 @Test public void testLexerPredCyclicPrediction() throws Exception { 174 String grammar = 175 "grammar T;\n" + 176 "s : A ;\n" + 177 "A : (B)=>(B|'y'+) {System.out.println(\"alt1\");}\n" + 178 " | B {System.out.println(\"alt2\");}\n" + 179 " | 'y'+ ';'" + 180 " ;\n" + 181 "fragment\n" + 182 "B : 'x'+ ;\n" ; 183 String found = execParser("T.g", grammar, "TParser", "TLexer", 184 "s", "xxx", false); 185 186 assertEquals("alt1\n", found); 187 } 188 testLexerPredCyclicPrediction2()189 @Test public void testLexerPredCyclicPrediction2() throws Exception { 190 String grammar = 191 "grammar T;\n" + 192 "s : A ;\n" + 193 "A : (B '.')=>(B|'y'+) {System.out.println(\"alt1\");}\n" + 194 " | B {System.out.println(\"alt2\");}\n" + 195 " | 'y'+ ';'" + 196 " ;\n" + 197 "fragment\n" + 198 "B : 'x'+ ;\n" ; 199 String found = execParser("T.g", grammar, "TParser", "TLexer", 200 "s", "xxx", false); 201 assertEquals("alt2\n", found); 202 } 203 testSimpleNestedPred()204 @Test public void testSimpleNestedPred() throws Exception { 205 String grammar = 206 "grammar T;\n" + 207 "s : (expr ';')+ ;\n" + 208 "expr\n" + 209 "options {\n" + 210 " k=1;\n" + 211 "}\n" + 212 "@init {System.out.println(\"enter expr \"+input.LT(1).getText());}\n" + 213 " : (atom 'x') => atom 'x'\n" + 214 " | atom\n" + 215 ";\n" + 216 "atom\n" + 217 "@init {System.out.println(\"enter atom \"+input.LT(1).getText());}\n" + 218 " : '(' expr ')'\n" + 219 " | INT\n" + 220 " ;\n" + 221 "INT: '0'..'9'+ ;\n" + 222 "WS : (' '|'\\n')+ {$channel=HIDDEN;}\n" + 223 " ;\n" ; 224 String found = execParser("T.g", grammar, "TParser", "TLexer", 225 "s", "(34)x;", false); 226 String expecting = 227 "enter expr (\n" + 228 "enter atom (\n" + 229 "enter expr 34\n" + 230 "enter atom 34\n" + 231 "enter atom 34\n" + 232 "enter atom (\n" + 233 "enter expr 34\n" + 234 "enter atom 34\n" + 235 "enter atom 34\n"; 236 assertEquals(expecting, found); 237 } 238 testTripleNestedPredInLexer()239 @Test public void testTripleNestedPredInLexer() throws Exception { 240 String grammar = 241 "grammar T;\n" + 242 "s : (.)+ {System.out.println(\"done\");} ;\n" + 243 "EXPR\n" + 244 "options {\n" + 245 " k=1;\n" + 246 "}\n" + 247 "@init {System.out.println(\"enter expr \"+(char)input.LT(1));}\n" + 248 " : (ATOM 'x') => ATOM 'x' {System.out.println(\"ATOM x\");}\n" + 249 " | ATOM {System.out.println(\"ATOM \"+$ATOM.text);}\n" + 250 ";\n" + 251 "fragment ATOM\n" + 252 "@init {System.out.println(\"enter atom \"+(char)input.LT(1));}\n" + 253 " : '(' EXPR ')'\n" + 254 " | INT\n" + 255 " ;\n" + 256 "fragment INT: '0'..'9'+ ;\n" + 257 "fragment WS : (' '|'\\n')+ \n" + 258 " ;\n" ; 259 String found = execParser("T.g", grammar, "TParser", "TLexer", 260 "s", "((34)x)x", false); 261 String expecting = // has no memoization 262 "enter expr (\n" + 263 "enter atom (\n" + 264 "enter expr (\n" + 265 "enter atom (\n" + 266 "enter expr 3\n" + 267 "enter atom 3\n" + 268 "enter atom 3\n" + 269 "enter atom (\n" + 270 "enter expr 3\n" + 271 "enter atom 3\n" + 272 "enter atom 3\n" + 273 "enter atom (\n" + 274 "enter expr (\n" + 275 "enter atom (\n" + 276 "enter expr 3\n" + 277 "enter atom 3\n" + 278 "enter atom 3\n" + 279 "enter atom (\n" + 280 "enter expr 3\n" + 281 "enter atom 3\n" + 282 "enter atom 3\n" + 283 "ATOM 34\n" + 284 "ATOM x\n" + 285 "ATOM x\n" + 286 "done\n"; 287 assertEquals(expecting, found); 288 } 289 testTreeParserWithSynPred()290 @Test public void testTreeParserWithSynPred() throws Exception { 291 String grammar = 292 "grammar T;\n" + 293 "options {output=AST;}\n" + 294 "a : ID INT+ (PERIOD|SEMI);\n" + 295 "ID : 'a'..'z'+ ;\n" + 296 "INT : '0'..'9'+;\n" + 297 "SEMI : ';' ;\n"+ 298 "PERIOD : '.' ;\n"+ 299 "WS : (' '|'\\n') {$channel=HIDDEN;} ;\n"; 300 301 String treeGrammar = 302 "tree grammar TP;\n" + 303 "options {k=1; backtrack=true; ASTLabelType=CommonTree; tokenVocab=T;}\n" + 304 "a : ID INT+ PERIOD {System.out.print(\"alt 1\");}"+ 305 " | ID INT+ SEMI {System.out.print(\"alt 2\");}\n" + 306 " ;\n"; 307 308 String found = execTreeParser("T.g", grammar, "TParser", "TP.g", 309 treeGrammar, "TP", "TLexer", "a", "a", "a 1 2 3;"); 310 assertEquals("alt 2\n", found); 311 } 312 testTreeParserWithNestedSynPred()313 @Test public void testTreeParserWithNestedSynPred() throws Exception { 314 String grammar = 315 "grammar T;\n" + 316 "options {output=AST;}\n" + 317 "a : ID INT+ (PERIOD|SEMI);\n" + 318 "ID : 'a'..'z'+ ;\n" + 319 "INT : '0'..'9'+;\n" + 320 "SEMI : ';' ;\n"+ 321 "PERIOD : '.' ;\n"+ 322 "WS : (' '|'\\n') {$channel=HIDDEN;} ;\n"; 323 324 // backtracks in a and b due to k=1 325 String treeGrammar = 326 "tree grammar TP;\n" + 327 "options {k=1; backtrack=true; ASTLabelType=CommonTree; tokenVocab=T;}\n" + 328 "a : ID b {System.out.print(\" a:alt 1\");}"+ 329 " | ID INT+ SEMI {System.out.print(\" a:alt 2\");}\n" + 330 " ;\n" + 331 "b : INT PERIOD {System.out.print(\"b:alt 1\");}" + // choose this alt for just one INT 332 " | INT+ PERIOD {System.out.print(\"b:alt 2\");}" + 333 " ;"; 334 335 String found = execTreeParser("T.g", grammar, "TParser", "TP.g", 336 treeGrammar, "TP", "TLexer", "a", "a", "a 1 2 3."); 337 assertEquals("b:alt 2 a:alt 1\n", found); 338 } 339 testSynPredWithOutputTemplate()340 @Test public void testSynPredWithOutputTemplate() throws Exception { 341 // really just seeing if it will compile 342 String grammar = 343 "grammar T;\n" + 344 "options {output=template;}\n" + 345 "a\n" + 346 "options {\n" + 347 " k=1;\n" + 348 "}\n" + 349 " : ('x'+ 'y')=> 'x'+ 'y' -> template(a={$text}) <<1:<a>;>>\n" + 350 " | 'x'+ 'z' -> template(a={$text}) <<2:<a>;>>\n"+ 351 " ;\n" + 352 "WS : (' '|'\\n')+ {$channel=HIDDEN;}\n" + 353 " ;\n" ; 354 String found = execParser("T.g", grammar, "TParser", "TLexer", 355 "a", "xxxy", false); 356 357 assertEquals("1:xxxy;\n", found); 358 } 359 testSynPredWithOutputAST()360 @Test public void testSynPredWithOutputAST() throws Exception { 361 // really just seeing if it will compile 362 String grammar = 363 "grammar T;\n" + 364 "options {output=AST;}\n" + 365 "a\n" + 366 "options {\n" + 367 " k=1;\n" + 368 "}\n" + 369 " : ('x'+ 'y')=> 'x'+ 'y'\n" + 370 " | 'x'+ 'z'\n"+ 371 " ;\n" + 372 "WS : (' '|'\\n')+ {$channel=HIDDEN;}\n" + 373 " ;\n" ; 374 String found = execParser("T.g", grammar, "TParser", "TLexer", 375 "a", "xxxy", false); 376 377 assertEquals("x x x y\n", found); 378 } 379 testOptionalBlockWithSynPred()380 @Test public void testOptionalBlockWithSynPred() throws Exception { 381 String grammar = 382 "grammar T;\n" + 383 "\n" + 384 "a : ( (b)=> b {System.out.println(\"b\");})? b ;\n" + 385 "b : 'x' ;\n" ; 386 String found = execParser("T.g", grammar, "TParser", "TLexer", 387 "a", "xx", false); 388 assertEquals("b\n", found); 389 found = execParser("T.g", grammar, "TParser", "TLexer", 390 "a", "x", false); 391 assertEquals("", found); 392 } 393 testSynPredK2()394 @Test public void testSynPredK2() throws Exception { 395 // all manually specified syn predicates are gated (i.e., forced 396 // to execute). 397 String grammar = 398 "grammar T;\n" + 399 "\n" + 400 "a : (b)=> b {System.out.println(\"alt1\");} | 'a' 'c' ;\n" + 401 "b : 'a' 'b' ;\n" ; 402 String found = execParser("T.g", grammar, "TParser", "TLexer", 403 "a", "ab", false); 404 405 assertEquals("alt1\n", found); 406 } 407 testSynPredKStar()408 @Test public void testSynPredKStar() throws Exception { 409 String grammar = 410 "grammar T;\n" + 411 "\n" + 412 "a : (b)=> b {System.out.println(\"alt1\");} | 'a'+ 'c' ;\n" + 413 "b : 'a'+ 'b' ;\n" ; 414 String found = execParser("T.g", grammar, "TParser", "TLexer", 415 "a", "aaab", false); 416 417 assertEquals("alt1\n", found); 418 } 419 420 } 421