[Home](../index.md) > [Tutorials](index.md) > Lookahead

---

This tutorial refers to examples that are available in the source code on [GitHub](https://github.com/javacc/javacc/tree/master/examples/Lookahead).

### <a name="toc"></a>Contents

- [**What is a LOOKAHEAD?**](#what-is)
  * [Avoiding backtracking](#backtracking)
  * [Choice points in JavaCC grammars](#choice-points)
  * [Default choice determination algorithm](#default-choice)
- [**LOOKAHEAD Specification**](#specification)
  * [Multi-token LOOKAHEAD](#multi-token)
  * [Setting a global LOOKAHEAD](#global)
  * [Setting a local LOOKAHEAD](#local)
  * [Syntactic LOOKAHEAD](#syntactic)
  * [Semantic LOOKAHEAD](#semantic)
  * [General structure of LOOKAHEAD](#general)

## <a name="what-is"></a>What is a LOOKAHEAD?

The job of a parser is to read an input stream and determine whether or not the input stream conforms to the grammar.

This determination in its most general form can be quite time consuming.

#### <a name="example1"></a>Example 1

```java
void Input() :
{}
{
  "a" BC() "c"
}

void BC() :
{}
{
  "b" [ "c" ]
}
```

In this simple example, it is quite clear that there are exactly two strings that match the above grammar, namely:

```java
abc
abcc
```

The general way to perform this match is to walk through the grammar based on the string as follows (here we use `abc` as the input string):

| Step  | Description |
| :---: | :--- |
| 1 | There is only one choice here - the first input character must be `a` and since that is indeed the case, we are OK.|
| 2 | We now proceed on to non-terminal BC. Again there is only one choice for the next input character - it must be `b`. The input matches this one too, so we are still OK.|
| 3 | We now come to a *choice point* in the grammar. We can either go inside the `[...]` and match it, or ignore it altogether. We decide to go inside. So the next input character must be a `c`. We are again OK.|
| 4 | Now we have completed with non-terminal BC and go back to non-terminal `Input`. Now the grammar says the next character must be yet another `c`. But there are no more input characters, so we have a problem.|
| 5 | When we have such a problem in the general case, we conclude that we may have made a bad choice somewhere. In this case, we made a bad choice in step [3]. So we retrace our steps back to step [3] and make another choice and try that. This process is called *backtracking*.|
| 6 | We have now backtracked and made the other choice we could have made at step [3] - namely, ignore the `[...]`. Now we have completed with non-terminal BC and go back to non-terminal `Input`. Now the grammar says the next character must be yet another `c`. The next input character is a `c`, so we are OK now.|
| 7 | We realize we have reached the end of the grammar (end of non-terminal `Input`) successfully. This means we have successfully matched the string `abc` to the grammar.|

As the above example indicates, the general problem of matching an input with a grammar may result in large amounts of backtracking and making new choices and this can consume a lot of time. The amount of time taken can also be a function of how the grammar is written. Note that many grammars can be written to cover the same set of inputs - or the same language, i.e. there can be multiple equivalent grammars for the same input language.

The following grammar would speed up the parsing of the same language as compared to the previous grammar:

```java
void Input() :
{}
{
  "a" "b" "c" [ "c" ]
}
```

The following grammar slows it down even more since the parser has to backtrack all the way to the beginning:

```java
void Input() :
{}
{
  "a" "b" "c" "c"
|
  "a" "b" "c"
}
```

We can even have a grammar that looks like the following:

```java
void Input() :
{}
{
  "a" ( BC1() | BC2() )
}

void BC1() :
{}
{
  "b" "c" "c"
}

void BC2() :
{}
{
  "b" "c" [ "c" ]
}
```

This grammar can match `abcc` in two ways, and is therefore considered *ambiguous*.

### <a name="backtracking"></a>Avoiding backtracking

The performance hit from such backtracking is unacceptable for most systems that include a parser. Hence most parsers do not backtrack in this general manner - or do not backtrack at all. Rather, they make decisions at choice points based on limited information and then commit to it.

Parsers generated by JavaCC make decisions at choice points based on some exploration of tokens further ahead in the input stream, and once they make such a decision, they commit to it - i.e. no backtracking is performed once a decision is made.

The process of exploring tokens further in the input stream is termed *looking ahead* into the input stream - hence our use of the term `LOOKAHEAD`.

Since some of these decisions may be made with less than perfect information, you need to know something about `LOOKAHEAD` to make your grammar work correctly. *N.B. JavaCC will warn you in these situations*.

The two ways in which you make the choice decisions work properly are:

1. Modify the grammar to make it simpler.
2. Insert hints at the more complicated choice points to help the parser make the right choices.


### <a name="choice-points"></a>Choice points in JavaCC grammars

There are 4 types of choice points in JavaCC:

| Expansion                                                   | Description |
| :---------------------------------------------------------: | :--- |
| <p><code>( exp1 \| exp2 \| ... )</code></p> | The generated parser must somehow determine which of `exp1`, `exp2` etc to select to continue parsing. |
| <p><code>( exp )?</code></p> | The generated parser must somehow determine whether to choose `exp` or to continue beyond the `( exp )?` without choosing `exp`. *N.B. Note: `( exp )?` may also be written as `[ exp ]`*. |
| <p><code>( exp )*</code></p> | The generated parser must do the same thing as in the previous case, and furthermore, after each time a successful match of `exp` (if `exp` was chosen) is completed, this choice determination must be made again. |
| <p><code>( exp )+</code></p> | This is essentially similar to the previous case with a mandatory first match to `exp`. |

Remember that token specifications that occur within angular brackets `<...>` also have choice points. But these choices are made in different ways and are the subject of a different tutorial.

### <a name="default-choice"></a>Default choice determination algorithm

The default choice determination algorithm looks ahead 1 token in the input stream and uses this to help make its choice at choice points. The following examples will describe the default algorithm fully.

#### <a name="example2"></a>Example 2

Consider the following grammar:

```java
void basic_expr() :
{}
{
  <ID> "(" expr() ")"	// Choice 1
|
  "(" expr() ")"	// Choice 2
|
  "new" <ID>		// Choice 3
}
```

The choice determination algorithm works as follows:

```java
if (next token is <ID>) {
  // choose Choice 1
} else if (next token is "(") {
  // choose Choice 2
} else if (next token is "new") {
  // choose Choice 3
} else {
  // produce an error message
}
```

In the above example, the grammar has been written such that the default choice determination algorithm does the right thing. Another thing to note is that the choice determination algorithm works in a top to bottom order - if `Choice 1` was selected, the other choices are not even considered. While this is not an issue in this example (except for performance) it will become important when local ambiguities require the insertion of `LOOKAHEAD` hints.

#### <a name="example3"></a>Example 3

Consider the modified grammar:

```java
void basic_expr() :
{}
{
  <ID> "(" expr() ")"	// Choice 1
|
  "(" expr() ")"	// Choice 2
|
  "new" <ID>		// Choice 3
|
  <ID> "." <ID>		// Choice 4
}
```

Then the default algorithm will always choose `Choice 1` when the next input token is `<ID>` and never choose `Choice 4` even if the token following `<ID>` is a `.`.

You can try running the parser generated from [Example 3](#example3) on the input `id1.id2`. It will complain that it encountered a `.` when it was expecting a `(`.

*N.B. When you built the parser, it would have given you the following warning message:*

```java
Warning: Choice conflict involving two expansions at
         line 25, column 3 and line 31, column 3 respectively.
         A common prefix is: <ID>
         Consider using a lookahead of 2 for earlier expansion.
```

JavaCC detected a situation in the grammar which may cause the default lookahead algorithm to do strange things. The generated parser will still work using the default lookahead algorithm, but it may not do what you expect of it.

#### <a name="example4"></a>Example 4

Now consider the following grammar:

```java
void identifier_list() :
{}
{
  <ID> ( "," <ID> )*
}
```

Suppose the first `<ID>` has already been matched and that the parser has reached the choice point (the `(...)*` construct). Here's how the choice determination algorithm works:

```java
while (next token is ",") {
  choose the nested expansion (i.e. go into the (...)* construct)
	consume the "," token
	if (next token is <ID>) {
    consume it, otherwise report error
  }
}
```

In the above example, note that the choice determination algorithm does not look beyond the `(...)*` construct to make its decision.

#### <a name="example5"></a>Example 5

Suppose there was another production in that same grammar as follows:

```java
void funny_list() :
{}
{
  identifier_list() "," <INT>
}
```

When the default algorithm is making a choice at `( "," <ID> )*` it will always go into the `(...)*` construct if the next token is a `,`. It will do this even when `identifier_list` was called from `funny_list` and the token after the `,` is an `<INT>`. Intuitively, the right thing to do in this situation is to skip the `(...)*` construct and return to `funny_list`.

As a concrete example, suppose your input was `id1, id2, 5`, the parser will complain that it encountered a `5` when it was expecting an `<ID>`.

*N.B. When you built the parser, it would have given you the following warning message:*

```java
Warning: Choice conflict in (...)* construct at line 25, column 8.
         Expansion nested within construct and expansion following construct
         have common prefixes, one of which is: ","
         Consider using a lookahead of 2 or more for nested expansion.
```

JavaCC detected a situation in the grammar which may cause the default lookahead algorithm to do strange things. The generated parser will still work using the default lookahead algorithm, but it may not do what you expect of it.

We have shown examples of two kinds of choice points in the examples above - `exp1 | exp2 | ...`, and `(exp)*`. The other two types of choice points `(exp)+` and `(exp)?` behave similarly to `(exp)*` so it is not necessary to provide further examples of their use.

## <a name="specification"></a>LOOKAHEAD Specification

### <a name="multi-token"></a>Multi-token LOOKAHEAD specifications

So far, we have described the default lookahead algorithm of the generated parsers. In the majority of situations, the default algorithm works just fine. In situations where it does not work well, JavaCC provides you with warning messages like the ones shown above. If you have a grammar that goes through JavaCC without producing any warnings, then the grammar is a `LL(1)` grammar. Essentially, `LL(1)` grammars are those that can be handled by top-down parsers (such as those generated by JavaCC) using at most one token of `LOOKAHEAD`.

When you get these warning messages, you can do one of two things.

#### Option 1 - Grammar modification

You can modify your grammar so that the warning messages go away. That is, you can attempt to make your grammar `LL(1)` by making some changes to it.

#### <a name="example6"></a>Example 6

The following grammar shows how you how to change [Example 3](#example3) to make it `LL(1)`:

```java
void basic_expr() :
{}
{
  <ID> ( "(" expr() ")" | "." <ID> )
|
  "(" expr() ")"
|
  "new" <ID>
}
```

What we have done here is to refactor the fourth choice into the first choice. Note how we have placed their common first token `<ID>` outside the parentheses, and then within the parentheses we have yet another choice which can now be performed by looking at only one token in the input stream and comparing it with `(` and `.`. This process of modifying grammars to make them `LL(1)` is called *left factoring*.

#### <a name="example7"></a>Example 7

The following grammar shows how [Example 5](#example5) may be changed to make it `LL(1)`:

```java
void funny_list() :
{}
{
  <ID> "," ( <ID> "," )* <INT>
}
```

*N.B. This change is somewhat more drastic.*

### Option 2 - Parser hints

You can provide the generated parser with some hints to help it out in the non-`LL(1)` situations that the warning messages bring to your attention.

All such hints are specified using either setting the global `LOOKAHEAD` value to a larger value or by using the `LOOKAHEAD(...)` construct to provide a local hint.

A design decision must be made to determine if `Option 1` or `Option 2` is the right one to take. The only advantage of choosing `Option 1` is that it makes your grammar perform better. JavaCC generated parsers can handle `LL(1)` constructs much faster than other constructs. However, the advantage of choosing `Option 2` is that you have a simpler grammar - one that is easier to develop and maintain, and focuses on human-friendliness and not machine-friendliness.

Sometimes `Option 2` is the only choice - especially in the presence of user actions.

Suppose [Example 3](#example3) contained actions as shown below:

```java
void basic_expr() :
{}
{
  { initMethodTables(); } <ID> "(" expr() ")"
|
  "(" expr() ")"
|
  "new" <ID>
|
  { initObjectTables(); } <ID> "." <ID>
}
```

Since the actions are different, left-factoring cannot be performed.


### <a name="global"></a>Setting a global LOOKAHEAD specification

You can set a global `LOOKAHEAD` specification by using the option `LOOKAHEAD` either from the command line, or at the beginning of the grammar file in the options section. The value of this option is an integer which is the number of tokens to look ahead when making choice decisions. As you may have guessed, the default value of this option is `1` - which derives the default `LOOKAHEAD` algorithm described above.

Suppose you set the value of this option to `2`. Then the `LOOKAHEAD` algorithm derived from this looks at two tokens (instead of just one token) before making a choice decision. Hence, in [Example 3](#example3), `Choice 1` will be taken only if the next two tokens are `<ID>` and `(`, while `Choice 4` will be taken only if the next two tokens are `<ID>` and `.`. Hence, the parser will now work properly for [Example 3](#example3). Similarly, the problem with [Example 5](#example5) also goes away since the parser goes into the `(...)*` construct only when the next two tokens are `,` and `<ID>`.

By setting the global `LOOKAHEAD` to `2` the parsing algorithm essentially becomes `LL(2)`. Since you can set the global `LOOKAHEAD` to any value, parsers generated by JavaCC are called `LL(k)` parsers.

## <a name="local"></a>Setting a local LOOKAHEAD specification

You can also set a local `LOOKAHEAD` specification that affects only a specific choice point. This way, the majority of the grammar can remain `LL(1)` and hence perform better, while at the same time one gets the flexibility of `LL(k)` grammars.

#### <a name="example8"></a>Example 8

Here's how [Example 3](#example3) is modified with local `LOOKAHEAD` to fix the choice ambiguity problem:

```java
void basic_expr() :
{}
{
  LOOKAHEAD(2)
  <ID> "(" expr() ")"	// Choice 1
|
  "(" expr() ")"	// Choice 2
|
  "new" <ID>		// Choice 3
|
  <ID> "." <ID>		// Choice 4
}
```

Only the first choice (the first condition in the translation below) is affected by the `LOOKAHEAD` specification. All others continue to use a single token of `LOOKAHEAD`:

```java
if (next 2 tokens are <ID> and "(" ) {
  // choose Choice 1
} else if (next token is "(") {
  // choose Choice 2
} else if (next token is "new") {
  // choose Choice 3
} else if (next token is <ID>) {
  // choose Choice 4
} else {
  // produce an error message
}
```

#### <a name="example9"></a>Example 9

Similarly, [Example 5](#example5) can be modified as shown below:

```java
void identifier_list() :
{}
{
  <ID> ( LOOKAHEAD(2) "," <ID> )*
}
```

*N.B. The `LOOKAHEAD` specification has to occur inside the `(...)` which is the choice is being made. The translation for this construct is shown below (after the first `<ID>` has been consumed):*

```java
while (next 2 tokens are "," and <ID>) {
  choose the nested expansion (i.e., go into the (...)* construct)
  consume the "," token
  consume the <ID> token
}
```

**We strongly discourage you from modifying the global LOOKAHEAD default**.

Most grammars are predominantly `LL(1)`, hence you will be unnecessarily degrading performance by converting the entire grammar to `LL(k)` to facilitate just some portions of the grammar that are not `LL(1)`. If your grammar and input files being parsed are very small, then this is okay.

You should also keep in mind that the warning messages JavaCC prints when it detects ambiguities at choice points (such as the two messages shown earlier) simply tells you that the specified choice points are not `LL(1)`. JavaCC does not verify the correctness of your local `LOOKAHEAD` specification - it assumes you know what you are doing.


#### <a name="example10"></a>Example 10

JavaCC cannot verify the correctness of local `LOOKAHEAD`'s as the following example of `if` statements illustrates:

```java
void IfStm() :
{}
{
 "if" C() S() [ "else" S() ]
}

void S() :
{}
{
  ...
|
  IfStm()
}
```

This example is the famous *dangling else* problem. If you have a program that looks like:

```java
if C1 if C2 S1 else S2
```

The `else S2` can be bound to either of the two `if` statements. The standard interpretation is that it is bound to the inner `if` statement (the one closest to it). The default choice determination algorithm happens to do the right thing, but it still prints the following warning message:

```java
Warning: Choice conflict in [...] construct at line 25, column 15.
         Expansion nested within construct and expansion following construct
         have common prefixes, one of which is: "else"
         Consider using a lookahead of 2 or more for nested expansion.
```

To suppress the warning message, you could simply tell JavaCC that you know what you are doing as follows:

```java
void IfStm() :
{}
{
 "if" C() S() [ LOOKAHEAD(1) "else" S() ]
}
```

To force `LOOKAHEAD` ambiguity checking in such instances, set the option `FORCE_LA_CHECK` to `true`.

### <a name="syntactic"></a>Syntactic LOOKAHEAD

Consider the following production taken from the Java grammar:

```java
void TypeDeclaration() :
{}
{
  ClassDeclaration()
|
  InterfaceDeclaration()
}
```

At the syntactic level, `ClassDeclaration` can start with any number of `abstract`, `final`, and `public` statements. While a subsequent semantic check will produce error messages for multiple uses of the same modifier, this does not happen until parsing is completely over. Similarly, `InterfaceDeclaration` can start with any number of `abstract` and `public` statements.

What if the next tokens in the input stream are a very large number of `abstract` statements (say 100 of them) followed by `interface`? It is clear that a fixed amount of `LOOKAHEAD` (such as `LOOKAHEAD(100)`) will not suffice. One can argue that this is such a weird situation that it does not warrant any reasonable error message and that it is okay to make the wrong choice in some pathological situations.

But suppose one wanted to be precise about this. The solution here is to set the `LOOKAHEAD` to infinity - that is, set no bounds on the number of tokens to `LOOKAHEAD`. One way to do this is to use a very large integer value (such as the largest possible integer) as follows:

```java
void TypeDeclaration() :
{}
{
  LOOKAHEAD(2147483647)
  ClassDeclaration()
|
  InterfaceDeclaration()
}
```

One can also achieve the same effect with *syntactic* `LOOKAHEAD`. In syntactic `LOOKAHEAD`, you specify an expansion to try it out and, if that succeeds, then the following choice is taken.

The above example can be rewritten using syntactic `LOOKAHEAD` as follows:

```java
void TypeDeclaration() :
{}
{
  LOOKAHEAD(ClassDeclaration())
  ClassDeclaration()
|
  InterfaceDeclaration()
}
```

Essentially, what this is saying is:

```java
if (the tokens from the input stream match ClassDeclaration) {
  // choose ClassDeclaration()
} else if (next token matches InterfaceDeclaration) {
  // choose InterfaceDeclaration()
} else {
  // produce an error message
}
```

The problem with the above syntactic `LOOKAHEAD` specification is that the `LOOKAHEAD` calculation takes too much time and does a lot of unnecessary checking. In this case, the `LOOKAHEAD` calculation can stop as soon as the token `class` is encountered, but the specification forces the calculation to continue until the end of the class declaration has been reached, which is rather time consuming.

This problem can be solved by placing a shorter expansion to try out in the syntactic `LOOKAHEAD` specification as in the following example:

```java
void TypeDeclaration() :
{}
{
  LOOKAHEAD( ( "abstract" | "final" | "public" )* "class" )
  ClassDeclaration()
|
  InterfaceDeclaration()
}
```

Essentially, what this is saying is:

```java
if (the next set of tokens from the input stream are a sequence of
  "abstract", "final", and "public" followed by a "class") {
  // choose ClassDeclaration()
} else if (next token matches InterfaceDeclaration) {
  // choose InterfaceDeclaration()
} else {
  // produce an error message
}
```

By doing this, you make the choice determination algorithm stop as soon as it sees `class` i.e. make its decision at the earliest possible time.

You can place a bound on the number of tokens to consume during syntactic lookahead as follows:

```java
void TypeDeclaration() :
{}
{
  LOOKAHEAD(10, ( "abstract" | "final" | "public" )* "class" )
  ClassDeclaration()
|
  InterfaceDeclaration()
}
```
In this case, the `LOOKAHEAD` determination is not permitted to go beyond `10` tokens. If it reaches this limit and is still successfully matching `( "abstract" | "final" | "public" )* "class"`, then `ClassDeclaration` is selected.

When such a limit is not specified, it defaults to the largest integer value (`2147483647`).

### <a name="semantic"></a>Semantic LOOKAHEAD

Let us go back to [Example 1](#example1):

```java
void Input() :
{}
{
  "a" BC() "c"
}

void BC() :
{}
{
  "b" [ "c" ]
}
```

Let us suppose that there is a good reason for writing a grammar this way (maybe the way actions are embedded). As noted earlier, this grammar recognizes two string `abc` and `abcc`. The problem here is that the default `LL(1)` algorithm will choose the `[ "c" ]` every time it sees a `c` and therefore `abc` will never be matched. We need to specify that this choice must be made only when the next token is a `c`, and the token following that is not a `c`. This is a negative statement - one that cannot be made using syntactic `LOOKAHEAD`.

We can use semantic `LOOKAHEAD` for this purpose. With semantic `LOOKAHEAD`, you can specify any arbitrary boolean expression whose evaluation determines which choice to take at a choice point.

The above example can be instrumented with semantic `LOOKAHEAD` as follows:

```java
void BC() :
{}
{
  "b"
  [ LOOKAHEAD( { getToken(1).kind == C && getToken(2).kind != C } )
    <C:"c">
  ]
}
```

First, we give the token `c` a label `C` so that we can refer to it from the semantic `LOOKAHEAD`. The boolean expression essentially states the desired property.

The choice determination decision is therefore:

```java
if (next token is "c" and following token is not "c") {
  // choose the nested expansion (i.e., go into the [...] construct)
} else {
  // go beyond the [...] construct without entering it.
}
```

This example can be rewritten to combine both syntactic and semantic `LOOKAHEAD` as follows :

```java
void BC() :
{}
{
  "b"
  [ LOOKAHEAD( "c", { getToken(2).kind != C } )
    <C:"c">
  ]
}
```

Recognize the first `c` using syntactic `LOOKAHEAD` and the absence of the second using semantic `LOOKAHEAD`.

### <a name="general"></a>General structure of LOOKAHEAD

We've pretty much covered the various aspects of `LOOKAHEAD` in the previous sections. We shall now present a formal language reference for `LOOKAHEAD` in JavaCC.

The general structure of a `LOOKAHEAD` specification is:

```java
LOOKAHEAD ( amount, expansion, { boolean_expression } )
```

The `amount` specifies the number of tokens to `LOOKAHEAD`, `expansion` specifies the expansion to use to perform syntactic `LOOKAHEAD`, and `boolean_expression` is the expression to use for semantic `LOOKAHEAD`.

At least one of the three entries must be present. If more than one are present, they are separated by commas.

The default values for each of these entities is defined below:

```java
amount:
  - if expansion is present, this defaults to 2147483647.
  - otherwise (boolean_expression must be present then) this defaults to 0.
```

*N.B. When `amount` is `0`, no syntactic `LOOKAHEAD` is performed.  Also, `amount` does not affect the semantic `LOOKAHEAD`.*

```java
expansion:
  - defaults to the expansion being considered.
```

```java
boolean_expression:
  - defaults to true.
```
<!---
## Nested Evaluation of Semantic `LOOKAHEAD`

To be done.

## `JAVACODE` Productions

To be done.
-->
<br>

---

[NEXT >>](charstream.md)

<br>