Name:
(as it would appear on official course roster)
Umail address:	@umail.ucsb.edu	section 2pm, 4pm or 5pm
Optional: name you wish to be called if different from name above.
Optional: name of "homework buddy" (leaving this blank signifies "I worked alone"

h16: Parsing

ready?	assigned	due	points
true	Tue 11/07 09:30AM	Wed 11/15 05:50PM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

MAY ONLY BE TURNED IN IN THE LECTURE/LAB LISTED ABOVE AS THE DUE DATE,
OR IF APPLICABLE, SUBMITTED ON GRADESCOPE. There is NO MAKEUP for missed assignments;
in place of that, we drop the three lowest scores (if you have zeros, those are the three lowest scores.)

As preparation for your lab08, please read both of the following. Note that links are available at the online version of this assignment, here: https://ucsb-cs56-f17.github.io/hwk/h16/

CS56 Parsing Tutorial: https://ucsb-cs56-pconrad.github.io/tutorials/parsing/

(10 pts) Please fill in the information at the top of this homework sheet, including your name and umail address. Put the time your discussion section starts (2pm, 4pm or 5pm) in the space indicated (the one you are registered for—even if you usually attend a different one.) If the other two items apply, please fill them in as well. Please do this every single time you submit homework for this class.
Compilers/interpreters are often divided into three phases: tokeniztion, parsing, and interpretation. Briefly describe the main "job" of each of these phases, in terms of its "input" and "output.
1. (10 pts) Tokenization
2. (10 pts) Parsing
3. (10 pts) Interpretation
```
public String speak(Animal a) {
  if (a instanceof Dog) {
    return "Bark!";
  } else if (a instanceof Cat) {
    return "Meow";
  } else if (a instanceof Fish) {
    return "Blub";
  } else {
    assert(false);
    return "IMPOSSIBLE";
  }
}
```
(10 pts) The phrase code smell is used by some software developers to refer to things in “other people’s code” that suggest that the code may have some problems, and needs to be refactored.

Long sequences of if/else statements that use instanceof are often considered to be a so-called code smell. For example, the code in the box at right.

Please give at least two reasons that this style of code is not desirable, as compared to some of the available alternatives.
For each of the ASTs shown below (a, b, and c), give an arithmetic expression that would result in this tree. Parentheses may be used. Note that there may be more than one correct answer.
1. (10 pts)
2. (10 pts)
3. (10 pts)
(a) (b) (c)
(20 pts) In your own words, how does an AST capture the idea of operator precedence?