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 
testSimple()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 
testSemPred()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 
testTernaryExpr()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 
testDeclarationsUsingASTOperators()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 
testDeclarationsUsingRewriteOperators()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 
testExpressionsUsingASTOperators()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 
testExpressionsUsingRewriteOperators()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 
testExpressionAssociativity()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 
testJavaExpressions()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 
testReturnValueAndActions()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 
testReturnValueAndActionsAndASTs()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 
runTests(String grammar, String[] tests, String startRule)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