| 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 <...> 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 |
<ID> "(" expr() ")" // Choice 1 |
| 289 |
| |
| 290 |
"(" expr() ")" // Choice 2 |
| 291 |
| |
| 292 |
"new" <ID> // 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 <ID>) { |
| 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 |
<ID> "(" expr() ")" // Choice 1 |
| 328 |
| |
| 329 |
"(" expr() ")" // Choice 2 |
| 330 |
| |
| 331 |
"new" <ID> // Choice 3 |
| 332 |
| |
| 333 |
<ID> "." <ID> // 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 <ID> and never choose Choice 4 even if the token |
| 340 |
following <ID> 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: <ID> |
| 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 |
<ID> ( "," <ID> )* |
| 370 |
} |
| 371 |
|
| 372 |
</tt></pre> |
| 373 |
<p> |
| 374 |
Suppose the first <ID> 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 <ID>) 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() "," <INT> |
| 399 |
} |
| 400 |
</tt></pre> |
| 401 |
<p> |
| 402 |
When the default algorithm is making a choice at ( "," <ID> )*, 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 <INT>. 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 |
<ID>. 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 |
<ID> ( "(" expr() ")" | "." <ID> ) |
| 466 |
| |
| 467 |
"(" expr() ")" |
| 468 |
| |
| 469 |
"new" <ID> |
| 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 <ID> 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 |
<ID> "," ( <ID> "," )* <INT> |
| 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(); } <ID> "(" expr() ")" |
| 527 |
| |
| 528 |
"(" expr() ")" |
| 529 |
| |
| 530 |
"new" <ID> |
| 531 |
| |
| 532 |
{ initObjectTables(); } <ID> "." <ID> |
| 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 <ID> and "(", while |
| 555 |
choice 4 will be taken only if the next two tokens are <ID> 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 <ID>. |
| 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 |
<ID> "(" expr() ")" // Choice 1 |
| 584 |
| |
| 585 |
"(" expr() ")" // Choice 2 |
| 586 |
| |
| 587 |
"new" <ID> // Choice 3 |
| 588 |
| |
| 589 |
<ID> "." <ID> // 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 <ID> 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 <ID>) { |
| 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 |
<ID> ( LOOKAHEAD(2) "," <ID> )* |
| 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 <ID> has been consumed): |
| 627 |
</p> |
| 628 |
<pre><tt> |
| 629 |
|
| 630 |
while (next 2 tokens are "," and <ID>) { |
| 631 |
choose the nested expansion (i.e., go into the (...)* construct) |
| 632 |
consume the "," token |
| 633 |
consume the <ID> 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 && getToken(2).kind != C } ) |
| 896 |
<C:"c"> |
| 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 |
<C:"c"> |
| 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> |