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.
