FINAL EXAM
CSU 670 FALL 2005				Karl Lieberherr

Open book and open notes


Question 1: Implementing a simple style rule
===========================================================
10 UNKNOWNs, 4 points each = 40 points

Consider the following class dictionary ConcreteClasses:

import edu.neu.ccs.demeter.dj.*;

Main = .
CGraph = <classDefs> List(ClassDef).
ClassDef = <lhs> ClassName <rhs> Body.
Body = "=" <parts> List(Part) ".".
Part = ClassName.

List(S) ~ {S}.
ClassName = Ident.

which defines a simple form of class dictionaries.

Your task is to implement the following version of the terminal buffer rule.

The terminal classes Ident and String, if they appear
on the rhs of a class definition, must be the only
element of the Part_List.

For example, class B violates TBR:

B = Ident D.

I have written a program P1 that checks TBR and produces the following output:

 VIOLATION of TBR for class B
terminal class name = Ident
 appears inappropriately on rhs 

done

Find the UNKNOWNs in the following program P1:

Main { {{
  public static void main(String args[]) throws Exception {
    CGraph m = CGraph.parse(System.in);
    ClassGraph cg = new ClassGraph(true, false);
    ClassGraph cgWithoutTail = new ClassGraph(cg,
	             "from CGraph bypassing -> *,tail,* to *");
    m.checkTBR(cgWithoutTail);
    System.out.println("done");
  }
}}
}

CGraph { {{
  void checkTBR(ClassGraph cg) {
    cg.traverse(this, "UNKNOWN1",
    new Visitor(){
    int numberOfParts = 0;
    ClassName current;
    void before (ClassDef host) { 
       UNKNOWN2
    }
    void before (Body host) { 
       UNKNOWN3
    }
    void after (Body host) { 
       numberOfParts = 0;
    } 
    void before (ClassName host) { 
       if ((numberOfParts > 1) && (host.isTerminal())) {
         System.out.println(" VIOLATION of TBR for class " + 
	   UNKNOWN4.get_ident());

         System.out.println("terminal class name = " + UNKNOWN5.get_ident());
         System.out.println(" appears inappropriately on rhs ");
         System.out.println();
       };
    }
    });
  }
}}
}
ClassName { {{
  boolean isTerminal(){
    Ident i = this.UNKNOWN6();
    Ident nIdent = UNKNOWN7;
    Ident nString = UNKNOWN8;
    return (i.UNKNOWN9(nIdent) || i.UNKNOWN10(nString));
  }     
}}
}


Question 2: Class dictionary design and program design
===========================================================
16 UNKNOWNs 3 points each = 48 points

In this part we are extending the program from question 1 with a new feature:
Abstract classes.

We want to process inputs like:

A = B.
B = Ident D.
CC : A | B     X Y Ident.
CC2 : A | B common X Y Ident.
DD : A Ident B.
DD2 : A common Ident B.

which you know from Demeter class dictionaries.

Your program should produce the output below:


 VIOLATION of TBR for class B
terminal class name = Ident
 appears inappropriately on rhs 

 VIOLATION of TBR for class CC
terminal class name = Ident
 appears inappropriately on rhs 

 VIOLATION of TBR for class CC2
terminal class name = Ident
 appears inappropriately on rhs 

 VIOLATION of TBR for class DD
terminal class name = Ident
 appears inappropriately on rhs 

 VIOLATION of TBR for class DD2
terminal class name = Ident
 appears inappropriately on rhs 

done

Notice that we don't implement flattening of the class dictionary.
We have the simple rule for an abstract class:

The terminal classes Ident and String, if they appear
on the rhs of a class definition, must be the only part.

A : B common Ident.

does not violate TBR.

Find the UNKNOWNs in the following class dictionary (program.cd)
and program (program.beh)

program.cd:

import edu.neu.ccs.demeter.dj.*;

Main = .
CGraph = <classDefs> List(ClassDef).
ClassDef = <lhs> ClassName <rhs> Body.
Body : UNKNOWN1 | Abstract common <parts> List(UNKNOWN2) UNKNOWN3.
Concrete = UNKNOWN4.
Abstract = ":" <subclasses> UNKNOWN5 [UNKNOWN6].
Common = "common".
Part = ClassName.

List(S) ~ {S}.
BarList(S) ~ S {"UNKNOWN7" S}.

ClassName = Ident.



Main { {{
  public static void main(String args[]) throws Exception {
    CGraph m = CGraph.parse(System.in);
    ClassGraph cg = new ClassGraph(true, false);
    ClassGraph cgWithoutTail = new ClassGraph(cg,
       "from CGraph bypassing -> *,tail,* to *");
    m.checkTBR(cgWithoutTail);
    System.out.println("done");
  }
}}
}

CGraph { {{
  void checkTBR(final ClassGraph cg) {
    cg.traverse(this, "UNKNOWN8",
    new Visitor(){
    int numberOfParts = 0;
    ClassName current;
    void before (ClassDef host) { 
       current = (ClassName) cg.fetch(host,
         "from UNKNOWN9 via -> *,UNKNOWN10,* to UNKNOWN11");
    }
    void before (Body host) { 
       UNKNOWN12
    }
    void after (Body host) { 
       UNKNOWN13
    } 
    void before (ClassName host) { 
       if UNKNOWN14 {
         System.out.println(" VIOLATION of TBR for class " + 
	   UNKNOWN15.get_ident());

         System.out.println("terminal class name = " + UNKNOWN16.get_ident());
         System.out.println(" appears inappropriately on rhs ");
         System.out.println();
       };
    }
    });
  }
}}
}
ClassName { {{
  boolean isTerminal(){
    // unchanged: same as in question 1
  }     
}}
}

Question 3: Class dictionary design and program design
============================================================
8 UNKNOWNs 3 points each = 24 points

Here we extend the program from question 1 with another feature:
parameterized classes.

For the input:

A(S) = B(S) Ident.
B = Ident D.
C(S) = U Ident D(S).
Sandwich(S) = List(Ident) X Y S String.
Y = List(String).
Y1 = List(String) List(X).
Z = String.

we want the following output:

 VIOLATION of TBR for class A
terminal class name = Ident
 appears inappropriately on rhs 

 VIOLATION of TBR for class B
terminal class name = Ident
 appears inappropriately on rhs 

 VIOLATION of TBR for class C
terminal class name = Ident
 appears inappropriately on rhs 

 VIOLATION of TBR for class Sandwich
terminal class name = String
 appears inappropriately on rhs 

done

Notice that a terminal class name on the right hand side
of a class definition is visited only if it is not in an actual
parameter position.

Find the UNKNOWNs below:

import edu.neu.ccs.demeter.dj.*;

Main = .
CGraph = <classDefs> List(ClassDef).
ClassDef = <lhs> UNKNOWN1 <rhs> Body.
Body = "=" <parts> List(Part) ".".
Part = UNKNOWN2.

ClassSpec = ClassName
  [Params].
  Params = "(" List(ClassSpec) ")".
// for formals on lhs, need only List(ClassName)
// Language is more general than needed for the sake of brevity

List(S) ~ {S}.
ClassName = Ident.



Main { {{
  public static void main(String args[]) throws Exception {
    CGraph m = CGraph.parse(System.in);
    ClassGraph cg = new ClassGraph(true, false);
    ClassGraph cgWithoutTail = new ClassGraph(cg,
       "from CGraph bypassing -> *,tail,* to *");
    m.checkTBR(cgWithoutTail);
    System.out.println("done");
  }
}}
}

CGraph { {{
  void checkTBR(final ClassGraph cg) {
    cg.traverse(this, UNKNOWN3,
    new Visitor(){
    int numberOfParts = 0;
    ClassName current;
    void before (ClassDef host) { 
       current = (ClassName) cg.fetch(host, UNKNOWN4);
    }
    void before (Body host) { 
       UNKNOWN5
    }
    void after (Body host) { 
       numberOfParts = 0;
    } 
    void before (ClassName host) { 
       if UNKNOWN6 {
         System.out.println(" VIOLATION of TBR for class " + 
	   UNKNOWN7.get_ident());

         System.out.println("terminal class name = " + UNKNOWN8.get_ident());
         System.out.println(" appears inappropriately on rhs ");
         System.out.println();
       };
    }
    });
  }
}}
}
ClassName { {{
  boolean isTerminal(){
    // unchanged: same as in question 1
  }     
}}
}


Question 4: Class dictionary design and program design
=============================================================
15 UNKNOWNs 3 points each = 45 points

Here we consider a program that has both features:
parameterized classes and abstract classes.
Note that there is interaction between the features:
The parameterized classes may be abstract.

The input:

A = B.
B = Ident D.
C(S) = U Ident D(S).
Sandwich(S) = List(Ident) X Y S String.
AAAA : B(Ident) | X | Y common String Y.
AAA : B(Ident) | X | Y .
Z = Ident.
Z1 = List(String) List(Ident).

produces the output:

 VIOLATION of TBR for class B
terminal class name = Ident
 appears inappropriately on rhs 

 VIOLATION of TBR for class C
terminal class name = Ident
 appears inappropriately on rhs 

 VIOLATION of TBR for class Sandwich
terminal class name = String
 appears inappropriately on rhs 

 VIOLATION of TBR for class AAAA
terminal class name = String
 appears inappropriately on rhs 

done

Find the UNKNOWNs in program.cd and program.beh below:

import edu.neu.ccs.demeter.dj.*;

Main = .
CGraph = <classDefs> List(ClassDef).
ClassDef = <lhs> UNKNOWN1 <rhs> Body.
Body : UNKNOWN2 | Abstract common <parts> List(UNKNOWN3) UNKNOWN4 .
Concrete = UNKNOWN5.
Abstract = ":" <subclasses> UNKNOWN6 [UNKNOWN7].
Common = "common".
Part = UNKNOWN8.

ClassSpec = ClassName
  [Params].
  Params = "(" List(ClassSpec) ")".
// for formals on lhs, need only List(ClassName)
// Language is more general than needed for the sake of brevity

List(S) ~ {S}.
BarList(S) ~ S {UNKNOWN9 S}.

ClassName = Ident.



Main { {{
  public static void main(String args[]) throws Exception {
    CGraph m = CGraph.parse(System.in);
    ClassGraph cg = new ClassGraph(true, false);
    ClassGraph cgWithoutTail = new ClassGraph(cg,
       "from CGraph bypassing -> *,tail,* to *");
    m.checkTBR(cgWithoutTail);
    System.out.println("done");
  }
}}
}

CGraph { {{
  void checkTBR(final ClassGraph cg) {
    cg.traverse(this, UNKNOWN10,
    new Visitor(){
    int numberOfParts = 0;
    ClassName current;
    void before (ClassDef host) { 
       current = (ClassName) cg.fetch(host, UNKNOWN11);
    }
    void before (Body host) { 
       UNKNOWN12
    }
    void after (Body host) { 
       numberOfParts = 0;
    } 
    void before (ClassName host) { 
       if UNKNOWN13 {
         System.out.println(" VIOLATION of TBR for class " + 
	   UNKNOWN14.get_ident());

         System.out.println("terminal class name = " + UNKNOWN15.get_ident());
         System.out.println(" appears inappropriately on rhs ");
         Srstem.out.println();
       };
    }
    });
  }
}}
}
ClassName { {{
  boolean isTerminal(){
    // unchanged: same as in question 1
  }     
}}
}

Question 5: Parsing
=====================================================================
1 UNKNOWN 30 points

Consider the following class dictionary Almost-Self:

List(S) ~ {S}.

Main = String.
CGraph = CollectionClassDef <concreteClassDefs> List(ClassDef) EOF .
ClassDef = <lhs> ClassSpec <rhs> Body.
Body = "=" <before> List(Syntax) 
           [<first> OptPart] 
	   Part <parts> List(Part) 
	   [<last> OptPart] 
	   <after> List(Syntax) ".".
Syntax = String.
Part = [Label] ClassSpec.
Label = "<" PartName ">".

ClassSpec = ClassName
  [Params].
Params = "(" List(ClassSpec) ")".
// for formals on lhs, need only List(ClassName)
// Language is more general than needed for the sake of brevity

CollectionClassDef = <lhs> ClassSpec CollectionBody ".".
CollectionBody = "~" "{" ClassName "}".
OptPart = "[" Part "]".

ClassName = Ident.
PartName = Ident.

It is an attempt to write a self-describing class dictionary
using concrete and collection classes only. The attempt did not
quite succeed.
If we use the above class dictionary as both program.cd
and program.input
and run demeterj, we get:

Exception in thread "main" ParseException: Encountered "Part" at line 8, column 12.
Was expecting one of:
    "." ...
        <STRING_LITERAL> ...

Line 8 is:

Part <parts> List(Part)


Show the minimal number of changes to program.input,
which is a copy of program.cd, that are needed to make
it a syntactically correct input.

Note that you change program.input after copying it from program.cd.
program.cd is not changed.

Put your answer into UNKNOWN1.

Question 6: Class dictionary Design
=========================================
5 UNKNOWs 3 points each = 15 points

Consider the following input examples:

  ( 
    (datatype Container 
      (a_Container (contents ItemList)
                   (capacity Number)
		   (total_weight Number)))
    (datatype Item
      (Cont (c Container))
      (Simple (name String) (weight Weight)))

    (datatype Weight
      (a_Weight (v Number)))

    (datatype ItemList
      (Empty)
      (NonEmpty (first Item) (rest ItemList))))


  (
    (datatype H (aH (f F)))
    (datatype F 
      (Hid_A (e E) (g G))
      (Hid_B (e E) (g G))
      (Hid_C (g G))
    )
    (datatype E 
      (aE))
    (datatype G 
      (aG))
  )
  ( (datatype H))

Develop an object-oriented and language design in the form of a class dictionary.


Program = L(CD) EOF.

CD = UNKNOWN1(DD).
DD = "UNKNOWN2" TypeName L(Alternative) "UNKNOWN3".
Alternative = "(" AlternativeName UNKNOWN4 ")".
TypedField = UNKNOWN5.
FieldName = Ident.
TypeName = Ident.
AlternativeName = Ident.

L(S) ~ {S}.
PL(S) ~ "(" {S} ")".

Make your class dictionary LL(1), non-left-recursive, inductive
and follow the terminal buffer rule (TBR).


Question 7:
=================================================

In developing an Eclipse plugin, what are the steps to add a button in the
toolbar of the Eclipse workbench? Some action will be executed after this button
is clicked.

Please describe concisely what you need to add.



Question 8:
=================================================

What is a growth plan for a software development project?

Give a brief one paragraph description.