FINAL COM 1205 Winter 2003
Karl Lieberherr
Software Design and Development
========================================================================
Open book and open notes
1: 23 points parsing, printing, 3-way pattern matching
2: 52 points write semantic checker
3: 21 points Don't Repeat Yourself Principle
4: 33 points predict output of program
5: 20 points class dictionary design
---
149 points
If there are multiple correct answers for a question, make a note.
The following class dictionary is used in questions
1 through 5.
import edu.neu.ccs.demeter.dj.*;
import java.util.*;
Main = .
Input = "cds" <cds> List(Cd)
"glue" CdGlue
"traversals" <travs> List(Traversal) EOF.
Cd = <cdName> CdName <classDefs> List(ClassDef).
ClassDef = <n> ClassName <parts> List(Part).
Part = PartName ClassName.
CdGlue = <correspondences> List(Corresp).
Corresp= <first> QualifiedClass "=" <second> QualifiedClass.
QualifiedClass = CdName "." ClassName.
Traversal = TraversalName List(Seg).
Seg = "in" CdName "from" <from1> ClassName "to" <to1> ClassName.
CdName = Ident.
ClassName = Ident.
PartName = Ident.
TraversalName = Ident.
List(S) ~ "(" {S} ")".
Question 1:
===========
23 UNKNOWNs: 1 point each
1: 23 points
Consider the following input and object graph:
Find the UNKNOWNs.
input:
============================================================
cds
(
UNKNOWN1
UNKNOWN2
UNKNOWN3 ( UNKNOWN4 B c C )
B ( )
C ( )
)
Y
(
C ( b B)
B ( e E)
E ( )
)
)
glue
(
X.C = Y.C
)
traversals
(
t1 (
in X from A to C
in Y from C to E
)
)
object graph:
============================================================
: Input (
<cds> : Cd_List {
<first> : Nonempty_Cd_List (
<it> : Cd (
<cdName> : CdName (
<ident> : Ident "X" )
<classDefs> : ClassDef_List {
<first> : Nonempty_ClassDef_List (
<it> : ClassDef (
<n> : ClassName (
<ident> : Ident "A" )
<parts> : Part_List {
<first> : Nonempty_Part_List (
<it> : Part (
<partname> : PartName (
<ident> : Ident "b" )
<classname> : ClassName (
<ident> : Ident "B" ) )
<next> : Nonempty_Part_List (
<it> : Part (
// several lines omitted
<cdglue> : CdGlue (
<correspondences> : Corresp_List {
<first> : Nonempty_Corresp_List (
<it> : UNKNOWN5 (
<first> : UNKNOWN6 (
<UNKNOWN7> : UNKNOWN8 (
<UNKNOWN9> : UNKNOWN10 )
<UNKNOWN11> : UNKNOWN12 (
<UNKNOWN13> : UNKNOWN14 ) )
<second> : UNKNOWN15 (
<cdname> : CdName (
<ident> : Ident "Y" )
<classname> : ClassName (
<ident> : Ident "UNKNOWN16" ) ) ) ) } )
<travs> : Traversal_List {
<first> : Nonempty_Traversal_List (
<it> : Traversal (
<traversalname> : TraversalName (
<ident> : Ident "UNKNOWN17" )
<seg_list> : Seg_List {
<first> : Nonempty_Seg_List (
<it> : Seg (
<cdname> : CdName (
<ident> : Ident "UNKNOWN18" )
<from1> : ClassName (
<ident> : Ident "UNKNOWN19" )
<to1> : ClassName (
<ident> : Ident "UNKNOWN20" ) )
<next> : Nonempty_Seg_List (
<it> : Seg (
<cdname> : CdName (
<ident> : Ident "UNKNOWN21" )
<from1> : ClassName (
<ident> : Ident "UNKNOWN22" )
<to1> : ClassName (
<ident> : Ident "UNKNOWN23" ) ) ) ) } ) ) } )
Question 2:
===========
13 UNKNOWNs, 4 points each
2: 52 points
Write a program that checks that all the CdName-objects
that are used in the glue part or the traversals part
of an Input-object are
defined in the cds part of the same Input-object.
Your program must print "true" or "false".
Use the "containsAll" method of interface Collection:
boolean containsAll(Collection c)
Returns true if this collection
contains all of the elements
in the specified collection c.
The class graph object of class ClassGraph is available
in variable cg. Find the UNKNOWNs below.
The Input object is in variable i.
List defined = UNKNOWN1.UNKNOWN2(i,
" from UNKNOWN3 " +
UNKNOWN4 +
" via UNKNOWN5 " +
" to edu.neu.ccs.demeter.Ident");
List used = UNKNOWN6.UNKNOWN7(i,
" from UNKNOWN8 " +
UNKNOWN9 +
" via UNKNOWN10 " +
" to edu.neu.ccs.demeter.Ident");
System.out.println(UNKNOWN11.UNKNOWN12(UNKNOWN13));
Question 3:
===========
7 UNKNOWNs, 3 points each
3: 21 points
Consider the following two methods gather1 and gather2 that violate
the DRY principle:
List gather1(ClassGraph cg){
List l1 = cg.gather(this,
"from Input via Traversal " +
"via -> *,from1,* " +
"via ClassName to edu.neu.ccs.demeter.Ident");
l1.remove(0);
System.out.println(l1.toString());
System.out.println(" done gather 1 ");
return(l1);
}
List gather2(ClassGraph cg){
List l2 = cg.gather(this,
"from Input via Traversal " +
"via -> *,to1,* " +
"via ClassName to edu.neu.ccs.demeter.Ident");
l2.remove(l2.size()-1);
System.out.println(l2.toString());
System.out.println(" done gather 2 ");
return(l2);
}
Write a new method gather that follows the DRY principle:
Find the UNKNOWNs below.
List gather(ClassGraph cg, UNKNOWN1 UNKNOWN2, UNKNOWN3 UNKNOWN4){
List l = cg.gather(this,
"from Input via Traversal " +
UNKNOWN5 +
"via ClassName to edu.neu.ccs.demeter.Ident");
UNKNOWN6
System.out.println(l.toString());
System.out.println(" done gather " + kind);
return(l);
}
How will you replace the two calls
List l1 = i.gather1(cg2);
List l2 = i.gather2(cg2);
by two calls to gather? Put your answer in UNKNOWN7.
Question 4:
===========
11 UNKNOWNs, 3 points each
4: 33 points
Consider the following program, input and output.
Find the UNKNOWNs:
Main {
{{
public static void main(String args[]) throws Exception {
Input i = Input.parse(System.in);
ClassGraph cg = new ClassGraph(true,false);
ClassGraph cg2 = new ClassGraph(cg,
"from Input bypassing -> *,tail,* to *");
System.out.println(" output ");
i.process(cg2);
List l1 = i.gather1(cg2);
List l2 = i.gather2(cg2);
System.out.println(l1.equals(l2));
System.out.println(" done" );
}
}}
}
Input {
{{
void process(ClassGraph cg){
cg.traverse(this, "from Input via Traversal to CdName",
new Visitor() {
void before (CdName host){
System.out.println(host.get_ident()); }
}
);
}
List gather1(ClassGraph cg){
List l1 = cg.gather(this,
"from Input via Traversal " +
"via -> *,from1,* " +
"via ClassName to edu.neu.ccs.demeter.Ident");
l1.remove(0);
System.out.println(l1.toString());
System.out.println(" done gather 1 ");
return(l1);
}
List gather2(ClassGraph cg){
List l2 = cg.gather(this,
"from Input via Traversal " +
"via -> *,to1,* " +
"via ClassName to edu.neu.ccs.demeter.Ident");
l2.remove(l2.size()-1);
System.out.println(l2.toString());
System.out.println(" done gather 2 ");
return(l2);
}
}}
}
input:
cds
(
X
(
A ( b B c C)
B ( d D e E)
)
Y
(
A ( b B c C)
B ( d D e E)
)
)
glue
(
X.C = Y.C Y.E = Z.E Z.D = U.D
)
traversals
(
t1 (
in X from A to C
in Y from C to E
in Z from E to D
in U from D to E
)
)
output:
output
UNKNOWN1
UNKNOWN2
UNKNOWN3
UNKNOWN4
[UNKNOWN5, UNKNOWN6, UNKNOWN7]
done gather 1
[UNKNOWN8, UNKNOWN9, UNKNOWN10]
done gather 2
UNKNOWN11
done
Question 5:
===========
2 UNKNOWNs, 10 points each.
5: 20 points
Extend the class dictionary so that it accepts the following input:
// same as before
...
traversals // this part is new
(
t1 (
in X from A via {X1,X2} bypassing {Y1} to C
in Y from C via {X1,X2} bypassing {Y1} via {C} to E
in Z from E bypassing {Y1} via {C} to D
in U from D bypassing {Y1} via {X1} bypassing {Y1} to E
)
)
Basically you can have any number of bypassing and via
constraints between "from" and "to".
Make your modification of the class dictionary
as simple as possible. Give the classes that you
modify and how you modify them
and write the new classes that are needed.
Put your modified classes in UNKNOWN1.
Put your new classes in UNKNOWN2.