CODEWITHSUNDEEP
parsingcompiler-construction
duckling
duckling

Reputation: 1

Compilers: First and Follow Sets of a grammar that does not contain epsilon

In my current compilers course, I've understood how to find the first and follow sets of a grammar, and so far all of the grammars I have dealt with have contained epsilon. Now I am being asked to find the first and follow sets of a grammar without epsilon, and to determine whether it is LR(0) and SLR. Not having epsilon has thrown me off, so I don't know if I've done it correctly. I would appreciate any comments on whether I am on the right track with the first and follow sets, and how to begin determining if it is LR(0)

Consider the following grammar describing Lisp arithmetic:

S -> E // S is start symbol, E is expression

E -> (FL) // F is math function, L is a list

L -> LI | I // I is an item in a list

I -> n | E // an item is a number n or an expression E

F -> + | - | *

FIRST:

FIRST(S)= FIRST(E) = {(}

FIRST(L)= FIRST(I) = {n,(}

FIRST(F) = {+, -, *}

FOLLOW:

FOLLOW(S) = {$}

FOLLOW(E) = FOLLOW(L) = {), n, $}

FOLLOW(I) = {),$}

FOLLOW(F) = {),$}

Upvotes: 0

Views: 1249

Answers (1)

robot1208
robot1208

Reputation: 311

The FIRST sets are right, but the FOLLOW sets are incorrect.

The FOLLOW(S) = {$} is right, though technically this is for the augmented grammar S' -> S$ .

E appears on the right side of S -> E and I -> E, both of which mean that the follow of that set is in the follow of E, so: FOLLOW(E) = FOLLOW(S) ∪ FOLLOW(I) .

L appears on the right hand side of L -> LI, which gives FOLLOW(L) ⊇ FIRST(I) , and E -> (FL), which gives FOLLOW(L) ⊇ {)} .

I appears on the right side of L -> LI | I , which gives FOLLOW(I) = FOLLOW(L) .

F appears on the right side in E -> (FL) , which gives FOLLOW(F) = FIRST(L)

Solving for these gives:

FOLLOW(F) = {n, (}

FOLLOW(L) = FIRST(I) ∪ {)} = {n, (, )}

FOLLOW(I) = {n, (, )}

FOLLOW(E) = {$} ∪ {n, (, )} = {n, (, ), $}

Upvotes: 0

Related Questions