Question 1.1:

Yes, it is LL(1).
There is only one alternation class: Mode.
The first set of RegularFile is "regular".
The first set of Directory is "(".
They are distinct and therefore LL(1) Rule 1 is satisfied.
None of the alternatives may be empty and therefore
LL(1) Rule 2 is satisfied too.

Question 1.2:
No, it is no longer LL(1).
The first set of RegularFile is "(".
The first set of Directory is "(".   
They are not disjoint and therefore LL(1) Rule 1 is violated.

Note that the class dictionary is now even ambiguous because
() can mean a file with no blocks or a directory without entries.

Note that non-ambiguous does not imply LL(1).

Queestion 2:
============

Separating levels of abstraction is the theme here.
You are given an object graph and are asked to
"invent" a corresponding class graph.


The object graph happens to describe a class graph for class graph.
So you have to jugle three levels of abstraction.

Cd_graph = < first > Adj < rest > Adj_list_ .
Adj = < vertex > Vertex < ns > Neighbors  .
Neighbors : Construct | Alternat .
Construct =  < c_ns > Any_vertex_list_ .
Alternat =  < first > Vertex  < second > Vertex .
Any_vertex_ : Labeled_vertex | Syntax_vertex .
Nany_vertex_list = <first> Any_Vertex_ <rest> Any_vertex_list_.
Any_vertex_list_ : Nany_vertex_list | Empty.
Empty = .
Vertex = Ident.
Labeled_vertex = Ident Vertex.
Syntax_vertex = char.
Adj_list_ : Empty_cd_graph |  Cd_graph.
Empty_cd_graph = .
Answers question 3:

Question 3:
===========

Here is a systematic approach:

Translate from A through A1 through A2 through A3 ...
to
{A -> A1 to-stop A1 -> A2 to-stop A2 -> A3 ... }

For each leg l[i] compute the propagation graph p[i] and define
a traversal method t[i] for that traversal graph.
When t[i] enters its target at which it stops, switch to t[i+1].


For 1:

The following is NOT correct:

t0:
  A.x
  X.b t1

t1:
  B
  X.b
    c
  C

translation rule:
tt:
  X.y
defines a traversal tt for class X calling tt for part y
  X.y tt2
defines a traversal tt for class X calling tt2 for part y


This hand-generated traversal is NOT equal to "from A via B to C"?

The above is a summary to:

  class A {
    public void t0( ) {
      x.t0();
    }
  }

  class X {
    void t0(){
      System.out.println(" at X t0");
      b.t1();
    }
    void t1(){
      System.out.println(" at X t1");
      b.t1();
      c.t1();
    }
  }

  class B {
    void t1(){
      System.out.println(" at B t1");
    } 
  }

  class C { 
    void t1(){
       System.out.println(" at C t1");
    } 
  }


The correct answer is:
(Note: Demeter/Java does not handle this correctly
but DJ does)

  class A {
    public void t0( ) {
      x.t0();
    }
  }

  class X {
    void t0(){
      super.t0_bef();
      System.out.println(" at X t0");
      super.t0(); // this is essentially what's missing in the
			// Demeter/Java-generated code
    }
    void t1(){
      super.t1_bef();
      System.out.println(" at X t1");
      b.t1(); 
      c.t1();
    }
  }

  class B {
    void t0_bef() {
      System.out.println(" at B t0");
    }
    void t0() {
      this.t1();
    }
    void t1_bef(){
      System.out.println(" at B t1");
    } 
    void t1() {
      // do nothing; premature termination
      // (to catch t1() on an E-object)
    }
  }

  class C { 
    void t1(){
       System.out.println(" at C t1");
    } 
  }

===============

For 2:

t0:
  A.b1
  B1.b t1

t1: 
  B.if b1
  B1.b
     d
  D.f1
  F1.f t2

t2:
  F.if f1
  F1.f
     g
  G

translation rule:
tt:
  X.y
defines a traversal tt for class X calling tt for part y
  X.y tt2
defines a traversal tt for class X calling tt2 for part y
  X.if y
defines a traversal tt for class X calling tt for part y
but only if part y exists.


Question 4:
===========
4.1:
ClassGraph cd = new ClassGraph();

PrintWriter printWriter = new PrintWriter();
Visitor htmlPrintVisitor = new HTMLPrintVisitor(printWriter);
StrategyGraph sg = new StrategyGraph("from Document to *");
TraversalGraph tg = TraversalGraph.compute(cd,sg);

tg.traverse(document, htmlPrintVisitor);

The default traversal order of DJ happens to be
recursive preorder.
The traversal traverses the Document and prints it in
HTML format.



4.2:
Since DJ is just Java the new exception class can
be subclassed from java.lang.Exception.
The top function that does the traversal
inside DJ should implement a catching block,
destroy the exception and return the result.



From dougo@ccs.neu.edu Mon Nov 15 16:45:33 1999
To: Karl Lieberherr <lieber@ccs.neu.edu>

Answers for 4.1 and 4.2 by Doug Orleans:

only a partial answer was expected to get full credit.

Karl Lieberherr writes:
 > PrintWriter printWriter = new PrintWriter();
 > Visitor htmlPrintVisitor = new HTMLPrintVisitor(printWriter);
 > TreeTraversal treeTraversal = 
 >   new RecursivePreorderTreeTraversal(htmlPrintVisitor);
 > treeTraversal.traverse(document);
 > printWriter.close();

 > What is your interpretation of the behavior of this code?
 > Give a brief explanation in English.

It traverses the tree object representing the XML document, in
depth-first preorder, printing all its elements as HTML (by calling
methods on a HTMLPrintVisitor object as it traverses).

 > Write a DJ program that has a similar behavior.
 > Assume that you are given HTMLPrintVisitor.

  PrintWriter printWriter = new PrintWriter();
  Visitor htmlPrintVisitor = new HTMLPrintVisitor(printWriter);
  TraversalGraph treeTraversal =
    TraversalGraph.compute(new ClassGraph(), new Strategy("from * to *");
  treeTraversal.traverse(document, htmlPrintVisitor);
  printWriter.close();

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

If it extends RuntimeException, you'd simply need to add a

    try {
	...
    } catch (EndTraversalException e) {
    }

block around the body of TraversalGraph.traverse() (as well as fetch()
and gather() and the container adapters).  Also, the code that invokes
visitor methods and catches InvocationTargetException would have to
see if the contained exception were an EndTraversalException and
re-throw it (rather than throw a plain RuntimeException which is what
it does now).

If it is a checked exception, the user's Visitor methods that throw
an EndTraversalException would have to declare it in the method
signature; fortunately this doesn't affect method invocation through
the Java Reflection API, but Demeter/Java would have to declare this
exception in all of its generated traversal methods.

--Doug

Notes:
unchecked exceptions are exceptions of classes
RuntimeException and Error, or subclasses of these exceptions.
checked exceptions must be declared.

public Object invoke(Object onThis, Object[] args)
throws IllegalAccessException, IllegalArgumentException,
InvocationTargetException

InvocationTargetException is thrown by invoke
if the invoked method itself throws an exception.