------------------------------------------- CSC200 - Undergraduate Problem Seminar XML Parser Generator Group 7, Phase 2 Michael Aronson - maronson@cs.rochester.edu -Testing -Documentation -Preliminary Component Design Michael George - mdgeorge@cs.rochester.edu -Testing -Code Generator/Validator -Project Design and Implementataion Richard Golden - rgolden@cs.rochester.edu -Testing -Parser production and design ------------------------------------------- Manual and Documentation ------------------------------------------- -Summary- FEATURES: -Uses generated code for self-describing DTD as part of the code generator. -Supports inheritance (and therefore union) -Generated code has design pattern -Generated code well commented CAVEATS: -Unknown performance bounds -Poor exception handling -Introduction- The XML Parser Generator that we have produced during Phase 2 is the culmination of the project we started during Phase 1. During Phase 1, we produced an XML DTD language, an XML Scanner, and an XMLNode Tree for use by other people in the production of an XML Parser Generator. For Phase 2, we chose a language, a scanner, and a tree written by other teams for the production of our XML Parser Generator. In chosing components, we set out to find a language, tree, and scanner that closely resembled the ones we had previously designed. We chose the Group 5 language and the Group 6 Scanner with this fact in mind. For the tree, we chose to employ the submission by Group 14. -Language- The Group 5 language was chosen because, like the language we produced during Phase 1, offered both maximum functionality and minimum complexity. It contains five tags: TYPE, ATTRIBUTE, CONTAINS, ELEMENT, and CDATA. TYPE is the dtd declaration tag. ATTRIBUTE is an attribute declaration tag. CONTAINS is a tag to declare something as a child of its parent tag. ELEMENT is a dtd element declaration tag. We slightly modified the language in that the original Group 5 specification says that TYPE tags can accept CONTAINS tags as well as ELEMENT tags. In our implementation, TYPE tags can only accept ELEMENT tags, and ELEMENT tags can accept CONTAINS tags to describe members of the ELEMENT being described. In order to specify the top level tag, we added the root attribute to the TYPE tag. Note that this enforces the condition of a single top-level tag. In addition to that change, we added and moved a few attributes. We moved the "multiplicity" attribute from the ELEMENT tag to the CONTAINS tag, because we felt this made more sense. We added the "superclass" and "abstract" attributes to the ELEMENT tag in order to support our inheritance scheme. We added the "optional" attribute to the ATTRIBUTE tag, which allows values to remain unspecified. This was required in order to handle default values uniformly. Finally, we added the CDATA tag, to replace #String in the previous implementation. This allows internal tag data to be treated uniformly. For a precise and detailed list of our changes to the language, compare the files lang/TYPE.dtd which describes our language, and lang/oldTYPE.dtd which was submitted by group 5. -Scanner- The Group 6 scanner was chosen for ease of use and functionality. It's usage is relatively straightforward, it's documentation is good, and it gets the job done. The scanner was modified to allow access to the current token, and the token class was modified to allow access to the string of the token type. -Tree- Of the trees, our selection is perhaps the most innovative second to our own submission. It uses an interesting list representation of levels of the tree, which means children are iterated over as opposed to being accessed from the parent node. Attributes of a node are stored in HashMaps, which allows for the easy building of XMLTrees with attribute lists and children tags. This allows for the easy extraction of such information. The Group 14 tree also offers validation routines, but these have been turned off. Our original plans called for the design of our own validation routines and with this and the terms of the project in mind, we have elected to conform to our original designs. It was modified to allow for the printing of the tree from the tree class. The code for this was spliced in from the group's own test file, but before our modification was previously unavailable as a function of the tree. -Design and Implementation- Since our output is a hierarchy of classes that statically describes an XML document of a given DTD, and since we have a DTD that describes DTDs, we chose to use our generated code for the TYPE dtd in our code generator. More specifically, the generated code consists of an outer class, named Tag which in turn contains inner classes for each of our ELEMENT tags. The outer class also contains a reference to the root element type (which is taken from the "root" attribute of the DTD). Each of these classes contains a constructor which takes an XMLNode and builds itself recursively, verifying all the way. The code generator is dependant upon the generated code for the specific instance of the generated.TYPETag class, which is generated from lang/TYPE.dtd. After the scanner breaks the input DTD into tokens, and the parser builds an XMLTree out of them, we create a generated.TYPETag out of the resulting XMLTree. This approach has the advantage that any verification we provide for generic XML documents we get for free for DTDs. In addition, the generator.XMLCodeGen class serves as an example and a test case for itself. Finally, generator.XMLCodeGen gets the extra ease that comes with working on a statically typed object hierarchy. In other words, after compiling the Generate class, you can run Generate ../lang/TYPE.dtd and it will output a file identical to src/generated/TYPETag.java, and this file is used by the Generate class. If you want to change or add to the TYPE dtd, you can modify TYPE.dtd and simply re-generate. In order to support something union-compatible, we chose to implement simple inheritance. The ELEMENT tag contains a "superclass" attribute which allows it to act as another tag type. In order to accomplish this, we did two things: - when an element's inner class is generated, it extends it's superclass - when a tag is read in, the type is automatically determined using reflection. The resulting object is then cast to the parent class type, and if that succeds, we know that the subclass is actually really a subclass. In other words, if I read in a tag whose name is "TYPE", I query the java runtime for a class called TYPE and then query the for the proper constructor, then invoke it and cast the result. Although this inheritance scheme is super-fancy and works well on valid input, it leads to some very complicated error messages, and we didn't have time to get the exception handling right. The problem is that an exception raised during a dynamic invocation is wrapped inside a java.lang.reflect.InvocationTargetException, and thrown to the caller. Attempting to unwind this exception is confusing (and in fact caused sun to rework some of the exception handling for version 1.4), and we simply didn't have time to sort it out. Another possible caveat of dynamic type resolution is efficiency, since we have no idea what kind of time penalty we pay for these lookups. The dynamic resolution is performed in the base type, generated.TagBase in the create method. Our output code supports the Visitor design pattern. The Tag class contains an interface called Visitor which has a visit method for each of the ELEMENT based inner classes. It also contains a Visitable interface which all of the ELEMENT based inner classes implement. For more discussion of the Visitor design pattern, see "Design Patterns" by Gamma et. al.. -Organization- Directory Purpose doc/ -Contains the USER_MANUALS from the other components, in addition to this USER_MANUAL lang/ -Contains oldTYPE.dtd and TYPE.dtd, which are the original and our self-describing DTD, respectively. lib/ -Contains compiled java class files src/ -Contains executable sources: Generate.java: runs the code generator Counter.java: counts nodes in a Tree Calculator.java: calculates the value of an Expression. src/generated -Contains the generated package. The generated package consists of all generated code, as well as the InvalidXMLException class and the TagBase class, which are tightly linked to the generated code. src/generator -Contains the XMLCodeGen class, which generates the code. src/parser -Contains the Parser. src/scanner -Contains group 6's scanner. src/tree -Contains group 14's tree. src/util -Contains common exception classes test -Contains the provided test cases test/dtd -Contains DTD's that represent the types in the provided test cases. -Compilation- There is a Makefile provided. Simply typing make in the top level directory will compile the code generator, generate code for the test cases, and compile the test programs. Alternatively, there are rules for building just the code generator (make Generate), the Expression calculator (make Calculator) or the node counter (make Counter). Also, there is a rule called "make clean" which restores the directory tree to its original contents. IMPORTANT: do not delete the file "src/generated/TYPETag.java". Although this file is generated, it is also a key component of the generator, and you can't regenerate it without it. However, it is safe to overwrite it with a new version. -Usage- All programs should be run from the lib directory or with the lib directory in the CLASSPATH. to run the Code Generator: $] java Generate where the file at contains a valid DTD. The generated class will be written to standard out, and should be redirected to a file called generated/Tag.java where is the name of the TYPE tag in the DTD. to run the Calculator: $] java Calculator where the file at contains a valid Expression (conforms to the test/dtd/Expression.dtd DTD). This will print the result of the expression on standard out. to run the Counter: $] java Counter where the file at contains a valid Tree (conforms to the test/dtd/Tree.dtd DTD). This will print the number of occurences of the given group number to standard out. -Advanced Usage- to generate the TYPETag class and compare it to the current TYPETag class: $] java Generate ../lang/TYPE.dtd | diff - ../src/TYPETag.java -Known Issues- Our error handling is super state of the art, it just isn't fully functional yet. Author's Note - They changed the whole error handling mechanism in Java because it is so confusing in regards to reflection. So confusing, in fact, that it confused us. :( -Test Results- Expression1 - 4 Expression2 - 1 Expression3 - Error in the input file (tried to have 3) Expression4 - Unknown error due to our wonderful, yet non-functional, error handling. We suspect that this error is in the test case itself, but we cannot be sure.