CSci532 Programming Languages and Paradigms: Homework 1

Due date: Monday, September 22, 2008 in class
Each homework may have a different weight, which depends on its level of difficulty.
Absolutely no copying others' work


  1. Using the following context-sensitive grammar:     (20%)
         <sentence> ::= abc | a<thing>bc
         <thing>b   ::= b<thing>
         <thing>c   ::= <other>bcc 
         a<other>   ::= aa | aa<thing> 
         b<other>   ::= <other>b
    derive the <sentence> aaabbbccc and construct a derivation tree for it.






  2. Describe the language over the terminal set {a, b} defined by the following grammar:     (20%)
         <string> ::= a <B> | b <A>
         <A> ::= a | a <string> | b <A> <A>
         <B> ::= b | b <string> | b <B> <B>






  3. Show the following grammar is ambiguous:     (30%)
         <stmt> ::= if <expr> then <stmt> | <matchedStmt>
         <matchedStmt> ::= if <expr> then <matchedStmt> else <stmt> | other 
         <expr> ::= 0 | 1






  4. Write a BNF specification of the syntax of the Roman numerals less than 100.     (30%)