CSU 670
Fall 2003			Karl Lieberherr

MIDTERM

Question 1:
============================================================
10 UNKNOWNs, 3 points each.
30 points

Consider the following class dictionary called SELF-DESCRIBING.
It is used in several questions.

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.
Syntax_vertex = <string> String.
Labeled_vertex = "<" <label_name> Ident ">" 
                     <class_name> Vertex.
Adj_list: Cd_graph | Empty_cd_graph .
Any_vertex_list: Nany_vertex_list | Empty.
Nany_vertex_list = 
  <first> Any_vertex <rest> Any_vertex_list.
Empty = .
Empty_cd_graph = .
Vertex = <name> Ident.

Main = .


Write a class dictionary for Trip objects.
Your class dictionary has to be legal with respect to 
the class dictionary SELF-DESCRIBING as well as
the class dictionary of class dictionaries for Demeter. 
Your class dictionary has to be non-ambiguous.
The structure of trip objects is given by:
Each trip object contains a list of day trip objects.
There are three kinds of day trip objects:
luxury, normal and economy. All three kinds of day trip objects
have a day name and  a list of locations.

A sample sentence of the trip language is:

trip
day 1 luxury "Amsterdam" "Rotterdam" -
day 2 normal "Bonn" "Mainz" -
day 3 economy "Basel" "Zurich" -
end


Find the UNKNOWNs below.

Trip UNKNOWN0.
DayTripList UNKNOWN1.
EDayTripList UNKNOWN2.
NDayTripList UNKNOWN3.
DayTrip UNKNOWN4.
LocationList UNKNOWN5.
ELocationList UNKNOWN6.
NLocationList UNKNOWN7.
DTKind UNKNOWN8.
UNKNOWN9.
Luxury = "luxury".
Normal = "normal".
Economy = "economy".
Location = <s> String.
Day = <n> Integer.

Main = .

Question 2:
=============================================================
UNKNOWNs 0-3: 3 points each; UNKNOWN 4: 20 points: 32 points

Write a program that finds all tokens in a 
class dictionary that satisfies class dictionary 
SELF-DESCRIBING.

For example: For the class dictionary SELF-DESCRIBING (in the *.input file):

// class dictionary
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.
Syntax_vertex = <string> String.
Labeled_vertex = "<" <label_name> Ident ">" 
                     <class_name> Vertex.
Adj_list: Cd_graph | Empty_cd_graph .
Any_vertex_list: Nany_vertex_list | Empty.
Nany_vertex_list = 
  <first> Any_vertex <rest> Any_vertex_list.
Empty = .
Empty_cd_graph = .
Vertex = <name> Ident.

Main = .
// end class dictionary

the output should be:

 .
 =
 :
 |
 <
 >

Find the UNKNOWNs below:

Program:

Main {
  {{ 
  static Cd_graph graph; 
  static UNKNOWN0 x; 
  static public void main(String args[]) throws Exception {
    x = new UNKNOWN1(UNKNOWN2, UNKNOWN3);
    graph = Cd_graph.parse(System.in);
    graph.printSyntax();
  }
  }}
}

Cd_graph {
  {{
  void printSyntax() {
    UNKNOWN4
  }
  }}
}

Question 3:
==============================================================
1 UNKNOWN: 30 points

Consider the following sentence:

basket
  (a 
    (o 
       ()) 
	  )

and the output when the entire basket object is displayed
using the DisplayVisitor:

: Basket  (
	<fl> : NFruitList  (
		<first> : Apple  ( )
		<rest> : NFruitList  (
			<first> : Orange  ( )
			<rest> : EFruitList  ( ) ) ) ) 

Find the class dictionary by 
giving the UNKNOWN below.


Basket = "basket" <fl> FruitList.
UNKNOWN (consisting of several class definitions)


Question 4:
===============================================================
7 UNKNOWNs, 3 points each: 21 points

Consider the class dictionary SELF-DESCRIBING
and the following method 

Cd_graph {
  void display() bypassing -> *,tail,* to * (DisplayVisitor);
  {{
  void test(){
    TraversalGraph tg = new TraversalGraph(
      "from Cd_graph bypassing -> *,rest,* to Adj", Main.cg);
    System.out.println(tg);
    tg. traverse(this, new Visitor() {
	void before(Adj host){ System.out.println(host); }
    });
  }
  }}
}

called on the object corresponding to the sentence:

// class dictionary
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.
Syntax_vertex = <string> String.
Labeled_vertex = "<" <label_name> Ident ">" 
                     <class_name> Vertex.
Adj_list: Cd_graph | Empty_cd_graph .
Any_vertex_list: Nany_vertex_list | Empty.
Nany_vertex_list = 
  <first> Any_vertex <rest> Any_vertex_list.
Empty = .
Empty_cd_graph = .
Vertex = <name> Ident.

///////////////
CountingVisitor = <total> int.
///////////////

Main = .

The output produced by test() is:

Start set: [Cd_graph: {0}]
Copy 0:
 Nodes:
 UNKNOWN0
 UNKNOWN1
 java.lang.Object
 java.io.Serializable
 UNKNOWN2
 Edges:
 -> UNKNOWN3,UNKNOWN4,UNKNOWN5
 Edges to other copies:
Finish set: [Adj: {0}]
UNKNOWN6@910040


Find the UNKNOWNs.