ITEC 380 2020spring ibarland

home—lectures—recipe—exams—hws—D2L—zoom (snow day)

grammars

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.

The following two problems were deferred from the previous homework. We'd talked about passing-functions-as-arguments in lecture (briefly); here are further notes & videos: passing-functions-before.rkt
1. shapes-in-a-row, from previous homework
2. my-filter, from previous homework

grammars

3. (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.
4. (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.
5. (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¹.
6. (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). The problem doesn't explicity give rules for the non-terminal ID, but since that's one of the examples we essentially did in lecture (and is in the book), you can assume there are rules (which you don't need to refer to). You can thus write things like “ID ( ARG_LIST ) ⇒* foo ( ARG_LIST )” where “⇒*” means “derives in multiple steps”.

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

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

   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 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 repetitions of the letter “x”, separated by commas and ending in a semicolon (which we won't end with in our part (c), next):

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

      This grammar can certainly generate “x, x, x;”.

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

   3. (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.
   4. (3pts) Once you have your grammar, give a leftmost derivation of: function f( a, b ) { z = a*b; return a+z; }.

8. (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.)

   TODO Ian: first ask for a parse tree from the book's Example 2.4, for something like “2 + (x * -4)”. Students worked on linear-structures in previous examples, and continue that rather than seeing a tree-structure when asked for such a branching structure.

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

   hints: Make sure you can derive expressions like “!!!!!!false” and “((((targetFound))))”, in addition to the expression below. You might want to ask yourself:

   • What is allowed to follow a “!”?
   • What is allowed on each side of “||”?

   For comparison, see that book Example 2.4, and what is allowed on either side of binary operators like “+”, and also what it allowed to follow the unary-negation “-”.

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

Trees

The following two problems will be deferred to the following homework, and are not due with this homework.
9. (5pts) Write the function count-name, which takes in an anc-tree (as in lecture) and a string, and returns how many times that name occurs as a name in the anc-tree.
10. (5pts) Write a function that takes in an anc-tree, an eye-color to change, and a new eye-color to replace it with. It returns a similar anc-tree where those eye-colors have been changed, but stopping if the new-eye-color is encountered. For example, you'll might replace all brown-eyed childs with a 'green except that when you reach a green-eyed person, you don't change any of their ancestors. Call your function change-eyes-to-until⁵.

home—lectures—recipe—exams—hws—D2L—zoom (snow day)

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

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