ITEC 380 2008fall ibarland

home—info—lectures—exams—archive

hw04
grammar
hw04

1. (7pts) Programming Exercise 15.8 (subst-in-tree), in Scheme. Include sufficient test cases.
   Note that this function takes in any list-of-S-expression.
   You are welcome (but not required) to use any of {map, filter, foldl}.
   This is (slightly) easier than the file/folder example covered in lecture.
2. (4pts) 3.4 (add Java's ++ and -- to the AExpr def'n)
   You may want to work some of the other problems and come back to this one. (But on the hw you turn in, please include this before the following solutions, thanks.)
3. (3pts) 3.6c Show a parse tree.
4. (3pts) 3.7d Show a parse tree.
5. (4pts) 3.8 (prove grammar ambiguous)
6. (2pts) 3.10 (English description of a grammar)
7. (3pts) 3.11 (which strings derivable?)
   1. baab
   2. bbbab
   3. bbaaaaa
   4. bbbab
8. (3pts) 3.12 (which strings derivable?)
   1. abcd
   2. acccbd
   3. acccbcc
   4. acd
   5. accc
9. (4pts) 3.16 (convert BNF to EBNF)
10. (3pts) 3.17 (convert EBNF to BNF) For next time: Use your new grammar to derive AbAbAbA.
11. (4pts) Write filter-r, which is like filter except that it processes the list elements left-to-right, by using an accumulator. Your function (and any helper functions) should be tail-recursive. (The code for the regular version of filter is given here.)

    ; filter : (-> (-> alpha boolean) (list-of alpha) (list-of alpha)) ; Return a list of all elements of 'data' which are 'good?'. ; (define (filter good? data) (cond [(empty? data) empty] [(cons? data) (if (good? (first data)) (cons (first data) (filter good? (rest data))) (filter good? (rest data)))]))

    ; even-num? any -> boolean ; Just like 'even?', but will accept *any* input, not merely numbers. ; (define (even-num? x) (and (number? x) (even? x))) (check-expect (filter even-num? '()) '()) (check-expect (filter even-num? '(2)) '(2)) (check-expect (filter even-num? '(3)) '()) (check-expect (filter even-num? '(2 3 4)) '(2 4)) (check-expect (filter even-num? '(2 3 4 5)) '(2 4)) (check-expect (filter even-num? '(1 2 3 4 "viii")) '(2 4)) (check-expect (filter string? '(2 3 4 5)) '()) (check-expect (filter-r even-num? '()) '()) (check-expect (filter-r even-num? '(2)) '(2)) (check-expect (filter-r even-num? '(3)) '()) (check-expect (filter-r even-num? '(2 3 4)) '(4 2)) (check-expect (filter-r even-num? '(2 3 4 5)) '(4 2)) (check-expect (filter-r even-num? '(1 2 3 4 5)) '(4 2)) (check-expect (filter-r even-num? '(1 2 3 4 "viii")) '(4 2)) (check-expect (filter-r string? '(2 3 4 5)) '())

home—info—lectures—exams—archive

©2008, Ian Barland, Radford University Last modified 2008.Nov.07 (Fri)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu