Bison: GLR-parsing of valid expression fails without error message

Question

I'm working on a GLR-parser in GNU bison and I have the following problem:

the language I'm trying to parse allows boolean expressions including relations (<,>,<=,...) and boolean composition (and, or, not). Now the problem is that the language also allows to have multiple arithmetic expressions on the right side of a relation... and they are composed using the same AND token that is used for boolean composition! This is a very dumb language-design, but I can't change it.

So you can have a > b and c which is supposed to be equivalent to (a > b) and (a > c) and you can also have a > b and c > d which is supposed to be equivalent to (a > b) and (c > d)

The S/R conflict this causes is already obvious in this example: after reading a > b with lookahead and you could either reduce the a > b to a boolean expression and wait for another boolean expression or you could shift the and and wait for another arithmetic expression.

My grammar currently looks like this:

booleanexpression
    : relation
    | booleanexpression TOK_AND booleanexpression
    ...
;
relation
    : arithmeticexpression TOK_GT maxtree
    ...
;
maxtree
    : arithmeticexpression
    | maxtree TOK_AND maxtree
    ...
;

The language is clearly not LR(k) for any k, since the S/R conflict can't be resolved using any constant k-lookahead, because the arithmeticexpression in between can have arbitrarily many tokens. Because of that, I turned GLR-parsing on.

But when I try to parse a > b and c with this, I can see in my debug outputs, that the parser behaves like this:

• it reads the a and at lookahead > it reduces the a to an arithmeticexpression
• it reads the b and at lookahead and it reduces the b to an arithmeticexpression and then already to a maxtree
• it reduces the a > b to a relation
• it reads the c and reduces it to an arithmeticexpression

then nothing happens! The and c are apparently discarded - the debug outputs don't show any action for these tokens. Not even an error message. The corresponding if-statement doesn't exist in my AST (I still get an AST because I have error recovery).

I would think that, after reading the b, there should be 2 stacks. But then the b shouldn't be reduced. Or at least it should give me some error message ("language is ambiguous" would be okay and I have seen that message before - I don't see why it wouldn't apply here). Can anyone make sense of this?

From looking at the grammar for a while, you can tell that the main question here is whether after the next arithmeticexpression there comes

• another relation token (then you should reduce)
• another boolean composition (then you should shift)
• a token outside of the boolean/arithmetic -expression syntax (like THEN) which would terminate the expression and you should also shift

Can you think of a different grammar that captures the situation in a better / more deterministic way? How would you approach the problem? I'm currently thinking about making the grammar more right-to-left, like

booleanexpression : relation AND booleanexpression
maxtree : arithmeticexpression AND maxtree
etc.

I think that would make bison prefer shifting and only reduce on the right first. Maybe by using different non-terminals it would allow a quasi-"lookahead" behind the arithmeticexpression...

Side note: GnuCOBOL handles this problem by just collecting all the tokens, pushing them on an intermediate stack and manually building the expression from there. That discourages me, but I cling to the hope that they did it this way because bison didn't support GLR-parsing when they started...

EDIT: a small reproducible example

%{
#include <stdio.h>
int yylex ();
void yyerror(const char* msg);
%}

%glr-parser
%left '&'
%left '>'

%%
input: %empty | input bool '\n' {printf("\n");};

arith : 'a' | 'b' | 'c';
maxtree : arith { printf("[maxtree : arith]  "); }
        | maxtree '&' maxtree { printf("[maxtree : maxtree & maxtree]  "); } ;
rel : arith '>' maxtree { printf("[rel : arith > maxtree]  "); } ;
bool : rel { printf("[bool : rel]  "); }
     | bool '&' bool { printf("[bool : bool & bool]  "); } ;
%%

void yyerror(const char* msg) { printf("%s\n", msg); }
int yylex () {
    int c;
    while ((c = getchar ()) == ' ' || c == '\t');
    return c == EOF ? 0 : c;
}
int main (int argc, char** argv) {
    return yyparse();
}

this one strangely does print the error message "syntax error" on input a>b&c.

Answer 1

Being able to simplify grammars by using precedence declarations is really handy (sometimes) [Note 1] but it doesn't play well with using GLR parsers because it can lead to early rejection of an unambiguous parse.

The idea behind precedence declarations is that they resolve ambiguities (or, more accurately, shift/reduce conflicts) using a simple one-token lookahead and a configured precedence between the possible reduction and the possible shift. If a grammar has no shift/reduce conflict, the precedence declarations won't be used, but if they are used they will be used to suppress either the shift or the reduce, depending on the (static) precedence relationship.

A Bison-generated GLR parser does not actually resolve ambiguity, but it allows possibly incorrect parses to continue to be developed until the ambiguity is resolved by the grammar. Unlike the use of precedence, this is a delayed resolution; a bit slower but a lot more powerful. (GLR parsers can produce a "parse forest" containing all possible parses. But Bison doesn't implement this feature, since it expects to be parsing programming languages and unlike human languages, programming languages cannot be ambiguous.)

In your language, it is impossible to resolve the non-determinism of the shift/reduce conflict statically, as you note yourself in the question. Your grammar is simply not LR(1), much less operator precedence, and GLR parsing is therefore a practical solution. But you have to allow GLR to do its work. Prematurely eliminating one of the plausible parses with a precedence comparison will prevent the GLR algorithm from considering it later. This will be particularly serious if you manage to eliminate the only parse which could have been correct.

In your grammar, it is impossible to define a precedence relationship between the rel productions and the & symbol, because no precedence relationship exists. In some sentences, the rel reduction needs to win; in other sentences, the shift should win. Since the grammar is not ambiguous, GLR will eventually figure out which is which, as long as both the shift and the reduce are allowed to proceed.

In your full language, both boolean and arithmetic expressions have something akin to operator precedence, but only within their respective domains. An operator precedence parser (and, equivalently, yacc/bison's precedence declarations) works by erasing the difference between different non-terminals; it cannot handle a grammar like yours in which some operator has different precedences in different domains (or between different domains).

Fortunately, this particular use of precedence declarations is only a shortcut; it does not give any additional power to the grammar and can easily and mechanically be implemented by creating new non-terminals, one for each precedence level. The alternative grammar will not be ambiguous. The classic example, which you can find in pretty well any textbook or tutorial which includes parsing arithmetic expressions, is the expr/term/factor grammar. Here I've also provided the precedence grammar for comparison:

                              %left '+' '-'
                              %left '*' '/'
%%                            %%
expr  : term
      | expr '+' term         expr: expr '+' expr
      | expr '-' term             | expr '-' expr
term  : factor
      | term '*' factor           | expr '*' expr
      | term '/' factor           | expr '/' expr
factor: ID                        | ID
      | '(' expr ')'              | '(' expr ')'

In your minimal example, there are already enough non-terminals that no new ones need to be invented, so I've just rewritten it according to the above model.

I've left the actions as I wrote them, in case the style is useful to you. Note that this style leaks memory like a sieve, but that's ok for quick tests:

%code top {
#define _GNU_SOURCE 1
}

%{
#include <ctype.h>
#include <stdio.h>
#include <string.h>

int yylex(void);
void yyerror(const char* msg);
%}

%define api.value.type { char* }
%glr-parser
%token ID

%%
input   : %empty
        | input bool '\n'   { puts($2); }

arith   : ID
maxtree : arith 
        | maxtree '&' arith { asprintf(&$$, "[maxtree& %s %s]", $1, $3); }
rel     : arith '>' maxtree { asprintf(&$$, "[COMP %s %s]", $1, $3); }
bool    : rel
        | bool '&' rel      { asprintf(&$$, "[AND %s %s]", $1, $3); }
%%

void yyerror(const char* msg) { printf("%s\n", msg); }
int yylex(void) {
    int c;
    while ((c = getchar ()) == ' ' || c == '\t');
    if (isalpha(c)) {
      *(yylval = strdup(" ")) = c;
      return ID;
    }
    else return c == EOF ? 0 : c;
}

int main (int argc, char** argv) {
#if YYDEBUG
    if (argc > 1 && strncmp(argv[1], "-d", 2) == 0) yydebug = 1;
#endif
    return yyparse();
}

Here's a sample run. Note the warning from bison about a shift/reduce conflict. If there had been no such warning, the GLR parser would probably be unnecessary, since a grammar without conflicts is deterministic. (On the other hand, since bison's GLR implementation optimises for determinism, there is not too much cost for using a GLR parser on a deterministic language.)

$ bison -t -o glr_prec.c glr_prec.y
glr_prec.y: warning: 1 shift/reduce conflict [-Wconflicts-sr]
$ gcc -Wall -o glr_prec glr_prec.c
$ ./glr_prec
a>b
[COMP a b]
a>b & c
[COMP a [maxtree& b c]]
a>b & c>d
[AND [COMP a b] [COMP c d]]
a>b & c & c>d
[AND [COMP a [maxtree& b c]] [COMP c d]]
a>b & c>d & e
[AND [COMP a b] [COMP c [maxtree& d e]]]
$

---

Notes

1. Although precedence declarations are handy when you understand what's actually going on, there is a huge tendency for people to just cargo-cult them from some other grammar they found on the internet, and not infrequently a grammar which was also cargo-culted from somewhere else. When the precedence declarations don't work as expected, the next step is to randomly modify them in the hopes of finding a configuration which works. Sometimes that succeeds, often leaving behind unnecessary detritus which will go on to be cargo-culted again.

   So, although there are circumstances in which precedence declarations really simplify grammars and the unambiguous implementation would be quite a lot more complicated (such as dangling-else resolution in languages which have many different compound statement types), I've still found myself recommending against their use.

   In a recent answer to a different question, I wrote what I hope is a good explanation of the precedence algorithm (and if it isn't, please let me know how it falls short).

Answer 2

Welcome to the wonderful world of COBOL. I could be wrong, but you may have a few additional problems here. An expression such as A > B AND C in COBOL is ambiguous until you know how C was declared. Consider the following program:

   IDENTIFICATION DIVISION.
   PROGRAM-ID EXAMPLE.
   DATA DIVISION.
   WORKING-STORAGE SECTION.
   01     A     PIC 9 VALUE 2.
   01     B     PIC 9 VALUE 1.
   01     W     PIC 9 VALUE 3.
       88 C           VALUE 3.
   PROCEDURE DIVISION.
       IF A > B AND C
          DISPLAY 'A > B AND 88 LEVEL C is TRUE because W = ' W
       ELSE
          DISPLAY 'A not > B or 88 LEVEL C is not TRUE'
       END-IF
       DISPLAY 'A: ' A ' B: ' B ' W:' W  
       GOBACK
       .

Output from this program is:

A > B AND 88 LEVEL C is TRUE because W = 3
A: 2 B: 1 W: 3

In essence the expression: A > B AND C is equivalent to: A > B AND W = 3. Had C been defined in a manner similar to A and B, the semantics would have been: A > B AND A > C, which in this case, is FALSE.

Answer 3

The code mentioned above works well, but I had never gotten it to work in my real project, even though I couldn't see a difference between my real project and this code.

This drove me crazy, but I just found another problem in my code, which prevented this method from working: I had an (admittedly cargo-culted) %skeleton "lalr1.cc" in my prologue, which disabled the GLR parsing again! I needed to replace this with

%skeleton "glr.cc"