Computing NULLABLE, FIRST and FOLLOW Sets

Here is a quick tutorial on how to compute NULLABLE, FIRST and FOLLOW sets for a given Context Free Grammar (CFG). What I have below is more an informal methodology on working out the aforementioned sets.

For Nullable

1. Start by looking for all productions with only an “ε” in the Right-Hand Side of the production. Ex: X –> ε. All such non-terminals are termed NULLABLE, hence in our example “X” is NULLABLE.

2. Following the same example as in step 1, start looking for productions where nullable non-terminal X is is being used in the RHS of the production. Ex: Y –> X. Note that its important to pick up only the productions that have ONLY nullable non-terminals on the RHS and not a combination of nullable and other non-terminals. These productions have the non-teminals pointing to nullable non-terminal(s) and hence are also nullable. So in our example, Y is NULLABLE too.

3. Now for the last straw, In a production like say  “Y –> ABC”, Y is NULLABLE if and only if ALL A, B and C are NULLABLE! So ensure that you look for productions where all the non-terminals in the RHS are nullable, then you have yourself another nullable non-terminal.

Now you have a list of all the NULLABLE non-terminals.

For FIRST

1. Write Empty FIRST sets for all non-terminals (variables) in the LHS as we will keep filling up these empty sets as we compute FIRST!

2. Start by tackling the productions which START with a terminal. So look for productions of the form “A –> aβ” and FIRST(A) will contain “a” in it. Nice and Simple! Example: E –> (E). The RHS starts with a terminal “(“, so FIRST(E) contains “(” in it. Remember to keep adding all such terminals to your corresponding FIRST set.

3. Now lets deal with the productions that have Non-Terminals on the RHS only. So we are now looking for productions of the form “A –> Bβ”. Following our example, Say X,Y are NULLABLE and we have a production like  Z –> XYZ

3a. If B is not nullable, then FIRST(A) contains FIRST(B) (when I say contains it means you should copy over all non-terminals from one FIRST set to the other to reflect this) and you can stop processing that production. So in our example, if X was not nullable you could say FIRST(Z) contains FIRST(X) and stop processing. Now for the tricky bit.

3b. When B is nullable, We must compute FIRST(β) which is basically looking for productions of form A –> Bβ recursively and in the process we add to the relevant FIRST sets. So in our example, we would start like so

FIRST(X) contains FIRST(XYZ) = FIRST(X).

Since X is nullable, we continue this search … so FIRST(X) also contains  FIRST(YZ) = FIRST(Y).  We are not done yet!

Since Y is also nullable, we continue … and add to FIRST(X) non-terminals from FIRST(Z). That is it you are DONE!

Note that even if a non-terminal is nullable, you must copy over non-terminals from it’s FIRST set to the FIRST set of the LHS non-terminal.

For FOLLOW

1. The Follow sets will be formed by spotting non-terminals from the RHS of the production this time. So unlike FIRST sets, we focus on the non-terminals on the right hand side of the production and work backwards (well in a way).

So first step is to look for productions of the form  “A –> … Bβ”.

FOLLOW(B) contains FIRST(β). Note how its FOLLOW(B) not A! Ex: E –> E + S, then FOLLOW(E) contains FIRST(“+ S”) which is the terminal “+”. Don’t forget how to compute FIRST!

2. If β is NULLABLE, then FOLLOW(B) contains FOLLOW(A) in it. Ex:  E –> XY and Y is nullable, then FOLLOW(X) contains all terminals in FOLLOW(E). Also watch out for productions like, E –> X because it can be treated as X being followed by something nullable, and hence FOLLOW(X) contains FOLLOW(E) in our example. Think of it as something NULLABLE right behind X, because X is the very last non-terminal in the production.

Note: You must recursively look for this format of  … Bβ even in a single production to compute the FOLLOW sets of each constituent variable.

Thats it you are done computing FOLLOW sets.

Now for one final example to wrap up all the rules and show you how to apply this methodology.

Consider the grammar below

Z –> d | XYZ

Y –> c | ε

X –> Y | a

Lets start by computing the nullable set.

Y –> ε   => Y is NULLABLE.

X –> Y and Y is nullable =>  X is NULLABLE.

Z is not nullable. So now we have {X,Y} as our NULLABLE non-terminals.

Lets compute the FIRST sets now. Initially FIRST(X) = FIRST(Y) = FIRST(Z) = {}.

Lets start by looking for the productions that start with a terminal first.

X –> a  => a in FIRST(X)

Y –> c => c in FIRST(Y)

Z –> d => d in FIRST(Z)

Now lets deal with the productions that have variables in them.

X –> Y and c in FIRST(Y) => c is also in FIRST(X)

Z –> XYZ and {a,c} in FIRST(X) => {a,c} also in FIRST(Z)

Now for the NULLABLE + FIRST set computation rules,

Z –> XYZ, Nullable X and c in FIRST(Y) => c is in FIRST(Z); no change to FIRST(Z) as we already have c in it!

Z –> XYZ and Nullable (XY) => FIRST(Z) includes FIRST(Z); no change needed here.

So finally, FIRST(X) = {a,c}  FIRST(Y) = {c} and  FIRST(Z) = {a,c,d}

Finally the FOLLOW sets.

Z –> XYZ and c in FIRST(Y) (same as FIRST(YZ) ) => c in FOLLOW(X)

Z –> XYZ, Nullable Y and a,c,d in FIRST(Z) => a,c,d in FOLLOW(X)

Z –> XYZ and a,c,d in FIRST(Z) => a,c,d in FOLLOW(Y)

X –> Y and a,c,d in FOLLOW(X) => a,c,d in FOLLOW(Y)  as FOLLOW(Y) contains FOLLOW(X).

So finally, FOLLOW(X) =  FOLLOW(Y) = {a,c,d} and  FOLLOW(Z) = {}

Advertisements

No comments yet

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: