Final Exam CSU 670 Fall 2004
Karl Lieberherr
===================================================

Question 1:
===========
60 + 20 + 15 + 20 + 21 + 10 = 146

Consider the following program
(program.cd and program.beh file) and the input and
output.

Find all UNKNOWNs:

Find the UNKNOWNs in program output (you must understand
the program to do this). I followed the rule:
1 UNKNOWN per line for this part of question 1,
except for UNKNOWN18 and UNKNOWN25.
UNKNOWN 6 - 25: 3 points each: 60

Find the UNKNOWNs in program (for ClassName printing).
You basically write a program.
UNKNOWN 1 - 2: 10 points each: 20

Print list of classes involved in the traversal
in alphabetical order. (Basically the set of classes
that your project would highlight.)
UNKNOWN 3: 15 points

Find UNKNOWNs in the program to change the Exps-object.
You basically write a program.
UNKNOWN 4 - 5: 10 points each: 20

Find UNKNOWNs in the displayed object 
(1 point per UNKNOWN). (This is easy: parsing skill).
UNKNOWN 26 - 46: 1 point per UNKNOWN: 21 points

The final task is to improve the class dictionary
Exps.
Eliminate the duplication in classes
Forward , Backward , Later , UpOverDown. 
Put your answer into
UNKNOWN 47: 10 points. 

Here is the class dictionary Exps:
======================================================

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

Exps = 
  <exps> CommaList(Exp) 
  [*l "equations" <eqs> CommaList(Equation)].
Exp : Simple | Compound | QuantifierCompound.
Simple : Forward | Backward | 
	 Sequential | Later | UpOverDown .
Forward = 
  "->" <source> ClassName 
  ["edge" EdgeName] [<steps> Steps] 
  <target> ClassName.
Backward = 
  "<-" <source> ClassName 
  ["edge" EdgeName] [<steps> Steps] 
  <target> ClassName.
Sequential = "seq" <source> ClassName CommaList(ClassName).
Later = 
  "->X<-" <source> ClassName 
  ["edge" EdgeName] [<steps> Steps] 
  <target> ClassName.
UpOverDown = 
  "=>X<=" <source> ClassName 
  ["edge" EdgeName] [<steps> Steps] 
  <target> ClassName.
Exists = "exists" CommaList(ClassName) *l Exp.

Steps: Unlimited | Limited.
// if steps is absent, the default meaning is unlimited
Unlimited = "*".
Limited = <i> Integer.

Compound = Op <args> CommaList(Exp).
Op : Join | Union.
Join = "join".
Union = "union".

QuantifierCompound : Exists.

Equation = *l <left> Exp "=" *l <right> Exp.
ClassName = Ident.
EdgeName = Ident.

CommaList(S) ~ "(" *l + S {"," *l S *s} - *l ")" .

Main = <s> String.


Program input:
========================================

(join (-> A 3 B, -> B 2 C)
,
exists (X) join (-> A X, <- X B) 
// B before A one hill
,
->X<- A * B // B before A, several hills
,
=>X<= A B // up, over and down: class graph: 
	  // special kind of meta graph 
,
seq A (B, C)
,
// reachability formula "from A to B", B concrete
exists (R1) join ( =>X<= A edge e R1, =>X<= R1 B)
)
equations (
-> A B = =>X<= A B // if B is concrete
,
seq A (Q, C) = join( -> A Q, ->X<- Q C)
)

Program:
========================================

Main {
{{
  static ClassGraph cg;
  public static void main(String args[]) throws Exception {
    Exps es = Exps.parse(System.in);
    ClassGraph g = new ClassGraph(true,false);
    cg = new ClassGraph(true, false);
    cg = new ClassGraph(cg,
	    "from Exps bypassing -> *,tail,* to *");
    cg.traverse(es,"from Exps to Simple", new Visitor() {
      public void start() 
	{System.out.println("Testing the evaluator");};
      public void before(Exp host){
	host.print();
        System.out.println(" new Exp ===================== ");
	List l = host.eval();
        for(Iterator i = l.iterator(); i.hasNext();) {
          System.out.print(" ClassName ");
          ((ClassName)i.next()).print();
          System.out.println();
	};
      }
      public void before(Equation host){
        System.out.println(" start of Equation-object +++++++++++++ ");
      } ;});

    ///////////////////////////////////////////////////
    // print all ClassName-objects that are contained in
    // Sequential-objects that are contained in Exps-object
    // See the output for an example how the output should be printed.
    ///////////////////////////////////////////////////

    cg.traverse(es,UNKNOWN1, 
    UNKNOWN2
    );
    TraversalGraph tg = 
      new TraversalGraph("from Exps via Sequential to ClassName", cg);
    System.out.println("TraversalGraph");
    System.out.println();

    // Put into UNKNOWN3 a sorted list of all classes 
    // touched by the traversal

    System.out.println(tg);

    // The purpose of the following traversal is
    // to modify the "steps" data member of 
    // Forward- and Backward-objects using the rule:
    // if steps is null then set steps to an Unlimited-object.
    // See the output for an example

    cg.traverse(es, "UNKNOWN4", 
    UNKNOWN5
    );
    System.out.println(" modified Exps-object ");
    es.print();
    System.out.println();
    System.out.println(" displayed object ");
    es.display();
    System.out.println(" done ");
  }
}}
}

ClassName {
  void print() to * (PrintVisitor);
}

Exp {
  void print() to * (PrintVisitor);
}

Exps {
  void print() to * (PrintVisitor);
  void display() to * (DisplayVisitor);
}

Exp {
{{
  abstract List eval();
}}
}

Simple {
{{
  abstract List eval();
}}
}

Forward {
{{
  List eval(){ ArrayList t = new ArrayList();
    t.add(source); return t;
  };
}}
}

Backward {
{{
  List eval(){ ArrayList t = new ArrayList();
    t.add(source); t.add(target); return t;
  };
}}
}

Sequential {
{{
  List eval(){ return new ArrayList();};
}}
}

Later {
{{
  List eval(){ ArrayList t = new ArrayList();
    t.add(source); t.add(target); return t;
  };
}}
}

UpOverDown {
{{
  List eval(){ ArrayList t = new ArrayList();
    t.add(target); return t;
  };
}}
}

Exists {
{{
  List eval(){ return new ArrayList();};
}}
}


Op {
{{
  abstract List apply(List t);
}}
}

Union {
{{
  List apply(List args){
    List r = new ArrayList();
    for(Iterator i = args.iterator(); i.hasNext();)
      r.addAll((List)i.next());
      return r;
  }
}}
}

Join {
{{
  List apply(List args){
    List r = new ArrayList();
    for(Iterator i = args.iterator(); i.hasNext();)
      r.addAll((List)i.next());
      return r;
  }
}}
}


Compound {
{{
  List eval(){
	List t = new ArrayList();
	for(Enumeration e = args.elements();e.hasMoreElements();)
  	  t.add(((Exp)e.nextElement()).eval());
        return op.apply(t);
  }
}}
}

Program output:
========================================

Reading project file program.prj...
Running the test...
Testing the evaluator
join(
	->A 3 B,
	->B 2 C 
) new Exp ===================== 
 UNKNOWN6 
 UNKNOWN7
->A 3 B new Exp ===================== 
 UNKNOWN8
->B 2 C new Exp ===================== 
 UNKNOWN9 
exists(
	X
)
join(
	->A X,
	<-X B 
) new Exp ===================== 
join(
	->A X,
	<-X B 
) new Exp ===================== 
 UNKNOWN10
 UNKNOWN11 
 UNKNOWN12 
->A X new Exp ===================== 
 UNKNOWN13
<-X B new Exp ===================== 
 UNKNOWN14
 UNKNOWN15
->X<-A*B new Exp ===================== 
 UNKNOWN16
 UNKNOWN17
=>X<=A B new Exp ===================== 
 ClassName B
seq A(
	B,
	C 
) new Exp ===================== 
UNKNOWN18
) new Exp ===================== 
join(
	=>X<=A edge e R1,
	=>X<=R1 B 
) new Exp ===================== 
 UNKNOWN19
 UNKNOWN20
=>X<=A edge e R1 new Exp ===================== 
 UNKNOWN21
=>X<=R1 B new Exp ===================== 
 UNKNOWN22 
 start of Equation-object +++++++++++++ 
->A B new Exp ===================== 
 UNKNOWN23 
=>X<=A B new Exp ===================== 
 UNKNOWN24
 start of Equation-object +++++++++++++ 
UNKNOWN25
) new Exp ===================== 
join(
	->A Q,
	->X<-Q C 
) new Exp ===================== 
 ClassName A
 ClassName Q
 ClassName C
->A Q new Exp ===================== 
 ClassName A
->X<-Q C new Exp ===================== 
 ClassName Q
 ClassName C
start with ClassName printing
A
B
C
A
Q
C
done with ClassName printing
TraversalGraph

UNKNOWN3 (not the entire TraversalGraph, only the classes
sorted alphabetically)

 modified Exps-object 
(
	join(
		->A 3 B,
		->B 2 C 
	),
	exists(
		X
	)
	join(
		->A*X,
		<-X*B 
	),
	->X<-A*B,
	=>X<=A B,
	seq A(
		B,
		C 
	),
	exists(
		R1
	)
	join(
		=>X<=A edge e R1,
		=>X<=R1 B 
	)     
)
equations(
	
	->A*B=
	=>X<=A B,
	
	seq A(
		Q,
		C 
	)=
	join(
		->A*Q,
		->X<-Q C 
	) 
)
 displayed object 
: Exps  (
 <exps> : UNKNOWN26  {
  <first> : Nonempty_Exp_CommaList  (
   <it> : UNKNOWN27  (
    <op> : UNKNOWN28  ( )
    <args> : UNKNOWN29  {
     <first> : Nonempty_Exp_CommaList  (
      <it> : UNKNOWN30  (
       <source> : UNKNOWN31  (
        <ident>  : Ident "UNKNOWN32" )
       <steps> : UNKNOWN33  (
        <i>  : Integer "UNKNOWN34" )
       <target> : UNKNOWN35  (
        <ident>  : Ident "UNKNOWN36" ) )
     <next> : Nonempty_Exp_CommaList  (
      <it> : Forward  (
       <source> : UNKNOWN37  (
        <ident>  : Ident "UNKNOWN38" )
       <steps> : Limited  (
        <i>  : Integer "UNKNOWN39" )
       <target> : ClassName  (
        <ident>  : Ident "UNKNOWN40" ) ) ) ) } )
  <next> : Nonempty_Exp_CommaList  (
   <it> : UNKNOWN41  (
    <classname_commalist> : ClassName_CommaList  {
     <first> : Nonempty_ClassName_CommaList  (
      <it> : ClassName  (
       <ident>  : Ident "UNKNOWN42" ) ) }
    <exp> : Compound  (
     <op> : UNKNOWN43  ( )
     <args> : Exp_CommaList  {
      <first> : Nonempty_Exp_CommaList  (
       <it> : UNKNOWN44  (
        <source> : ClassName  (
         <ident>  : Ident "UNKNOWN45" )
        <steps> : Unlimited  ( )
        <target> : ClassName  (
         <ident>  : Ident "UNKNOWN46" ) )
etc.


Question 2: Class Dictionary Design
===================================

UNKNOWNS 1 -  25: 1 point each:  25
UNKNOWNS 26 - 29: 4 points each: 16
                                 41 total
Consider the following class dictionary "Documents"
with UNKNOWNs and an input that is syntactically correct.
Find the UNKNOWNs in the class dictionary.

Documents = List(Document) EOF.
Document = UNKNOWN1 "UNKNOWN2" <cm> Comment UNKNOWN3 "UNKNOWN4" <pg> Pages 
           ["UNKNOWN5" <opt> OptParms] .
Pages UNKNOWN6.
OptParms = ["UNKNOWN7" <title> TL] ["UNKNOWN8" <vers> Vers] 
           ["UNKNOWN9" <cr> CR] ["UNKNOWN10" <date> DT] ["UNKNOWN11" <bb> BB] 
           ["*postfile*" <pfile> PFILE] ["*plane-modes*" <pl> Planes]
           ["*no-prolog*" <nopro> NOPRO]  .
Vers = <v> Number.
CR = <creator> String.
DT = <date> String.
PFILE = <pfilename> String.
TL = <tl> String.
BB = UNKNOWN12.
Page = "UNKNOWN13" <pa> Page_attributes <di> Displayable_items.
Displayable_items ~ {Displayable_item}.
Displayable_item : Text2 | Rules | Graphics | Patterns. 
Text2 = "*text*" <ti> Text_slug ["*pl*" <plane> Number].
Rules = "UNKNOWN14" <ri> Rule_item ["*pl*" <plane> Number].
Graphics = "*graphic*" <gi> Graphic_item ["*pl*" <plane> Number].
Patterns = "*pattern*" <pat> Pattern_item ["*pl*" <plane> Number].
Text_slug = [";;" <cm> Comment]  <characters> String <pos> Position
            ["*attributes*" <ta> Text_attributes] .
Text_attributes ~ {Text_attribute}.
Text_attribute : Pointsize | Typeface | Angle | UNKNOWN15 | Color |
                  Kern | Reverse_video.
Rule_item =  ["UNKNOWN16" <cm> Comment] 
  <width> Number <pos1> Position <pos2> Position
            [<tint> Tint] [ <color> Color]
            ["UNKNOWN17" <dash> Number].
Graphic_item =  [";;" <cm> Comment] <width> Number 
		<depth> Number <pos> Position
               <name> String ["*scx*" <scx> Number] 
	       ["*scy*" <scy> Number] 
               [ <angle> Angle].
Pattern_item : Circle_Pattern | Square_Pattern.
Circle_Pattern = "*circle*" <patnum> Number <linewidth> Number 
                <pos> Position <radius> Number.
Square_Pattern = "*square*" <patnum> Number <leftlowcorner> Position 
                 <height> Number <width> Number.
Page_attributes = "UNKNOWN18" <width> UNKNOWN19 <depth> UNKNOWN20
                  [ <color> Color] ["*tint*" <tint> Tint]
                  ["UNKNOWN21" <angle> Number].
Position = <xpos> Number <ypos> Number.
Pointsize = "UNKNOWN22" <p> Number.
Typeface = "UNKNOWN23" <tface> Tface.  
Tface : Tnum | Tstring.
Tnum = <tnum> Number.
Tstring = <tstring> String.
Angle = "*angle*" <a> Number.
Tint = "*tint*" <tn> Number.
Color = "UNKNOWN24" <c1> Number <c2> Number <c3> Number.
Kern = "*kern*" <k> Number.
Reverse_video = "UNKNOWN25" <rv> Number.
Comment = <str> String.
Planes = <plmin> Number <plmax> Number.
NOPRO = <np> Number.

List(S) ~ {S}.
Main = <s> String.


Sample input:
==========================================================
*document*
*page*
*page_attributes* 200 300
*text*
  "Hello World" 20 30
*page*
*page_attributes* 200 300
*text*
  "Hello World" 20 30

;; "abc"
*document*
*page*
*page_attributes* 200 300
  *color* 3 5 7 *angle* 30
*text*
  "Hello World" 20 30 
    *attributes*
       *pointsize* 12
*optional* 
  *title* "MyTitle"
  *version* 9
  *creator* "john"
  *date* "3/17/04"
  *bbox* 1 2 3 4

*document*
*page*
*page_attributes* 200 300
*text* ;; "xyz"
  "Hello World" 20 30 
    *attributes*
       *pointsize* 12
       *angle* 90
    *pl* 6

*document*
*page*
*page_attributes* 200 300
*text*
  "Hello World" 20 30 
    *attributes*
       *pointsize* 12
       *angle* 90
       *tint* 7

*document*
*page*
*page_attributes* 200 300
*text*
  "Hello World" 20 30 
    *attributes*
       *pointsize* 12
       *angle* 90
       *tint* 7
       *color* 220 100 90
*rule*
  ;; "xyz" 3 400 500 600 700 
  *dash* 7
*document*
*page*
*page_attributes* 200 300
*text*
  "Hello World" 20 30 
    *attributes*
       *pointsize* 12
       *angle* 90
       *tint* 7
       *color* 220 100 90
       *kern* 2

*document*
*page*
*page_attributes* 200 300
*text*
  "Hello World" 20 30 
    *attributes*
       *pointsize* 12
       *angle* 90
       *tint* 7
       *color* 220 100 90
       *kern* 2
       *rv* 8 
       *typeface* "Daves-Bold-Italic" 

The class dictionary "Documents" violates the Terminal Buffer rule.
Find three violations of the Terminal Buffer rule and 
put the violating class definitions
into UNKNOWN26.

The class dictionary contains duplication that should be eliminated.
Consider the classes Text2, Rules, Graphics, Patterns.
How can you improve them?
Put your answer into UNKNOWN27.

Consider the classes:
Document, Text_slug, Rule_item, Graphic_item 
that all refer to a comment.
Is there duplication that can be removed?
Put your answer into UNKNOWN28.

The following input contains a syntactic error related to 
class Tint:

*document*
*page*
*page_attributes*  500 500 *color* 3 *tint* 4 *angle* 90
*text* "Hello World" 20 30 
  *attributes* *tint* 12 *kern* 15 
    *typeface* "DaveBold" *angle* 30 *tint* 5
*graphic* 10 20 30 40 "davesgraphic"

Where is the first syntactic error?
Put the first wrong token into UNKNOWN29.