Software Design and Development
COM 1205  Winter 2001 Prof. Karl Lieberherr

MIDTERM

YOUR NAME:

Open book and open notes.

Points:
Question 1: 				30 points
Question 2: 15 UNKNOWNs: 4 points each: 60 points
Question 3: 18 UNKNOWNs, 2 points each, 36 points
Question 4:  8 UNKNOWNs, 2 points each, 16 points
                                       142 points total


Question 1:
============================================
30 points

In this exam you get two class dictionaries:
The first one is called SchemaSimple and the the second
one SchemaComplex. SchemaSimple is a simplification
of SchemaComplex. You find the structure of SchemaSimple
also in SchemaComplex. SchemaSimple is given 
in graphical form as a UML class diagram and the
SchemaComplex is given in textual form (in question 2).

SimpleSchema will be used for traversal related questions
and SchemaComplex for programming questions.
The class dictionaries are about XML schemas. The cds define
the structure and the syntax of XML schemas but
you don't need any previous knowledge of XML.
Both cds only define a subset of XML schemas.

Consider class dictionary SchemaSimple and 
the traversal strategies:

from Schema to TypeDef : 10 points
from Schema to Attribute: 10 points
from Schema to Element : 10 points

Highlight all the classes whose objects might be 
traversed on some object of the start class of the strategy. 
Mark the classes directly in the UML class diagram
(you get 3 copies of the diagram).

Example
The traversal strategy: "from Attribute to AttrValue" results
in two classes: Attribute and AttrValue.

Question 2:
==================
15 UNKNOWNs: 4 points each: 60 points.

Consider the following class dictionary SchemaComplex:


import java.util.*;
import java.io.*;
import edu.neu.ccs.demeter.dj.*;
//******************************************************************************
// Basic definitions
//******************************************************************************
Main		= .
List(S)		~ { + *l S -}.
//******************************************************************************
// PART 1:  Definitions of structures implementing the components of the input
// XML schema specification
//******************************************************************************

Schema		= "<" [ <prefixS> NSRef ] "schema"
		    <attrs> List(AttrValue)
		    ">"
		    <items> List(SchemaItem)
		    "</" [ <prefixE> NSRef ] "schema>" *EOF*.
NSRef		= <namespace> Ident ":".
AttrValue	= [ lookahead (@2@) <prefix> NSRef ]
		    <attrName> Ident "=" <attrValue> String.

SchemaItem	: 
		  lookahead (@4@) Annotation |
		  lookahead (@4@) Attribute |
		  lookahead (@4@) ElementItem |
		  lookahead (@4@) TypeDef 
		  | Comment
		  .

Annotation	= "<" [ <prefixS> NSRef ] "annotation>"
		    List(AnnotationContent)
		    "</" [ <prefixE> NSRef ] "annotation>".
AnnotationContent : 
		    lookahead (@4@) Appinfo |
		    lookahead (@4@) Documentation.
Appinfo		= "<" [ <prefixS> NSRef ] "appinfo>"
		    <attrs> List(AttrValue)
		    "</" [ <prefixE> NSRef ] "appinfo>".
Documentation	= "<" [ <prefixS> NSRef ] "documentation"
		    <attrs> List(AttrValue)
		    RestOfDocumentation.
RestOfDocumentation : EmptyDocumentation | NonEmptyDocumentation.
EmptyDocumentation = "/>".
NonEmptyDocumentation = ">"
			  [ <documentation> String ]
			  "</" [ <prefixE> NSRef ] "documentation>".
Attribute	= "<" [ <prefixS> NSRef ] "attribute"
		    <attrs> List(AttrValue)
		    RestOfAttribute.
RestOfAttribute	: EmptyAttribute | NonEmptyAttribute.
EmptyAttribute	= "/>".
NonEmptyAttribute = ">"
		      [ lookahead (@4@) Annotation ]
		      "</" [ <prefixE> NSRef ] "attribute>".

Element		= "<" [ <prefixS> NSRef ] "element"
		    <attrs> List(AttrValue)
		    RestOfElement.
RestOfElement	: EmptyElement | NonEmptyElement.
EmptyElement	= "/>".
NonEmptyElement	= ">"
		    [ lookahead (@4@) Annotation ]
		    [ lookahead (@4@) <type> TypeDef ]
		    "</" [ <prefixE> NSRef ] "element>".

TypeDef		: lookahead (@4@) SimpleType |
		  lookahead (@4@) ComplexType.
SimpleType	= "<" [ <prefixS> NSRef ] "simpleType"
		    <attrs> List(AttrValue)
		    ">"
		    [ lookahead (@4@) Annotation ]
		    "</" [ <prefixE> NSRef ] "simpleType>".

ComplexType	= "<" [ <prefixS> NSRef ] "complexType"
		    <attrs> List(AttrValue)
		    ">"
		    [ lookahead (@4@) Annotation ]
		    ComplexTypeContent
		    List(Attribute)
		    "</" [ <prefixE> NSRef ] "complexType>".
ComplexTypeContent = 
		     [ lookahead (@4@) ElementItem ].

ElementItem	: 
		  lookahead (@4@) Element |
		  lookahead (@4@) SequenceGroup 
		  .

SequenceGroup	= "<" [ <prefixS> NSRef ] "sequence"
		    <attrs> List(AttrValue)
		    ">"
		    [ lookahead (@4@) Annotation ]
		    List(ElementItem)
		    "</" [ <prefixE> NSRef ] "sequence>".

Comment		= "<!--" <comment> String "-->".




Consider the following program that finds
all names of complex types in an XML schema.
The program finds all ComplexType-objects and then searches
the Attribute_List to find an attribute with name "name".

Fr example, the following complex type definition is
introducing a type called PurchaseOrderType.

 <xsd:complexType name="PurchaseOrderType">       

The program will put string "PurchaseOrderType" into a HashSet-object.

Find the UNKNOWNs below.


Schema {
  {{
    HashSet getDefThings(ClassGraph cg){
      String definedThings =
	"from Schema to ComplexType";
      Visitor v = new Visitor(){
	HashSet r = new HashSet();
	void before(ComplexType host){
	  String n = UNKNOWN1.UNKNOWN2().search_name();
	  if (!(n == null)) r.add(n);
        }
	public Object UNKNOWN3(){return r;}
      };
      cg.UNKNOWN4(this,UNKNOWN5,UNKNOWN6);
      return (HashSet) v.UNKNOWN7();
    }
  }}
}

AttrValue_List {
{{
String search_name(){
  UNKNOWN8 en = this.elements();
  String s = new String("name");
  String result;
  while (UNKNOWN9.UNKNOWN10()) {
    UNKNOWN11 n = (UNKNOWN12) en.UNKNOWN13();
    if (s.equals(n.UNKNOWN14().toString())) {
      result = n.UNKNOWN15();
      System.out.println("Type " + result + " found");
      return result;
    }
  }
  System.out.println("NOTHING FOUND");
  return null;
}
}}
}

If getDefThings(..) is called on the Schema-object
described in XML2AP.input:

<xsd:schema xmlns:xsd="http://www.w3.org/2000/08/XMLSchema">

 <xsd:annotation>
  < xsd : documentation >
   "Purchase order schema for Example.com.  Copyright 2000 Example.com. All rights reserved."
  </xsd:documentation>
 </xsd:annotation>

 <xsd:element name="purchaseOrder" type="PurchaseOrderType"/>

 <xsd:element name="comment" type="xsd:string"/>

 <xsd:complexType name="PurchaseOrderType">
  < xsd : sequence >
   <xsd:element name="shipTo" type="USAddress"/>
   <xsd:element name="billTo" type="USAddress"/>
   <xsd:element ref="comment" minOccurs="0"/>
   <xsd:element name="items"  type="Items"/>
  </xsd:sequence>
  <xsd:attribute name="orderDate" type="xsd:date"/>
 </xsd:complexType>

 <xsd:complexType name="USAddress">
  < xsd : sequence >
   <xsd:element name="name"   type="xsd:string"/>
   <xsd:element name="street" type="xsd:string"/>
   <xsd:element name="city"   type="xsd:string"/>
   <xsd:element name="state"  type="xsd:string"/>
   <xsd:element name="zip"    type="xsd:decimal"/>
  </xsd:sequence>
  <xsd:attribute name="country" type="xsd:NMTOKEN"
     use="fixed" value="US"/>
 </xsd:complexType>

 <xsd:complexType name="Items">
  <xsd:sequence >
   <xsd:element name="item" minOccurs="2" maxOccurs="unbounded">
    <xsd:complexType >
     <xsd:sequence >
      <xsd:element name="productName" type="xsd:string" maxOccurs="unbounded"/>
      <xsd:element name="quantity" type="xsd:positiveInteger"/>
      <xsd:element name="USPrice"  type="xsd:decimal"/>
      <xsd:element ref="comment"   minOccurs="0" maxOccurs="unbounded"/>
      <xsd:element name="shipDate" type="xsd:date" minOccurs="0"/>
     </xsd:sequence>
     <xsd:attribute name="partNum" type="string"/>
    </xsd:complexType>
   </xsd:element>
  </xsd:sequence>
 </xsd:complexType>

</xsd:schema>


we get the following output:

Type PurchaseOrderType found
Type USAddress found
Type Items found
NOTHING FOUND


Question 3:
===========
18 UNKNOWNs, 2 points each, 36 points

Use again class dictionary SchemaComplex.
Consider the following two program fragments.
The first one eliminates all AttrValue-objects contained
in the attrs data member of Element-objects.

For example:

<xsd:element name="purchaseOrder" type="PurchaseOrderType"/>  
is translated to:
<xsd:element/>  

The second program fragment eliminates name space references 
(NSRef-objects)
from complex types (ComplexType-objects). For example:

<xsd:complexType name="PurchaseOrderType">     
is translated to:
<complexType name="PurchaseOrderType">

Find the UNKNOWNs below (cg2 is the class graph for XML schemas,
s is a Schema-object):

    System.out.println(" Eliminate attributes from elements ");
    cg2.UNKNOWN1(s,"from UNKNOWN2 to UNKNOWN3", UNKNOWN4 UNKNOWN5() {
      void UNKNOWN6(UNKNOWN7 host){
	System.out.println(" Element found ");
	host.UNKNOWN8(new UNKNOWN9());
      }
    });
    System.out.println("========");
    System.out.println(" Eliminate name space refs from complex types ");
    cg2.UNKNOWN10(s,"from UNKNOWN11 to UNKNOWN12", UNKNOWN13 UNKNOWN14() {
      void UNKNOWN15(UNKNOWN16 host){
	System.out.println(" ComplexType found ");
	host.UNKNOWN17(UNKNOWN18);
      }
    });



Question 4:
===========
8 UNKNOWNs, 2 points each, 16 points.

The following class dictionary is not LL1.

SchemaItem	: 
		  Annotation |
		  Attribute |
		  SequenceGroup |
		  Comment .

Annotation	= "<" [ <prefixS> NSRef ] "annotation>".
Attribute	= "<" [ <prefixS> NSRef ] "attribute".
SequenceGroup	= "<" [ <prefixS> NSRef ] "sequence".
Comment		= "<!--" <comment> String "-->".

NSRef		= <namespace> Ident ":".

The following class dictionary defines the same language
and is LL1. Find the UNKNOWNs.

SchemaItem	: 
                  AAS |
		  Comment
		  .

UNKNOWN1 = UNKNOWN2 [ <UNKNOWN3> UNKNOWN4 ] Rest.
UNKNOWN5 :
		  AnnotationR |
		  AttributeR |
		  SequenceGroupR .

AnnotationR	= UNKNOWN6.
AttributeR	= UNKNOWN7.
SequenceGroupR	= UNKNOWN8.
Comment		= "<!--" <comment> String "-->".

NSRef		= <namespace> Ident ":".