C++ GLR parsers with Bison

Question

I'm using Bison to generate a parser. I've got one shift/reduce conflict where I really need Bison to use GLR rather than LALR to deal with it. But I've passed the %glr-parser directive and the source file still states that it's a LALR parser. I even found a "glr.cc" skeleton which suggests that it is a GLR C++ parser and using it by %skeleton "glr.cc" didn't change the output. Does Bison not ship all algorithms for all it's target languages?

Answer 1

You just need %glr-parser to get a GLR parser. Note that GLR parsers may STILL have conflicts (shift/reduce or reduce/reduce), its just that the generated parser will try both alternatives and unify the result.

If you want to shut up the messages about the conflicts, you can use %expect and %expect-rr. Hoever, just blindly using a GLR parser where you don't understand what all the conflicts are is dangerous -- the resulting parser might take exponentially long to parse some inputs if you're not careful, or might give you ambiguity errors at runtime.

Answer 2

I don't know what you mean by "%skeleton "glr.cc" didn't change the output", because it does! Are you sure you really regenerated the output? If you did, please provide more details.

$ echo "%% exp: '0'" > /tmp/f.y
$ bison -S lalr1.cc /tmp/f.y -o f1.cc
$ bison -S glr.cc /tmp/f.y -o f2.cc
$ ls -l f1.cc f2.cc
-rw-r--r--  1 akim  wheel  28373 30 oct 09:29 f1.cc
-rw-r--r--  1 akim  wheel  82767 30 oct 09:29 f2.cc

Answer 3

I've got the same problem. The things I've learned — Bison return 1 if fail to generate new output. The question: why? Because I have disabled C++ Variants (%define api.value.type variant), that is not supported by GLR in Bison, but forget about %define api.token.constructor. And Bison with no promt just breaks.

Good luck with troubleshooting.