CODEWITHSUNDEEP
parsingcompiler-constructiongrammarcontext-free-grammarcompiler-theory
user3638992
user3638992

Reputation: 87

Reducing grammar to LL1

I have the following grammar:

A-> AB|CA
B-> Bd | ef
C-> e|f

I removed left recursion as follows and my grammar looks as below:

A->CAA'
A'-> BA'
A'-> epsilon
B-> efB'
B'->dB'
B'-> epsilon
C->e
C->f

The problem I'm having after this is ambiguity when constructing parse table for this. Can someone point to me in the right direction for this? Or I think I'm making mistakes in calculating First and Follow Sets for Parse Table.

Upvotes: 1

Views: 332

Answers (1)

Gene
Gene

Reputation: 47010

Edit

Woops. The original grammar does not derive any string of terminals, so trying to make it LL(1) is pointless. The first production always produces a form with an A in it, and there is no other derivation from A. Did you skip something or have a typo in your post?

To be fixed:

Your left recursion removal is good. Now you need the prediction sets for each production:

A->CAA'            first(CAA') = { e, f }
A'-> BA'           first(BA') = { e }
A'-> epsilon       follow(A') = follow(A) = { end of input }
B-> efB'           first(efB') = { e }
B'->dB'            first(dB') = { d }
B'-> epsilon       follow(B') = { end of input }
C->e               first(e) = { e }
C->f               first(f) = { f }

There are no ambiguities here because the predict sets of each right hand side corresponding to any given left hand side have null pairwise intersections.

What ambiguity were you seeing?

Upvotes: 1

Related Questions