ITEC 380 2018fall ibarland

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

grammars
hw05

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.

1. (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.
2. (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.
3. (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¹.
4. (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-.

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

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

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

home—lectures—recipe—exams—hws—D2L—breeze (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