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 :(

  • 1
    Well, what have you tried and where exactly are you stuck? – Raphael Nov 10 '15 at 15:19
up vote 1 down vote accepted
  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

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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