First Set Examples

We will go over examples of the First Set Algorithm on both the LR and LL grammers.

	1	E	->	E + T
	2	E	->	E - T
	3	E	->	T
	4	T	->	T * F
	5	T	->	T / F
	6	T	->	F
	7	F	->	( E )
	8	F	->	identifier

The first part of the algorithm adds the first symbol of each rule, I, to the FIRST(LHS(I)).

for I = each rule
	for J = first rhs to last rhs
		add RHS(I,J) to FIRST(LHS(I))
		if not NULL(RHS(I,J)) then break for next I
	next J
next I

This produces a table that looks like:

    LHS	|  E  T  F +  -  *  /  (  )  identifier
    -------------------------------------------
    E	|  E  T
    T   |     T  F
    F   |		       (     identifier

The second part of the algorithm iterates over the FIRST set while there are changes.

CHANGES=1
while CHANGES
	CHANGES=0
	for I = each NT
		for J = each NT in FIRST(I)
			add FIRST(J) to FIRST(I)
		next J
	next I
end while

The first non-terminal is E. We add the FIRST(E) to the FIRST(E) which, of course, does nothing. We next add the FIRST(T) to the FIRST(E) which adds F. THen we add FIRST(F), which adds in '(' and identifier.

    LHS	|  E  T  F  +  -  *  /  (  )  identifier
    --------------------------------------------
    E	|  E  T  F		(     identifier
    T   |     T  F
    F   |			(     identifier

The next non-terminal is T. We add the FIRST(T) to the FIRST(T) which, of course, does nothing. We next add the FIRST(F) which adds in '(' and identifier.

    LHS	|  E  T  F  +  -  *  /  (  )  identifier
    --------------------------------------------
    E	|  E  T  F		(     identifier
    T   |     T  F		(     identifier
    F   |			(     identifier

The last non-terminal is F and there are no non-terminals in the FIRST(F) so there is nothing to do.

At the end of the first pass, we have had changes, so we start the second pass going over the FIRST set, starting with E. The second pass functions much like the first, except that it doesn't make any additions to the First set. With no changes at the end of the second pass, we complete the First Set algorithm.

	 1	E	->	T E1
	 2	E1	->	+ T E1
	 3	E1	->	- T E1
	 4	E1	->
	 5	T	->	F T1
	 6	T1	->	* F T1
	 7	T1	->	/ F T1
	 8	T1	->
	 9	F	->	( E )
	10	F	->	identifier