The HTML Parser Generator


(c) Copyright 1996-98, Sunil Mishra (smishra@cc.gatech.edu)
    All Rights Reserved

Features
Parser Components
Parser Interface
Examples

Features

The HTML Parser Generator is a semi-SGML compliant framework for generating customized HTML parsers. It comes with source code and a couple of examples that demonstrate its flexibility. Some of the major features are listed below:

Modular and extensible design maximizes flexibility.
Explicit representation of the DTD allows a new DTD to be easily substituted.
Includes DTD's for HTML 2.0 and HTML 3.2.
Thread safe, which allows multiple parsers to run simultaneously.
Can be used independently or in conjunction with CL-HTTP.
Allows partial and selective parsing of HTML documents for improved efficiency.
Portable across several flavors of LISP in a variety of environments.

The parsers generated are string based. If this is inconvenient, a considerably older, less powerful and unsupported stream based parser is available.

Parser Components

The parser has been divided into three distinct modules. This approach should simplify the process of modifying and adapting the parser to a new purpose. A more detailed description of the parser components follows.

DTD Compiler

The DTD compiler provides a means for translating a lispified DTD into a form usable by the parser. The input, in the form of a lispified DTD, is augmented with additional information that is required for additional fault tolerance. The output is a set of data structures that contain the relationships specified in the DTD. As long as these constraints on the input and output are obeyed, this module may be safely replaced with another mechanism without interfering with the other components.

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 simply noted.

Lexer

This parser is designed to handle HTML as it commonly appears, rather than to produce a parser that is fully SGML compliant. Consequently, this lexer does not implement all the constructs SGML specifies. Extending the lexer to deal with other SGML constructs (such as marked sections and the full parsing of declarations) should involve relatively straightforward extensions to the existing code.

The lexer is based on Dan Connoly's flex specification. Error reporting has been replaced by reasonable workarounds, and the additional SGML constructs mentioned have been ignored. Comments too are currently ignored, though all the code for reporting them is present in the lexer. The lexer and the parser always preserve spaces. It is up to the system using them to deal with whitespace appropriately.

The lexer is fully contained in the file html-reader.lisp, except for some references to the tag definitions, and to the constant *eof*. (In MCL *eof* is a variable.) The function next-html-token takes an input a parser structure, which contains the state of a parse process. Encapsulating the state into a structure allows a program to run multiple instances of the parser simultaneously. A call to next-html-token returns the next token in the remaining unprocessed HTML. A token may be a string, an entity, a tag open or tag close marker, or a comment. So long as these constraints are satisfied, the lexer may be modified in any manner.

Parser Generator

The parser generator provides a flexible framework for defining a customized HTML parser. The parser defined is in the form of a DFA. It consists of a set of contexts and conditions for making context transitions. The transitions are defined in a highly constrained language that allows for testing arbitrary conditions. The contexts are where the actual parsing takes place. They employ a language that can be used to specify LISP code to execute when various parse events are encountered. The events of interest are the opening and closing of an HTML tag, and parsing of PCDATA. Along with arbitrary LISP code, special forms for performing specific functions are available.

The parser generator is built around two macros. The first, define-html-parser, defines a function that handles the parser's context transitions. Each context is embodied within a function defined using the macro define-html-parser-context. The context function should not be called directly, but only through the parser function. Given below is the relationship between the parser definitions and the functions they turn into. Further details of the syntax are discussed under the macro descriptions.

The two macros are designed to resemble LISP function definition macros (such as defun). The macros augment the lambda list with some standard arguments, which will be discussed below.

The primary parser function (defined through define-html-parser) has relatively little functionality. It is intended to hand control over to some context, or end the parse process if necessary. The macro's syntax limits the parser function to testing the return value from the last context, and selecting the next context to execute. Four paramters are added to the argument list the macro receives. The exact form of the resulting argument list is presented under the macro descriptions.

input: This is the HTML string input for parsing.
:save-fragments: If this keyword argument is set, the part of the input string corresponding to each HTML tag parsed is saved. Note that this string shares its structure with the original input string, so modifying it is not advisable.
:html-tag-instance-class: The value of this keyword argument determines the class of the tag instances the parser creates. The default value is html-tag-instance. Any value given to this argument should be a subclass of html-tag-instance.
:unknown-tag-instance-class: As with html-tag-instance, this keyword argument determines the class of the tag instances created for those tags that are not present in the DTD. Again, any value this argument receives be a subclass of unknown-tag-instance.

The input string is parsed entirely within the various parser contexts used. The syntax provided allows the user to embed arbitrary LISP code in places where an event might be expected. An event in the course of parsing HTML is opening a tag, closing a tag, or reading some data. Event processing can be conditionalized by the name of the tag parsed. All PCDATA however is passed through the same LISP code. Each context is allowed to return a single value, which may be used by the parser to select the next context to execute. The context's function thus is to correctly order the various HTML tags extracted, for processing by the user defined LISP code. This process is complicated by the presence of implicit tag opens and closes, and incorrect HTML.

Each context provides two special forms for handling HTML data that is automatically bound to some variables. Both the variables and the forms have a syntax identical to ordinary LISP functions and variables. All of these are described below.

parser: This variable is bound to a data structure that describes the parse process, including the input string, the stack of open tags, and the current state of the input. This data should be treated as read only information.
it: This variable is bound to the current structure being processed. The structure may be explicitly present in the HTML, or its existence may be inferred from the input context. It can be either a tag or PCDATA.
start: This variable holds the start position of the current token in the input string. For an open tag, it tells where the open tag token begins. For a close tag, it tells where the close tag token begins.
end: This variable stores the end position of the current token in the input string. Like start, it is relative to the token, and not the tag as a whole.
(save data): Calling this special form tells the parser to save the indicated data, which can either be PCDATA or a tag. Only the first call on a tag is effective. All subsequent calls are ignored. Although the structure saved can be something other than the last token read, doing so with tags can involve playing with the internals of the parser. A far better method for saving customized structures is to subclass html-tag-instance and uknown-tag-instance, and include in them special purpose slots. Saving involves linking the structure to the last surrounding tag that was saved. Saving a tag when it is opened enables all the children of the tag to be saved under it. On the other hand, saving a tag when it is closed results in a situation where any children saved are linked to the parent of the tag, altering the structure of the HTML in a possibly undesirable manner.
(exit-context value): This special form tells the context to exit as soon as possible, returning the value value. Once seen, all code that follows it is ignored. Only clean-up operations, such as processing the implied opening and closing of tags, are performed. The function takes an optional argument that acts as a return value from the context.

Using such a defined parser is quite straightforward. The function initialize-parser may optionally be called if a DTD other than the default DTD is to be used. The parser function can then be called with the input, the other arguments required, and the optional keyword arguments. Some optional initialization code is executed, then the start context is called. Its return value is tested to determine the next context to execute. This cycle continues until either the input is exhausted, or an end transition is encountered. An unaccounted transition results in an error. The return value of the parser is the return value of the last context executed.

When a context is first entered, all the open tags on the parse stack are tested against the conditionals defined for open tags. A tag is processed no more than one time in any given context. Once the tags on the stack have been processed, the next token is taken from the input string. The context continues to extract tokens so long as the exit-context special form is not encountered, and some input remains to be processed. If the parser runs out of input while in a context, it executes the :on-eof forms.

The parser does not enforce or consider the many ordering or repetition rules that the DTD defines. It only deals with inclusion, exclusion and containement constraints. So, one might be able to have two bodies within a single HTML document. Although broken, it allows the parser to recover a parse of all the parts of the document. This amounts to handing over other decisions to whatever program is using the parser.

It is somewhat more difficult to produce a reasonable parse of a document while ignoring containment rules. The following rules describe how the parser deals with out of context tags:

Search the stack of open HTML tags to find a tag that may contain the out of place tag.
If there is no such tag on the stack, recursively apply this rule to the tag that is the most likely container of this tag.
If the tag is an unknown, it can fall under any tag with a non-empty content, and can include any tag.

For example, if a lone <li> is found immediately inside a <body>, the the parser shall check the stack to see if there is a tag on the stack that can contain the <li>. Since its immediate container is <body>, no such tag is present. The most likely container for an <li> is defined to be a <ul>, which is then put on the stack as the container of the <li>.

These are often not the right heuristics to apply while parsing a page. Instances of input that would break the parser include <a ...><h1>foo</h1</a>, a relatively common construct. The parse result would look like <a ...></a><h1>foo</h1>, which is certainly undesirable. Another place where this breaks is if the document begins with an incorrectly defined comment. Such a comment is treated as PCDATA. Consequently, the start of the <body> is assumed to be at this point. Ignoring ordering and numerical constraints allows us to proceed to parse the entire document, and then let the larger application decide how to treat the entire document. Though not ideal, this solution does leave us with the ability to recover.

Parser Interface

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.

Data Structures

html-parser-token [class]
These are defined based on the tokenizer from CL-HTTP. They are used to name various objects. html-parser-token is an abstract class, of which no instances are contructed. It's subclasses are 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. These names can be tag names and attribute names, both of which are case insensitive. They are constructed by attaching a #t in front of the string form of the token name. For instance, #t"ul" corresponds to the name token for 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 &uuml.

html-tag [class]
The data read from the lispified version of the DTD about HTML tags is stored in instances of this class. These are likely to be of limited value when parsing an HTML document.

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.

abstract-tag-instance [class]
This is the class of all the instantiated tags. Its subclasses, rather than it, should be instantiated. The class has slots for the tag it instantiates, the HTML parts (tags and PCDATA) within the tag instance, the tag it is a part of, the attribute values defined for the tag, and the part of the HTML document this tag represents. The attribute values are stored as an association list, indexed on the attribute structure in the tag definition. If the attribute is not defined in the DTD, the html-name-token corresponding to the attribute name is used.

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 information about the particular parse process. 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 only be modified by the internals of the parser.

tag-parser-data [structure]
This structure stores transient information about HTML tags as they are parsed. These structures, rather than tag instances themselves, are stored on the parser stack mentioned above.

Variables and Constants

*html-dtd-list* [constant]
This association list translates an HTML DOCTYPE to a lispified DTD filename. It is not currenly used.

*current-dtd* [variable]
This variable stores the DTD loaded while initializing the parser. If nil, the parser is not initialized.

*html-tags* [variable]
This is a list of all the tags read from the DTD file.

*html-root* [variable]
This variable contains the root tag for the DTD. The root tag is the only tag that does not have a container. It is calculated, rather than arbitrary set to the HTML tag.

*html-characters* [variable]
This variable enumerates the HTML character entities defined in the DTD.

Macros

define-html-parser [macro] (name args &rest forms)
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 that executes some initialization code, followed by a series of context transitions. The optional initialization code is executed as an implicit progn. The lambda list of the generated function takes as input a combination of some pre-defined parameters and those provided in lambda-list. The generated function has a lambda list of the form

(input-string {arg}* &key :save-fragments :html-tag-instance-class
                          :unknown-tag-instance-class {keyword-arg}*
                     {other-arg-form}*)

The macro expansion, in other words, adds some arguments to the lambda list given to the macro. These arguments have the following roles:

input-string: This is the HTML string input for parsing.
:save-fragments: If this keyword argument is set, the part of the input string corresponding to each HTML tag parsed is saved. Note that this string shares its structure with the original input string, so modifying it is not advisable.
:html-tag-instance-class: The value of this keyword argument determines the class of the tag instances the parser creates. The default value is html-tag-instance. Any value given to this argument should be a subclass of html-tag-instance.
:unknown-tag-instance-class: As with html-tag-instance, this keyword argument determines the class of the tag instances created for those tags that are not present in the DTD. Again, any value this argument receives be a subclass of unknown-tag-instance.

The transitions list defines the desired context transitions. The first context executed is the one headed by :start. Each context is a function call to a parser context that returns a two values - the name of the context and a second arbitrary value. context may be replaced by :end, in which case the parse process is terminated. An ordinary context transition is headed by the name of the last context executed, and a test on the return value of the context. The test is interpreted as follows:

t: The transition is made without performing any tests.
symbol | string | html-name-token: If not already an html-name-token, the test object is translated to one. This value is then compared using eq with the generic function name applied to the return value of the last context. (name tries to coerce its input to an html-name-token.) The format for specifying an html-name-token is #t"tag-name", where tag-name is a case insensitive name for the tag. For instance, #t"img" is the token for the HTML tag img.
function: The return value of the last context is passed as an argument to the specified function. The transition is made if the function does not return nil.
(:eval {form*}): {form*} is evaluated as an implicit progn. The return value is compared via eq to the result of calling the generic function name on the return value of the last context.

Parsing terminates automatically when the input string is exhausted.

define-html-parser-context [macro] (name arguments &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-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 constitute an implicit progn composed of arbitrary LISP expressions. They can include references to the following special forms and variables:

parser: This variable is bound to a data structure that describes the parse process, including the input string, the stack of open tags, and the current state of the input. This data should be treated as read only information.
it: This variable is bound to the current structure being processed. The structure may be explicitly present in the HTML, or its existence may be inferred from the input context. It can be either a tag or PCDATA.
start: This variable holds the start position of the current token in the input string. For an open tag, it tells where the open tag token begins. For a close tag, it tells where the close tag token begins.
end: This variable stores the end position of the current token in the input string. Like start, it is relative to the token, and not the tag as a whole.
(save data): Calling this special form tells the parser to save the indicated data, which can either be PCDATA or a tag. Only the first call on a tag is effective. All subsequent calls are ignored. Although the structure saved can be something other than the last token read, doing so with tags can involve playing with the internals of the parser. A far better method for saving customized structures is to subclass html-tag-instance and uknown-tag-instance, and include in them special purpose slots. Saving involves linking the structure to the last surrounding tag that was saved. Saving a tag when it is opened enables all the children of the tag to be saved under it. On the other hand, saving a tag when it is closed results in a situation where any children saved are linked to the parent of the tag, altering the structure of the HTML in a possibly undesirable manner.
(exit-context value): This special form tells the context to exit as soon as possible, returning the value value. Once seen, all code that follows it is ignored. Only clean-up operations, such as processing the implied opening and closing of tags, are performed. The function takes an optional argument that acts as a return value from the context.

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.

Functions

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.

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.

Examples

Simple Parser

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 :html-tag-instance-class
                                    :unknown-tag-instance-class)

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.

Parser with Handler Call-back

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 html-tag-instance-class
                               unknown-tag-instance-class)

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.

Parser for Collecting Links

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.

The HTML Parser Generator

Contents