My task is to calculate FIRST and FOLLOW sets for the following grammar:
P ::= S CS .
S ::= ( int , int )
CS ::= C CS | epsilon
C ::= left int | right int | low C
I got the following first sets:
FIRST(S) = {'('}
FIRST(C) = {left,right,low}
FIRST(CS) = {left,right,low,epsilon}
FIRST(P) = FIRST(S) = {'('}
For the following sets I calculated:
FOLLOW(P) = $ (or empty)
FOLLOW(C) = {left,right,low,'.'}
FOLLOW(CS) = {'.'}
FOLLOW(S) = {left,right,low}
I tried out my solution using first and follow sets generator and what I got with FOLLOW(S) was: FOLLOW(S) = {'.', left, right, low}. Is generator's solution correct and why? I calculated my solution using formula: FOLLOW(S) = FIRST({left,right,low} concat FOLLOW(P)) = {left, right, low}. Can someone please explain me why my/ generator's solution is not correct and check whether I got everything else right? I also want to know why I don't have int in any first or follow set and if this will be okay with building parser later anyway. Thank you
When you compute FOLLOW sets you have to be careful with empty productions.
In this case, CS has an empty production, which means that S might be followed by a . in P → S CS .. Similarly, the C in C CS might be at the end of the production, so C could also be followed by a .
int can only appear after a left or right token. It can never appear at the beginning of a nom-terminal nor immediately following a non-terminal. So it is entirely expected that it not be in any FIRST or FOLLOW set.