Question

2. Consider the following context free grammar with terminals (), +, id, num, and starting symbol S. S (ST) F-id Fnum a. Compute the first and follow set of all non-terminals (use recursion or iteration, show all the steps) Show step-by-step (the parsing tree) how the following program is parsed: (num+num+id)) b.

Answer 1

ANSWER :

S -> F

S -> (ST)

T -> ?

T -> +FT

F -> id

F -> num

a)

FIRST function :

FIRST(S) = FIRST(F)

FIRST(S) = {(}

FIRST(T) = {?}

FIRST(T) = {?,+}

FIRST(F) = {id,num}

FIRST(S) = {(,id,num}

FOLLOW function :

FOLLOW(S) = {$,FIRST(T)} = {$,+, FIRST())} = {$,+,)}

FOLLOW(T) = {)}

FOLLOW(F) = {FOLLOW(S)} = {$,+,)}

FOLLOW(F) = {$,+,),FIRST(T)} = {$,+,),FOLLOW(T)} = {$,+,)}

FOLLOW(F) = {$,+,)}

Table for first and follow function :

	FIRST	FOLLOW
S	{(,id,num}	{$,+,)}
T	{?,+}	{)}
F	{id,num}	{$,+,)}

b)

Parse Table :

	(	)	+	id	num	$
S	S->(ST)			S->F	S->F
T		T->?	T->+FT
F				F->id	F->num

We have given a program ((num+num+id))

Parse Tree :

hun