+++ /dev/null
------------------------------------------------- -*- 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 prdecessor 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 unambigously 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 orginal 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.
projects / helm.git / blobdiff