CPSC 425 Spring 2008
Parsing Solutions

Grammar

1. <S> := <A>$
2. <A> := b<A>c<B> 
3. <A> := <C>a
4. <B> := b<B>
5. <B> := λ
6. <C> := ca 
7. <C> := λ


First, Follow, and Predict sets

First(A) = {a,b,c}
First(bAcB) = b
First(Ca) = {a,c}
First(bB) = b
First(λ) = λ
First(ca) = c

Follow(S) = {$}
Follow(A) = {$,c}
Follow(B) = {$,c}
Follow(C) = {a}

Predict(1) = {a,b,c}
Predict(2) = {b}
Predict(3) = {a,c}
Predict(4) = {b}
Predict(5) = {$,c}
Predict(6) = {c}
Predict(7) = {a}

Parse "baca$"

Input
(Current lookahead underlined) 		Step in derivation
(Space separates matched portion of string from unmatched portion) 		Action to take next
baca$ <S> => <A>$ Expand <A> w/lookahead b: Prod 2
baca$   => b<A>c<B>$ Match b
baca$   => b  <A>c<B>$ Expand <A> w/lookahead a: Prod 3
baca$   => b  <C>ac<B>$ Expand <C> w/lookahead a: Prod 7
baca$   => b ac<B>$ Match a
baca$   => ba c<B>$ Match c
baca$   => bac <B>$ Expand <B> w/lookahead a: Parse error. Expected b,c, or $; got a.

Parse "bbaccb$"

Input
(Current lookahead underlined) 		Step in derivation
(Space separates matched portion of string from unmatched portion) 		Action to take next
bbaccb$ <S> => <A>$ Expand <A> w/lookahead b: Prod 2
bbaccb$   => b<A>c<B>$ Match b
bbaccb$   => b <A>c<B>$ Expand <A> w/lookahead b: Prod 2
bbaccb$   => b  b<A>c<B>c<B>$ Match b
bbaccb$   => bb   <A>c<B>c<B>$ Expand <A> w/lookahead a: Prod 3
bbaccb$   => bb   <C>ac<B>c<B>$ Expand <C> w/lookahead a: Prod 7
bbaccb$   => bb   ac<B>c<B>$ Match a
bbaccb$   => bba   c<B>c<B>$ Match c
bbaccb$   => bbac   <B>c<B>$ Expand <B> w/lookahead c: Prod 5
bbaccb$   => bbac   c<B>$ Match c
bbaccb$   => bbacc   <B>$ Expand <B> w/lookahead b: Prod 4
bbaccb$   => bbacc   b<B>$ Match b
bbaccb$   => bbaccb   <B>$ Expand <B> w/lookahead $: Prod 5
bbaccb$   => bbaccb  $ Match $; parse complete.