Question 8856 – Compiler-Design

For the grammar below, a partial LL(1) parsing table is also presented along with the grammar. Entries that need to be filled are indicated as E1, E2, and E3. ε is the empty string, $ indicates end of input, and, | separates alternate right hand sides of productions.

S → aAbB | bAaB | ε
A → S
B → S

The FIRST and FOLLOW sets for the non-terminals A and B are

Correct Answer: A

Question 16 Explanation:

FIRST (P): is the set of terminals that begin the strings derivable from non terminal P. If P derives epsilon then we include epsilon in FIRST(P).
FOLLOW(P): is the set of terminals that can appear immediately to the right of P in some sentential form.
FIRST(A) = FIRST (S)
FIRST (S) = FIRST (aAbB) and FIRST (bAaB) and FIRST (ϵ)
FIRST(S) = {a, b, ϵ}
FIRST (B) = FIRST (S) = {a, b, ϵ} = FIRST (A)
FOLLOW(A) = {b} // because of production S→a A b B
FOLLOW(A) = {a} // because of production S→ b A a B
So FOLLOW (A) = {a, b}
FOLLOW (B) = FOLLOW (S) // because of production S→ a A b B
FOLLOW (S) = FOLLOW (A) // because of production S → A
So FOLLOW (S) = {$, a, b} = FOLLOW(B)

FIRST(A) = {a,b,ε} = FIRST(B)
FOLLOW(A) = {a,b}
FOLLOW(B) = {a,b,$}

FIRST(A) = {a,b,$}
FIRST(B) = {a,b,ε}
FOLLOW(A) = {a,b}
FOLLOW(B) = {$}

FIRST(A) = {a,b,ε} = FIRST(B)
FOLLOW(A) = {a,b}
FOLLOW(B) = ∅

FIRST(A) = {a,b} = FIRST(B)
FOLLOW(A) = {a,b}
FOLLOW(B) = {a,b}

0 0 votes

Article Rating

0 Comments

Inline Feedbacks

View all comments