CS 331 Spring 2009
Assignment 1

Assignment 1 is due at 5 p.m. Tuesday, February 10. It is worth 25 points.

Procedures

E-mail answers to the exercises below to ffggc@uaf.edu, using the subject “PA1”.

• Your answers should consist of a file containing the answers to Exercises A–H. This file (or an archive file containing it) should be attached to your e-mail message.
• Be sure to include your name in your e-mail.
• I may not read your homework e-mail immediately. If you wish to discuss the assignment (or anything else) with me, send me a separate message with a different subject line.

Exercises (25 pts total)

1. Run the Haskell program prog1.hs (on the web page), and tell me its output.

   Note: To run the program in Hugs, do

   > :load prog1.hs
   > main

   (where “> ” represents the Hugs prompt, and should not be typed). If you are using a Haskell compiler (such as GHC), then simply compile the program and run the executable.
    

2. Write a BNF grammar for the C++ while construct. Your start symbol should be <while_stmt>. You may assume that nonterminals <expr> (a C++ expression) and <stmt> (a C++ statement) are defined elsewhere. Furthermore a block (“{ ... }”) is not considered to be a statement, and is not handled by the <stmt> symbol. Note: Give me an actual BNF grammar, not just some reasonable grammar-ish thing (as on Quiz 2).
    
3. 1. Prove that the following grammar is ambiguous by finding a sentence with two different parse trees.

      <S> → <X>
      <X> → <X> a <X> | b

      Your answer should consist of the sentence and the two parse trees.

   2. Give a non-ambiguous grammar that generates the same language as the above grammar.
   
    
4. Give an English description of the language generated by the following grammar, whose start symbol is <S>.

   <S> → <A>
   <A> → a <A> a | <B>
   <B> → b <B> | b

   
    
5. Consider the following grammar, whose start symbol is <S>.

   <S> → <A> | <B> | x
   <A> → a <A> | <B>
   <B> → bc <B> | <A> | x

   Which of the following strings are in the language generated by this grammar?

   1. abx
   2. abcaax
   3. abcabc
   4. bcbcbx
   5. bcx
   
    
6. Explain the difference between “inherited”, “synthesized”, and “intrinsic” attributes.
    
7. In each part, determine the weakest precondition for the given assignment statement, with the given postcondition.
   1. a = 2 * b + 5
      {a == 3}
   2. a = 2 * b - 6
      {a > 0}
   3. a = b * b + 4
      {a > 0}
   
    
8. Do Page 37, problem 16. The criteria mentioned are those in section 1.3, pages 7–20.
    

CS 331 Spring 2009: Assignment 1 / Updated: 3 Feb 2009 / Glenn G. Chappell / ffggc@uaf.edu