Midterm COM 3360
Fall 1999, November 4                  Karl Lieberherr
===============

Open books and open notes

Question 1:
20 points

Consider the class dictionary:

Directory = <entries> List(DirectoryEntry).
DirectoryEntry = INode FileName.
INode = Mode Size.
Mode : RegularFile | Directory.
Size = <i> int.
RegularFile = "regular" <blocks> List(Block).
Block = Data.
Data = "data".
FileName = Ident.
List(S) ~ "(" {S} ")".       

Question 1.1:
10 points

Is it LL(1)? Explain.

Question 1.2:
10 points

Delete "regular" from RegularFile. Is the modified class dictionary
still LL(1)?
Explain.


Question 2:
20 points.

Abstracting a class graph from constructor calls.

Consider the constructor calls below. Write one class dictionary
that could have been used to define the classes involved
in the constructor calls.

You will have to invent certain names. Names you invent (as opposed to the ones
that are given by the constructor calls below) should terminate with _.

Vertex adj1_vertex = new Vertex(new Ident("Cd_graph"));
Vertex adj1_cls1 = new Vertex(new Ident("Adj"));
Vertex adj1_cls2 = new Vertex(new Ident("Adj_list"));
Nany_vertex_list adj1_nvl2 = 
  new Nany_vertex_list(new Labeled_vertex(
  new Ident("rest"),adj1_cls2),new Empty());
Nany_vertex_list adj1_nvl1 = 
  new Nany_vertex_list(new Labeled_vertex(
    new Ident("first"),adj1_cls1), adj1_nvl2);
Neighbors adj1_neighbors = new Construct( adj1_nvl1);
Adj adj1 = new Adj(adj1_vertex, adj1_neighbors);

Vertex adj2_vertex = new Vertex(new Ident("Adj"));
Vertex adj2_cls1 = new Vertex(new Ident("Vertex"));
Vertex adj2_cls2 = new Vertex(new Ident("Neighbors"));

Nany_vertex_list adj2_nvl3 = new Nany_vertex_list(new Syntax_vertex("."),
new Empty());	
				
Nany_vertex_list adj2_nvl2 = 
  new Nany_vertex_list(new Labeled_vertex(
    new Ident("rest"), adj2_cls2), adj2_nvl3);	
Nany_vertex_list adj2_nvl1 = 
  new Nany_vertex_list(new Labeled_vertex(
    new Ident("first"), adj2_cls1), adj2_nvl2);
Neighbors adj2_neighbors = new Construct( adj2_nvl1);

Adj adj2 = new Adj(adj2_vertex, adj2_neighbors);

Vertex adj3_vertex = new Vertex(new Ident("Neighbors"));
Vertex adj3_first = new Vertex(new Ident("Construct"));				
Vertex adj3_second = new Vertex(new Ident("Alternat"));		
Neighbors adj3_neighbors = new  Alternat(adj3_first, adj3_second);
Adj adj3 = new Adj(adj3_vertex, adj3_neighbors);

Vertex adj4_vertex = new Vertex(new Ident("Construct"));
Vertex adj4_cls = new Vertex(new Ident("Any_vertex_list"));		
Nany_vertex_list adj4_nvl2 = 
  new Nany_vertex_list(new Labeled_vertex(
    new Ident("c_ns"), adj4_cls), new Empty());	
Nany_vertex_list adj4_nvl1 = new Nany_vertex_list(new Syntax_vertex("="),
adj4_nvl2);
Neighbors adj4_neighbors = new Construct( adj4_nvl1);
Adj adj4 = new Adj(adj4_vertex, adj4_neighbors);

Vertex adj5_vertex = new Vertex(new Ident("Alternat"));
Vertex adj5_cls = new Vertex(new Ident("Vertex"));		
Nany_vertex_list adj5_nvl4 = 
  new Nany_vertex_list(new Labeled_vertex(new Ident("second"), adj5_cls),
new Empty());	
Nany_vertex_list adj5_nvl3 = 
  new Nany_vertex_list(new Syntax_vertex("|"), adj5_nvl4);
Nany_vertex_list adj5_nvl2 = 
  new Nany_vertex_list(new Labeled_vertex(
    new Ident("first"), adj5_cls), adj5_nvl3);	
Nany_vertex_list adj5_nvl1 = 
  new Nany_vertex_list(new Syntax_vertex(":"), adj5_nvl2);
Neighbors adj5_neighbors = new Construct( adj5_nvl1);
Adj adj5 = new Adj(adj5_vertex, adj5_neighbors);

Vertex adj6_vertex = new Vertex(new Ident("Any_vertex"));
Vertex adj6_first = new Vertex(new Ident("Labeled_vertex"));				
Vertex adj6_second = new Vertex(new Ident("Syntax_vertex"));		
Neighbors adj6_neighbors = new  Alternat(adj6_first, adj6_second);
Adj adj6 = new Adj(adj6_vertex, adj6_neighbors);

Adj_list cd_graph6 = new Cd_graph(adj6, new Empty_cd_graph());
Adj_list cd_graph5 = new Cd_graph(adj5, cd_graph6);
Adj_list cd_graph4 = new Cd_graph(adj4, cd_graph5);
Adj_list cd_graph3 = new Cd_graph(adj3, cd_graph4);
Adj_list cd_graph2 = new Cd_graph(adj2, cd_graph3);
Cd_graph cd_graph =  new Cd_graph(adj1, cd_graph2);


Question 3:
===========
30 points

The program below is a testing program for traversal strategies.
It uses the AP Library but it uses the classes StrategyGraph and ClassGraph 
from DJ. The class graphs and strategy graphs are parsed from strings.

Program MyMain.java:

import EDU.neu.ccs.demeter.aplib.*;
import EDU.neu.ccs.demeter.aplib.sg.*;
import EDU.neu.ccs.demeter.aplib.cd.*;

class MyMain {

//args[0]-ClassGraph  args[1]-StrategyGraph
  public static void main(String[] args) {
    if(args.length<2)
    {
	System.out.println("usage: java MyMain \"ClassGraph\" \"StrategyGraph\"");
	return;
    }

    //print the command
    System.out.println("java MyMain "+"\""+args[0]+"\" "+"\""+args[1]+"\"");
    System.out.println("output:\n");

    ClassGraph cg = ClassGraph.fromString(args[0]);
    StrategyGraph sg = StrategyGraph.fromString(args[1]);
    if (sg == null || cg == null)
    {
	System.out.println("StategyGraph or ClassGraph failed to instantiate");
	return;
    }

System.out.println();
System.out.println("Class Graph");
System.out.println(cg.toString());
System.out.println();
System.out.println("Strategy Graph");
System.out.println(sg.toString());
System.out.println();

// The following name map defines the identity map
    NameMapI m=new NameMapI(){
	public String get(String l){return l;}
    };

    TraversalGraph tg = TraversalGraph.compute(cg,sg,m);
    if (tg != null) {
	System.out.println(tg.toString());
        // cg.printTraversalEdges(tg, ... );
    }
  }
}


Testing script to run the above program multiple times:

#!bin/sh
#sh run_test

cd /proj/adaptive/www/course/exams/m-3360-f99/q3
javac MyMain.java

java MyMain "A=X. X=B C. B:X|E. E=. C=." "from A through B to C"
java MyMain "A=B1 C. B1=B D. B=[B1]. C=D. D=E F1. E=G. F1=F G. F=[F1]. G=." \
  "from A through B through F to G"
java MyMain "A:B. B=C. C=." "from A bypassing ->A,b,B to C"

java MyMain "A=B. B=C. C=B A." "from B to C"
java MyMain "A=B. B=C. C=B." "from A to-stop C"


The testing script produces the following output:

java MyMain "A=X. X=B C. B:X|E. E=. C=." "from A through B to C"
output:


Class Graph
A = <x> X.
X = <b> B <c> C extends B.
B : X | E.
E = extends B.
C = .

Strategy Graph
{
	A -> { B }
	{ B } -> C
} source: A target: C 

Nodes:
X: in copies {0, 1}
C: in copies {1}
B: in copies {0, 1}
A: in copies {0}
Edges:
-> A,x,X: in copies {0}
-> X,c,C: in copies {1}
=> B,X: in copies {0, 1}
-> X,b,B: in copies {0, 1}, intercopy table {{0, 1}}

java MyMain "A=B1 C. B1=B D. B=[B1]. C=D. D=E F1. E=G. F1=F G. F=[F1]. G=." "from A through B through F to G"
output:


Class Graph
A = <b1> B1 <c> C.
B1 = <b> B <d> D.
B = [ <b1> B1].
C = <d> D.
D = <e> E <f1> F1.
E = <g> G.
F1 = <f> F <g> G.
F = [ <f1> F1].
G = .

Strategy Graph
{
	A -> { B }
	{ B } -> { F }
	{ F } -> G
} source: A target: G 

Nodes:
F1: in copies {1, 2}
B1: in copies {0, 1}
G: in copies {2}
F: in copies {1, 2}
D: in copies {1}
B: in copies {0, 1}
A: in copies {0}
Edges:
-> B,b1,B1: in copies {0, 1}
-> B1,d,D: in copies {1}
-> B1,b,B: in copies {0, 1}, intercopy table {{0, 1}}
-> A,b1,B1: in copies {0}
-> F1,f,F: in copies {1, 2}, intercopy table {{1, 2}}
-> D,f1,F1: in copies {1}
-> F1,g,G: in copies {2}
-> F,f1,F1: in copies {1, 2}

java MyMain "A:B. B=C. C=." "from A bypassing ->A,b,B to C"
output:


Class Graph
A : B.
B = <c> C extends A.
C = .

Strategy Graph
{
	A -> C bypassing -> A, b, B
} source: A target: C 

Nodes:
C: in copies {0}
B: in copies {0}
A: in copies {0}
Edges:
-> B,c,C: in copies {0}
=> A,B: in copies {0}

java MyMain "A=B. B=C. C=B A." "from B to C"
output:


Class Graph
A = <b> B.
B = <c> C.
C = <b> B <a> A.

Strategy Graph
{
	B -> C
} source: B target: C 

Nodes:
C: in copies {0}
B: in copies {0}
A: in copies {0}
Edges:
-> C,b,B: in copies {0}
-> B,c,C: in copies {0}
-> C,a,A: in copies {0}
-> A,b,B: in copies {0}

java MyMain "A=B. B=C. C=B." "from A to-stop C"
output:


Class Graph
A = <b> B.
B = <c> C.
C = <b> B.

Strategy Graph
{
	A -> C bypassing C
} source: A target: C 

Nodes:
C: in copies {0}
B: in copies {0}
A: in copies {0}
Edges:
-> B,c,C: in copies {0}
-> A,b,B: in copies {0}


Answer the following:

Describe a systematic approach on how to translate the traversal
graphs shown here into Java traversal code
and apply your approach to the first two cases:

java MyMain "A=X. X=B C. B:X|E. E=. C=." "from A through B to C"
java MyMain "A=B1 C. B1=B D. B=[B1]. C=D. D=E F1. E=G. F1=F G. F=[F1]. G=." \
  "from A through B through F to G"

In other words, give the detailed traversal code in Java for those two inputs.


Question 4:
=====================
30 points

The following is from 
XML for Java Compatibility API 2.0.15.
http://falconet.inria.fr/~java/classes/xml4j/TXapiDocs/
It is NOT expected that you have seen those pages.

I show you pieces of the documentation and ask
you to interpret it based on your knowledge of traversal/visitor
programming.

Consider the following example of XML4J (XML for Java) code:

----
PrintWriter printWriter = new PrintWriter();
Visitor htmlPrintVisitor = new HTMLPrintVisitor(printWriter);
TreeTraversal treeTraversal = 
  new RecursivePreorderTreeTraversal(htmlPrintVisitor);
treeTraversal.traverse(document);
printWriter.close();

Documentation:
public class RecursivePreorderTreeTraversal
extends TreeTraversal

RecursivePreorderTreeTraversal defines a specific 
document object tree traversal algorithm for use by the
visitor design pattern. This algorithm visits the 
Parent before visiting its children. 

Documentation: 
public class HTMLPrintVisitor
extends ToXMLStringVisitor

HTMLPrintVisitor implements the Visitor interface 
in the visitor design pattern for the purpose of printing in
HTML-like format the various DOM- and XML4J-defined Nodes. 

----

Question 4.1:
15 points
What is your interpretation of the behavior of this code?
Give a brief explanation in English.
Write a DJ program that has a similar behavior.
Assume that you are given HTMLPrintVisitor.

Consider the following documentation of EndTraversalException:

public class EndTraversalException
extends TreeTraversalException

----
XML4J tree traversal exception which signals from a 
Visitor to the tree traversal algorithm that all further
traversal should be ended because the visit 
on the document object hierarchy has been successfully completed.
For example, this exception could be used by 
search Visitors that are looking for the first TXElement Node
which contains certain state data. 
----

Question 4.2:
15 points
How could EndTraversalException be added to DJ?
Give a brief discussion of the interesting issues.