C++ GLR parsers with Bison

Asked 15/12, 2011 at 21:31 Answered 15/6, 2019 at 5:45

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?

Menopause answered 15/12, 2011 at 21:31 Comment(5)

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 ? – Beast 15/12, 2011 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. – Menopause 15/12, 2011 at 21:37

ANTLR has several hacks to deal with some kinds of non LL grammars. – Beast 15/12, 2011 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. – Menopause 15/12, 2011 at 21:39

I would ask such questions on the mailing list devoted to bison... – Beast 16/12, 2011 at 6:40

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.

Unrealizable answered 15/12, 2011 at 22:48 Comment(4)

This doesn't really answer the question- I said I attempted %glr-parser – Menopause 15/12, 2011 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. – Unrealizable 16/12, 2011 at 0: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. – Menopause 16/12, 2011 at 1:4

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. – Isocrates 2/10, 2012 at 11:21

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

Breeks answered 30/10, 2012 at 8:30 Comment(0)

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.

Westhead answered 15/6, 2019 at 5:45 Comment(0)

Recommended topics

Hot tags