Midterm 1, CSCI 3155
September 28th, 2004

You have 70 minutes to answer these questions.  Please read all questions before you start.  This is a closed-book exam.  The points for a question are split evenly between its parts.  Please remember that you are bound by the CU honor code.

1. (20 points) This question covers the topic: Syntax and Semantics, BNF.
   1. [Skill 2.2] Describe in your own words the language that this BNF grammar generates

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

   2. [Skill 2.5] Write a BNF grammar for a language that contains all sentences that contain one or more 'a' and one 'b'.  For example, aaabaa, baaa, and aab are in the language but b or a or aaaa are not in the language.
2. (20 points) This question covers the topic: Type checking and equality
   1. [Skill 5.2] Let's suppose you are designing a programming language and need to pick whether the language will use name equality or structural equality.  Give one advantage of name equality over structural equality and one advantage of structural equality over name equality.  Support your points with examples.
   2. [Skill 5.3] Consider the types

      class C1 {
        int i;
        C1 *x;
      }
      class C2 {
        C2 *x;
        int i;
      }
      class C3 {
        int i;
        C1 *x;
      }

      1. Are types C1 and C2 the same by structural equality?  Explain.
      2. Are types C1 and C3 the same by structural equality?  Explain.
          
3. (30 points) This question covers the topic: Data types
   1. Give an example program that uses an enumeration type.  Argue why integers or named integer constants would be less appropriate than the enumeration type.
   2. Give an example program that uses a subrange type.  Argue why integers would be less appropriate than the subrange type.
4. (20 points) This question covers the topics: Bindings and Scoping

1. [Synthesis] Write a program that demonstrates the difference between the scope of a variable and its lifetime.  Explain your example.
2. [Synthesis] How are the storage binding and lifetime of a variable related to each other?  Explain.