CSU 670 Midterm
Februray 23, 2004					Karl Lieberherr

Open Books and Open Notes

Question 1:
=========================================================
10 UNKNOWNs, 4 points each: 40 points
Writing a class dictionary

Consider the following input:

add to part before A.x: "begin"
add to class before A: "begin"
add to part after  B.y: "end"
add to collection S1 before { : "("
add to collection S1 after { : ","
add to class after X: "end"
add to collection S2 after { : ","
add to part after  C.y: "="
add to collection S3 before } : ":"
add to collection S1 after } : ")"
add to class after A: "end"
add to part after  D.y: ":"
add to collection S4 after { : "("

Write a class dictionary that accepts this input and all
"similar" inputs.

Find the UNKNOWNs in the following class dictionary:
Note that an UNKNOWN may be NOTHING.

SyntaxEnhancement = UNKNOWN1 EOF.
Enhancement = UNKNOWN2 EnhancementBody.
EnhancementBody : UNKNOWN3 .
PartCoordinate = "part" UNKNOWN4 ClassName UNKNOWN5 PartName UNKNOWN6.
ClassBody = "class" UNKNOWN7 ClassName UNKNOWN8.
CollectionCoordinate = "collection" ClassName UNKNOWN9.
CurlyBracket : Left | Right.
Left = "{".
Right = "}".

Where : Before | After.
Before = "before".
After = "after".

List(S) ~ UNKNOWN10.

PartName = Ident.
ClassName = Ident.
SyntaxToken = String.


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

Consider the following class dictionary CD1:

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

Example = CList(Tree) EOF.
Tree = Ident [<subtrees> Tree_List].
Tree_List ~ "(" Tree {Tree} ")".

CList(S) ~ "{" S {"," S} "}".
Main = .

Write a program using the DJ library that prints 
all Ident-objects of leafs, i.e., trees that don't have subtrees.

For example, for the input, 

{
abc ( mnl abc def (ghi))
,
ghi
}

the program produces:

mnl
abc
ghi
ghi

Find the UNKNOWNs in the program below:

Main {
  {{
  public static ClassGraph cg;
  public static void main(String args[]) throws Exception {
    Example m = Example.parse(System.in);
    cg = new ClassGraph(true, false);
    m.printLeaves();
    System.out.println();
  }
  }}
}

Example {
{{
  void printLeaves() {
    UNKNOWN1.UNKNOWN2(UNKNOWN3,UNKNOWN4, UNKNOWN5() {
      void before(UNKNOWN6 host){
        if (UNKNOWN7 == null) {
          System.out.println(host.get_ident());
        }
      }
    });
  }
}}
}

Question 3:
=============================================================
17 UNKNOWNs
UNKNOWNs 1 - 16: 1 points each : 16 points
UNKNOWN17:       20 points
				 36 points total

Consider the following class dictionary CD2:

import edu.neu.ccs.demeter.dj.*;
Example = CList(Tree) EOF.
Tree : Leaf | Inner common Ident.
Leaf = "leaf".
Inner = <subtrees> Tree_List.
Tree_List ~ "(" Tree {Tree} ")".

CList(S) ~ "{" S {"," S} "}".
Main = .


Consider the following input:

{
( ( leaf mnl leaf abc ( (leaf ghi) def) abc ) def ) xyz
,
leaf ghi
}

Consider the corresponding object:

: Example  (
 <tree_clist> : Tree_CList  {
  <first> : Nonempty_Tree_CList  (
   <it> : UNKNOWN1  (
    <subtrees> : Tree_List  {
     <first> : Nonempty_Tree_List  (
      <it> : UNKNOWN2  (
       <subtrees> : Tree_List  {
        <first> : Nonempty_Tree_List  (
         <it> : UNKNOWN3  (
	  <ident>  : Ident "UNKNOWN4" )
         <next> : Nonempty_Tree_List  (
	  <it> : UNKNOWN5  (
	   <ident>  : Ident "UNKNOWN6" )
	  <next> : Nonempty_Tree_List  (
           <it> : UNKNOWN7  (
            <subtrees> : Tree_List  {
             <first> : Nonempty_Tree_List  (
              <it> : UNKNOWN8  (
               <subtrees> : Tree_List  {
                <first> : Nonempty_Tree_List  (
	         <it> : UNKNOWN9  (
                  <ident>  : Ident "UNKNOWN10" ) ) }
               <ident>  : Ident "UNKNOWN11" ) ) }
           <ident>  : Ident "UNKNOWN12" ) ) ) ) }
        <ident>  : Ident "UNKNOWN13" ) ) }
     <ident>  : Ident "UNKNOWN14" )
  <next> : Nonempty_Tree_CList  (
   <it> : UNKNOWN15  (
    <ident>  : Ident "UNKNOWN16" ) ) ) } )

Write a program that prints the Ident-objects of all the leaves. For the 
class dictionary and input above it should print:

mnl
abc
ghi
ghi

Find the UNKOWN below.

Main {
  {{
  public static ClassGraph cg;
  public static void main(String args[]) throws Exception {
    Example m = Example.parse(System.in);
//    m.display();
    System.out.println();
    cg = new ClassGraph(true, false);
    m.printLeaves();
    System.out.println();
  }
  }}
}

Example {
  void display() to * (DisplayVisitor);
{{
  void printLeaves() {
    UNKNOWN17
  }
}}
}

Question 4:
============================================================
1 UNKNOWN 20 points

Consider again the class dictionary CD1  used in earlier question:

Example = CList(Tree) EOF.
Tree = Ident [<subtrees> Tree_List].
Tree_List ~ "(" Tree {Tree} ")".

CList(S) ~ "{" S {"," S} "}".
Main = .

and the corresponding input sentence:

{
abc ( mnl abc def (ghi))
,
ghi
}

Now consider again the class dictionary CD2 used in earlier question:

Example = CList(Tree) EOF.
Tree : Leaf | Inner common Ident.
Leaf = "leaf".
Inner = <subtrees> Tree_List.
Tree_List ~ "(" Tree {Tree} ")".

CList(S) ~ "{" S {"," S} "}".
Main = .

Manually translate the above input sentence
to the language of the second class dictionary CD2.

Put your answer into UNKNOWN1.