(c) Copyright 1996, Sunil Mishra (smishra@cc.gatech.edu)
All Rights Reserved
This is my second version of an HTML parser. This one is a string, rather than a stream, parser. The differences between it and the stream parser are rather small, so it should take a relatively small effort to convert it back to a stream parser. Please contact me if you want the source code for the last version of the stream parser.
The strong division of the parser into three distinct components should afford a great deal of flexibility while either extending the parser, or applying it in a new context. A more detailed description of each follows.
The DTD compiler is probably the weakest part of the parser, owing to my less than complete understanding of SGML. Given that it is a standalone system, extending or even replacing the compiler with something that produces output in a similar format should not effect the rest of the program.
The DTD compiler reads a DTD file translated from the source to LISP structures, and compiles it into a binary that thereafter does not require the compiler for use. A full SGML lexer and parser might be able to generate most of this structure automatically given a text input file, I do not have the skill or the knowledge to make take this direction. Further, given the quality of HTML out there, some non-SGML hacks have been necessary to make the DTD more useful.
The parameter entity definitions in the DTD are essentially ignored once the DTD has been compiled, and right now I do not have a reasonable mechanism for dealing with entity definitions. Within the scope of HTML, it is sufficient to know what the entity names are, and perhaps what they translate to. I have even ignored the translation part. It is not a priority for me. This should however be relatively simple to do, it should not require anything more than looking up an alist of entity-value pairs.
The lexer is fully contained in the file html-reader.lisp, except for some references to the tag definitions, and to the variable *eof*.
I have tried to make the lexer as SGML compliant as my knowledge would allow me to. Rules have had to be broken in some cases (such as when parsing CDATA sequences and handling broken open tag definitions) to handle some broken HTML out there. Extending the parser to include other SGML constructs (such as marked sections and the full parsing of declarations) should be relatively simple. One should be able to follow the conditionals to see how this works. I am not as sure of my handling of CDATA and PCDATA, but it is all I need given my requirements.
The lexer is based on the flex parser specification by Dan Connoly [1]. I have followed the spec as closely as possible on all matters that relate to HTML parsing, while leaving out aspects that are reported as errors. (I needed a parser, not a verification tool, though I see no reason why this cannot be used to build one.)
The lexer always preserves spaces in PCDATA that is in the context of a container that can contain it. Otherwise, strings consisting solely of whitespace are discarded. The application using the parser's output ought to decide if and how whitespace ought to be collapsed.
The parser is designed to deal with bad markup as well as it possibly can. It 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. This is, of course, broken, but is the result of a handful of heuristics I have applied to the parser:
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.
Also, if there is a non-standard comment at the start of the page, the comment would be treated as PCDATA. The HTML document would be started at that point, and end when the actual start of the HTML document is encountered. This is not desirable either.
I will more than likely come across other instances of markup that break the parser, and adding ad hoc fixes is the last thing I wish to do. I shall introduce new heuristics for dealing with problems as I gain a better understanding of what is needed.
The parser itself does not hold on to any structures it constructs. It is up to the program to do so by supplying an appropriate handler. It is fairly simple to ask the system to call the handler on the root tag HTML, and construct a structure for all the tags. It about as easy to extract all the anchors that have an HREF attribute.
This section discusses the internal data structures used in the HTML parser. It is not required knowledge for using the parser per se, but would be necessary for anyone that decides to use the output for anything useful. All these definitions are in HTML-PARSER:v6;defs.lisp.
Note that the term accessor is used here liberally. An accessor may be an accessor or a reader.
Each tag, after loading from the lispified DTD, is stored as an instance of the class html-tag. Each instance stores all that is known about the tag, and is pertinent to the parsing process. The pertinent accessors defined on each tag are:
The attributes are defined as independent structures. They have the following accessors defined:
The tags and attributes themselves may not be of much interest to most application programs. The document structre, when parsed, is available as instances of the class html-tag-instance, stored hierarchically. The top level is always an instance of HTML. The parser makes an effort to instantiate all implied openings and closings of tags.
The tag instances have the following accessors that might be of interest to an application:
The special character entities defined in HTML (such as >) are represented as tokens. They have no internal structure, nor is there any information associated with the characters. This was not an issue in the design of the parser. Unfortunately, there is no easy way to refer to the token, except through a function invocation:
(make-html-entity-token "gt" 0 2)
Using the parser falls into a three step process:
The first step is simple enough. It amounts to compiling the parser and the DTD with either the lisp server in memory, or not. The second step involves a call to the function
(html-parser:initialize-parser)
The main parser function is parse-html. It is advisable to call this function within a call to the macro with-tag-handler, otherwise a parsing context (in which tag structure is put together) shall never be established. In other words, the parser shall never return any results.
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 function to call when a specified context is completed. 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 cannot be present in the open tag markup. test is an optional generalized test that must return t for a context to be established. A context is established only if the conjuction of all the above conditions holds. body is executed within the established context. It may be anything, 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 &optional tags)
tags is the list of tags for which the structure has to be collected. It too can be a list of symbols or strings (including PCDATA and UNKNOWN) specifying which tags ought to be included in the collected structures. (I had considered including the specification for tags in with-tag-handler, but could not guage how valuable this would be.)
[1] See http://www.w3.org/pub/WWW/MarkUp/SGML/sgml-lex/sgml-lex