CODEWITHSUNDEEP
parsinggrammar
Tasbeer
Tasbeer

Reputation:

First & Follow set for Arithmetic Expressions

I want to know if my FIRST and FOLLOW set I made for this grammar is correct or not

S -> TS'
S' -> +TS' | -TS' | epsilon
T -> UT'
T' -> *UT' | /UT' | epsilon
U -> VX
X -> ^U | epsilon
V -> (W) | -W | W | epsilon
W -> S | number 

FIRST(S) = FIRST(T) = FIRST(U) = FIRST(V) = FIRST(W) = { ( , - , + , number ,     epsilon } 
FIRST(T') = { *, / , epsilon} 
FIRST(S') = { + , - , epsilon}
FIRST(X) = { ^ , epsilon}

FOLLOW(S) = FOLLOW(S') = FOLLOW(V) = {$}
FOLLOW(T) = {+ , - , $ }
FOLLOW(T')= {+, - , $ }
FOLLOW(U) = FOLLOW(X) = { * , / , + , - ,$ }
FOLLOW(W) = { ) , $ }

Upvotes: 1

Views: 4556

Answers (1)

Toon Krijthe
Toon Krijthe

Reputation: 53366

Just a remark:

You said:

FIRST(U) = FIRST(V)

Which is correct, but, V can be epsilon which means FIRST(U) = FIRST(V) + FIRST(X)

And X can be epsilon to.

Those epsilons can be quite frustrating sometimes.

There is a little more to say. Just a few rules: - Capitals are nonterminal - lowercase are terminals - epsilon is used for an empty rule - $ is used to note the end of the input.

  • First(a) = {a}
  • First(A,B) = First(A), if epsilon is not in First(A)
  • First(A,B) = First(A) + First(B), if epsilon in First(A)

  • First(A|B) = First(A) + First(B)

  • Follow(T) includes $ if T is the start symbol

  • Follow(T) includes First(A) if there is a rule with ..TA..
  • Follow(T) includes Follow(A) if there is a rule A -> ..T
  • Follow(T) includes Follow(A) if there is a rule A -> ..TB and B can be epsilon
  • Follow(T) never includes epsilon

Example:

E  = TE'
E' = +TE'|epsilon
T  = FT'
T' = *FT' | epsilon
F = (E) | id

First(E)   = First(T) = First(F) = {(, id}
First(E')  = {+, epsilon}
First(T)   = First(F) = {(, id}
First(T')  = {*, epsilon}
First(F)   = {(, id}

Follow(E)  = {$, )}
Follow(E') = Follow(E) = {$, )}
Follow(T)  = First(E') + Follow(E') = {$, ), +}
Follow(T') = Follow(T) = {$, ), +}
Follow(F)  = First(T') + Follow(T') + Follow(T) = {*, $, ), +}

Your grammar is much more complex and a bit weird (are you sure there are no mistakes in the grammar?) but you can follow the rules.

Upvotes: 5

Related Questions