(c) Copyright 1996-98,2000 Sunil Mishra <smishra@everest.com>
All Rights Reserved
The HTML Parser Generator is a software package written in Common Lisp for generating customized HTML parsers in Common Lisp. The parser is based on SGML semantics, and is partially validating. It comes with source code and some examples that demonstrate its flexibility. The parser features:
The parsers generated expect string input. A stream oriented parser may be developed in the future, if the need arises.
The framework is functionally decomposable into three modules. Each of these modules performs a functionally distinct task, though the implementation knits them closely together.
The DTD compiler translates a lispified DTD into an internal representation. The DTD is augmented with information used for recovering from source level errors in the parser. In processing the DTD, the compiler explicates the relationships between the different HTML tags, including expansions for the tags' content models. In doing so, it also locates the root tag for the HTML document, which is generally <html>.
The parameter entity definitions in the DTD can be ignored once the DTD has been compiled. The compilation process directly substitutes the values of these entities where they are used. Ordinary entity definitions are noted for future processing.
There are some differences in expressions that are found in a traditional DTD and the lispified version we use. Most of these differences stem from lisp having a prefix rather than infix syntax. Preserving the semantics of inlining used in SGML takes a little more work than the literal insertion mechanism used in the latter. Moreover, the operator names are different. We have introduced :or, :and, :sequence and :set keywords to provide the combinations that SGML uses. Repeated and optional elements are represented using the keywords *, + and ?. We have tried to preserve the semantics of these operations. If any differences exist, they should be considered bugs and reported.
As we have noted previously, the HTML parser is not a validating parser. It obeys some of the semantics of SGML, but notably it tries to correct commonly observed errors in writing HTML documents. This policy effects the implementation of the lexer as well as the parser.
The lexer is based on Dan Connoly's flex specification for SGML. Error reporting has been replaced by reasonable workarounds, and some of the less frequently employed SGML constructs have been given a reasonable interpretation. (Comments too are ignored, though all the code for reporting them is present in the lexer.) The lexer and the parser preserve whitespace. It is up to the application using them to interpret whitespace appropriately.
The lexer is fully contained in the file html-reader.lisp, and relies on information made available by the DTD compiler. The function next-html-token takes as input the parser state, and returns the next token in the HTML string. A token may be a string, an entity, a tag open or tag close marker, or a comment.
The parser generator provides a flexible framework for defining a customized HTML parser. We provide facilities for a programmer to define a finite state machine for the parser. It comprises some parsing contexts and a controller that selects contexts based on some defined conditions. The controller in principle acts upon defined parsing events and activates the appropriate context. The context then parses the document until an exit condition is met.
The macro define-html-parser is used for defining the controller, while define-html-parser-context produces a parser context. Both of these macros expand into lisp functions. The controller function defined through the former macro tests a set of conditions to select a context to execute. It then uses the context's return value to execute another context, until the HTML string is exhausted or an explicit exit is found. The context defines a set of events. Upon encountering one of these events, the corresponding lisp form is executed. Events may be defined on the opening or closing of a tag, on encountering data, or on encountering the end of the HTML string. Further details of the expansions are discussed under the macro descriptions.
This section walks through the interface functions and some utilities that the HTML parser system provides. The description is in terms of the role each individual piece plays, rather than how they connect to one another. Please look at the parser components overview for the big picture.
html-parser-token [class]
This is the base class for all HTML parser tokens. HTML parser tokens are
characterized by uniqueness and persistence. In other words, two references
to a token are guaranteed to refer to the same object in memory. And the
token may be compiled, with the guarantee that when loaded the token shall
maintain its identity. It has two subclasses: html-name-token and
html-entity-token.
html-name-token [class]
html-name-token is the subclass of html-parser-token used
for defining names in HTML. HTML names are defined to be case insensitve
objects that begin with an alphabetic character. They are used for
representing tag names, attribute names, and enumerated attribute
values. Given the frequency with which these symbols are accessed, we have
defined a reader macro, #t, for refering to name tokens. So, the
token #t"ul" names the tag UL.
html-entity-token [class]
html-entity-token is the subclass of html-parser-token
used for representing HTML entities. These tokens are case sensitive, and
are constructed by prefixing a #e to the string name of the
entity. For instance, #e"uuml" is the name token for the HTML
entity ü.
html-tag [class]
The data read from the lispified version of the DTD about HTML tags is
stored in instances of this class. We expect them to be of limited interest
in parser applications.
html-attribute [class]
Instances of this class are used to store information about the attributes
of the various tags. They are also used to index the tag attributes parsed
from an HTML document. They are again expected to be of limited interest to
parser application developers.
abstract-tag-instance [class]
This is the abstract base class of instantiated tags. Only two of its
subclasses, html-tag-instance and unknown-tag-instance,
are instantiated. Each instance names the class it instantiates, lists its
content (HTML tags, PCDATA and CDATA), its container tag, the attribute
values, and optionally the raw string that corresponds to this HTML tag.
An association list indexed by the attribute structure (or a name token if
the attribute is not defined in the DTD) is used to store attribute values.
The string content is a displaced string on the original input string,
otherwise the space requirements for this data might become
excessive. The string content should therefore never be
modified.
html-tag-instance [class]
This subclass of abstract-tag-instance is for representing
instances of tags defined in the DTD. It, or any of its subclasses, can be
used for this purpose. More information on this can be found in the macro definition for define-html-parser.
unknown-tag-instance [class]
This subclass of abstract-tag-instance is used for representing
instances of tags that are not defined in the DTD. It can be substituted
with any other of its subclasses. For more information, please refer to the
macro definition for define-html-parser.
parser [structure]
This is a transient structure for storing state information while parsing a
document. It contains the input string, the current state of the input
string, a stack containing the open tags the parser has seen, etc. This
data should never be modified by the application program.
tag-parser-data [structure]
We use instances of tag-parser-data to store data about tags as
they are parsed. This information is transient. It is created when a tag
is opened, and is stored on the parser stack. When the tag closes, this
information is used for finalizing the tag instance, and the structure is
discarded. It should not be modified by the application program.
*html-dtd-list* [constant]
This association list translates an HTML DOCTYPE to a lispified
DTD filename. The document type is not gathered from the HTML document, but
must be explicitly provided by the application programmer.
*current-dtd* [variable]
We store the document type in use in this variable. If the parser is not
initialized, this variable is nil.
*html-tags* [variable]
All the tags read from the DTD file are stored in this variable.
*dtd-toplevel-tags* [variable]
This variable stores the root tags for the DTD. Only the root tags
are not specified as the content of any other tag. They are
calculated during parser initialization.
*html-characters* [variable]
This variable enumerates the HTML character entities defined in the
DTD.
define-html-element [macro]
(names &key start-optional
end-optional attributes content
inclusions exclusions)
Defines one or more new HTML elements (otherwise called tags). The
structure of this macro deliberately mirrors the DTD definitions. The
difference is that the element and attribute definitions have been brought
together into a common definition. This arguably robs us of some
flexibility, but substantially improves clarity.
define-html-entity [macro]
(name value)
Defines a new entity. The entity may be a regular entity or a parameter
entity. A regular entity is available only outside the DTD for use, while a
parameter entity can only be used inside the scope of the DTD. (An
operational interpretation of this is that the parameter entities exist
only while the DTD is being compiled, while the regular entities exist only
when an HTML document is being interpreted.) Given that an entity name is
case sensitive, name must be an entity token or a
string. Value may be an arbitrary expression. The lispified DTD is limited
to approximating the behavior of a parameter entity in SGML, for literal
inlining in the lispified DTD would generate the wrong semantics. Please
send a bug report if any discripancies in behavior are found.
define-html-characters [macro]
(&rest characters)
As input, the macro expects strings. These strings are coerced to entity
tokens, and may be looked up when parsing a document.
define-html-parser [macro]
(name args &restforms)
The more elaborated syntax and description of this macro is given
below:
define-html-parser parser-name ({arg}* [&key {keyword-arg}*]
{other-arg-form}*)
[(:initialization {form}*)]
(:transitions transition-list)
arg-separator ::= &key | &rest | &aux
transition-list ::= [[ (:start context) |
{(last-context-name transition-test context)}* |
{(last-context-name transition-test :end)}* ]]
transition-test ::= t | symbol | string | html-name-token | function |
(:eval {form}*)
This macro expands into a function named parser-name. The lambda list of this function is a combination of some pre-defined arguments and those provided in lambda-list. The generated function has a lambda list of the form
(input-string {arg}*
&key :save-fragments :make-tag-instance-fn
{keyword-arg}*
{other-arg-form}*)
The role of the arguments introduced is as follows:
(defun parser-make-tag-instance (&rest initargs
&key instance-of &allow-other-keys)
(let ((name (name instance-of)))
(apply #'make-instance (if (eq name #t"UNKNOWN")
'unknown-tag-instance
'html-tag-instance)
initargs)))
When called, parser-name executes the initialization forms as an implicit progn, then begins the transition loop. The first transition taken is the one headed by :start. Each context is a function call to a parser context that returns two values - the name of the context and a second arbitrary value. These values are then used to select the next transition to follow. The head of the transition is compared to the first return value, that is, the name of the context, and the transitions's second element (transition-test) is treated as a predicate to test the second return value. The first transition to satisfy both test conditions is followed. A transition may have :end in its context position. Selecting this transition terminates parsing.
The transition-test on the second return value is interpreted as follows:
Parsing terminates automatically when the input string is exhausted.
define-html-parser-context [macro]
(namearguments &rest forms)
The full syntax and description of the macro is given below.
define-html-parser-context name ({arg}* [&aux {aux-arg}*])
[(:use-variables {use-variable}*)]
[(:on-open-tag {tag-conditional-form}*)]
[(:on-close-tag {tag-conditional-form}*)]
[(:on-pcdata {form}*)]
[(:on-cdata {form}*)]
[(:on-eof {form}*)]
tag-conditional-form ::= (tag-condition {form}*)
tag-condition ::= :any | tag-name | ({tag-name}*)
tag-name ::= symbol | string | html-name-token
This macro defines a function for an HTML parser context. The function named name has the following lambda list:
(parser {arg}* &aux {aux-arg}* {use-variable}* exitp exit-var)
The {form}* found in tag-conditional-form constitutes an implicit progn composed of arbitrary LISP expressions. It can include references to the following special forms and variables:
Each tag-conditional-form that matches the current tag is executed. Matching is limited to testing the name of the tag. The name can be specified as a symbol, a string or an html-name-token. A list of tags can be specified in place of a single tag. Alternatively, the keyword :any can be used to define some code to execute for any tag encountered.
contains [generic-function]
(tag-reference)
Returns the contents of the specified tag. The tag may be an
html-tag instance, a tag instance, or a tag name (symbol, string
or name token). Note that the results indicate the statically defined
content model from the DTD. This content model may be modified through the
DTD using inclusions and exclusions.
modify-dtd-list [function]
(document-type dtd-file)
Records a new document type, or modifies an existing one. Useful for
applications that wish to specify additional DTD's. The
document-type is a DTD document type declaration, and
the dtd-file is the pathname of the DTD file. If the
dtd-file is a string, it is assumed to be a file name
in the HTML parser directory. If it is a pathname, it is used as
specified.
tag-definition [generic-function]
(arg)
Finds the tag definition of the specified object. The tag of interest may be
specified through a tag instance or a tag name (as a string, symbol, or a
name token).
entity-definition [generic-function]
(arg)
Finds the value of the specified entity. The entity name can be expressed
as a string, symbol, or a name token.
tag-attribute-definition [generic-function]
(attribute tag)
Finds the definition of the given attribute in the
tag. attribute may be a name token
or a string, and the tag may be a string, a name token
or an html-tag definition.
subreference [function]
(vector &optional start end)
A simple utility function that constructs a displaced array reference to
the input vector. It does not make a copy of its input, so modifying the
resulting vector shall also modify the source vector. Its argument list
matches that of subseq. The default behavior is to create a
reference to the whole vector. One may optionally specify
start and end indices.
instance-of [generic-function]
(tag-instance)
Given a tag instance, this function returns the corresponding tag
definition.
token-name [generic-function]
(token)
Returns the string name of a token object.
initialize-parser [function]
(&optional doctype)
This function loads and initializes a DTD for use with the parser. The
default DTD is that for HTML 3.2. The only other option currently available
is loading the one for HTML 2.0. This function must be
called before a parser is invoked.
intern-name-token [function]
(token-name &optional replace-p)
Creates a new name token. Setting replace-p deletes the existing
token, which is similar to uninterning a symbol in its effect. This
operation should be applied with care.
intern-entity-token [function]
(token-name &optional replace-p)
Creates a new name token. Setting replace-p deletes the existing
token, which is similar to uninterning a symbol in its effect. This
operation should be applied with care.
file->string [function]
(path)
Returns the contents of the file indicated by path as a
string.
stream->string [function]
(stream)
Returns the contents of stream as a string.
name [function]
(object)
Returns the name of the html-tag indicated by
object, or nil if the object cannot correspoond to
an html-tag.
parts [function]
(tag-instance)
Returns the parts of tag-instance.
part-of [function]
(tag-instance)
Returns the tag that tag-instance is a part of.
html-fragment [function]
(tag-instance)
Returns the string fragment corresponding to tag-instance
in the input string.
attr-values [function]
(tag-instance)
Returns all the attribute-value pairs for the given
tag-instance.
attr-val [function]
(attribute tag-data &optional default-value error-if-not-found)
Tries to look for a value corresponding to attribute in
tag-data. attribute can be specified as a
string, symbol or an html-name-token. If not
found, default-value is returned, unless
error-if-not-found is set. Otherwise an error is
signalled.
parser-input [function]
(parser)
Returns the input string for a particular instance of
parser.
parser-stack [function]
(parser)
Returns the parser stack for a particular instance of
parser.
make-pcdata-string [function]
(parts &optional collect-alt-p)
Constructs a string out of the PCDATA contained in the
parts given to the function. If
collect-alt-p is set, each tag encountered is tested for an
ALT attribute. If found, the value of the attribute is collected,
otherwise the PCDATA contained within the tag is used.
html-whitespace-p [function]
(char)
Tests if the char is whitespace by HTML standards.
tokenize-name [function]
(string)
Constructs an instance of html-name-token from
string.
tokenize-entity [function]
(string)
Constructs an instance of html-entity-token from
string.
ensure-html-parser-tokens [function]
(tree &key ignore-if (destructive t))
Attempts to translate all items found in tree to an
html-name-token. All items that satisfy the predicate
ignore-if are skipped. If destructive is set, the tree is
modified destructively. Otherwise, parts of the tree that can be safely
reused shall not be duplicated while constructing a result tree.
As the name suggests, this parser does very little. It parses the HTML document, and returns the parsed structure. The code for the parser is in HTML-PARSER:html-utilities.lisp. The parser has one context that runs until the input is exhausted, or an HTML close tag token is encountered.
The syntax for calling the parser is
(simple-parser html-document
&key save-fragments make-tag-instance-fn)
where html-document is the HTML document stored in a string. The keyword arguments play the same role as in the description of the macro define-html-parser.
This is a more extended example demonstrating some of the additional flexibility that may be gained by defining a parser as a series of transitions in a DFA. The code for the parser is contained in HTML-PARSER:examples;handler.lisp, and needs to be loaded as an optional package.
The main parser function is parse-with-handler. It should be called in a context defined by the macro with-tag-handler. This macro establishes a call back condition. If on parsing some HTML tag the conditions defined by the macro are satisfied, the specified handler is called. These contexts may be nested to form a hierarchy. Without a context, the parser shall parse the document but never process any of the data generated from the parse.
with-tag-handler has the following lambda list:
(with-tag-handler (<tags> <handler-function> &key <with-attributes> <without-attributes> <test>) <body>)
tags is the list of tags for which a context should be established. This may be a symbol, list of symbols or strings, or the value t which stands for all tags. The symbols or strings should be names of tags for which to establish contexts, or PCDATA, or UNKNOWN. handler-function is the call-back function for the context. with-attributes is a list of attributes that must be present in the open tag markup, and without-attributes is a list of tags that should not be present in the open tag markup. test is an arbitrary lisp predicate that determines if the desired context is present. A context is said to be present only if the conjuction of all the above conditions holds. body is executed within the established handler. It may be any lisp form, including other with-tag-handler specifications (which provides a mechanism for specifying multiple handlers), and one or more calls to parse-html.
parse-html has the lambda list
(parse-html input &key tags save-fragments make-tag-instance-fn)
tags is the list of tags which have to be present in the resulting parse structure. It too can be a list of symbols or strings, including PCDATA and UNKNOWN. (I had considered including the specification for tags in with-tag-handler, but could not guage how valuable this would be.) save-instance-fragments, html-tag-instance-class and unknown-tag-instance-class have their usual function.
The function html-parse-result is a simple example of how the handler call-back mechanism is supposed to be used. It takes an input path as a string or a pathname, and invokes the parser on the specified file. The return value is a parse of the HTML document rooted in an instance of the HTML tag.
This example demonstrates how the parser may be linked in with the World Wide Web Walker (w4) in the CL-HTTP system. It takes one of the examples in the CL-HTTP package, show-web-link-map, and redefines it to use the parser to collect all links in the document. For this example to work, it is necessary to first load the CL-HTTP system, then the HTML Parser Generator. Then, the W4-WEB-WALKER and the W4-WEB-WALKER-DEMOS need to be loaded. Finally, the parser definition and additional functions the example needs are in the file HTML-PARSER:examples;parser-show-link-map.
When this is done, the example should work as before, collecting links from not only the a tag, but also from the img and link tags. Access the page /cl-http/w4.html relative to the CL-HTTP server, and follow the link to the show-web-link-map example. Use the form to generate the trace for all nodes starting from a WWW page.
There are two forms of the HTML parser available. The primary distribution of the html-parser is available through the lambda-codex at SourceForge. The HTML parser depends on mk-defsystem, plist and tokenizer packages. Installation instructions should also be available at the lambda-codex home page.
Another distribution is present in the Common Lisp Hypermedia Server (cl-http). This version uses the tokenizer and propery list packages in the cl-http distribution. As a result, there is one difference with the primary distribution at SourceForge. The function clear-parameter-entities is undefinable, as the cl-http tokenizer does not define a function for mapping over tokens.