2
$\begingroup$

I am trying to build a LL(1) parse table for the following grammar:

S -> L
L -> L : L
L -> id R
R -> ( L )
R -> ( )
R -> Epsilon

There are two problems here. First, the L rules are a left recursion and the R rules have ( as the same prefix.

So I modified the Grammar to this one:

S -> L
L -> id R X
X -> : L X
X -> Epsilon
R -> ( P
R -> Epsilon
P -> L )
P -> )

I then checked the grammar with the JFLAP Tool and it says that my grammar is not LL(1). But I just don't see the problem.

Can somebody help me out here?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Your original grammar is ambiguous:

L → L : L
L → id R

Suppose we have id : id : id. (For simplicity, I'm just letting R derive the empty string, but any valid derivation of the Rs would end up with the same ambiguity.) That needs to be derived from S → L → L1 : L2, but from there, either L1 or L2 can derive L : L. In effect, the two cases correspond to : associating to the left or associating to the right, but with longer sequences of :-separated id R clauses, the number of possible parses increases exponentially.

Your rewrite does not eliminate this ambiguity, it just makes it harder to see.

In short, you need to decide how : associates. It probably makes most sense for it to associate to the left, but an LL grammar really only handles right-association. (That's not a huge problem since you can reassociate the AST easily enough, but with an LR parser generator you wouldn't have to do any of this.) If we rewrite L as right-associative, we automatically eliminate the left-recursion problem:

S  → L
L  → L'
L  → L' : L
L' → id R

(Really, L' is not very useful in this case; it would have been almost as simple to write L → id R | id R L. But in either case, you end up needing to factor out the common prefix.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hi rici. Thanks for your answer. I understand you wrote and entered it into Jflap, but it still says that the grammar is not LL(1). is the tool reliable? $\endgroup$
    – AdelPoint
    Commented Aug 30, 2015 at 14:21
  • $\begingroup$ @adelpoint: actually, i did not try it with any tool. So I might have missed another problem. $\endgroup$
    – rici
    Commented Aug 30, 2015 at 14:58
  • 1
    $\begingroup$ Thanks anyway. It helped me understand the Problem better :) $\endgroup$
    – AdelPoint
    Commented Aug 30, 2015 at 15:26
  • $\begingroup$ @AdelPoint: Looking at it, I realize that my change introduces another shared prefix which needs to be factored out. I really don't see the point to LL grammar generators, personally; excellent LR generators are available and IMHO you don't need to think nearly as hard about grammars to write an LR-parseable grammar. YMMV. $\endgroup$
    – rici
    Commented Aug 30, 2015 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.