CODEWITHSUNDEEP
parsingcontext-free-grammarlr-grammar
sgoenka1
sgoenka1

Reputation: 53

SLR(1) or LR(1) Parsing

We find follow(A) in case we find a production of type

A → α

Can α here be ε?

Like In the below example:

P → aPa | bPb | ε

If α could be ε, it is not LR(1)

Upvotes: 3

Views: 1067

Answers (1)

templatetypedef
templatetypedef

Reputation: 372664

Yes, α can be ε. α represents an arbitrary string, and since ε is a string it is a possible α

Because of this, your grammar isn't LR(1), and therefore it isn't SLR(1) either (since all SLR(1) grammars are also LR(1)).

To see this, we can construct the LR(1) configurating sets:

(1)  P' -> .P     ($)
     P  -> .aPa   ($)
     P  -> .bPb   ($)
     P  -> .      ($)

(2)  P  -> a.Pa   ($)
     P  -> .aPa   (a)
     P  -> .bPb   (a)
     P  -> .      (a)

At this point we can stop because there's a shift/reduce confict: we can't tell whether to shift a or reduce P → ε given the terminal a.

With some more advanced math, you can prove that there are no LR(1) grammars for this language (the language of all even-length palindromes). This follows because the languages with LR(1) grammars are precisely the deterministic context-free languages, and the set of all even-length palindromes is not a deterministic context-free language.

Hope this helps!

Upvotes: 1

Related Questions