How to find FIRST sets for a recursive grammar

Question

I have a grammar:

S → SL | ε
L → A; | E; | C;
E → (EBE) | N | V
A → let V =E
C → while E do S | while E do S else S
B → + | - | * | >
V → x | y | z
N → ND | N0 | D
D → 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

I am trying to build the parse table for me to be able to prove that it is not an LL(1) grammar. I am currently stuck of finding the FIRST set for S. I keep getting S in the set and cannot reach a terminal of G. What would FIRST(SL) be?

When I do FIRST(SL), I keep going back to FIRST(S), which goes to FIRST(SL) ⋃ FIRST(ε) = FIRST(S) ⋃ {ε}, and the FIRST(S) will repeat itself over and over.

user2277550 · Accepted Answer · 2019-10-10 04:45:02Z

1

Capital letters represent non-terminals. Small letters represent terminals.

First and Follow are the TERMINAL symbols that precede or succeed a terminal or a non terminal (in a pre order traversal of the parse tree).

For all A -> xYZ
First (A) = {x}
For all A-> Xyz
First (A) = First(X)
For all A-> εYZ
First (A) = First(Y)

Take the union of all these terminal symbols.

edited Oct 10, 2019 at 4:45

answered Oct 10, 2019 at 4:23

user2277550

6198 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

FatimahFatCakes Over a year ago

I'm sorry but can you elaborate further? I'm not sure what you mean. Those just look like the basic rules for the FIRST set. Thank you!

FatimahFatCakes Over a year ago

I understand, but when if I do FIRST(SL), I keep going back to FIRST(S), which goes to FIRST(SL) ⋃ FIRST(ε) = FIRST(S) ⋃ {ε}, and the FIRST(S) will repeat itself over and over.

user2277550 Over a year ago

The third rule is what you want. If both the first and the follow sets are the same, then the grammar is not in LL(1) :)

Collectives™ on Stack Overflow

How to find FIRST sets for a recursive grammar

1 Answer 1

3 Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Related