## CPSC 425 Spring 2008Parsing 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\$ => \$ Expand w/lookahead b: Prod 2 baca\$ => bc\$ Match b baca\$ => b  c\$ Expand w/lookahead a: Prod 3 baca\$ => b  ac\$ Expand w/lookahead a: Prod 7 baca\$ => b ac\$ Match a baca\$ => ba c\$ Match c baca\$ => bac \$ Expand 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\$ => \$ Expand w/lookahead b: Prod 2 bbaccb\$ => bc\$ Match b bbaccb\$ => b c\$ Expand w/lookahead b: Prod 2 bbaccb\$ => b  bcc\$ Match b bbaccb\$ => bb   cc\$ Expand w/lookahead a: Prod 3 bbaccb\$ => bb   acc\$ Expand w/lookahead a: Prod 7 bbaccb\$ => bb   acc\$ Match a bbaccb\$ => bba   cc\$ Match c bbaccb\$ => bbac   c\$ Expand w/lookahead c: Prod 5 bbaccb\$ => bbac   c\$ Match c bbaccb\$ => bbacc   \$ Expand w/lookahead b: Prod 4 bbaccb\$ => bbacc   b\$ Match b bbaccb\$ => bbaccb   \$ Expand w/lookahead \$: Prod 5 bbaccb\$ => bbaccb  \$ Match \$; parse complete.