1
h09
CS56 M16
Name:
(as it would appear on official course roster)
Umail address: @umail.ucsb.edu section
9am or 10:30am
Optional: name you wish to be called
if different from name above.
Optional: name of "homework buddy"
(leaving this blank signifies "I worked alone"

h09: Parsing and the Visitor Design Pattern

ready? assigned due points
true Tue 07/12 09:30AM Thu 07/14 09:30AM

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-m16.github.io/hwk/h09/

  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 (either 9am or 10:30am) in the space indicated. 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. (5 pts) Tokenization
    2. (5 pts) Parsing
    3. (5 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. (5 pts)

    2. (5 pts)

    3. (5 pts)

    (a) ast1.png (b) ast3.png (c) ast4.png

  5. (10 pts) In your own words, how does an AST capture the idea of operator precedence?

  6. (20 pts) One of the main ideas in the visitor pattern tutorial is the difference between single dispatch and double dispatch. Suppose you were interviewing at some company (say, Amazon, Facebook, Google, Microsoft) and you got a head’s up from an alum that “single vs. double dispatch” is one of the interview questions they ask to see if people “know their stuff”. What concise, but precise answer would you rehearse so that the interviewer would know you understand the difference?

  7. (20 pts) Why, according to the tutorial, is the visitor pattern may be a good fit for a compiler/interpreter? In your answer, be sure to specify: what object is being “visited” in a compiler/interpreter.

http://UCSB-CS56-M16.github.io/hwk/h09