If you want to make money online : Register now

[Answers] How to remove empty strings a.k.a (lambda, epsilon) from a LR(0) grammar

, , No Comments
Problem Detail: 

Say I have the following grammar:

E  -> TE' E' -> +TE'| -TE' | λ T  -> (E) |  id 

I need to build the finite state machine with the LR(0) items,

But I know in order to do this I have to remove the λ.

How to I accomplish this ?

Also, after I have the SLR(1) table, how to I prove is valid ?

Thanks, I'm studying for an exam, and I'm stuck here :(

Asked By : Andres Zapata

Answered By : Anton Trunov

  1. Find all nullable variables. In this case only E' is nullable.

  2. Let me illustrate the second step with an example:

Replace a production A -> BCD with a family of productions like this (assuming B, C & D are nullable):

A -> BCD | BC | BD | CD | B | C | D 
  1. Delete all the productions with the empty string as the right-hand side.

With all that in mind we get:

E  -> TE' | T E' -> +TE'| -TE' | +T | -T T  -> (E) |  id 
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49311

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback