NOTE: The following text is partly out of date, but not fully.
------------------------------------------------ -*- indented-text -*-
Some Notes About the Design:
----------------------------------------------------------------------
----------------------------------------------------------------------
Compilation
----------------------------------------------------------------------
Compilation is non-trivial because:
- The lexer and parser generators ocamlllex resp. ocamlyacc normally
create code such that the parser module precedes the lexer module.
THIS design requires that the lexer layer precedes the entity layer
which precedes the parser layer, because the parsing results modify
the behaviour of the lexer and entity layers. There is no way to get
around this because of the nature of XML.
So the dependency relation of the lexer and the parser is modified;
in particular the "token" type that is normally defined by the
generated parser is moved to a common predecessor of both lexer
and parser.
- Another modification of the standard way of handling parsers is that
the parser is turned into an object. This is necessary because the
whole parser is polymorphic, i.e. there is a type parameter (the
type of the node extension).
......................................................................
First some modules are generated as illustrated by the following
diagram:
markup_yacc.mly
| |
\|/ \|/ [ocamlyacc, 1]
V V
markup_yacc.mli markup_yacc.ml
| --> renamed into markup_yacc.ml0
[awk, 2] \|/ |
V \|/ [sed, 3]
markup_yacc_token.mlf V
| | markup_yacc.ml
markup_lexer_types_ | |
shadow.mli | | | markup_lexer_types_
\|/ [sed, \|/ | shadow.ml
V 4] V | |
markup_lexer_types.mli | | [sed, 4]
\|/ \|/
V V
markup_lexer_types.ml
markup_yacc_shadow.mli
|
\|/ [replaces, 5]
V
markup_yacc.mli
markup_lexers.mll
|
\|/ [ocamllex, 6]
V
markup_lexers.ml
Notes:
(1) ocamlyacc generates both a module and a module interface.
The module is postprocessed in step (3). The interface cannot
be used, but it contains the definition of the "token" type.
This definition is extracted in step (2). The interface is
completely replaced in step (5) by a different file.
(2) An "awk" script extracts the definition of the type "token".
"token" is created by ocamlyacc upon the %token directives
in markup_yacc.mly, and normally "token" is defined in
the module generated by ocamlyacc. This turned out not to be
useful as the module dependency must be that the lexer is
an antecedent of the parser and not vice versa (as usually),
so the "token" type is "moved" to the module Markup_lexer_types
which is an antecedent of both the lexer and the parser.
(3) A "sed" script turns the generated parser into an object.
This is rather simple; some "let" definitions must be rewritten
as "val" definitions, the other "let" definitions as
"method" definitions. The parser object is needed because
the whole parser has a polymorphic type parameter.
(4) The implementation and definition of Markup_lexer_types are
both generated by inserting the "token" type definition
(in markup_lexer_types.mlf) into two pattern files,
markup_lexer_types_shadow.ml resp. -.mli. The point of insertion
is marked by the string INCLUDE_HERE.
(5) The generated interface of the Markup_yacc module is replaced
by a hand-written file.
(6) ocamllex generates the lexer; this process is not patched in any
way.
......................................................................
After the additional modules have been generated, compilation proceeds
in the usual manner.
----------------------------------------------------------------------
Hierarchy of parsing layers:
----------------------------------------------------------------------
From top to bottom:
- Parser: Markup_yacc
+ gets input stream from the main entity object
+ checks most of the grammar
+ creates the DTD object as side-effect
+ creates the element tree as side-effect
+ creates further entity objects that are entered into the DTD
- Entity layer: Markup_entity
+ gets input stream from the lexers, or another entity object
+ handles entity references: if a reference is encountered the
input stream is redirected such that the tokens come from the
referenced entity object
+ handles conditional sections
- Lexer layer: Markup_lexers
+ gets input from lexbuffers created by resolvers
+ different lexers for different lexical contexts
+ a lexer returns pairs (token,lexid), where token is the scanned
token, and lexid is the name of the lexer that must be used for
the next token
- Resolver layer: Markup_entity
+ a resolver creates the lexbuf from some character source
+ a resolver recodes the input and handles the encoding scheme
----------------------------------------------------------------------
The YACC based parser
----------------------------------------------------------------------
ocamlyacc allows it to pass an arbitrary 'next_token' function to the
parsing functions. We always use 'en # next_token()' where 'en' is the
main entity object representing the main file to be parsed.
The parser is not functional, but uses mainly side-effects to accumulate
the structures that have been recognized. This is very important for the
entity definitions, because once an entity definition has been found there
may be a reference to it which is handled by the entity layer (which is
below the yacc layer). This means that such a definition modifies the
token source of the parser, and this can only be handled by side-effects
(at least in a sensible manner; a purely functional parser would have to
pass unresolved entity references to its caller, which would have to
resolve the reference and to re-parse the whole document!).
Note that also element definitions profit from the imperative style of
the parser; an element instance can be validated directly once the end
tag has been read in.
----------------------------------------------------------------------
The entity layer
----------------------------------------------------------------------
The parser gets the tokens from the main entity object. This object
controls the underlying lexing mechanism (see below), and already
interprets the following:
- Conditional sections (if they are allowed in this entity):
The structures <![ INCLUDE [ ... ]]> and <! IGNORE [ ... ]]> are
recognized and interpreted.
This would be hard to realize by the yacc parser, because:
- INCLUDE and IGNORE are not recognized as lexical keywords but as names.
This means that the parser cannot select different rules for them.
- The text after IGNORE requires a different lexical handling.
- Entity references: &name; and %name;
The named entity is looked up and the input source is redirected to it, i.e.
if the main entity object gets the message 'next_token' this message is
forwarded to the referenced entity. (This entity may choose to forward the
message again to a third entity, and so on.)
There are some fine points:
- It is okay that redirection happens at token level, not at character level:
+ General entities must always match the 'content' production, and because
of this they must always consist of a whole number of tokens.
+ If parameter entities are resolved, the XML specification states that
a space character is inserted before and after the replacement text.
This also means that such entities always consists of a whole number
of tokens.
- There are some "nesting constraints":
+ General entities must match the 'content' production. Because of this,
the special token Begin_entity is inserted before the first token of
the entity, and End_entity is inserted just before the Eof token. The
brace Begin_entity...End_entity is recognized by the yacc parser, but
only in the 'content' production.
+ External parameter entities must match 'extSubsetDecl'. Again,
Begin_entity and End_entity tokens embrace the inner token stream.
The brace Begin_entity...End_entity is recognized by the yacc parser
at the appropriate position.
(As general and parameter entities are used in different contexts
(document vs. DTD), both kinds of entities can use the same brace
Begin_entity...End_entity.)
+ TODO:
The constraints for internal parameter entities are not yet checked.
- Recursive references can be detected because entities must be opened
before the 'next_token' method can be invoked.
----------------------------------------------------------------------
The lexer layer
----------------------------------------------------------------------
There are five main lexers, and a number of auxiliary lexers. The five
main lexers are:
- Document (function scan_document):
Scans an XML document outside the DTD and outside the element instance.
- Content (function scan_content):
Scans an element instance, but not within tags.
- Within_tag (function scan_within_tag):
Scans within <...>, i.e. a tag denoting an element instance.
- Document_type (function scan_document_type):
Scans after <!DOCTYPE until the corresponding >.
- Declaration (function scan_declaration):
Scans sequences of declarations
Why several lexers? Because there are different lexical rules in these
five regions of an XML document.
Every lexer not only produces tokens, but also the name of the next lexer
to use. For example, if the Document lexer scans "<!DOCTYPE", it also
outputs that the next token must be scanned by Document_type.
It is interesting that this really works. The beginning of every lexical
context can be recognized by the lexer of the previous context, and there
is always a token that unambiguously indicates that the context ends.
----------------------------------------------------------------------
The DTD object
----------------------------------------------------------------------
There is usually one object that collects DTD declarations. All kinds of
declarations are entered here:
- element and attribute list declarations
- entity declarations
- notation declarations
Some properties are validated directly after a declarations has been added
to the DTD, but most validation is done by a 'validate' method.
The result of 'validate' is stored such that another invocation is cheap.
A DTD becomes again 'unchecked' if another declaration is added.
TODO: We need a special DTD object that allows every content.
The DTD object is known by more or less every other object, i.e. entities
know the DTD, element declarations and instances know the DTD, and so on.
TODO: We need a method that deletes all entity declarations once the DTD
is complete (to free memory).
----------------------------------------------------------------------
Element and Document objects
----------------------------------------------------------------------
The 'element' objects form the tree of the element instances.
The 'document' object is a derivate of 'element' where properties of the
whole document can be stored.
New element objects are NOT created by the "new class" mechanism, but
instead by an exemplar/instance scheme: A new instance is the duplicate
of an exemplar. This has the advantage that the user can provide own
classes for the element instances. A hashtable contains the exemplars
for every element type (tag name), and there is a default exemplar.
The user can configure this hashtable such that for elements A objects
of class element_a, for elements B objects of class element_b and so on
are used.
The object for the root element must already be created before parsing
starts, and the parser returns the (filled) root object. Because of this,
the user determines the *static* type of the object without the need
of back coercion (which is not possible in Ocaml).
----------------------------------------------------------------------
Newline normalization
----------------------------------------------------------------------
The XML spec states that all of \n, \r, and \r\n must be recognized
as newline characters/character sequences. Notes:
- The replacement text of entities always contains the original text,
i.e. \r and \r\n are NOT converted to \n.
It is unclear if this is a violation of the standard or not.
- Content of elements: Newline characters are converted to \n.
- Attribute values: Newline characters are converted to spaces.
- Processing instructions: Newline characters are not converted.
It is unclear if this is a violation of the standard or not.
----------------------------------------------------------------------
Empty entities
----------------------------------------------------------------------
Many entities are artificially surrounded by a Begin_entity/End_entity pair.
This is sometimes not done if the entity is empty:
- External parameter entities are parsed entities, i.e. they must match
the markupdecl* production. If they are not empty, the Begin_entity/End_entity
trick guarantees that they match markupdecl+, and that they are only
referred to at positions where markupdecl+ is allowed.
If they are empty, they are allowed everywhere just like internal
parameter entities. Because of this, the Begin_entity/End_entity pair
is dropped.
- This does not apply to parameter entities (either external or internal)
which are referred to in the internal subset, nor applies to internal
parameter entities, nor applies to general entities:
+ References in the internal subset are only allowed at positions where
markupdecl can occur, so Begin_entity/End_entity is added even if the
entity is empty.
+ References to internal parameter entities are allowed anywhere, so
never Begin_entity/End_entity is added.
+ References to general entities: An empty Begin_entity/End_entity pair
is recognized by the yacc parser, so special handling is not required.
Moreover, there is the situation that an empty entity is referred to
after the toplevel element:
<!DOCTYPE doc ...[
<!ENTITY empty "">
]>
<doc></doc>∅
- This is illegal, and the presence of an empty Begin_entity/End_entity pair
helps to recognize this.
