Question 1:
===========

Consider the following program and the input and
output.

Find the UNKNOWNs in program output (you must understand
the program to do this).

Find the UNKNOWNs in program (for ClassName printing).
You basically write a program.

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

Find UNKNOWNs in the program to change the Exps-object.
You basically write a program.

Find UNKNOWNs in the displayed object 
(1 point per UNKNOWN, 10 UNKNOWNs). (This is easy).

The final task is to improve the class dictionary.
Eliminate the duplication.

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.
    ///////////////////////////////////////////////////

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

    // Put into UNKNOWN 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, "UNKNOWN", 
    UNKNOWN
    );
    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 ===================== 
 UNKNOWN 
 UNKNOWN
->A 3 B new Exp ===================== 
 UNKNOWN
->B 2 C new Exp ===================== 
 UNKNOWN 
exists(
	X
)
join(
	->A X,
	<-X B 
) new Exp ===================== 
join(
	->A X,
	<-X B 
) new Exp ===================== 
 UNKNOWN
 UNKNOWN 
 UNKNOWN 
->A X new Exp ===================== 
 UNKNOWN
<-X B new Exp ===================== 
 UNKNOWN
 UNKNOWN
->X<-A*B new Exp ===================== 
 UNKNOWN
 UNKNOWN
=>X<=A B new Exp ===================== 
 ClassName B
seq A(
	B,
	C 
) new Exp ===================== 
UNKNOWN
) new Exp ===================== 
join(
	=>X<=A edge e R1,
	=>X<=R1 B 
) new Exp ===================== 
 UNKNOWN
 UNKNOWN
=>X<=A edge e R1 new Exp ===================== 
 UNKNOWN
=>X<=R1 B new Exp ===================== 
 UNKNOWN 
 start of Equation-object +++++++++++++ 
->A B new Exp ===================== 
 UNKNOWN 
=>X<=A B new Exp ===================== 
 UNKNOWN
 start of Equation-object +++++++++++++ 
seq A(
	Q,
	C 
) 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

UNKNOWN
 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> : Exp_CommaList  {
  <first> : Nonempty_Exp_CommaList  (
   <it> : Compound  (
    <op> : Join  ( )
    <args> : Exp_CommaList  {
     <first> : Nonempty_Exp_CommaList  (
      <it> : Forward  (
       <source> : ClassName  (
        <ident>  : Ident "A" )
       <steps> : Limited  (
        <i>  : Integer "3" )
       <target> : ClassName  (
        <ident>  : Ident "B" ) )
     <next> : Nonempty_Exp_CommaList  (
      <it> : Forward  (
       <source> : ClassName  (
        <ident>  : Ident "B" )
       <steps> : Limited  (
        <i>  : Integer "2" )
       <target> : ClassName  (
        <ident>  : Ident "C" ) ) ) ) } )
  <next> : Nonempty_Exp_CommaList  (
   <it> : Exists  (
    <classname_commalist> : ClassName_CommaList  {
     <first> : Nonempty_ClassName_CommaList  (
      <it> : ClassName  (
       <ident>  : Ident "X" ) ) }
    <exp> : Compound  (
     <op> : Join  ( )
     <args> : Exp_CommaList  {
      <first> : Nonempty_Exp_CommaList  (
       <it> : Forward  (
        <source> : ClassName  (
         <ident>  : Ident "A" )
        <steps> : Unlimited  ( )
        <target> : ClassName  (
         <ident>  : Ident "X" ) )
etc.