ITEC380 grammars

grammars
and tail-recursion

~~Tentative/to-be-determined some problems due Mar.21 (Thu), and the remainder~~ due by Mar.26 (Tue) in class, hardcopy and D2L. (I personally recommend completing at least #3 and either #9 or #10 by class on Thursday, to help ensure you're on the right track.)
Submit a single pdf file named hw06.pdf:

I suggest using a text-editor like Word (or LibreOffice or DrRacket or similar): The derivations are best written in a text-editor where you can copy/paste one line and replace a single non-terminal to create the next line. But for parse-trees, I recommend drawing them freehand.

Your hardcopy should include your answers, and your (presumably-hand-drawn) trees. Including images is optional for the pdf; I will use your hardcopy to grade the trees.

If you do want to incorporate your images (in the single pdf), you can of course do so via Word/LibreOffice/etc.; you may also do so via DrRacket's Insert » Insert Image…, and then printing to pdf.

Your name and the assignment-number must be in a comment at the start of the file, along with a link to this assignment page.

grammars

(2pts) “Check Your Understanding” Question 2.1 (syntax vs. semantics: p.53 in 4ed, or p.50 in 3ed) — give a short (1-2 sentences) answer in your own words.

(2pts) “Check Your Understanding” Question 2.8 (re “ambiguous”: p.53 in 4ed, or p.51 in 3ed) — give a short (~1 sentence) answer in your own words.

(4pts) Exercise 2.12, part b only (a parse tree for “a b a a”; pp.107–8 in 4ed, or pp.104–5 in 5ed, and is exercise 2.9 in 2ed).
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 ¹.

(4pts) Exercise 2.13, part b only (except make it a leftmost derivation of “foo(a, b)” rather than a rightmost; p.108 in 4ed, and p.105 in 3ed).

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-.

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

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

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 …).

(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).
(2pts) As we consider how to define <JsIdents>, a comma-separated list of identifiers, we note that the book has 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-separated lists of “x”s (albeit still ending in a semicolon, unlike our part (c) next):
<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).
(3pts) Define rule(s) for the nonterminal <JsIdents> which correctly generates 0 or more comma-separated identifiers.
Presume that you already have rules for a nonterminal “<JsIdent>” (a single identifier).
You will need to include a second “helper” nonterminal.
(3pts) Once you have your grammar, give a leftmost derivation of: function f( a, b ) { z = a*b; return a+z; }.

(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 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 / is unambiguous, although you are welcome to.) For this problem, you may use the Extended BNF constructs ? and ^* (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 ³.

tail recursion

(4pts) Write my-list-ref, which takes a list and an index, and returns the list item at the indicated index (0-based). (my-list-ref 2 (list 'a 'b 'c 'd 'e)) will return 'c. In Java, this function is called List#get(int). Your signature should include a type-variable such as α or T. The pre-condition ⁴ is that the index is less than the length of the list. Of course, do not just call the built-in list-ref; you should follow the data-definition for natural numbers, instead of for lists. (So do not check for the empty-list ⁵.)

data def'n: A natural-number is:

0, OR

(+ 1 [natural-number])

The predicates zero? and positive? are often used to distinguish the two branches, though of course = and > could be used equally-well.
For a longer discussion of the same, see natnum-defn-taster.rkt for thinking of sub1 as the “getter” to pull out the “natural-number field, which a positive is built out of”. For mathematically-inclined, here's “if your language provided neither numbers nor `+`, how would you do addition?”.

(2pts) A tail-recursive function is one where after making a recursive call.

Note: Note that being tail-recursive is a property of a function’s source-code. The fact that a tail-recursive function can be optimized to not unnecessarily-allocate stack space is a compiler-implementation issue — albeit it’s what makes the concept of tail-recursion important.

Reading: Scott also discusses recursion and tail-recursion, in §6.6.1 (both 3rd and 4th eds).

(5pts) Based on Exercise 11.6b from Scott (third ed., 10.6b), min:

First, complete the following Java while-loop, in spirit similar to stringAppendWhoa from lecture.

#|
   /** Return the smallest number in a list.
     * @pre <code>!nums.isEmpty()</code>
     * @return the smallest number in `nums`.
     */
    static Double myMin( List<Double> nums ) {
        // initialize our loop-variables:
        double minSoFar = nums.get(    );
        List<Double> numsRemaining = nums.subList(    ,nums.size());

        while (                          ) {
            double a = numsRemaining.get(0);  // corresponding to Scott’s variable `a`
            minSoFar = (               ?            :      );
            numsRemaining =                                                       ;
            }
        return minSoFar;
        }
|#

(Your code must be legal Java, but you don't need to submit an extra .java file — you can just paste the method into a #| racket block comment |#.)

Now, convert the above code to a tail-recursive racket function. Use corresponding names (e.g. “my-min”, “nums-remaining”, etc.). Include signature, purpose-statement, and test-cases for both your main function and your helper. Part of the grade is based on whether your solution has a nearly word-for-word equivalent in the java code above. So don't add e.g. throwing an exception, since that's not in the Java code given here.
Btw: The book’s starting-code calls (empty? (rest l)) — something not in the template. It’s a bit of a hack to stray from the template: Scott wants to avoid making a helper-function, but still return a sentinel-value answer for empty-lists.
However, when converting to tail-recursion, this difference ends up being moot: as you make a helper/wrapper function for the tail-recursion, that extra check disappears.

scheme vs racket: The book’s scheme code uses: car, cdr, null?, and #t. In racket, these names are (respectively): first, rest, empty?, and #true.

This looks familiar: Yes, this problem is nearly identical to the “my-max” function in the notes that we went over in class. Oh well. I figure if you understand that example, then this problem won take long, and if you come across difficulties then it's still a good problem to work through.

(5pts) Inspired by Scott's exercise about log2 (11.6a; third ed. 10.6a): Here is a function to convert a number to its base-2 representation ⁶:

(check-expect (natnum->string/binary 0) "") 
(check-expect (natnum->string/binary 1) "1")
(check-expect (natnum->string/binary 2) "10")
(check-expect (natnum->string/binary 3) "11")
(check-expect (natnum->string/binary 4) "100")
(check-expect (natnum->string/binary 5) "101")
(check-expect (natnum->string/binary 15) "1111")
(check-expect (natnum->string/binary 16) "10000")
(check-expect (natnum->string/binary (+ 1024 8 4)) "10000001100")
(check-expect (natnum->string/binary #x0A) "1010")  ; hex literal "0A"
(check-expect (natnum->string/binary #xFFFF) "1111111111111111")
(check-expect (natnum->string/binary #xFeedBee) "1111111011101101101111101110")

; natnum->string/binary : natnum -> string
; Return the binary-numeral representing n (without any leading zeroes).
; Note that the numeral for zero, without leading zeros, is the empty-string!
;
(define (natnum->string/binary n)
    (cond [(zero? n) ""]
          [(positive? n) (string-append (natnum->string/binary (quotient n 2))
                                        (if (even? n) "0" "1"))]))

Btw: This code doesn’t quite follow the design-recipe for natural-numbers, because it recurs on (quotient n 2) rather than (sub1 n). But it still works fine because it “reduces” the natnum to a smaller one. To reason about this code, you wouldn’t use straight-up mathematical induction; instead you’d call it “strong induction”.

The above code is not tail-recursive, because after the recursive call, it must still call .
Give a tail-recursive version of this function. (Be sure to include tests, purpose-statement, etc. for any helper function you write.)

¹ I encourage you to notate, to the right of each step, the exact rule-number used for that step (numbering the grammar rules 1,2,3a,3b, etc.). ↩

² The best answer is the shortest: if you have a simple example that uncovers the grammar's flaw, that is better than a long example doing so. ↩

³ You can turn in your printout + your drawing, or if you really want just one file to turn in, you can take a photo and then insert it into DrRacket. ↩

⁴ Remember, your code doesn't need to check the pre-condition; if the caller violates it, your code can do whatever it likes — return a wrong answer, throw a (different) exception, run forever. For example, in Java "hello".substring(3,1) throws an exception with the slightly odd message “String index out of range: -2”. ↩

⁵ Since passing in an empty-list is a violation of the pre-condition, you don't need to check for it. Software design suggests your code can do anything it likes in this situation; signalling and error message yourself is a nice "extra", but I want to not do that here, to help reinforce how code follows from the data-definition. ↩

⁶ Realize that numbers, numerals, and digits are three distinct concepts. In programming, the distinction becomes clear: numbers/numerals/digits correspond to double/string/char, respectively. ↩

This page licensed CC-BY 4.0 Ian Barland
Page last generated

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

grammars and tail-recursion

grammars

tail recursion

grammars
and tail-recursion