Common Lisp support for the 'Extensible Markup Language' (CL-XML)

10 november 1997
james anderson, benno biewer <mecom-gmbh@mixx.de>

this memo introduces a common lisp package which implements a primitive "processor" for data streams serialized according to the proposed "extensible markup language" standard (of which the 08.12.97 version accompanies this distribution). this document describes the proposed approach and explains how to try the processor out.

background

there are two reasons to work towards support for XML in common lisp: the present thinking about XML proposes a triad of standards the present collection of files provides a minimal implementation for XML. it also includes a provisional pattern matcher for use, for example, as the core of an XSL matcher, and a compiler for element models which can be used to implement validation.

this version of the processor can parse and process two sorts of documents

an XML document is read to produce an internal node tree which represents the node containment relations denoted in the stream and which establishes links to the specified element definitions for reference to model and attribute declarations. if the XML document specifies a source for a DTD, the DTD document is read to produce an internal representations of the declared elements, models, atttributes, and entities. [v0.16: as an optional step when creating element definitions, the respective model is compiled to produce a validation predicate. use of the predicates are left to the 'application' either by means of auxiliary (likely :before) constraint methods, for example on XML-ELEMENT.APPEND-ELEMENT or on (SETF XML-NODE.CONTENT)(t XML-ELEMENT).

DTD and XML streams are, for the most part, processed identically. a distinction is limited to two interface functions which read the named respective stream type and enforce content constraints on the results.
READ-DTD-STREAM (generic-function (stream) DTD)
READ-XML-STREAM (generic-function (stream) XML-ELEMENT)
additional interface functions are provided to read individual elements, read PCDATA, CDATA, etc. look at "interface.lisp" for descriptions.

the reading and construction process is controlled by numerous parameter bindings. there are, for example, bindings to specify the class of each node to be instantiated. see "global-bindings.lisp" for explanations.

this prototype includes support for the following elements. a distinction is made between parsing and processing. the former means that the element is read and instantiated. the latter means that the relations or side effects specified by the standard are implemented.
 
element parsed processed comments
<!-- yes yes comments are appended to the parent node. they are bound separate from element children and keyed to the immediately preceeding element.
!ELEMENT yes yes element definitions are bound to the parent DTD. the names are required to be of the same package as the DTD. where element references appear in a model, supplementary (non-standard) ELEMENT-REFERENCE nodes are generated to accommodate forward references and to accept instance-specific attributes.
!ENTITY yes yes
!NOTATION yes no
![CDATA[ yes yes bound as text to the parent node
![INCLUDE[ yes yes read as a string and reparsed. the last element in the stream is returned.
![IGNORE[ yes yes read as string and discarded
?XML yes yes no support for encoding
?NAMESPACE yes yes namespaces are implemented through packages. each DTD is associated with a package which has the
same name as the DTD. where a DTD has been included by virtue of a namespace reference, the respective package is renamed according to the "AS" attribute. the original name becomes a nickname.
!DOCTYPE yes yes in a document type definition, it specifies the name of the DTD.
in an XML document, it references the respective DTD and or provides an internal definition
&entity; yes yes named entity references are appended to the content of containing elements. methods to retrieve and parse the referenced entity's content are not yet implemented. if they were PCDATA only, the dtd is available through the containing elements dtd-element-reference and the string content could be reread with READ-PROCESS-PCDATA. this should wait, however, until we understand the meaning and uses of notations, since things like external entities and binary data aren't that simple.
%entity; yes yes wherever they are permitted (type names, models, attributes, ... ?), parameter entities are supported by concatenating streams. the entity value is prepended to the active stream in place of the entity reference. this means that syntactic restrictions specified by the standard for entity values are not enforced.
element yes yes elements are parsed and processed. the processing step appends an element to its parent node.
attributes are parsed and bound to the element node. limited attribute normalization is not supported.
empty elements are supported.

the processor performs limited case-folding. all element names are folded to upper case. attribute names and values are left unmodified with the exceptions: ID, IDREF, IDREFS, NMTOKEN, NMTOKENS. although element name folding is not specified by the standard, ID value folding would appear to require it. i do not believe this is according to standard, but i do not yet understand the case handling rules.


 

programm structure

this implementation is an extension of the standard lisp reader. it augments the reader with reader macros which transform the serial xml representation into the equivalent node tree. it is a 'hand-coded' implementation of the XML standard and makes no attempt to implement the bnf-specification through the means of automatic translation.

it is implemented in terms of three constructs: (take a look at "markup-reader.lisp")

  1. reader macros:

    2. the xml standard specifies distinct lexical rules for different aspects of a document. for our purposes, by virtue of the presence of internal document type definitions, the circumstances hold true for xml documents and document type definitions. the lexical behaviour of the parser is defined for each aspect of a document in terms of a specific readtable. each table comprises aspect-specific character syntax and/or reader macros. the lexical analysis is then left (with the exception of occasional application of peek-char) to the reader.
  2. structural analysis through generic dispatch

    3. the xml standard specifies a small number of structural forms: each has a specific syntax and specific lexical constraints. in order to accommodate these difference, while providing for the foreseeable need to extend the processor, the the parser is distributed among several generic functions and their respective methods.
    the parsing process is initiated in reader macros specific to each lexical aspect. these macros collect a datum, which then serves as the discriminator for an aspect-specific parsing function. this read/discriminate process continues until the element syntax is determined, at which point the parse is performed by a specific method.

    the parsing process can be understood to pass control among several levels. from outermost to innermost they are: 

    read-dtd-stream
read-xml-stream
markup-dispatching-reader-macro
  read-element-stream
  read-element
  element-reader-macro
   read-typed-markup-element
    read-typed-processing-instruction
    read-typed-markup-declaration
    read-typed-section-element
     read-markup-tag-attributes
     read-markup-tag-type
     read-markup-tag-parameters  read-process-pcdata
      read-process-cdata
      read-process-pcdata
      read-pcdata
      read-cdata
       read
  3. construction by side-effect

    4. the standard cl reader constructs data structures from returned values to embody relationships identical to the lexical structure of the read expressions. an xml processor, in contrast, instantiates relations which are not necessarily denoted through lexical containment. while the lexical-structural identity may hold for element data, it does not hold for declarations and the relation implied by processing instructions is completely unspecified. for this reason we propose an xml processor which acts as a side-effecting reader rather than as a functional reader. this means that each object establishes a dynamic context as it is read and permits lexically contained objects to assert their relation to it or to any other, or appropriate object.

examples

the directory "dtd" includes several simple document type definitions. one for lisp "lisp.dtd" and one for XSL patterns "xsl.dtd". the directory "xml" contains small example files. one from microsoft contains a channel description. the the best sources for further examples are net resources: