Parsing Techniques in Limpid

Parsing Character Input

Unless otherwise set, a character (byte) source is treated as UTF-8. This means that single-byte 7-bit ASCII, as well as a character encodings of up to 6 bytes are processed automatically.

The bytes are read from an input stream and processed by a CharacterConverter inside a Reader.

Forming Characters into String Tokens

A Reader is used by a TokenStream to assemble tokens. This is automatically managed on the basis of defined whitespace and defined single-character delimiters, selected by setWhitespace() and setDelimiters().

Environment	Whitespace Chars	Delimiter Chars
XML Parsing	" \n\t "	"=/\"\'!?"
DTD Parsing	" \n\t "	"<>()=,|*+?!#\"\'%&;"
XPath Parsing	" \n\t "	"|/^[]()=!@:,\"'$+-*<>"

Using the Tokens: XML

Nodes are constructed by XMLParser. This is quite straight-forward, involving a loop consisting of:

• Get a token from the TokenStream with nextToken();
• Identify the type of node to be constructed on the basis of the token;
• Constuct the node, using a combination of nextToken() and getDelimitedString() (eg, for getting attribute values).

Using the Tokens: DTD

DTD has a deceptive syntax, superficially like XML, but it is less regular and requires much more decision making during the parse. In Limpid, the information content of the DTD is extracted and used to construct a simple, but W3C-compliant, Schema document.

Using the Tokens: XPath

XPath has a complicated and flexible syntax. To be W3C-compliant, it is necessary to implement a full LALR (look-ahead left-to-right) parser. Unlike XML and DTD, the grammatical productions for XPath expressions have the following complications:

• Multicharacter tokens, such as ">=", "!=";
• Operator precedence, such as "<" before "and" before "or";
• Some of the grammatical productions are recursive;
• Characters are typically obtained from a string (DOMString or string literal), rather than from a file.

The steps involved in XPath processing are:

• Create a StringStream from the input;
• Wrap the StringStream in a TokenStream;
• Set the delimiter set for the TokenStream;
• Read the tokens and add them to a TokenHandler;
• Scan the TokenHandler and combine single-character tokens to form compound tokens (eg ">=");
• Process a stream from the TokenHandler to form a crude DOM;
• Process this DOM to apply precedence operators ("and" before "or") and obtain a structured document;
• Transform this document into an XPath instance.

This sequence has the same overall outcome as the stack-based approach in classical texts for LALR parsing, and shows very nicely just how useful the DOM can be for organizing complex data.