Compilers - Factoring a Grammar for Predictive Parsers ?

Author

Factoring a Grammar for Predictive Parsers ?

Vimal

2007-08-17, 7:20 pm

Hi
I have a grammar G generating a language L. To write predictive parsers
for the grammar, I would like to convert the grammar G into an equivalent
grammar G' such that it is easy to "predictively" parse the input and test
for membership.
Q: Is it always possible to do such a conversion?
Q: If possible, I would like to know how to convert this grammar
to help predictive parsers.

S -> {L} | {}
L -> E | E,L
E -> { | } | ,

The grammar generates valid expressions to represent sets. But
its difficult to parse, because, the set can contain { or } or , as an
element. So, this confuses me :(

The predictive parser I would be using (not code one), is Haskell's Parsec.

Thanks!

Vimal
Department of Computer Science and Engineering
Indian Institute of Technology Madras
PS: To the editor: I am not sure if this question is valid in your forum!
I just hope it is not misunderstood as a "Solve my homework" type question :)
I really broke my head on this one, so, some help required!

Vimal

2007-08-18, 7:11 pm

> A few points which will help you:
> 1. I don't feel the grammar you quoted does its intended purpose. Try
> generating a few strings following the various
> possibilities of derivation. Are these the intended strings? I feel
> you need to correct the grammar a little bit.
NOTE:
I forgot to add this rule in the grammar!
E -> { | } | , | S

Yes, the grammar is intended to confuse us. The very fact that { or } or , can
be elements of a set is the problem for us. But, if you had also noticed
(I didn't when I first saw the grammar) was that the grammar is ambiguous!
The string {{},{}} has two distince parse trees.

> 2. With a proper grammar, if you fail to produce a predictive parser
> Look for possibilities of left factoring
> Look for possibilities of avoiding left recursion.
> The dragon book contain details on this.

I will check them out.
This grammar can be left factored, but I get epsilon productions which I am
trying to avoid.

>
> By the way, I have not used the tool you mentioned above. I hope this
> information help you
>

The Parsec tool, performs best on predictive LL(1) grammars and also parses
context sensitive grammar! More information here:
http://legacy.cs.uu.nl/daan/download/parsec/parsec.html

Vimal

Sponsored Links