CSU 670 Midterm
October 29, 2004                                       Karl Lieberherr

Open Books and Open Notes

Question 1:
=============================================================
Class dictionary design
25 UNKNOWNs, 3 points each: 75 points  

Consider the following class dictionary and input.
Find the UNKNOWNs.

// Security Automaton extended for Chinese Wall Policy
// for one subject

ChineseWallPolicyChecker = List(ChineseWallAutomaton) EOF.
ChineseWallAutomaton = "UNKNOWN1" "UNKNOWN2" "UNKNOWN3" AutomatonName 
  "UNKNOWN4" <currentState> State
  UNKNOWN5 "UNKNOWN6" <startState> State UNKNOWN7 
  "UNKNOWN8" <transition> Transition
  "UNKNOWN9" <groups> UNKNOWN10(UNKNOWN11)
  "UNKNOWN12" <citypes> UNKNOWN13(UNKNOWN14)
  "UNKNOWN15" <history> UNKNOWN16(UNKNOWN17).

State = <accesses> List(Group).
Access = ObjektId "group" Group.
Group = GroupName ["citype" CIType].
CIType = CITypeName.

Transition = <newAccess> UNKNOWN18.

ObjektId = Ident.
GroupName = Ident.
CITypeName = Ident.
AutomatonName = Ident.

UNKNOWN19 

///////////////////////////////////////////////////////////////
input:
///////////////////////////////////////////////////////////////

(
Chinese Wall automaton consultant_Mary
currentState
  (Shell)
startState
  ()
transition
  oid_research group Mobil
groups
  (Shell citype Oil Mobil citype Oil UBS citype Bank)
citypes
  (Oil Bank)
history
  (oid1 group Shell oid2 group Shell oid3 group Shell)

UNKNOWN20 consultant_John
currentState
  (Winterthur AllState UBS)
transition
  oid_research group AllState
groups
  (AllState citype Insurance Wintherthur citype Insurance UBS citype Bank)
citypes
  (Insurance Bank Retail WholeSale)
UNKNOWN21
  (oid1 UNKNOWN22 Winterthur oid2 UNKNOWN23 AllState oid3 UNKNOWN24 UBS )

Chinese Wall automaton consultant_Karl
currentState
  (Shell)
transition
  oid_research group Mobil
groups
  (Shell citype Oil Mobil citype Oil UBS citype Bank)
UNKNOWN25
  (Oil Bank)
history
  (oid1 group Shell oid2 group Shell oid3 group Shell)
)


Question 2:
=============================================================
Understanding a program.
6 UNKNOWNs, 10 points each: 60 points.

Consider the following class dictionary XPath1,
behavior file, input and output.
Find the UNKNOWNs in the input/output part.

// Neven-xpath.pdf
import edu.neu.ccs.demeter.dj.*;
import java.util.*;

XPath = List(Exp) EOF.
Exp : Simple | BinaryCompound | UnaryCompound.
Simple : ElementTest | WildCard.
BinaryCompound = "(" BOp <arg1> Exp <arg2> Exp ")".
UnaryCompound = "{-{" UOp <arg1> Exp "}-}".
BOp : Disjunction | Child | Descendant | Filter.
UOp : Chi | Des.
Chi = "/".
Des = "desc".
Disjunction = "|".
Child = "/". 
Descendant = "desc" .
Filter = "filt".
ElementTest = Name.
WildCard = "*".
Name = Ident.

Main = <s> String.
List(S) ~ "(" {S} ")".

CountingVisitor = <c> int  extends Visitor .

Behavior file:
=================================================


Main {
  public static void main(String args[]) throws Exception {{
    XPath m = XPath.parse(System.in);
    // m.display();
    ClassGraph cgfull = new ClassGraph(true, false);
    ClassGraph cg = new ClassGraph(cgfull,
      "from XPath bypassing -> *,tail,* to *");
    Visitor countingVis = new CountingVisitor();

    Integer i1 = (Integer) cg.traverse(m, 
      "from XPath via BinaryCompound to Disjunction",
      countingVis);
    System.out.println(i1.intValue() + " disjunction in binary ");
    System.out.println();

    Integer i2 = (Integer) cg.traverse(m, 
      "from XPath to Disjunction",
      countingVis);
    System.out.println(i2.intValue() + " disjunctions ");
    System.out.println();

    List v;

    v = cg.gather(
      m,
      "from XPath via UnaryCompound to Disjunction");
    System.out.println(v.size() + " list length disjunction in unary ");

    v = cg.gather(
      m,
      "from XPath via BinaryCompound to Chi");
    System.out.println(v.size() + " list length Chi in binary ");

    v = cg.gather(
      m,
      "from XPath bypassing BinaryCompound to UnaryCompound");
    System.out.println(v.size() + " list length Unary bypassing Binary");
    System.out.println("done");
  }}
}

CountingVisitor {
  {{
  public void start() {c = 0; }
  // public void before(UnaryCompound host){
  //   System.out.println(host + " UnaryCompound visited");
  // }
  public void before(Disjunction host){
    // System.out.println(c + " Disjunction value of c");
    c++;
  }
  public Object getReturnValue() { return new Integer(c);}
  }}
}

XPath {
 void display() to * (DisplayVisitor); 
}

input:
==================================================

(
a
*
{-{/ {-{ /x }-} }-}
(| (/ p q) {-{ /y }-})
{-{/ (| x y)}-}
(/ a (| b c))
(/ 
  a 
  (desc
    b 
    (filt c {-{desc (| x (| y x))}-})
  ) 
)
{-{ / t }-UNKNOWN1
)

output:
==================================================
Reading project file program.prj...
Running the test...
UNKNOWN2

UNKNOWN3

UNKNOWN4
UNKNOWN5
UNKNOWN6
done


Question 3:
=============================================================
Following the DRY principle.
2 UNKNOWN, one per method.
20 points per method : 40 points.

Consider the program in question 2.
It violates the DRY principle.
Introduce methods that reduce the 
duplications. Define the two methods.

The call to the first method for its first use should be:

help1(cg, m, "from XPath via BinaryCompound to Disjunction",
" disjunction in binary ", countingVis);

The call to the second method for its first use should be:

help2(cg, m, "from XPath via UnaryCompound to Disjunction",
" list length disjunction in unary ");

Your answer consists of the two methods.


Question 4:
=============================================================
Parsing.
3 UNKNOWNs, one per input
5 points each: 15 points.

Consider the following inputs and the class dictionary
XPath1 from question 2. Clearly mark the first
token that is wrong with an arrow.

The class dictionary is XPath1.

// syntactically incorrect input
// what is the first token that is wrong?
(
(/ a (| b c) d)
)
// syntactically incorrect input
// what is the first token that is wrong?
(
(/ a {-{ | b c }-} d)
)
// syntactically incorrect input
// what is the first token that is wrong?
(
(/ a {-{ desc c }-} ))
)

Question 5:
=============================================================
4 UNKNOWNs: 10 points each: 40 points

Consider the slightly modified version of the XPath1 class dictionary
where each expression has a has-a edge called 
"parent" to the containing expression (see XPath2 below)
in a similar way as each directory in 
hw 4 had a has-a edge, called parent, to the
containing directory.

The class dictionary violates the DRY principle because ["parent" <parent> Exp]
is repeated three times. What is the easiest way to avoid this duplication?
Put your answer into UNKNOWN1.
Clearly indicate which classes you modify.

class dictionary XPath2:

// Neven-xpath.pdf
import edu.neu.ccs.demeter.dj.*;
import java.util.*;

XPath = List(Exp) EOF.
Exp : Simple | BinaryCompound | UnaryCompound.
Simple : ElementTest | WildCard common ["parent" <parent> Exp].
BinaryCompound = "(" BOp <arg1> Exp <arg2> Exp ")" 
  ["parent" <parent> Exp].
UnaryCompound = "{-{" UOp <arg1> Exp "}-}" 
  ["parent" <parent> Exp].
BOp : Disjunction | Child | Descendant | Filter.
UOp : Chi | Des.
Chi = "/".
Des = "desc".
Disjunction = "|".
Child = "/". 
Descendant = "desc" .
Filter = "filt".
ElementTest = Name.
WildCard = "*".
Name = Ident.

Main = <s> String.
List(S) ~ "(" {S} ")".

CountingVisitor = <c> int  extends Visitor .
ParentSettingVisitor = extends Visitor .
//////////////////////////////////////////////////////////////////

Now that the class dictionary is improved,
the next task is to write a program that sets the parent links
in a given list of expressions.
The program will visit all Binary- and Unary-objects and 
set the parent links of the contained subexpressions.
Remember that a strategy may have a set of target classes, such as
"from A via B to {C,D,E}.
Find the UNKNOWNs below.


Main {
  public static void main(String args[]) throws Exception {{
    XPath m = XPath.parse(System.in);
    // m.display();
    ClassGraph cgfull = new ClassGraph(true, false);
    ClassGraph cg = new ClassGraph(cgfull,
      "from XPath bypassing -> *,tail,* to *");
    System.out.println("done");

    String parents = "from XPath UNKNOWN2";
    cg.traverse(m,parents,new ParentSettingVisitor());
    m.display();
  }}
}
ParentSettingVisitor {
  {{
  public void before (BinaryCompound host) {
    UNKNOWN3
  }
  public void before (UnaryCompound host) {
    UNKNOWN4
  }
  }}
}

XPath {
 void display() bypassing -> *,parent,* to * (DisplayVisitor); 
}