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?

bison is free software, so you can study and improve its soruce code. By the way, did you consider using another parser generator, like ANTLR ? — Basile Starynkevitch, Dec 15 '11 at 21:35
@Basile: My grammar is not LL. As for improving it's source code, you mean, if I wanted to truck through six billion support utilities as well. — Puppy, Dec 15 '11 at 21:37
ANTLR has several hacks to deal with some kinds of non LL grammars. — Basile Starynkevitch, Dec 15 '11 at 21:38
@Basile: Why do I care? So does Bison. The ones I'm currently trying to use. Save me the hassle of moving my source code over. — Puppy, Dec 15 '11 at 21:39
I would ask such questions on the mailing list devoted to bison... — Basile Starynkevitch, Dec 16 '11 at 06:40

score 2 · Answer 1 · answered Dec 15 '11 at 22:48

2

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.

answered Dec 15 '11 at 22:48

Chris Dodd

119,907
13
134
226

This doesn't really answer the question- I said I attempted `%glr-parser` – Puppy Dec 15 '11 at 23:53
@DeadMG: then you got a GLR parser. Its just that GLR parsers have the same shift/reduce and reduce/reduce conflicts as LALR parsers, they just deal with them in a different way. – Chris Dodd Dec 16 '11 at 00:11
I didn't say I didn't have one because it still reported conflicts, I said I still had one because the source file's comments still stated so. – Puppy Dec 16 '11 at 01:04
Then you might have outdated generated files. Details on what bison's output is and what are the comments that are confusing might really help people see the problem. – Mihai Timar Oct 02 '12 at 11:21

score 1 · Answer 2 · answered Oct 30 '12 at 08:30

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

score 0 · Answer 3 · answered Jun 15 '19 at 05:45

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.

C++ GLR parsers with Bison

3 Answers3