Grammatica Reference Manual

Handling Ambiguities

Grammar ambiguities are points in the grammar where multiple alternatives conflict. As the parser is deterministic, a single alternative must be chosen and grammar ambiguities are therefore not allowed.

By looking several tokens ahead, a parser is able to resolve some grammar ambiguities. The LL parser in Grammatica supports looking many tokens ahead. See the figure below for a simple example that can be resolved by looking more than one token ahead.

Prod = "a" "b"
     | "a" "c" ;

Figure 1. A simple grammar ambiguity. This ambiguity cause problems for parsers with a single look-ahead token, but Grammatica can handle it by resorting to two look-ahead tokens.

Unfortunately, most ambiguities are not as easy to resolve automatically as the one in the figure above. An infinite number of look-ahead tokens may for example not be enough if the collision can itself consist of an infinite number of tokens. In these cases, the grammar must be rewritten to remove the ambiguity. In the figure below one such ambiguity and a resolution is shown.

OldProd = "a"* "b"
        | "a"* "c" ;

NewProd = "a"* ProdTail ;

ProdTail = "b"
         | "c" ;

Figure 2. An unresolvable grammar ambiguity and a refactored production. As the number of conflicting tokens is potentially infinite, this ambiguity cannot be resolved by the use of a look-ahead parser. Instead the production must be split into two, as illustrated by NewProd and ProdTail.

Unresolvable ambiguities can also occur due to loops in the grammar, causing some token sequence to possibly be repeated infinitely. Some ambiguities are also caused by an optional reference conflicting with the next reference inside a production alternative. All these types of ambiguities are detected by Grammatica and reported to the user.