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