Debian Codegraph @

www/doc/lookahead.html

raw
1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
2 <html xmlns="http://www.w3.org/1999/xhtml">
3 <!--
4
5 Copyright (c) 2006, Sun Microsystems, Inc.
6 All rights reserved.
7
8 Redistribution and use in source and binary forms, with or without
9 modification, are permitted provided that the following conditions are met:
10
11 * Redistributions of source code must retain the above copyright notice,
12 this list of conditions and the following disclaimer.
13 * Redistributions in binary form must reproduce the above copyright
14 notice, this list of conditions and the following disclaimer in the
15 documentation and/or other materials provided with the distribution.
16 * Neither the name of the Sun Microsystems, Inc. nor the names of its
17 contributors may be used to endorse or promote products derived from
18 this software without specific prior written permission.
19
20 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
21 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
22 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
23 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
24 LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25 CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26 SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27 INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
30 THE POSSIBILITY OF SUCH DAMAGE.
31
32 -->
33 <head>
34 <title>JavaCC: LOOKAHEAD MiniTutorial</title>
35 <!-- Changed by: Michael Van De Vanter, 14-Jan-2003 -->
36 </head>
37 <body bgcolor="#FFFFFF" >
38
39 <h1>JavaCC [tm]: LOOKAHEAD MiniTutorial</h1>
40
41
42 <p>
43 <strong>This tutorial refers
44 to examples that are available in the Lookahead directory under the
45 examples directory of the release. Currently, this page is a copy of
46 the contents of the README file within that directory.
47 </strong>
48 </p>
49
50
51 <h1>Lookahead tutorial</h1>
52
53 <p>
54 We assume that you have already taken a look at some of the simple
55 examples provided in the release before you read this section.
56 </p>
57
58 <h2>WHAT IS LOOKAHEAD?</h2>
59
60 <p>
61 The job of a parser is to read an input stream and determine whether
62 or not the input stream conforms to the grammar.
63 </p>
64 <p>
65 This determination in its most general form can be quite time
66 consuming. Consider the following example (file Example1.jj):
67 </p>
68 <pre><tt>
69
70 void Input() :
71 {}
72 {
73 "a" BC() "c"
74 }
75
76 void BC() :
77 {}
78 {
79 "b" [ "c" ]
80 }
81 </tt></pre>
82 <p>
83 In this simple example, it is quite clear that there are exactly two
84 strings that match the above grammar, namely:
85 </p>
86 <pre><tt>
87 abc
88 abcc
89 </tt></pre>
90 <p>
91 The general way to perform this match is to walk through the grammar
92 based on the string as follows. Here, we use "abc" as the input
93 string:
94 </p>
95 <ul>
96 <li><b>Step 1.</b>
97 There is only one choice here - the first input character
98 must be 'a' - and since that is indeed the case, we are OK.
99 </li>
100 <li><b>Step 2.</b>
101 We now proceed on to non-terminal BC. Here again, there is
102 only one choice for the next input character - it must be 'b'. The
103 input matches this one too, so we are still OK.
104 </li>
105 <li><b>Step 3.</b>
106 We now come to a "choice point" in the grammar.
107 We can either
108 go inside the [...] and match it, or ignore it altogether. We decide
109 to go inside. So the next input character must be a 'c'. We are
110 again OK.
111 </li>
112 <li><b>Step 4.</b>
113 Now we have completed with non-terminal BC and go back to
114 non-terminal Input. Now the grammar says the next character must be
115 yet another 'c'. But there are no more input characters. So we have
116 a problem.
117 </li>
118 <li><b>Step 5.</b>
119 When we have such a problem in the general case, we conclude
120 that we may have made a bad choice somewhere. In this case, we made
121 the bad choice in Step 3. So we retrace our steps back to step 3 and
122 make another choice and try that. This process is called
123 "backtracking".
124 </li>
125 <li><b>Step 6.</b>
126 We have now backtracked and made the other choice we could
127 have made at Step 3 - namely, ignore the [...]. Now we have completed
128 with non-terminal BC and go back to non-terminal Input. Now the
129 grammar says the next character must be yet another 'c'. The next
130 input character is a 'c', so we are OK now.
131 </li>
132 <li><b>Step 7.</b>
133 We realize we have reached the end of the grammar (end of
134 non-terminal Input) successfully. This means we have successfully
135 matched the string "abc" to the grammar.
136 </li>
137 </ul>
138 <p>
139 As the above example indicates, the general problem of matching an
140 input with a grammar may result in large amounts of backtracking and
141 making new choices and this can consume a lot of time. The amount of
142 time taken can also be a function of how the grammar is written. Note
143 that many grammars can be written to cover the same set of inputs - or
144 the same language (i.e., there can be multiple equivalent grammars for
145 the same input language).
146 </p>
147 <hr />
148 <p>
149 For example, the following grammar would speed up the parsing of the
150 same language as compared to the previous grammar:
151 </p>
152 <pre><tt>
153 void Input() :
154 {}
155 {
156 "a" "b" "c" [ "c" ]
157 }
158 </tt></pre>
159 <p>
160 while the following grammar slows it down even more since the parser
161 has to backtrack all the way to the beginning:
162 </p>
163 <pre><tt>
164 void Input() :
165 {}
166 {
167 "a" "b" "c" "c"
168 |
169 "a" "b" "c"
170 }
171 </tt></pre>
172 <p>
173 One can even have a grammar that looks like the following:
174 </p>
175 <pre><tt>
176
177 void Input() :
178 {}
179 {
180 "a" ( BC1() | BC2() )
181 }
182
183 void BC1() :
184 {}
185 {
186 "b" "c" "c"
187 }
188
189 void BC2() :
190 {}
191 {
192 "b" "c" [ "c" ]
193 }
194 </tt></pre>
195 <p>
196 This grammar can match "abcc" in two ways, and is therefore considered
197 "ambiguous".
198 </p>
199 <hr />
200 <p>
201 The performance hit from such backtracking is unacceptable for most
202 systems that include a parser. Hence most parsers do not backtrack in
203 this general manner (or do not backtrack at all), rather they make
204 decisions at choice points based on limited information and then
205 commit to it.
206 </p>
207 <p>
208 Parsers generated by Java Compiler Compiler make decisions at choice
209 points based on some exploration of tokens further ahead in the input
210 stream, and once they make such a decision, they commit to it. i.e.,
211 No backtracking is performed once a decision is made.
212 </p>
213 <p>
214
215 The process of exploring tokens further in the input stream is termed
216 "looking ahead" into the input stream - hence our use of the term
217 "LOOKAHEAD".
218 </p>
219 <p>
220 Since some of these decisions may be made with less than perfect
221 information (JavaCC [tm] will warn you in these situations, so you don't
222 have to worry), you need to know something about LOOKAHEAD to make
223 your grammar work correctly.
224 </p>
225 <p>
226 The two ways in which you make the choice decisions work properly are:
227 </p>
228 <ul>
229 <li>
230 Modify the grammar to make it simpler.
231 </li>
232 <li>
233 Insert hints at the more complicated choice points to help the
234 parser make the right choices.
235 </li>
236 </ul>
237
238 <h2>CHOICE POINTS IN JAVACC GRAMMARS</h2>
239
240 <p>
241 There are 4 different kinds of choice points in JavaCC:
242 </p>
243 <ol>
244 <li>
245 An expansion of the form: ( exp1 | exp2 | ... ). In this case, the
246 generated parser has to somehow determine which of exp1, exp2, etc.
247 to select to continue parsing.
248 </li>
249 <li>
250 An expansion of the form: ( exp )?. In this case, the generated parser
251 must somehow determine whether to choose exp or to continue beyond
252 the ( exp )? without choosing exp. Note: ( exp )? may also be written
253 as [ exp ].
254 </li>
255 <li>
256 An expansion of the form ( exp )*. In this case, the generated parser
257 must do the same thing as in the previous case, and furthermore, after
258 each time a successful match of exp (if exp was chosen) is completed,
259 this choice determination must be made again.
260 </li>
261 <li>
262 An expansion of the form ( exp )+. This is essentially similar to
263 the previous case with a mandatory first match to exp.
264 </li>
265 </ol>
266 <p>
267 Remember that token specifications that occur within angular
268 brackets &lt;...&gt; also have choice points. But these choices are made
269 in different ways and are the subject of a different tutorial.
270 </p>
271
272 <h2>THE DEFAULT CHOICE DETERMINATION ALGORITHM</h2>
273
274 <p>
275 The default choice determination algorithm looks ahead 1 token in the
276 input stream and uses this to help make its choice at choice points.
277 </p>
278 <p>
279 The following examples will describe the default algorithm fully:
280 </p>
281 <p>
282 Consider the following grammar (file Example2.jj):
283 </p>
284 <pre><tt>
285 void basic_expr() :
286 {}
287 {
288 &lt;ID&gt; "(" expr() ")" // Choice 1
289 |
290 "(" expr() ")" // Choice 2
291 |
292 "new" &lt;ID&gt; // Choice 3
293 }
294 </tt></pre>
295 <p>
296 The choice determination algorithm works as follows:
297 </p>
298 <pre><tt>
299
300 if (next token is &lt;ID&gt;) {
301 choose Choice 1
302 } else if (next token is "(") {
303 choose Choice 2
304 } else if (next token is "new") {
305 choose Choice 3
306 } else {
307 produce an error message
308 }
309 </tt></pre>
310 <hr />
311 <p>
312 In the above example, the grammar has been written such that the
313 default choice determination algorithm does the right thing. Another
314 thing to note is that the choice determination algorithm works in a
315 top to bottom order - if Choice 1 was selected, the other choices are
316 not even considered. While this is not an issue in this example
317 (except for performance), it will become important later below when
318 local ambiguities require the insertion of LOOKAHEAD hints.
319 </p>
320 <p>
321 Suppose the above grammar was modified to (file Example3.jj):
322 </p>
323 <pre><tt>
324 void basic_expr() :
325 {}
326 {
327 &lt;ID&gt; "(" expr() ")" // Choice 1
328 |
329 "(" expr() ")" // Choice 2
330 |
331 "new" &lt;ID&gt; // Choice 3
332 |
333 &lt;ID&gt; "." &lt;ID&gt; // Choice 4
334 }
335
336 </tt></pre>
337 <p>
338 Then the default algorithm will always choose Choice 1 when the next
339 input token is &lt;ID&gt; and never choose Choice 4 even if the token
340 following &lt;ID&gt; is a ".". More on this later.
341 </p>
342 <p>
343 You can try running the parser generated from Example3.jj on the input
344 "id1.id2". It will complain that it encountered a "." when it was
345 expecting a "(". Note - when you built the parser, it would have
346 given you the following warning message:
347 </p>
348 <pre><tt>
349 Warning: Choice conflict involving two expansions at
350 line 25, column 3 and line 31, column 3 respectively.
351 A common prefix is: &lt;ID&gt;
352 Consider using a lookahead of 2 for earlier expansion.
353 </tt></pre>
354 <p>
355 Essentially, JavaCC is saying it has detected a situation in your
356 grammar which may cause the default lookahead algorithm to do strange
357 things. The generated parser will still work using the default
358 lookahead algorithm - except that it may not do what you expect of it.
359 </p>
360 <hr />
361 <p>
362 Now consider the following example (file Example 4.jj):
363 </p>
364 <pre><tt>
365
366 void identifier_list() :
367 {}
368 {
369 &lt;ID&gt; ( "," &lt;ID&gt; )*
370 }
371
372 </tt></pre>
373 <p>
374 Suppose the first &lt;ID&gt; has already been matched and that the parser
375 has reached the choice point (the (...)* construct). Here's how the
376 choice determination algorithm works:
377 </p>
378 <pre><tt>
379
380 while (next token is ",") {
381 choose the nested expansion (i.e., go into the (...)* construct)
382 consume the "," token
383 if (next token is &lt;ID&gt;) consume it, otherwise report error
384 }
385
386 </tt></pre>
387 <hr />
388 <p>
389 In the above example, note that the choice determination algorithm
390 does not look beyond the (...)* construct to make its decision.
391 Suppose there was another production in that same grammar as follows
392 (file Example5.jj):
393 </p>
394 <pre><tt>
395 void funny_list() :
396 {}
397 {
398 identifier_list() "," &lt;INT&gt;
399 }
400 </tt></pre>
401 <p>
402 When the default algorithm is making a choice at ( "," &lt;ID&gt; )*, it
403 will always go into the (...)* construct if the next token is a ",".
404 It will do this even when identifier_list was called from funny_list
405 and the token after the "," is an &lt;INT&gt;. Intuitively, the right thing
406 to do in this situation is to skip the (...)* construct and return to
407 funny_list. More on this later.
408 </p>
409 <p>
410 As a concrete example, suppose your input was "id1, id2, 5", the
411 parser will complain that it encountered a 5 when it was expecting an
412 &lt;ID&gt;. Note - when you built the parser, it would have given you the
413 following warning message:
414 </p>
415 <pre><tt>
416
417 Warning: Choice conflict in (...)* construct at line 25, column 8.
418 Expansion nested within construct and expansion following construct
419 have common prefixes, one of which is: ","
420 Consider using a lookahead of 2 or more for nested expansion.
421 </tt></pre>
422 <p>
423 Essentially, JavaCC is saying it has detected a situation in your
424 grammar which may cause the default lookahead algorithm to do strange
425 things. The generated parser will still work using the default
426 lookahead algorithm - except that it may not do what you expect of it.
427 </p>
428 <hr />
429 <p>We have shown you examples of two kinds of choice points in the
430 examples above - "exp1 | exp2 | ...", and "(exp)*". The other two
431 kinds of choice points - "(exp)+" and "(exp)?" - behave similarly to
432 (exp)* and we will not be providing examples of their use here.
433 </p>
434
435 <h3>MULTIPLE TOKEN LOOKAHEAD SPECIFICATIONS</h3>
436
437 <p>
438 So far, we have described the default lookahead algorithm of the
439 generated parsers. In the majority of situations, the default
440 algorithm works just fine. In situations where it does not work
441 well, Java Compiler Compiler provides you with warning messages like
442 the ones shown above. If you have a grammar that goes through
443 Java Compiler Compiler without producing any warnings, then the
444 grammar is a LL(1) grammar. Essentially, LL(1) grammars are those
445 that can be handled by top-down parsers (such as those generated
446 by Java Compiler Compiler) using at most one token of LOOKAHEAD.
447 </p>
448 <p>
449 When you get these warning messages, you can do one of two things.
450 </p>
451 <p><b>Option 1</b></p>
452 <p>
453 You can modify your grammar so that the warning messages go away.
454 That is, you can attempt to make your grammar LL(1) by making some
455 changes to it.
456 </p>
457 <p>
458 The following (file Example6.jj) shows how you may change Example3.jj
459 to make it LL(1):
460 </p>
461 <pre><tt>
462 void basic_expr() :
463 {}
464 {
465 &lt;ID&gt; ( "(" expr() ")" | "." &lt;ID&gt; )
466 |
467 "(" expr() ")"
468 |
469 "new" &lt;ID&gt;
470 }
471
472 </tt></pre>
473 <p>
474 What we have done here is to factor the fourth choice into the first
475 choice. Note how we have placed their common first token &lt;ID&gt; outside
476 the parentheses, and then within the parentheses, we have yet another
477 choice which can now be performed by looking at only one token in the
478 input stream and comparing it with "(" and ".". This process of
479 modifying grammars to make them LL(1) is called "left factoring".
480 </p>
481 <p>
482 The following (file Example7.jj) shows how Example5.jj may be changed
483 to make it LL(1):
484 </p>
485 <pre><tt>
486 void funny_list() :
487 {}
488 {
489 &lt;ID&gt; "," ( &lt;ID&gt; "," )* &lt;INT&gt;
490 }
491 </tt></pre>
492 <p>
493 Note that this change is somewhat more drastic.
494 </p>
495 <hr />
496 <p><b>Option 2</b></p>
497 <p>
498 You can provide the generated parser with some hints to help it out
499 in the non-LL(1) situations that the warning messages bring to your
500 attention.
501 </p>
502 <p>
503 All such hints are specified using either setting the global LOOKAHEAD
504 value to a larger value (see below) or by using the LOOKAHEAD(...)
505 construct to provide a local hint.
506 </p>
507 <p>
508 A design decision must be made to determine if Option 1 or Option 2 is
509 the right one to take. The only advantage of choosing Option 1 is
510 that it makes your grammar perform better. JavaCC generated parsers
511 can handle LL(1) constructs much faster than other constructs.
512 However, the advantage of choosing Option 2 is that you have a simpler
513 grammar - one that is easier to develop and maintain - one that
514 focuses on human-friendliness and not machine-friendliness.
515 </p>
516 <p>
517
518 Sometimes Option 2 is the only choice - especially in the presence of
519 user actions. Suppose Example3.jj contained actions as shown below:
520 </p>
521 <pre><tt>
522
523 void basic_expr() :
524 {}
525 {
526 { initMethodTables(); } &lt;ID&gt; "(" expr() ")"
527 |
528 "(" expr() ")"
529 |
530 "new" &lt;ID&gt;
531 |
532 { initObjectTables(); } &lt;ID&gt; "." &lt;ID&gt;
533 }
534 </tt></pre>
535 <p>
536 Since the actions are different, left-factoring cannot be performed.
537
538 </p>
539
540 <h3>SETTING A GLOBAL LOOKAHEAD SPECIFICATION</h3>
541
542 <p>
543 You can set a global LOOKAHEAD specification by using the option
544 "LOOKAHEAD" either from the command line, or at the beginning of the
545 grammar file in the options section. The value of this option is an
546 integer which is the number of tokens to look ahead when making choice
547 decisions. As you may have guessed, the default value of this option
548 is 1 - which derives the default LOOKAHEAD algorithm described above.
549 </p>
550 <p>
551 Suppose you set the value of this option to 2. Then the LOOKAHEAD
552 algorithm derived from this looks at two tokens (instead of just one
553 token) before making a choice decision. Hence, in Example3.jj, choice
554 1 will be taken only if the next two tokens are &lt;ID&gt; and "(", while
555 choice 4 will be taken only if the next two tokens are &lt;ID&gt; and ".".
556 Hence, the parser will now work properly for Example3.jj. Similarly,
557 the problem with Example5.jj also goes away since the parser goes into
558 the (...)* construct only when the next two tokens are "," and &lt;ID&gt;.
559 </p>
560 <p>
561 By setting the global LOOKAHEAD to 2, the parsing algorithm
562 essentially becomes LL(2). Since you can set the global LOOKAHEAD to
563 any value, parsers generated by Java Compiler Compiler are called
564 LL(k) parsers.
565 </p>
566
567 <h3>SETTING A LOCAL LOOKAHEAD SPECIFICATION</h3>
568
569 <p>
570 You can also set a local LOOKAHEAD specification that affects only a
571 specific choice point. This way, the majority of the grammar can
572 remain LL(1) and hence perform better, while at the same time one gets
573 the flexibility of LL(k) grammars. Here's how Example3.jj is modified
574 with local LOOKAHEAD to fix the choice ambiguity problem (file
575 Example8.jj):
576 </p>
577 <pre><tt>
578
579 void basic_expr() :
580 {}
581 {
582 LOOKAHEAD(2)
583 &lt;ID&gt; "(" expr() ")" // Choice 1
584 |
585 "(" expr() ")" // Choice 2
586 |
587 "new" &lt;ID&gt; // Choice 3
588 |
589 &lt;ID&gt; "." &lt;ID&gt; // Choice 4
590 }
591 </tt></pre>
592 <p>
593 Only the first choice (the first condition in the translation below)
594 is affected by the LOOKAHEAD specification. All others continue to
595 use a single token of LOOKAHEAD:
596 </p>
597 <pre><tt>
598
599 if (next 2 tokens are &lt;ID&gt; and "(" ) {
600 choose Choice 1
601 } else if (next token is "(") {
602 choose Choice 2
603 } else if (next token is "new") {
604 choose Choice 3
605 } else if (next token is &lt;ID&gt;) {
606 choose Choice 4
607 } else {
608 produce an error message
609 }
610 </tt></pre>
611 <p>
612 Similarily, Example5.jj can be modified as shown below (file
613 Example9.jj):
614 </p>
615 <pre><tt>
616
617 void identifier_list() :
618 {}
619 {
620 &lt;ID&gt; ( LOOKAHEAD(2) "," &lt;ID&gt; )*
621 }
622 </tt></pre>
623 <p>
624 Note, the LOOKAHEAD specification has to occur inside the (...)* which
625 is the choice is being made. The translation for this construct is
626 shown below (after the first &lt;ID&gt; has been consumed):
627 </p>
628 <pre><tt>
629
630 while (next 2 tokens are "," and &lt;ID&gt;) {
631 choose the nested expansion (i.e., go into the (...)* construct)
632 consume the "," token
633 consume the &lt;ID&gt; token
634 }
635 </tt></pre>
636 <hr />
637 <p>
638 We strongly discourage you from modifying the global LOOKAHEAD
639 default. Most grammars are predominantly LL(1), hence you will be
640 unnecessarily degrading performance by converting the entire grammar
641 to LL(k) to facilitate just some portions of the grammar that are not
642 LL(1). If your grammar and input files being parsed are very small,
643 then this is okay.
644 </p>
645 <p>
646 You should also keep in mind that the warning messages JavaCC prints
647 when it detects ambiguities at choice points (such as the two messages
648 shown earlier) simply tells you that the specified choice points are
649 not LL(1). JavaCC does not verify the correctness of your local
650 LOOKAHEAD specification - it assumes you know what you are doing, in
651 fact, it really cannot verify the correctness of local LOOKAHEAD's as
652 the following example of if statements illustrates (file
653 Example10.jj):
654 </p>
655 <pre><tt>
656
657 void IfStm() :
658 {}
659 {
660 "if" C() S() [ "else" S() ]
661 }
662
663 void S() :
664 {}
665 {
666 ...
667 |
668 IfStm()
669 }
670
671 </tt></pre>
672 <p>
673 This example is the famous "dangling else" problem. If you have a
674 program that looks like:
675 </p>
676 <pre><tt>
677
678 "if C1 if C2 S1 else S2"
679
680 </tt></pre>
681 <p>
682 The "else S2" can be bound to either of the two if statements. The
683 standard interpretation is that it is bound to the inner if statement
684 (the one closest to it). The default choice determination algorithm
685 happens to do the right thing, but it still prints the following
686 warning message:
687 </p>
688 <pre><tt>
689
690 Warning: Choice conflict in [...] construct at line 25, column 15.
691 Expansion nested within construct and expansion following construct
692 have common prefixes, one of which is: "else"
693 Consider using a lookahead of 2 or more for nested expansion.
694
695 </tt></pre>
696 <p>
697 To suppress the warning message, you could simply tell JavaCC that
698 you know what you are doing as follows:
699 </p>
700 <pre><tt>
701 void IfStm() :
702 {}
703 {
704 "if" C() S() [ LOOKAHEAD(1) "else" S() ]
705 }
706 </tt></pre>
707 <p>
708 To force lookahead ambiguity checking in such instances, set the option
709 FORCE_LA_CHECK to true.
710 </p>
711
712 <h3>SYNTACTIC LOOKAHEAD</h3>
713
714 <p>
715 Consider the following production taken from the Java grammar:
716 </p>
717 <pre><tt>
718
719 void TypeDeclaration() :
720 {}
721 {
722 ClassDeclaration()
723 |
724 InterfaceDeclaration()
725 }
726 </tt></pre>
727 <p>
728 At the syntactic level, ClassDeclaration can start with any number of
729 "abstract"s, "final"s, and "public"s. While a subsequent semantic
730 check will produce error messages for multiple uses of the same
731 modifier, this does not happen until parsing is completely over.
732 Similarly, InterfaceDeclaration can start with any number of
733 "abstract"s and "public"s.
734 </p>
735 <p>
736 What if the next tokens in the input stream are a very large number of
737 "abstract"s (say 100 of them) followed by "interface"? It is clear
738 that a fixed amount of LOOKAHEAD (such as LOOKAHEAD(100) for example)
739 will not suffice. One can argue that this is such a weird situation
740 that it does not warrant any reasonable error message and that it is
741 okay to make the wrong choice in some pathological situations. But
742 suppose one wanted to be precise about this.
743 </p>
744 <p>
745 The solution here is to set the LOOKAHEAD to infinity - that is set no
746 bounds on the number of tokens to look ahead. One way to do this is
747 to use a very large integer value (such as the largest possible
748 integer) as follows:
749 </p>
750 <pre><tt>
751 void TypeDeclaration() :
752 {}
753 {
754 LOOKAHEAD(2147483647)
755 ClassDeclaration()
756 |
757 InterfaceDeclaration()
758 }
759 </tt></pre>
760 <p>
761 One can also achieve the same effect with "syntactic LOOKAHEAD". In
762 syntactic LOOKAHEAD, you specify an expansion to try out and it that
763 succeeds, then the following choice is taken. The above example is
764 rewritten using syntactic LOOKAHEAD below:
765 </p>
766 <pre><tt>
767
768 void TypeDeclaration() :
769 {}
770 {
771 LOOKAHEAD(ClassDeclaration())
772 ClassDeclaration()
773 |
774 InterfaceDeclaration()
775 }
776 </tt></pre>
777 <p>
778 Essentially, what this is saying is:
779 </p>
780 <pre><tt>
781
782 if (the tokens from the input stream match ClassDeclaration) {
783 choose ClassDeclaration()
784 } else if (next token matches InterfaceDeclaration) {
785 choose InterfaceDeclaration()
786 } else {
787 produce an error message
788 }
789
790 </tt></pre>
791 <p>
792 The problem with the above syntactic LOOKAHEAD specification is that
793 the LOOKAHEAD calculation takes too much time and does a lot of
794 unnecessary checking. In this case, the LOOKAHEAD calculation can
795 stop as soon as the token "class" is encountered, but the
796 specification forces the calculation to continue until the end of the
797 class declaration has been reached - which is rather time consuming.
798 This problem can be solved by placing a shorter expansion to try out
799 in the syntactic LOOKAHEAD specification as in the following example:
800 </p>
801 <pre><tt>
802
803 void TypeDeclaration() :
804 {}
805 {
806 LOOKAHEAD( ( "abstract" | "final" | "public" )* "class" )
807 ClassDeclaration()
808 |
809 InterfaceDeclaration()
810 }
811 </tt></pre>
812 <p>
813 Essentially, what this is saying is:
814 </p>
815 <pre><tt>
816 if (the nest set of tokens from the input stream are a sequence of
817 "abstract"s, "final"s, and "public"s followed by a "class") {
818 choose ClassDeclaration()
819 } else if (next token matches InterfaceDeclaration) {
820 choose InterfaceDeclaration()
821 } else {
822 produce an error message
823 }
824 </tt></pre>
825 <p>
826 By doing this, you make the choice determination algorithm stop as
827 soon as it sees "class" - i.e., make its decision at the earliest
828 possible time.
829 </p>
830 <p>
831 You can place a bound on the number of tokens to consume during
832 syntactic lookahead as follows:
833 </p>
834 <pre><tt>
835 void TypeDeclaration() :
836 {}
837 {
838 LOOKAHEAD(10, ( "abstract" | "final" | "public" )* "class" )
839 ClassDeclaration()
840 |
841 InterfaceDeclaration()
842 }
843 </tt></pre>
844 <p>
845 In this case, the LOOKAHEAD determination is not permitted to go beyond
846 10 tokens. If it reaches this limit and is still successfully matching
847 ( "abstract" | "final" | "public" )* "class", then ClassDeclaration is
848 selected.
849 </p>
850 <p>
851 Actually, when such a limit is not specified, it defaults to the largest
852 integer value (2147483647).
853 </p>
854
855 <h3>SEMANTIC LOOKAHEAD</h3>
856
857 <p>
858 Let us go back to Example1.jj:
859 </p>
860 <pre><tt>
861
862 void Input() :
863 {}
864 {
865 "a" BC() "c"
866 }
867
868 void BC() :
869 {}
870 {
871 "b" [ "c" ]
872 }
873 </tt></pre>
874 <p>
875 Let us suppose that there is a good reason for writing a grammar this
876 way (maybe the way actions are embedded). As noted earlier, this
877 grammar recognizes two string "abc" and "abcc". The problem here is
878 that the default LL(1) algorithm will choose the [ "c" ] every time
879 it sees a "c" and therefore "abc" will never be matched. We need to
880 specify that this choice must be made only when the next token is a
881 "c", and the token following that is not a "c". This is a negative
882 statement - one that cannot be made using syntactic LOOKAHEAD.
883 </p>
884 <p>
885 We can use semantic LOOKAHEAD for this purpose. With semantic
886 LOOKAHEAD, you can specify any arbitrary boolean expression whose
887 evaluation determines which choice to take at a choice point. The
888 above example can be instrumented with semantic LOOKAHEAD as follows:
889 </p>
890 <pre><tt>
891 void BC() :
892 {}
893 {
894 "b"
895 [ LOOKAHEAD( { getToken(1).kind == C &amp;&amp; getToken(2).kind != C } )
896 &lt;C:"c"&gt;
897 ]
898 }
899 </tt></pre>
900 <p>
901 First we give the token "c" a label C so that we can refer to it from
902 the semantic LOOKAHEAD. The boolean expression essentially states the
903 desired property. The choice determination decision is therefore:
904 </p>
905 <pre><tt>
906 if (next token is "c" and following token is not "c") {
907 choose the nested expansion (i.e., go into the [...] construct)
908 } else {
909 go beyond the [...] construct without entering it.
910 }
911 </tt></pre>
912 <p>
913 This example can be rewritten to combine both syntactic and semantic
914 LOOKAHEAD as follows (recognize the first "c" using syntactic
915 LOOKAHEAD and the absence of the second using semantic LOOKAHEAD):
916 </p>
917 <pre><tt>
918 void BC() :
919 {}
920 {
921 "b"
922 [ LOOKAHEAD( "c", { getToken(2).kind != C } )
923 &lt;C:"c"&gt;
924 ]
925 }
926 </tt></pre>
927
928 <h3>GENERAL STRUCTURE OF LOOKAHEAD</h3>
929
930 <p>
931 We've pretty much covered the various aspects of LOOKAHEAD in the
932 previous sections. A couple of advanced topics follow. However,
933 we shall now present a formal language reference for LOOKAHEAD in
934 Java Compiler Compiler:
935 </p>
936 <p>
937 The general structure of a LOOKAHEAD specification is:
938 </p>
939 <pre><tt>
940
941 LOOKAHEAD( amount,
942 expansion,
943 { boolean_expression }
944 )
945 </tt></pre>
946 <p>
947 "amount" specifies the number of tokens to LOOKAHEAD,"expansion"
948 specifies the expansion to use to perform syntactic LOOKAHEAD, and
949 "boolean_expression" is the expression to use for semantic
950 LOOKAHEAD.
951 </p>
952 <p>
953 At least one of the three entries must be present. If more than
954 one are present, they are separated by commas. The default values
955 for each of these entities is defined below:
956 </p>
957 <pre><tt>
958
959 "amount":
960 - if "expansion is present, this defaults to 2147483647.
961 - otherwise ("boolean_expression" must be present then) this
962 defaults to 0.
963
964 Note: When "amount" is 0, no syntactic LOOKAHEAD is performed. Also,
965 "amount" does not affect the semantic LOOKAHEAD.
966
967 "expansion":
968 - defaults to the expansion being considered.
969
970 "boolean_expression":
971
972 - defaults to true.
973 </tt></pre>
974
975 <h3>NESTED EVALUATION OF SEMANTIC LOOKAHEAD</h3>
976 <p>
977 To be done.
978 </p>
979
980 <h3>JAVACODE PRODUCTIONS</h3>
981 <p>
982 To be done.
983 </p>
984
985 </body>
986 </html>