Debian Codegraph @

examples/Lookahead/README

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