TA: Jade Cheng (TA)
ICS 313
HW 8 Problem set on p.198, nos. 4, 5
Due 2/17/19

[Exercise 4]

Show a trace of the recursive descent parse given in Section 4.4.1 for the
string a * (b + c).

Grammar: <expre>   --> <term> { (+|-) <term> }
         <term>    --> <factor> { (*|\) <term> }
         <factor>  --> id | <expr>

Solution: call lex      // return a
            enter <expr>
            enter <term>
            enter <factor>
          call lex      // return *
            exit <factor>
          call lex      // return (
            enter <factor>
          call lex      // return b
            enter <expr>
            enter <term>
            enter <factor>
          call lex      // return +
            exit <factor>
            exit <term>
          call lex      // return c
            enter <term>
            enter <factor>
          call lex      // return )
            exit <factor>
            exit <term>
            exit <expr>
          call lex      // return EOF
            exit <factor>
            exit <term>
            exit <expr>


[Exercise 5]

Given the following grammar and the right sentential form, draw a parse tree
and show the phrases and simple phrases, as well as the handle.

Grammar: S --> aAb | bBA
         A --> ab | aAB
         B --> aB |b

a. aaAbb
Parse Tree:

                    S
                  / | \
                 a  A  b
                   /|\
                  a A B
                      |
                      b

Handles:        b, aAB
Phrases:        aaAbb, aaABb, aAb
Simple Phrase:  b

b. bBab
Parse Tree:

                    S
                  / | \
                 b  B  A
                      / \
                     a   b

Handles:        ab
Phrases:        bBab, bBA
Simple Phrase:  ab

c. aaAbBb
   aaAbBb --> aSBb --> aSBB --> x
or aaAbBb--> aaAbBB --> aSBB --> x

Therefore the last string can not be derived from the given grammar.