Re: Factoring a Grammar for Predictive Parsers ?

Vimal <>
Fri, 17 Aug 2007 23:50:10 +0530

          From comp.compilers

Related articles
Factoring a Grammar for Predictive Parsers ? (Vimal) (2007-08-16)
Re: Factoring a Grammar for Predictive Parsers ? (Vimal) (2007-08-17)
| List of all articles for this month |

From: Vimal <>
Newsgroups: comp.compilers
Date: Fri, 17 Aug 2007 23:50:10 +0530
Organization: Compilers Central
References: 07-08-047 <>
Keywords: parse
Posted-Date: 18 Aug 2007 09:27:27 EDT

> 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.
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:


Post a followup to this message

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