CODEWITHSUNDEEP
parsingcompiler-constructioncontext-free-grammarll-grammar
Maroun Sassine
Maroun Sassine

Reputation: 347

Multiple entries in an LL(1) parsing table?

Given this grammar:

S → S1 S2

S1 → a | ε

S2 → ab | ε

Therefore, we have

FIRST(S1) = { a, ε }

FOLLOW(S1) = { a }

Does that mean that in the parsing table I'll have multiple definitions in the row for S1 and the column for a?

Upvotes: 1

Views: 1939

Answers (1)

templatetypedef
templatetypedef

Reputation: 372664

Yes, that's correct. (However, note that your FOLLOW set is wrong; it also contains the end-of-input marker $). The issue here is that if the parser sees an a, it can't tell if that's because it wants to use the derivation

S → S1S2 → a S2

Or the derivation

S → S1S2 → S2 → ab

To fix this, you can note that your grammar only generates the strings { a, ab, aab }. Therefore, you can build an LL(1) for the language grammar that directly produces those three strings:

S → aY

Y → ε | aZ

Z → ε | b

Hope this helps!

Upvotes: 1

Related Questions