1
h16
CS56 F16
Name:
(as it would appear on official course roster)
Umail address: @umail.ucsb.edu section
4pm, 5pm or 6pm
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 and the Visitor Design Pattern

ready? assigned due points
true Mon 11/07 12:30PM Thu 11/10 04:00PM

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 lab06, please read both of the following. Note that links are available at the online version of this assignment, here: http://ucsb-cs56-f16.github.io/hwk/h16/

  1. (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 (4pm, 5pm or 6pm) 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.
  2. 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
  3. 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.

  4. 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) ast1.png (b) ast3.png (c) ast4.png
  5. (20 pts) In your own words, how does an AST capture the idea of operator precedence?

http://UCSB-CS56-F16.github.io/hwk/h16