ITEC 380 2015fall ibarland

home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)

hw05
Invaders I; grammars

Due Oct.19 (Mon.) in class (hardcopy, and on D2L).

Your name and the assignment-number must be in a comment at the start of the file, and your hardcopy must be stapled. All functions/data must include the appropriate steps¹ of the-design-recipe—the design recipe: final version. In particular, test cases alone might be worth half the credit for a function. Unless otherwise indicated, two test cases will suffice for most problems, if they are testing different situations.

1. (2pts) Review Question 2.1 (p.50: syntax vs. semantics) — give a short (1-2 sentences) answer in your own words.
2. (2pts) Review Question 2.8 (p.51: define “ambiguous”) — give a short (~1 sentence) answer in your own words.
3. (4pts) Exercise 2.12, part b only (p.105: parse tree for “a b a a”). Note you can ignore the “$$”; the book uses this to indicate end-of-input. I recommend drawing your tree freehand³. Make sure that each non-leaf node of your tree corresponds directly to a rule in the grammar (the node is a rule's left-hand-side, and its children are exactly the right-hand-side) — no skipping steps⁴.
4. (4pts) Exercise 2.13, part b only (p.105: leftmost derivation of “foo(a, b)”).

   I encourage you to actually put all the nonterminals in upper-case (or at least first-letter-upcased), just to make it easier to tell terminals from non-.

5. Deriving lists, with a grammar:
   Suppose we had the following grammar rule for a javascript function, “<JsFunc>”:

   <JsFunc> → function <JsIdent>( <JsIdents> ) { <JsBody> }

   1. (3pts) Define rule(s) for the nonterminal <JsBody>, which can be 0 or more statements.
      Presume that you already have rules for a nonterminal “<JsStmt>” (an individual statement; note that statements already include semicolons, so your rules shouldn't add any additional ones).

   2. (2pts) As we consider how to define <JsIdents>, a comma-separated list of identifiers, we note that the book as something similar: in the example of <id_list> (§2.3, pp.67–69), they present rules for a non-empty list of comma-separated identifiers (and, ending in a semicolon). Removing the semicolon will be trivial, but we do need to figure out how to adapt it to allow the possibility of zero identifiers.

      Working towards a solution, the programmer MC Carthy comes up with the following attempt for a nonterminal that generates comma-seperated lists of “x”s (also ending in a semicolon):

      <XS> → ; | x; | x, <XS>

      Prove that this grammar is not correct, by giving a derivation⁵ of some string which is not a valid comma-separated list (ending in a semicolon).

   3. (3pts) Define rule(s) rules for the nonterminal <JsIdents> which correctly generates 0 or more comma-separated identifiers.
      Presume that you already have rules for a nonterminal “<JsIdent>” (an single identifier).
      You will need to include a second “helper” nonterminal.
   4. (3pts) Once you have your grammar, give a leftmost derivation of: function f( a, b ) { z = a*b; return a+z; }.

   For the grammar rules, write them as in class: in basic BNF using “→” (and “ε”), but not using Extended BNF constructs like ? and ^* (nor equivalently, written as _opt and …).

6. (6pts) Generating a grammar

   Give a grammar for Java's boolean expressions. (That is: a grammar describing exactly what you are allowed to put inside a the parentheses of a Java if (…) statement.)

   For this problem, assume that you already have grammar rules for a Java numeric expression (“NumExpr”, probably similar but, for Java, more-complete-than the book's Example 2.4, p.46), for a Java identifier (“Id”), and that the only boolean operators you want to handle are &&,||,!,== and the numeric predicates >, >=, and ==. (You do not need to worry about making a grammar that enforces precedence, although you are welcome to.) For this problem, you may use extended BNF constructs ? or ^* (or equivalently, written as _opt and …).

   Using your grammar, give a parse tree (not a derivation) for: a+2 > 5 || (!false == x)
   In the tree, for children of NumExpr and Id, you can just use “⋮” to skip from the non-terminal directly to its children, since you didn't write the exact rules for those nonterminals. I recommend drawing your tree freehand⁶.

The following problems will form the basis of our space-invader program, which we'll complete in the next homework. You may base your answer on hw04b-soln.rkt (but you certainly don't need to); of course give credit and URL if you do so.

Complete problems in racket, except for 5 and 6 which you'll complete in Java and racket, as instructed. Your Java method should compile and run and be correct, but then you can paste it into a racket block-comment (#| … |#) so that you only need submit&print one file. Make sure it is property formatted, of course.

7. (3pts) Write the template for a bullet-processing function, in both racket and Java.
   (In Java, you'll have to comment out the template, since the “...” won't compile.)

8. (5pts) In both racket and in Java: Write the function move-bullet (Java: Bullet#move⁷) that, for the given bullet, returns a new bullet object one “tick” (frame) later (ignoring any boundaries/collisions⁸).

   The Java and racket versions should both do the same thing: return a new object, rather than mutating any fields (Cf. derive-from in the lecture notes). The two versions should correspond as directly as possible (including all names being the same, up to idiomatic differences — racket prefers hyphens whereas Java uses camelCase).

   We won't use Java test-cases (since that entails overriding Object#equals, which is not really related to our problem, and is more involved⁹ than we'd prefer.

9. (4pts) Aliens
   Write move-alien : alien, real, real → alien, which returns an alien whose (x,y) position is shifted by the indicated amount. It should ignore walls/boundaries. (We already have the data-definition from hw04b-soln.rkt, but you still need the per-function design-recipe steps of course).

10. (3 pts) Cannons
    As discussed, a cannon might be represented as just a single real-number (see hw04b-soln.rkt). Write the function cannon-handle-key : cannon, keypress → cannon which returns a new cannon updated to handle a key event, moving the cannon either left, right, or not at all, depending.

    Since the documentation shows that key-events are (a certain subset of) strings, it's certainly possible to compare them via string=?. However, you might see that there is also the function key=?, which definitely feels more appropriate for this task (even though it works exactly the same as string=?, on key-events). In order to use key=?, you need to (require 2htdp/universe).

11. Worlds:

    1. (2pts) Define a “world” structure which contains a cannon , one bullet, and (for now¹⁰) exactly one alien.

       As usual for our data-definitions, make examples of the data (at least two), and a template.

    2. Give a template for a world-processing functions.
    3. (3pts) Write the function update-world : world → world which returns a new world one “tick” later.

       For the time being, you can have update-world simply move the world's alien to the right. Ultimately, this function will decide whether the alien(s) should be moving to the left or to the right (or, down) -- and to do that, we'll need to keep some further info (where?) which tracks which direction they're currently moving in. (And if you want to start implementing this now, that's totally fine — it'll save you time on the next homework, where we finish the game.)

       For now, you don't need test cases that involve the bullet colliding with anything — you can just have the bullet far away from any aliens or cannons.

    4. (2pts) Write the function world-handle-key : world, keypress → world which returns a new world updated to handle the keypress. (Should be easy -- mostly defers to cannon-handle-key, and your test cases will largely crib from that.)
12. Drawing functions:
    1. (2pts) Write the function draw-alien : alien, image -> image, which takes an alien and a “background” image, and returns that background image with an alien drawn on top of it.

       hint:place-image is a handy function; it is similar to overlay/xy except that it crops the result to the background.

       hint: For test-cases, include drawing an alien that is: (a) in the middle of a small image; and (b) one that is mostly off the left-edge but has just a few pixels showing.

       Note: Here's an image you can (modify to) use in your test-cases, in addition to a solid rectangle or whatever else you might choose: house-with-flowers.rkt. If you place this file in the same directory as other functions, you can just (require "house-with-flowers.rkt"), and then use its exported id (“house-with-flowers”, coincidentally). You don't need to print this file.

    2. (2pts) Write the similar function draw-cannon : cannon, image → image (where, as mentioned in hw04b-soln.rkt, cannon might be just a number).
    3. (0pts) Write the function draw-world : world -> image, which (for the moment) draws the alien and cannon (only) onto a blank background.

       hint: Call draw-alien with an empty-scene for the background; call draw-cannon passing it the result of draw-alien as the second argument.

    4. (1pt) Write the function draw-bullet : bullet, image -> image.
    5. (3pts) Change your draw-world so that it incorporates drawing the bullet as well. (You don't need to include your previous part (c); you can update the code and test-cases directly. Part (c.) was just so that you'd understand how to combine the drawing of two things, before you try drawing three.)

13. (5pts) To do collision detection, write a suitable helper function to detect when two rectangles overlap (e.g. the bullet's bounding-box and the region occupied by a brick). Make at least four test-cases¹¹ for this.

    There are several reasonable ways to represent rectangles, but it helps if your representation aligns with the arguments needed for 2htdp/image's overlay/xy, which places an images according to its center. I recommend passing in four numbers for each rectangle, rather than the more heavyweight approach of defining a rectangle-struct.

    hint: I recommend using half-open intervals, to define a rectangular region: A rectangle centered at 40,50 that is 60x80 would be considered to have x-coordinates in [40-30,40+30) — up to (but not including) the endpoint. It's not that big a deal, but it does mean it's easy to tile the entire plane while neither overlapping at all, nor leaving any 1-pixel-wide (or even infitesimal) gaps.

    If doing so, a useful helper function to write might be (<=< a b c): is a ≤ b < c?

    cool hint, from robotics: We can reduce this problem involving two rectangles to a simpler one: checking if an expanded version of the first rectangle merely contains the center of the second.
    For example: consider a 20×30 rectangle whose center corner is at (500,400) and a second rectangle which is 80×60. These two rectangles overlap exactly when the second rectangle's center is inside the (20+80)×(30+60) rectangle centered at (500,400). Sketching this example on paper will help you understand why this works.

All the above should have their tests, as well as signatures and (brief) purpose statements. Only after all tests pass, the following should work (in racket):

(require 2htdp/universe)

(big-bang some-initial-world
          [on-key  world-handle-key]
          [on-tick update-world]
          [to-draw draw-world])

  public boolean equals( /* Foo this, */ Object that ) {
    if (that==null) {
      return false;
      }
    else if (this==that) {
      return true; // short-circuit a common case
      }
    else if (that.getClass() != this.getClass()) {
      return false;  // CAUTION: unless we can be .equals to a subclass?
      }
    else {
      Foo thatt = (Foo)that;
      // NOW you can add your code that actually compares fields, say:
      return (this.someField==null ? thatt.someField==null : this.someField.equals( thatt.someField ))
          && (this.someOtherField==null ? thatt.someOtherField==null : this.someOtherField.equals(thatt.someOtherField)
          // If our constructors never create objects w/ `null`, we can shorten the preceding lines a bit.
          && …
          ;
      }
    }
      

home—lectures—recipe—exams—hws—D2L—breeze (snow day; distance)

©2015, Ian Barland, Radford University Last modified 2015.Oct.17 (Sat)

Please mail any suggestions (incl. typos, broken links) to ibarlandradford.edu