power of SLR

Thant Tessman <thant@acm.org>
16 Sep 2001 00:26:58 -0400

          From comp.compilers

Related articles
power of SLR thant@acm.org (Thant Tessman) (2001-09-16)
Re: power of SLR jjan@cs.rug.nl (J.H.Jongejan) (2001-09-20)
Re: power of SLR thant@acm.org (Thant Tessman) (2001-09-20)
Re: power of SLR blp@stanford.edu (Ben Pfaff) (2001-09-25)
| List of all articles for this month |

From: Thant Tessman <thant@acm.org>
Newsgroups: comp.compilers
Date: 16 Sep 2001 00:26:58 -0400
Organization: XMission http://www.xmission.com/
Keywords: parse, question
Posted-Date: 16 Sep 2001 00:26:58 EDT

I've implemented the SLR parser generator described in Appel's "Modern
Compiler Implementation in ML," but I've implemented it in C++. I
chose SLR because it was the most clearly described technique.

The parser generator seems to work on the example grammar in the book,
but reports ambiguities in grammars like the canonical:

E -> E - T
E -> T
T -> T / F
T -> F
F -> id
F -> ( E )

Is SLR really that weak? or do I have a bug in my implementation? Do I
need to implement LALR(1)? If SLR really is that weak, is there a way
to restate this grammar to make it unambiguous to an SLR parser
generator? LR(1) really seems like overkill for what I'm trying to
accomplish, and I have a reason for not using an off-the-shelf parser

Appel's book doesn't seem to cover parsing very thoroughly, but unlike
the dragon book, I can actually follow it. I also have "Parsing
Techniques: A Practical Guide" by Grune and Jacobs, which is so far
very readable, but the book (or possibly just the subject matter)
doesn't lend itself to skimming or skipping ahead.

Thank you for any feedback.


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.