Using GLR in its Simplest Form
==============================

The C++ example for GLR (see GLR Parsers) explains how to use the GLR parsing algorithm with some advanced features such as %dprec and %merge to handle syntactically ambiguous grammars. However, the GLR algorithm can also be used in a simpler way to parse grammars that are unambiguous, but fail to be LALR(1). Such grammars typically require more than one symbol of lookahead, or (in rare cases) fall into the category of grammars in which the LALR(1) algorithm throws away too much information (they are in LR(1), but not LALR(1), Mystery Conflicts).

This is described in the following section, using a problem that arises in the declaration of enumerated and subrange types in the programming language Pascal. These declarations look like this:

     type
       subrange = lo .. hi;
       enum = (a, b, c);

The original language standard allows only numeric literals and constant identifiers for the subrange bounds (lo and hi), but Extended Pascal (ISO 10206) and many other Pascal implementations allow arbitrary expressions there. This gives rise to the following situation, containing a superfluous pair of parentheses:

     type
       subrange = (a) .. b;

Compare this to the following declaration of an enumerated type with only one value:

     type
       enum = (a);

(The second declaration, as well as the parentheses in the first one, may not appear very useful, but they are syntactically valid, and there are more complicated, practically relevant cases.)

These two declarations look identical until the .. token. In particular, with normal LALR(1) one-token look-ahead it is not possible to decide between the two forms at the time the identifier a is parsed. It is, however, very desirable if not necessary for a compiler/interpreter to do so, since in the second case, a must become a new identifier to represent the enumeration value, while in the first case, a must be evaluated with its current meaning, which may be a constant or even a function call.

Parsing (a) as an ``unspecified identifier in parentheses'', to be resolved later, is not impossible, but requires substantial contortions both in the semantic actions and in large parts of the grammar (where the parentheses are nested in the recursive rules for expressions), which is generally not desirable.

One might think of using the lexer to distinguish between the two forms by returning different tokens for currently defined and undefined identifiers. But if these declarations occur in a local scope, and a is defined in an outer scope, indeed both forms are possible---either locally redefining a, or using the value of a from the outer scope. So this approach cannot work.

A solution to this problem is to use a GLR parser in its simplest form, i.e. without using special features such as %dprec and %merge. When the GLR parser reaches the critical state, it will simply split into two branches and pursue both syntax rules simultaneously. Sooner or later, one of them will run into a parsing error. In particular, if there is a .. token before the next ;, the rule for enumerated types will fail since it cannot accept .. anywhere; otherwise, the subrange type rule will fail since it requires a .. token. So one of the branches will die silently, and the other one continue normally, performing all the intermediate actions that were postponed during the split.

Of course, it is possible for both rules to fail, if the input is syntactically incorrect. Then both branches will die and the parser will report a syntax error as usual.

The effect of all this is that the parser seems to ``guess'' the correct branch to take, or in other words, it seems to use more look-ahead than the underlying LALR(1) algorithm actually allows for. In this example, LALR(2) would suffice, but also some cases that are not LALR(k) for any k can be handled this way.

Since there can be only two branches and necessarily one of them will die, there is no need to worry about merging the branches by using dynamic precedence or %merge.

Another potential problem of GLR does not arise here, either. In general, a GLR parser can take quadratic or cubic worst-case time, and the current Bison parser even takes exponential time and space for some grammars. In practice, this rarely happens, and for many grammars it is possible to prove that it cannot happen. This is the case in the present example: There is only one conflict between two rules, as Bison will report, and the environment where the conflict arises, i.e. type declarations, cannot be nested. So the number of branches that can exist at any time is limited by a constant (2), and the parsing time is still linear.

So here we have a case where we can use the benefits of GLR, almost without disadvantages. There are two things to note, though: Of course, one should carefully analyze the conflicts as reported by Bison to make sure that GLR splitting is only done where it is intended to be. A GLR parser splitting inadvertently may cause problems less obvious than an LALR parser statically choosing the wrong alternative in a conflict.

Also, interactions with the lexer (see Semantic Tokens) have to be considered with great care. Since a split parser consumes tokens without performing any actions during the split, the lexer cannot have current information about the proceeding parsing. Some cases of lexer interactions can simply be eliminated by using GLR, i.e. shifting the complications from the lexer to the parser. Remaining cases have to be checked for safety.

In our example, it would be safe for the lexer to return tokens based on their current meanings in some symbol table, because no new symbols are defined in the middle of a type declaration. (Though it is possible for a compiler/interpreter to define the enumeration constants as they are parsed, before the type declaration is completed, it actually makes no difference since they cannot be used within the same enumerated type declaration.)

Here is a Bison grammar corresponding to the example above. It parses a vastly simplified form of Pascal type declarations.

     %token TYPE DOTDOT ID

     %left '+' '-'
     %left '*' '/'

     %%

     decl: TYPE type_decls
         ;

     type_decls: type_decl
               | type_decls type_decl
               ;

     type_decl: ID '=' type ';'
              ;

     type: '(' id_list ')'
         | expr DOTDOT expr
         ;

     id_list: ID
            | id_list ',' ID
            ;

     expr: '(' expr ')'
         | expr '+' expr
         | expr '-' expr
         | expr '*' expr
         | expr '/' expr
         | ID
         ;

When used as a normal LALR(1) grammar, Bison will correctly complain about one reduce/reduce conflict. In the conflicting situation the parser will choose one of the alternatives, arbitrarily the one declared first. Therefore the following correct input is not recognized:

     type
       t = (a) .. b;

The parser can be turned into a GLR parser, while also telling Bison to be silent about the one known reduce/reduce conflict, simply by adding these two declarations to the Bison input file:

     %glr-parser
     %expect-rr 1

No change in the grammar itself is required. Now the parser will recognize all valid declarations, according to the limited syntax above, transparently. In fact, the user will not even notice when the parser splits.