ITEC 380 2016summerIII ibarland

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

task-week04-grammars
grammar questions
self-review

1. For the following grammar, give the indicated parse trees and derivations.

   conjugating verbs (background):

   In natural languages, verbs are often conjugated. For example, when using the verb run, one says I run, but she runs. In English, most verbs just add that s at the end of he/she/it cases (third person singular). But some verbs are irregular, like to be: One says have I am, but you are and she is.

   In Spanish, it's similar: for the verb programar, one says yo programo (I program), but tù programas (you program) and nosotros programos (we program). Similarly, the Spanish verb ser (to be) is irregular: yo soy (I am) but tù eres (you are) and ella es (she is).

   What follows is a simplistic grammar to capture conjugation of (a few) verbs, in Spanish. You don't need to know Spanish (or the notion of 'conjugating verbs') to understand/use the grammar, in the same way a computer can follow these grammar-instructions without actual understanding of Spanish.

   ConjVerb ::= ConjVerbReg | ConjVerbIrreg                       rules 1a,1b
   
   ConjVerbReg ::= yo SPACE RegVerbStem o                          rule 2a 
                   | tú SPACE RegVerbStem as                         rule 2b 
                   | ThirdPersonSingular SPACE RegVerbStem as     rule 2c 
                   | nosotros SPACE RegVerbStem amos                 rule 2d 
                   | vosotros SPACE RegVerbStem áis                  rule 2e 
                   | ThirdPersonPlural SPACE RegVerbStem an       rule 2f 
   
   RegVerbStem ::= program | aclar | practic | pregunt | purific     rules 3a–3e 
   ThirdPersonSingular ::= él | ella | usted                        rules 4a–c
   ThirdPersonPlural ::= ellos | ellas | ustedes                    rules 5a–5c 
   
   
   ConjVerbIrreg ::= ConjEstar | ConjSaber                        rules 6a,6b 
   
   
   ConjEstar ::= yo SPACE estoy                                     rule 7a 
                | tú SPACE estàs                                      rule 7b 
                | ThirdPersonSingular SPACE está                  rule 7c 
                | nosotros SPACE estamos                              rule 7d 
                | vosotros SPACE estáis                               rule 7e 
                | ThirdPersonPlural SPACE están                    rule 7f 
   
   ConjSaber ::= yo SPACE sé                                        rule 8a 
                 | tú SPACE sabes                                     rule 8b 
                 | ThirdPersonSingular SPACE sabe                  rule 8c 
                 | nosotros SPACE sabemos                             rule 8d 
                 | vosotros SPACE sabéis                              rule 8e 
                 | ThirdPersonPlural SPACE saben                   rule 8f 
   
   SPACE ::= ␣ that is, a space-character                                  rule 9 
         

   This grammar is explicit about when a space-character is to be included (written “␣”), something we ignored in the lecture-examples.

   Give a parse tree for the following strings, starting from the nonterminal ConjVerb. For one of them, also give a leftmost derivation, citing which rule you use in each step.

   1. “yo␣programo” “I program”
   2. “ellos␣practican” “they (dudes) practice”
   3. “usted␣está” “you are” — formal singular, and used with a passing quality, as in “you are hungry”

2. In lecture, we saw worked on a grammar for Java variable-declarations (simplified to omit privacy-modifiers), assuming we already have rules for the nonterminals Id_Java, Type_Java, and Expr_Java:

   VarDeclJava ::= TypeJava IdJava; 
                | TypeJava IdJava = ExprJava;
       

   Using that grammar, give a parse tree and/or leftmost derivation for the following.
   (You should have a tree containing “⋮” to represent the nodes between (say) Expr and the expression derived from that nonterminal, since w/o further rules we don't know exactly how that gets filled in.)

   1. “int n;”
   2. “int n = 5+k;”
   3. “Puppy bud = new Puppy( n, "arf", Math.sqrt(4.7) );”
   (All three trees are fairly small and short.)

3. In racket, we can use define to create and initialize an identifier.
   1. Give the racket-code of the Java-statements 1b,1c above.
      (Note that 1a does not have a racket-equivalent: in racket, we can't declare an identifier without giving it a value.)
   2. Give a grammar rule for VarDecl_racket, similar to what we had in Java, similarly assuming we already have rules for the nonterminals Id_racket and Expr_racket.

      Note that we're currently only handling define-for-identifiers, not define-for-functions (See #7 below.)

   3. Now give parse-trees for the two expressions from part (a).
4. List: 0-or-more-statements
   1. Make two examples of 0-or-more-Java-statements.
      (Hint: what are our favorite numbers in computer science, and how do they relate to writing test-cases?)
   2. Give a grammar for 0-or-more-Java-statements, assuming we already have rules for the nonterminal Stmt_java.
   3. Use your grammar to give the parse trees for your two examples in part (a).
5. List: parameter-lists
   1. Make three examples of parameter-lists in java (the stuff that occurs between “(” and “)” when you're defining a method).
      (Hint: what are our favorite numbers in computer science, and how do they relate to writing test-cases?)
   2. Give a grammar for parameter-lists in Java.
   3. Use your grammar to give the parse trees for your two examples in part (a).
6. Let's consider Java method-declarations (simplified to leave of privacy-modifiers):
   1. Give three examples of Java method-declarations.
      (Hint: what are our favorite numbers in computer science, and how do they relate to writing test-cases?)
   2. Now that we have a couple of examples of what we want to be able to generate, give a grammar for Java method-declarations (simplified to leave of privacy-modifiers), assuming we already have rules for the nonterminals Expr_racket.
7. Give a grammar for function-definition, in racket.

   (Of course: Make other non-terminals as needed, and start with a couple of examples (as part (a) in previous problems), and end with using your grammar to give parse-trees for your examples (as part (c) in previous problems).
   If you feel these steps are hauntingly similar the design-recipe — making examples of the data, and then running our code on the test-cases — that is no coincidence; it's because the design-recipe is a general problem-solving technique applicable to most problem-solving situations.)

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

©2015, Ian Barland, Radford University Last modified 2016.Jun.15 (Wed)

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