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 ":".