Theory for CD program

FIRST FUNCTION

First Function is used in the construction of Predictive Parser. The construction of a predictive parser is aided by two functions associated with grammar G. Those functions are FIRST and FOLLOW. They allow to fill in the entries of a predictive parsing table for G, whenever possible.

The procedure for computing First function is as follows:

To compute first(X) for all grammar symbols X, apply the following rules until no more terminals or (-- (epsilon) can be added to any first set.

Step 1:- If X is a terminal then First(X) = {X}.

Step 2:- If X > C (epsilon) is a production then add (-- (epsilon) to First(X).

Step 3:- If X is a non- terminal and X > Y₁Y₂-------Y_K is a production then place ‘a’ in First(Y_i) and (-- (epsilon) in all of First(Y_i)--------First(Y_i-1).