Here be dragons

The standard text on writing parsers and compilers is “Compilers. Principles, Techniques and Tools” by Aho, Sethi and Ullman. The book is so well known it has a nickname: “The Dragon Book”. This is because there is a picture of a dragon on the cover. Who says programmers aren’t creative? If you ever need to write a parser, never try to work out how to do it yourself. The area is well researched and excellent techniques are well known. All you need to do is apply them. The difference between a parser and a compiler is that a parser processes some text, providing information on its structure in a useful form. A compiler will contain a parser, but goes on to use its output to generate machine code. Usually compilers also make use of a symbol table, to store information about identifiers (like types, scope, number of parameters etc) and an error handler, to report errors, and possibly to take corrective action so that the remainder of the program can be parsed.

The phases can be simply described as follows:

1. Lexical analysis. This takes a stream of characters, and outputs a stream of tokens. A token is a non-divisible element of the language, like the keywords if or procedure, or the + and ; symbols are in Pascal. A sequence of characters that makes up a token is called a lexeme, hence the name. This phase is often responsible for removing whitespace (spaces, tabs and new lines) and recognising identifiers and keywords. Usually the lexical analyser recognises at least integers, instead of using grammar rules like the example given earlier. Regular expressions are usually sufficient to describe the actions needed, and they are often implemented as finite state machines.
2. Syntax analysis. This phase takes the stream of tokens and checks that they obey the grammar rules. The output from this stage is a hierarchical structure of tokens that I’m not actually going to describe, because it isn’t used in recursive descent parsers. Instead, the same information is implicit in the order of functions calls on the call stack. There is some flexibility in the division of labour between lexical and syntactic analysis. For example, sometimes whitespace is removed by the lexical analyser and sometimes by the syntax analyser.
3. Semantic analysis. This phase ensures that the program makes sense. This usually takes the form of type checking; making sure that you don’t multiply numbers and strings, for instance.
4. Code generation. This may result in either machine code, or an intermediate form like p-code. This enables the same back-end to be used for compilers for different languages. For instance, a Pascal and a C++ compiler might both produce p-code, and then use the same code optimisation and generation phases.
5. Code optimisation. Sometimes transformations can be made to make the code run more efficiently. Substituting actual values for constants,so they don’t need to be looked up at run-time, and taking advantage of instructions relevant to a particular microprocessor are simple examples.

Obviously, parsing an HTML file is going to have slightly different phases. A browser would replace code generation with producing an image of the page. Fortunately, we can stop at syntax analysis, at which point we will have enough information to produce our diagram. Basically, a parser consists of stages 1 to 3.

There are two easy ways to write a parser. One is to use to tools Lex and Yacc, which are freely available in several implementations (look for LexAndYacc.zip on the Delphi Super Page at http://sunsite.icm.edu.pl/delphi/ ). Their use is described in the Dragon Book. They are a little sophisticated for our purposes here, so we will use the other easy technique, recursive descent parsing, which is the easiest way to hand code a parser. Recursive descent is an example of a type of parsing scheme known as syntax-directed translation, which uses the grammatical rules to organise the code of the parser. The first step is always to define the grammar of the language we wish to parse. We then convert that grammar directly into code. Any changes or corrections are made the same way; change the grammar first, then change the code to reflect the new grammar. There is usually also a set of semantic rules, which specify what else to do, which might include type checking or updating the symbol table. For a larger project, these semantic rules should be more formally specified, but I am going to introduce them later on, when we get to write the parsing code.

To begin with, we need to define a few terms. A grammar defines the syntax of a language, that is, what that language looks like. It does not define the meaning, or semantics, of a language. Grammars are often defined using BNF, or Backus-Naur Form. This is itself an example of a context-free grammar, which have four components:

1. A set of tokens, known as terminal symbols.
2. A set of nonterminals, which are sequences of tokens.
3. A set of productions, which are the structuring rules of the grammar. Each production has a nonterminal on the left side, an arrow, and then a sequence of tokens and or nonterminals on the right side.
4. One of the nonterminals is defined as the start symbol.

In addition, BNF usually uses boldface strings to denote terminals, italics for nonterminals, and normal for tokens (usually numbers and symbols). We also usually use the symbol | to separate choices on the right side of a production. In Extended BNF, or EBNF, we use the symbols * and + to denote zero or more, and one or more instances of a terminal or nonterminal, respectively. (These operations are called Kleene closure and positive closure, by the way.) If we want to use either closure on a set of choices, the choices are enclosed in square brackets []. So, a set of productions that define how to write a number might be:

`number -> sign digitlist`
`sign -> + | - | ?`
`digitlist -> [0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9]+`

Here the symbol ? denotes the empty string. The rules can be read as:

“A number has the form of a sign followed by a digitlist, where a sign is the + symbol, or the – symbol, or a blank string (ie no symbol), followed by a list of at least one character from the integers 0 to 9 inclusive.”

We will use rules of this form to define HTML. As we aren’t interested in all possible elements of an HTML page, we will define only those portions of it that we need, but you will be able to extend the example easily enough if you wish. Recursive descent parsers have a set of recursive procedures to process the token stream, one procedure for each nonterminal in the grammar. For example, our simple grammar would have procedures called Number, Sign and DigitList, and the lexical analyser would just return single characters as tokens. When several rules (or productions) have the same noterminal on the left-hand side, they are combined into the one procedure.

At this point, we could get very boring, with tedious mathematical proofs, and talk about start and follow sets, canonical derivations and suchlike wonders. Instead, we’ll look very briefly at a couple of key concepts, and leave the details to Aho et al. One important notion is that of the lookahead symbol. As the name suggests, this is the next token in the input stream. It is used in predictive parsing to determine which grammar rule to use. So the lookahead symbol will used to determine the next procedure to call in our recursive descent parser. This is all a bit vague, so let’s consider another simple example grammar, used to define the form of simple expressions like 1 + 2, or 5 – 3. This example will also highlight an important point about writing grammars. Here are our rules:

`expr -> expr + term`
`expr -> expr – term`
`expr -> term`
`term -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9`

There is a problem with this set of productions. Suppose we begin at the start symbol, in this case expr (unless otherwise stated, the first nonterminal is considered to be the start symbol). The first production is fired, which looks for an expr, then a + token, then a term (ie a digit). When looking for an expr, the first rule is fired, and so on indefinitely. This is an example of a left recursive grammar. What we need to do is rewrite the productions so that the same language is defined, but where there is no left recursion. There is a formal method to use in these situations, which is well described in the Dragon Book, but basically we need to ensure that no rules have the form:

`A -> Ax`

The example grammar can be rewritten as:

`expr -> term rest`
`rest -> + expr | - expr | ?`
`term -> 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9`

Now we can unambiguously determine which production to apply. To make this a bit easier to follow, consider the following pseudocode:

`procedure expr;`
`begin`
`term;`
`rest;`
`end;`

`procedure rest;`
`begin`
`if lookahead = ‘+’ then`
`match(‘+’);`
`expr;`
`else if lookahead = ‘-‘ then`
`match(‘-‘);`
`expr;`
`else`
`Do nothing`
`end;`
`end;`

`procedure term;`
`begin`
`if IsDigit(lookahead) then`
`match(lookahead);`
`else`
`Raise error ‘digit expected’`
`end;`
`end;`

`procedure match(t : token);`
`begin`
`if lookahead = t then`
`lookahead := GetNextToken;`
`else`
`Raise error ‘t expected’`
`end;`
`end;`

Now it should be starting to become clear why this method of writing a parser is so simple. We simply rewrite the productions as code. There is an extra procedure match, which is used to simplify the other procedures. It gets the next token only if its argument matches the lookahead symbol. These procedures could be extended with code to provide the actions required by the semantic rules; evaluating the expression, for instance. To see how this works, try following this example through. Suppose we want to parse the string:

`7 – 2`

The steps are:

1. The start symbol is expr, so call that procedure. This calls the term procedure.
2. The term procedure finds the token 7, and returns to expr, which calls rest.
3. The rest procedure finds a – token, and therefore calls expr again (note the indirect recursion here).
4. The second instance of expr calls term, which finds the 2 token.
5. The second instance of expr calls rest again, which finds the empty set.
6. The second instance of expr returns to the first call of rest, which returns to the first call of expr, which then terminates.

The point of this little digression is that we need to make sure the grammar we use for parsing HTML files is not left recursive. Right recursion is fine, and will often lead to tail recursion in the code. That is, the last statement in a procedure is a recursive call of that same procedure. This can always be replaced by a while or repeat loop. Julian Bucknall wrote an excellent article on recursion in issue ?? which discusses how, and whether, to replace tail recursion.

Tag, you’re it

That’s probably sufficient background to start writing the HTML parser. Again, the first step is to write the grammar. We need to decide how much HTML we need to be able to decipher. Because we want to create a diagram with links between an HTML page and pages linked to it, along with any images used on the original page, we can ignore most tags, and only look for the following:

1. The A tag. The HREF attribute of this tag specifies the URL of a hypertext link.
2. The AREA tag. The HREF attribute of this tag specifies the URL of a hypertext link.
3. The BASE tag. This HREF attribute of this tag will modify any other URL on the page.
4. The FRAME tag. The SRC attribute of this tag specifies the URL of a hypertext link.
5. The IMG tag. The SRC attribute of this tag specifies the URL of a hypertext link, usually an image or video clip.
6. The LINK tag. The HREF attribute of this tag specifies the URL of another document that can be used in different ways in the current page. For example, if the REL attribute is set to STYLESHEET, the linked document is a style sheet. A style sheet is just a text file with instructions on how to modify some default characteristics of an HTML page. It is usually used to give a consistent look to all pages on a web site.
7. The TITLE and /TITLE tags. If it exists, we will use the document title as the name of the current page on the diagram. It is simple to parse, as the text between the start and end tags cannot contain any other HTML.

Note that we are ignoring the APPLET, BLOCKQUOTE, DEL, DIV, EMBED, HEAD, IFRAME, ILAYER, INPUT, INS, LAYER, META, OBJECT, Q, SCRIPT, SPAN, STYLE tags, all of which can have an URL as one of the attributes. You may like to add these yourself. In addition, we will want to ignore the content of comment and META tags, as they can contain all sorts of weird things.

The general form of an HTML tag is:

`<TAGNAME ATTRIBUTE1=value1 ATTRIBUTE2=value2 …>`

where TAGNAME can contain letters, numbers, hyphens and exclamation marks (<!-- --> and <!DOCTYPE> are legal tags). ATTRIBUTE tags generally contain only letters and hyphens, but because they can sometimes be event names, we will allow numbers as well. We will allow exclamation marks just to make the lexical analysis easier. If values contain anything other than letters, numbers, hyphens or periods, then they must be enclosed in double quotes. Also, in theory, every well-formed HTML document should have at least these elements:

`<!DOCTYPE>`
`<HTML>`
`<HEAD>`
`<TITLE>The document title goes here</TITLE>`
`</HEAD>`

`<BODY>`
`The actual document information goes here`
`</BODY>`
`</HTML>`

This is actually somewhat too complicated for our purposes, but it might be useful information for more sophisticated applications. You should note too, that in practice, many documents do not contain all these elements. We shall consider an HTML document to be simply a list of tags and data. All of this suggests the following grammar:

`Document -> [Tag | Data] +`
`Tag -> < TagName AttributeList > | < / TagName >`
`Data -> [any character except <]*`
`TagName -> Identifier`
`AttributeList -> [AttributeName AttributeRest]*`
`AttributeName -> Identifier | QuotedValue`
`AttributeRest -> = Value | ?`
`Value -> QuotedValue | PlainValue`
`Identifier -> [A..Z | a..z | 0..9 | - | !]+`
`QuotedValue -> “ [any character]* “`
`PlainValue -> [A..Z | a..z | 0..9 | - | .]+`

Notice that there is no left recursion in any production. Our semantic rules will involve recording information for certain attributes of the tags listed above. We will use a similar idea to the symbol table used in most compilers. For error handling, we will raise Delphi exceptions, as this will automatically release the call stack for us, and allow us to catch the exceptions in one place. The lexical analysis will be extremely simple, just returning tokens of one character. I have built in the capability to easily extend this if you wish. The definition of the parsing classes is shown below.

`interface`

`uses`
`SysUtils, Classes;`

`type`
`TjimToken = class(TObject)`
`private`
`FTokenType : Integer;`
`FAsString : string;`
`public`
`property TokenType : Integer read FTokenType write FTokenType;`
`property AsString : string read FAsString write FAsString;`
`end;`

`TjimLexicalAnalyser = class(TObject)`
`private`
`FText : string;`
`FPosition : Integer;`

`procedure SetText(const Value : string);`
`public`
`constructor Create;`

`procedure GetNextToken(NextToken : TjimToken);`
`property Text : string read FText write SetText;`
`end;`

`TjimSymbolType = (stTitle,stBase,stLink,stImage);`

`TjimSymbol = class(TCollectionItem)`
`private`
`FSymbolType : TjimSymbolType;`
`FSymbolValue : string;`
`public`
`procedure Assign(Source : TPersistent); override;`

`property SymbolType : TjimSymbolType read FSymbolType write FSymbolType;`
`property SymbolValue : string read FSymbolValue write FSymbolValue;`
`end;`

`TjimSymbolTable = class(TCollection)`
`private`
`function GetItem(Index : Integer) : TjimSymbol;`
`procedure SetItem(Index : Integer;Value : TjimSymbol);`
`public`
`function Add : TjimSymbol;`
`function AddSymbol(SymType : TjimSymbolType;SymValue : string) : TjimSymbol;`

`property Items[Index : Integer] : TjimSymbol read GetItem write SetItem; default;`
`end;`

`TjimHtmlParser = class(TObject)`
`private`
`FLookahead : TjimToken;`
`FLexAnalyser : TjimLexicalAnalyser;`
`FSymbolTable : TjimSymbolTable;`
`FLastTag : string;`

`procedure Match(T : Integer);`
`procedure ConsumeWhiteSpace;`
`procedure Document;`
`procedure Tag;`
`procedure Data;`
`procedure TagName;`
`procedure AttributeList;`
`function AttributeName : string;`
`function Value : string;`
`function Identifier : string;`
`function QuotedValue : string;`
`function PlainValue : string;`
`public`
`constructor Create;`
`destructor Destroy; override;`

`procedure Parse(const DocString : string);`

`property SymbolTable : TjimSymbolTable read FSymbolTable;`
`end;`

`EjimHtmlParserError = class(Exception);`

There are a couple of support classes to represent tokens and symbols. Should you wish to write a parser for your own purposes, these should function as templates you can build on. Usually, as here, the tokens have a type that is the ASCII value of the character, if they are single characters, otherwise it is some other predefined integer constant, outside the range 0 to 255. So, multiple character tokens would each need their own type. A common extra token type is a marker for the end of the document. We will use the constant ttEndOfDoc, defined to be –1. Obviously, the symbol table would need to store different information as well. Often this would include the type of the symbol (as in our application) which would then be used for type checking (which we won’t be doing). We will not go through the code for the lexical analyser as it is extremely simple, and you will easily be able to follow the code on the disk. Similarly, the symbol table and symbol objects are descended from TCollection and TCollectionItem, respectively, and are straightforward implementations as described in the Delphi help and Xavier Pacheco’s article in issue 10 (see how many opportunities to plug that CD-ROM I’m giving you, Mr Editor, do I get a commission?). Hopefully, the code for TjimHtmlParser will be easy to follow as well. A couple of examples should be enough to give you the gist.

`procedure TjimHtmlParser.Document;`
`begin {Document}`
`while FLookahead.TokenType <> ttEndOfDoc do begin`
`ConsumeWhiteSpace;`

`if FLookahead.AsString = '<' then begin`
`Tag;`
`end else begin`
`Data;`
`end;`
`end;`

`Match(ttEndOfDoc);`
`end; {Document}`

`procedure TjimHtmlParser.Tag;`
`begin {Tag}`
`Match(Ord('<'));`
`ConsumeWhiteSpace;`

`if FLookahead.AsString = '/' then begin`
`// Finding an end tag`
`Match(Ord('/'));`
`FLastTag := '/';`
`ConsumeWhiteSpace;`
`TagName;`
`end else begin`
`// Finding a start tag, or a tag that doesn't enclose anything`
`FLastTag := '';`
`ConsumeWhiteSpace;`
`TagName;`
`ConsumeWhiteSpace;`
`AttributeList;`
`end;`

`Match(Ord('>'));`
`end; {Tag}`

The procedure Document is the first procedure called when parsing a file, as it corresponds to the start symbol of our grammar. As you can see, it continues to process the file until the end of document marker is reached. We will consume whitespace in the parser rather than the lexical analyser, because in our simple example it is easier to manage. The lookahead symbol is sufficient for us to be able to determine which procedure to call next. If we follow the case where it is ‘<’, the Tag procedure will be called. In this procedure, the ‘<’ symbol is first matched, so that the next symbol is requested from the lexical analyser. After removing any whitespace, the lookahead symbol should be either a tag name, or the start of an end tag. To help us implement the semantic rules, we need to keep track of the last tag processed, so we will store its value in FLastTag. The TagName procedure collects the rest of the name, and if we are in a start tag, the attribute list is processed. The tag must end with a ‘>’ symbol. The other procedure are built in the same fashion. Some of them are complicated slightly because they are where our semantic rules are implemented. For instance, the TagName procedure steps through comment and META tags ignoring their content. The Data procedure collects the title of the document if the last tag was the TITLE tag, and having found it, adds it to the symbol table. The procedure that does most of the work, though, is AttributeList. It is shown below.

`procedure TjimHtmlParser.AttributeList;`
`var`
`FLastAttribute : string;`
`FLastValue : string;`
`begin {AttributeList}`
`while FLookahead.AsString <> '>' do begin`
`FLastAttribute := AttributeName;`
`ConsumeWhiteSpace;`

`if FLookahead.AsString = '=' then begin`
`Match(Ord('='));`
`ConsumeWhiteSpace;`
`FLastValue := Value;`
`ConsumeWhiteSpace;`

`// Should only get here if FLastAttribute is not an empty string`
`if (CompareText(FLastTag,'BASE') = 0) and`
`(CompareText('HREF',FLastAttribute) = 0) then begin`
`// Special case when found the HREF attribute of a BASE tag`
`FSymbolTable.AddSymbol(stBase,FLastValue);`
`end else if (CompareText(FLastTag,'IMG') = 0) and`
`(CompareText('SRC',FLastAttribute) = 0) then begin`
`// Found an image`
`FSymbolTable.AddSymbol(stImage,FLastValue);`
`end else if ((CompareText(FLastTag,'A') = 0) or`
`(CompareText(FLastTag,'AREA') = 0) or`
`(CompareText(FLastTag,'LINK') = 0)) and`
`(CompareText('HREF',FLastAttribute) = 0) then begin`
`// Found an ordinary link`
`FSymbolTable.AddSymbol(stLink,FLastValue);`
`end else if (CompareText(FLastTag,'FRAME') = 0) and`
`(CompareText('SRC',FLastAttribute) = 0) then begin`
`// Found an ordinary link`
`FSymbolTable.AddSymbol(stLink,FLastValue);`
`end;`
`end;`
`end;`
`end; {AttributeList}`

You can see that the syntactic work is done early. Our grammar states that an attribute list consists of a list of attributes after the tag name and before the ‘>’ symbol. Each attribute has a name, and possibly a value. In the case that the attribute does have a value, we need to check if it is one of the attributes we need for our diagram. So for our selected tags, we check the attribute name, stored in the local variable FLastAttribute, and if it is an URL we store it in the symbol table. This is the time that we determine the type of the URL, whether it is a BASE tag, an image, or another HTML file.

The remainder of the article is printed in the magazine.