CS 380 2024fall ibarland

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

grammars

Reading: Scott §3.6.4 and §11.6 (lambda expressions); §2.1 (grammars). ; functional vs imperative trade-offs: 11.8 ; functional overall: all of 11, incl. 11.2(FP concepts)

grammars

1. “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. “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. Exercise 2.12b a parse tree for “a b a a”; pp.107–8 in 4ed, or pp.104–5 in 5ed, and is exercise 2.9b 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. Using the grammar in the book's Example 2.4 (for <expr>, p.48–49 of Scott 4ed), give a leftmost derivation of the string 2+(3*-x).

   Gloss over “missing rules”: Presume that <id> ⇒* x, and similarly that <number> ⇒* 2 and <number> ⇒* 3, even though we aren't shown the rules for <id> nor <number>. In your derivation you'll have a step using “⇒*” where (exactly) one of those non-terminals gets replaced (to communicate that there are technically multiple steps that are not being shown).

   caution: Don't use the grammar of Example 2.8 by mistake.

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

   <JsFunc> → function <JsIdent>( <JsIdents> ) { <JsBody> } this is one long rule which contains two newlines

   For the grammar rules below, 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. 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. 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> (Examples 2.20 and 2.21 in §2.3), they present rules for a non-empty list of comma-separated identifiers. The book includes a semicolon at the end, which we're ignoring. 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 indeed generate “x, x, x”.

      Prove that this grammar is actually not what we want, by giving a derivation of some string which is not a valid comma-separated list-of-“x”s. As usual, for full credit give the shortest correct answer.²

   3. 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. Once you have your grammar, show that function f( a, b ) { z = a*b; return a+z; } is a <JsFunc> by drawing a parse tree.

      Gloss over “missing rules”: Since we're presuming that <JsIdent> ⇒* a and <JsStmt> ⇒* z = a*b; (using rules we haven't been shown), in your tree just draw a dotted line “⋮” between them e.g. from <JsIdent> to its leaf/descendent a, and from <JsStmt> to its leaf/descendent z = a*b;.

6. Generating a grammar

   1. Create a grammar for Java's boolean expressions.
      (That is: rules describing exactly what you are allowed to put, say, inside the parentheses of a Java if (…) … statement.)

      For this problem, assume that you already have grammar rules for a Java identifier (“<Id>”), for a Java numeric expression (“<NumExpr>” -- which is presumably similar to the book's Example 2.4, p.46), and that the only boolean operators you want to handle are &&,||,!,== and the numeric predicates >, >=, and ==. (You do not need to worry about enforcing precedence, 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. Make sure you cannot derive expressions like x false (two expressions not one), 2 > true (> can only occur between numeric-expressions, not boolean-expressions), or (the empty string). 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 “-”.

   2. Using your grammar, draw a parse tree (not a derivation) for: a+2 > 5 || ((!false == x))
      In the tree, for children of <NumExpr> and <Id>, you can just write “⋮” 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—hws—exams—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