Home | History | Annotate | Download | only in test 
      1 package org.antlr.test;
      2 
      3 import org.junit.Test;
      4 
      5 /** */
      6 public class TestLeftRecursion extends BaseTest {
      7 	protected boolean debug = false;
      8 
      9 	@Test public void testSimple() throws Exception {
     10 		String grammar =
     11 			"grammar T;\n" +
     12 			"s : a {System.out.println($a.text);} ;\n" +
     13 			"a : a ID\n" +
     14 			"  | ID" +
     15 			"  ;\n" +
     16 			"ID : 'a'..'z'+ ;\n" +
     17 			"WS : (' '|'\\n') {skip();} ;\n";
     18 		String found = execParser("T.g", grammar, "TParser", "TLexer",
     19 								  "s", "a b c", debug);
     20 		String expecting = "abc\n";
     21 		assertEquals(expecting, found);
     22 	}
     23 
     24 	@Test public void testSemPred() throws Exception {
     25 		String grammar =
     26 			"grammar T;\n" +
     27 			"s : a {System.out.println($a.text);} ;\n" +
     28 			"a : a {true}? ID\n" +
     29 			"  | ID" +
     30 			"  ;\n" +
     31 			"ID : 'a'..'z'+ ;\n" +
     32 			"WS : (' '|'\\n') {skip();} ;\n";
     33 		String found = execParser("T.g", grammar, "TParser", "TLexer",
     34 								  "s", "a b c", debug);
     35 		String expecting = "abc\n";
     36 		assertEquals(expecting, found);
     37 	}
     38 
     39 	@Test public void testTernaryExpr() throws Exception {
     40 		String grammar =
     41 			"grammar T;\n" +
     42 			"options {output=AST;}\n" +
     43 			"e : e '*'^ e" +
     44 			"  | e '+'^ e" +
     45 			"  | e '?'<assoc=right>^ e ':'! e" +
     46 			"  | e '='<assoc=right>^ e" +
     47 			"  | ID" +
     48 			"  ;\n" +
     49 			"ID : 'a'..'z'+ ;\n" +
     50 			"WS : (' '|'\\n') {skip();} ;\n";
     51 		String[] tests = {
     52 			"a",			"a",
     53 			"a+b",			"(+ a b)",
     54 			"a*b",			"(* a b)",
     55 			"a?b:c",		"(? a b c)",
     56 			"a=b=c",		"(= a (= b c))",
     57 			"a?b+c:d",		"(? a (+ b c) d)",
     58 			"a?b=c:d",		"(? a (= b c) d)",
     59 			"a? b?c:d : e",	"(? a (? b c d) e)",
     60 			"a?b: c?d:e",	"(? a b (? c d e))",
     61 		};
     62 		runTests(grammar, tests, "e");
     63 	}
     64 
     65 	@Test public void testDeclarationsUsingASTOperators() throws Exception {
     66 		String grammar =
     67 			"grammar T;\n" +
     68 			"options {output=AST;}\n" +
     69 			"declarator\n" +
     70 			"        : declarator '['^ e ']'!\n" +
     71 			"        | declarator '['^ ']'!\n" +
     72 			"        | declarator '('^ ')'!\n" +
     73 			"        | '*'^ declarator\n" + // binds less tight than suffixes
     74 			"        | '('! declarator ')'!\n" +
     75 			"        | ID\n" +
     76 			"        ;\n" +
     77 			"e : INT ;\n" +
     78 			"ID : 'a'..'z'+ ;\n" +
     79 			"INT : '0'..'9'+ ;\n" +
     80 			"WS : (' '|'\\n') {skip();} ;\n";
     81 		String[] tests = {
     82 			"a",		"a",
     83 			"*a",		"(* a)",
     84 			"**a",		"(* (* a))",
     85 			"a[3]",		"([ a 3)",
     86 			"b[]",		"([ b)",
     87 			"(a)",		"a",
     88 			"a[]()",	"(( ([ a))",
     89 			"a[][]",	"([ ([ a))",
     90 			"*a[]",		"(* ([ a))",
     91 			"(*a)[]",	"([ (* a))",
     92 		};
     93 		runTests(grammar, tests, "declarator");
     94 	}
     95 
     96 	@Test public void testDeclarationsUsingRewriteOperators() throws Exception {
     97 		String grammar =
     98 			"grammar T;\n" +
     99 			"options {output=AST;}\n" +
    100 			"declarator\n" +
    101 			"        : declarator '[' e ']' -> ^('[' declarator e)\n" +
    102 			"        | declarator '[' ']' -> ^('[' declarator)\n" +
    103 			"        | declarator '(' ')' -> ^('(' declarator)\n" +
    104 			"        | '*' declarator -> ^('*' declarator) \n" + // binds less tight than suffixes
    105 			"        | '(' declarator ')' -> declarator\n" +
    106 			"        | ID -> ID\n" +
    107 			"        ;\n" +
    108 			"e : INT ;\n" +
    109 			"ID : 'a'..'z'+ ;\n" +
    110 			"INT : '0'..'9'+ ;\n" +
    111 			"WS : (' '|'\\n') {skip();} ;\n";
    112 		String[] tests = {
    113 			"a",		"a",
    114 			"*a",		"(* a)",
    115 			"**a",		"(* (* a))",
    116 			"a[3]",		"([ a 3)",
    117 			"b[]",		"([ b)",
    118 			"(a)",		"a",
    119 			"a[]()",	"(( ([ a))",
    120 			"a[][]",	"([ ([ a))",
    121 			"*a[]",		"(* ([ a))",
    122 			"(*a)[]",	"([ (* a))",
    123 		};
    124 		runTests(grammar, tests, "declarator");
    125 	}
    126 
    127 	@Test public void testExpressionsUsingASTOperators() throws Exception {
    128 		String grammar =
    129 			"grammar T;\n" +
    130 			"options {output=AST;}\n" +
    131 			"e : e '.'^ ID\n" +
    132 			"  | e '.'^ 'this'\n" +
    133 			"  | '-'^ e\n" +
    134 			"  | e '*'^ e\n" +
    135 			"  | e ('+'^|'-'^) e\n" +
    136 			"  | INT\n" +
    137 			"  | ID\n" +
    138 			"  ;\n" +
    139 			"ID : 'a'..'z'+ ;\n" +
    140 			"INT : '0'..'9'+ ;\n" +
    141 			"WS : (' '|'\\n') {skip();} ;\n";
    142 		String[] tests = {
    143 			"a",		"a",
    144 			"1",		"1",
    145 			"a+1",		"(+ a 1)",
    146 			"a*1",		"(* a 1)",
    147 			"a.b",		"(. a b)",
    148 			"a.this",	"(. a this)",
    149 			"a-b+c",	"(+ (- a b) c)",
    150 			"a+b*c",	"(+ a (* b c))",
    151 			"a.b+1",	"(+ (. a b) 1)",
    152 			"-a",		"(- a)",
    153 			"-a+b",		"(+ (- a) b)",
    154 			"-a.b",		"(- (. a b))",
    155 		};
    156 		runTests(grammar, tests, "e");
    157 	}
    158 
    159 	@Test public void testExpressionsUsingRewriteOperators() throws Exception {
    160 		String grammar =
    161 			"grammar T;\n" +
    162 			"options {output=AST;}\n" +
    163 			"e : e '.' ID 				-> ^('.' e ID)\n" +
    164 			"  | e '.' 'this' 			-> ^('.' e 'this')\n" +
    165 			"  | '-' e 					-> ^('-' e)\n" +
    166 			"  | e '*' b=e 				-> ^('*' e $b)\n" +
    167 			"  | e (op='+'|op='-') b=e	-> ^($op e $b)\n" +
    168 			"  | INT 					-> INT\n" +
    169 			"  | ID 					-> ID\n" +
    170 			"  ;\n" +
    171 			"ID : 'a'..'z'+ ;\n" +
    172 			"INT : '0'..'9'+ ;\n" +
    173 			"WS : (' '|'\\n') {skip();} ;\n";
    174 		String[] tests = {
    175 			"a",		"a",
    176 			"1",		"1",
    177 			"a+1",		"(+ a 1)",
    178 			"a*1",		"(* a 1)",
    179 			"a.b",		"(. a b)",
    180 			"a.this",	"(. a this)",
    181 			"a+b*c",	"(+ a (* b c))",
    182 			"a.b+1",	"(+ (. a b) 1)",
    183 			"-a",		"(- a)",
    184 			"-a+b",		"(+ (- a) b)",
    185 			"-a.b",		"(- (. a b))",
    186 		};
    187 		runTests(grammar, tests, "e");
    188 	}
    189 
    190 	@Test public void testExpressionAssociativity() throws Exception {
    191 		String grammar =
    192 			"grammar T;\n" +
    193 			"options {output=AST;}\n" +
    194 			"e\n" +
    195 			"  : e '.'^ ID\n" +
    196 			"  | '-'^ e\n" +
    197 			"  | e '^'<assoc=right>^ e\n" +
    198 			"  | e '*'^ e\n" +
    199 			"  | e ('+'^|'-'^) e\n" +
    200 			"  | e ('='<assoc=right>^ |'+='<assoc=right>^) e\n" +
    201 			"  | INT\n" +
    202 			"  | ID\n" +
    203 			"  ;\n" +
    204 			"ID : 'a'..'z'+ ;\n" +
    205 			"INT : '0'..'9'+ ;\n" +
    206 			"WS : (' '|'\\n') {skip();} ;\n";
    207 		String[] tests = {
    208 			"a",		"a",
    209 			"1",		"1",
    210 			"a+1",		"(+ a 1)",
    211 			"a*1",		"(* a 1)",
    212 			"a.b",		"(. a b)",
    213 			"a-b+c",	"(+ (- a b) c)",
    214 
    215 			"a+b*c",	"(+ a (* b c))",
    216 			"a.b+1",	"(+ (. a b) 1)",
    217 			"-a",		"(- a)",
    218 			"-a+b",		"(+ (- a) b)",
    219 			"-a.b",		"(- (. a b))",
    220 			"a^b^c",	"(^ a (^ b c))",
    221 			"a=b=c",	"(= a (= b c))",
    222 			"a=b=c+d.e","(= a (= b (+ c (. d e))))",
    223 		};
    224 		runTests(grammar, tests, "e");
    225 	}
    226 
    227 	@Test public void testJavaExpressions() throws Exception {
    228 		// Generates about 7k in bytecodes for generated e_ rule;
    229 		// Well within the 64k method limit. e_primary compiles
    230 		// to about 2k in bytecodes.
    231 		// this is simplified from real java
    232 		String grammar =
    233 			"grammar T;\n" +
    234 			"options {output=AST;}\n" +
    235 			"expressionList\n" +
    236 			"    :   e (','! e)*\n" +
    237 			"    ;\n" +
    238 			"e   :   '('! e ')'!\n" +
    239 			"    |   'this' \n" +
    240 			"    |   'super'\n" +
    241 			"    |   INT\n" +
    242 			"    |   ID\n" +
    243 			"    |   type '.'^ 'class'\n" +
    244 			"    |   e '.'^ ID\n" +
    245 			"    |   e '.'^ 'this'\n" +
    246 			"    |   e '.'^ 'super' '('^ expressionList? ')'!\n" +
    247 			"    |   e '.'^ 'new'^ ID '('! expressionList? ')'!\n" +
    248 			"	 |	 'new'^ type ( '(' expressionList? ')'! | (options {k=1;}:'[' e ']'!)+)\n" + // ugly; simplified
    249 			"    |   e '['^ e ']'!\n" +
    250 			"    |   '('^ type ')'! e\n" +
    251 			"    |   e ('++'^ | '--'^)\n" +
    252 			"    |   e '('^ expressionList? ')'!\n" +
    253 			"    |   ('+'^|'-'^|'++'^|'--'^) e\n" +
    254 			"    |   ('~'^|'!'^) e\n" +
    255 			"    |   e ('*'^|'/'^|'%'^) e\n" +
    256 			"    |   e ('+'^|'-'^) e\n" +
    257 			"    |   e ('<'^ '<' | '>'^ '>' '>' | '>'^ '>') e\n" +
    258 			"    |   e ('<='^ | '>='^ | '>'^ | '<'^) e\n" +
    259 			"    |   e 'instanceof'^ e\n" +
    260 			"    |   e ('=='^ | '!='^) e\n" +
    261 			"    |   e '&'^ e\n" +
    262 			"    |   e '^'<assoc=right>^ e\n" +
    263 			"    |   e '|'^ e\n" +
    264 			"    |   e '&&'^ e\n" +
    265 			"    |   e '||'^ e\n" +
    266 			"    |   e '?' e ':' e\n" +
    267 			"    |   e ('='<assoc=right>^\n" +
    268 			"          |'+='<assoc=right>^\n" +
    269 			"          |'-='<assoc=right>^\n" +
    270 			"          |'*='<assoc=right>^\n" +
    271 			"          |'/='<assoc=right>^\n" +
    272 			"          |'&='<assoc=right>^\n" +
    273 			"          |'|='<assoc=right>^\n" +
    274 			"          |'^='<assoc=right>^\n" +
    275 			"          |'>>='<assoc=right>^\n" +
    276 			"          |'>>>='<assoc=right>^\n" +
    277 			"          |'<<='<assoc=right>^\n" +
    278 			"          |'%='<assoc=right>^) e\n" +
    279 			"    ;\n" +
    280 			"type: ID \n" +
    281 			"    | ID '['^ ']'!\n" +
    282 			"    | 'int'\n" +
    283 			"	 | 'int' '['^ ']'! \n" +
    284 			"    ;\n" +
    285 			"ID : ('a'..'z'|'A'..'Z'|'_'|'$')+;\n" +
    286 			"INT : '0'..'9'+ ;\n" +
    287 			"WS : (' '|'\\n') {skip();} ;\n";
    288 		String[] tests = {
    289 			"a",		"a",
    290 			"1",		"1",
    291 			"a+1",		"(+ a 1)",
    292 			"a*1",		"(* a 1)",
    293 			"a.b",		"(. a b)",
    294 			"a-b+c",	"(+ (- a b) c)",
    295 
    296 			"a+b*c",	"(+ a (* b c))",
    297 			"a.b+1",	"(+ (. a b) 1)",
    298 			"-a",		"(- a)",
    299 			"-a+b",		"(+ (- a) b)",
    300 			"-a.b",		"(- (. a b))",
    301 			"a^b^c",	"(^ a (^ b c))",
    302 			"a=b=c",	"(= a (= b c))",
    303 			"a=b=c+d.e","(= a (= b (+ c (. d e))))",
    304 			"a|b&c",	"(| a (& b c))",
    305 			"(a|b)&c",	"(& (| a b) c)",
    306 			"a > b",	"(> a b)",
    307 			"a >> b",	"(> a b)",  // text is from one token
    308 			"a < b",	"(< a b)",
    309 
    310 			"(T)x",							"(( T x)",
    311 			"new A().b",					"(. (new A () b)",
    312 			"(T)t.f()",						"(( (( T (. t f)))",
    313 			"a.f(x)==T.c",					"(== (( (. a f) x) (. T c))",
    314 			"a.f().g(x,1)",					"(( (. (( (. a f)) g) x 1)",
    315 			"new T[((n-1) * x) + 1]",		"(new T [ (+ (* (- n 1) x) 1))",
    316 		};
    317 		runTests(grammar, tests, "e");
    318 	}
    319 
    320 	@Test public void testReturnValueAndActions() throws Exception {
    321 		String grammar =
    322 			"grammar T;\n" +
    323 			"s : e {System.out.println($e.v);} ;\n" +
    324 			"e returns [int v, List<String> ignored]\n" +
    325 			"  : e '*' b=e {$v *= $b.v;}\n" +
    326 			"  | e '+' b=e {$v += $b.v;}\n" +
    327 			"  | INT {$v = $INT.int;}\n" +
    328 			"  ;\n" +
    329 			"INT : '0'..'9'+ ;\n" +
    330 			"WS : (' '|'\\n') {skip();} ;\n";
    331 		String[] tests = {
    332 			"4",			"4",
    333 			"1+2",			"3",
    334 		};
    335 		runTests(grammar, tests, "s");
    336 	}
    337 
    338 	@Test public void testReturnValueAndActionsAndASTs() throws Exception {
    339 		String grammar =
    340 			"grammar T;\n" +
    341 			"options {output=AST;}\n" +
    342 			"s : e {System.out.print(\"v=\"+$e.v+\", \");} ;\n" +
    343 			"e returns [int v, List<String> ignored]\n" +
    344 			"  : e '*'^ b=e {$v *= $b.v;}\n" +
    345 			"  | e '+'^ b=e {$v += $b.v;}\n" +
    346 			"  | INT {$v = $INT.int;}\n" +
    347 			"  ;\n" +
    348 			"INT : '0'..'9'+ ;\n" +
    349 			"WS : (' '|'\\n') {skip();} ;\n";
    350 		String[] tests = {
    351 			"4",			"v=4, 4",
    352 			"1+2",			"v=3, (+ 1 2)",
    353 		};
    354 		runTests(grammar, tests, "s");
    355 	}
    356 
    357 	public void runTests(String grammar, String[] tests, String startRule) {
    358 		rawGenerateAndBuildRecognizer("T.g", grammar, "TParser", "TLexer", debug);
    359 		boolean parserBuildsTrees =
    360 			grammar.indexOf("output=AST")>=0 ||
    361 			grammar.indexOf("output = AST")>=0;
    362 		writeRecognizerAndCompile("TParser",
    363 										 null,
    364 										 "TLexer",
    365 										 startRule,
    366 										 null,
    367 										 parserBuildsTrees,
    368 										 false,
    369 										 false,
    370 										 debug);
    371 
    372 		for (int i=0; i<tests.length; i+=2) {
    373 			String test = tests[i];
    374 			String expecting = tests[i+1]+"\n";
    375 			writeFile(tmpdir, "input", test);
    376 			String found = execRecognizer();
    377 			System.out.print(test+" -> "+found);
    378 			assertEquals(expecting, found);
    379 		}
    380 	}
    381 
    382 }
    383