ITEC 380 2014fall ibarland

most recent semester

hw05
grammars; tail recursion

Due: due Nov.04 (Mon) in class.
Use a computer (text file) for your derivations, since each step involves repeating (most of) the previous step. However, you can draw your tree freehand.

0. (0pts) Reading: 3.1, 3.2, 3.3
1. (3pts) Chpt.3: Review Question #1 [define syntax, semantics]; answer in your own words.
2. 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) The book's example for <ident_list> (§3.3.1.4¹) gives a grammar for a non-empty list of identifiers. However, we would like a grammar that also allows the empty list. To this end, we allow the special symbol “ε” (epsilon) to denote the empty-string.

      The programmer MC Carthy uses this feature, and comes up with the following attempt for a nonterminal that generates comma-seperated lists of “x”s:

      <XS> → ε | x | x, <XS>

      Prove that this grammar is not correct, by giving a derivation² of a string which is not a comma-separated list.

   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; }

   Give your grammar rules in basic BNF and → (and ε), but not using Extended BNF constructs like ? and ^* (nor equivalently, written as _opt and …).

3. (6pts) Chpt.3, #5 [write a BNF for boolean expressions in Java]

   For this problem, assume that you already have grammar rules for a Java numeric expression (“NumExpr”, probably similar to the book's Fig. 3.4), for a Java identifier (“Id”), and that the only 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³.

4. Write count-bigs-v2, which is like count-bigs from hw03a-soln.rkt:
   1. (3pts) Write it in Java, using a while-loop, and updating an accumulator (“so-far”) variable, and updating the list by using java.util.List#subList. (Similar to sum_v2 in the class notes.)
   2. (3pts) Write it as a tail-recursive function in racket (similar to sum-v2 in the class notes.)
   Between the two versions, use the same name for any variables/functions that correspond, up to idiomatic spelling (e.g. in the notes' sum_v2, the Java variable sumSoFar corresponded to the Racket variable sum-so-far).
5. Write reverse⁴, in two versions in Racket:
   1. (4pts) reverse-v1, which follows the usual design recipe. You'll need to create a helper-function to do this. (That helper function will itself follow the design recipe, of course!) (Do not use the built-in function append.)
   2. (3pts) as a tail-recursive function. (Call this version reverse-v2 or such.)
   3. (2pts) Time⁵ these two versions on some long lists and explain the timing results. (Remember the function nums-from from lecture.)
6. (2pts) What is the signature for map?                                                             
   (that is, the version of map we wrote in class, and that is in the student languages). Give your answer in a comment.

   Note: “function” is not a specific-enough type, although something like “number → boolean” is. Similarly, “list” is not specific enough⁶, but “(listof string)” is.

7. (4pts) Write a function which takes in a list of strings (some of which might be numerals), and returns a list of just the numerals, in descending numeric order (with any leading zeroes removed⁷). For example, given (list "hello" "35" "009" "hmm" "-7" "43"), your function would return (list "43" "35" "9" "-7").

   Your function should consist of calls to map and filter (and sort), as well as routine functions like string->number. It should not need cond/if, nor need any auxilliary helper functions. It is possible to write the function-body in a single line (or an equivalent let* which uses four local identifiers).

8. (4pts)
   1. Using just a call to filter and lambda, write an expression which returns all numbers in (list 7 13 9 10 11 19 20 21 99 15 0) that are in the half-open interval [10,20) (that is, numbers x in the range 10 ≤ x < 20).
   2. Write a function which takes in a list of real numbers and two real numbers a,b, and returns all elements in the list which are in the half-open interval [a,b) Your function-body should just be a call to filter, with an appropriate lambda.

9. (4pts) Write filter-out, which does the opposite of filter: it takes in a predicate and a list, and returns a list of all elements which fail the filter. For example, (filter-out even? (list 2 3 4 5)) should return (list 3 5). Give at least two additional test cases.

   Write your function without using filter or other higher-order functions — instead just use the standard list-processing template.

most recent semester

©2014, Ian Barland, Radford University Last modified 2014.Sep.27 (Sat)

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