ITEC 380 2012fall ibarland tlewis32

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

hw06
grammars; tail recursion

Due: due Oct.17 (Wed) 18:00.
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.

1. (0pts) Reading: 3.1, 3.2, 3.3
2. (3pts) Chpt.3: Review Question #1 [define syntax, semantics];
3. (3pts) Problem Set #11 (8ed: ??) [which strings are derived from a grammar]. For the strings that are derivable, give a left-most derivation (using “⇒” as in the book).
   1. baab
   2. bbbab
   3. bbaaaaa
   4. bbaab
4. 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 is 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 * or ….

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

   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 the children, the exact rules for those nonterminals aren't rules you wrote.

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

©2012, Ian Barland, Radford University Last modified 2012.Oct.18 (Thu)

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