parsing-brainstorming
Introduction
This is an attempt to get some of my thoughts on parsing, from practical experience implementing Cognition, out of my head and onto the wiki. Hopefully it will replace parsing once it reaches consensus, as this document is somewhat more detailed. It deals with how to parse the properties of a compound microformat once we have located the root element, which we shall call root
. It deals with simple properties which have no sub-properties (such as fn
in hCard), and with properties which may include an embedded microformat (such as agent
in hCard) — 95% of properties do fall into these categories. (Many of the others can be parsed by treating the property element as root
and then finding sub-properties using the techniques on this page, but some do occasionally require special handling.) TobyInk
Contributors
Primary Author: Toby Inkster (TobyInk)
Licence
The author of this page releases the algorithms described into the public domain.
Additionally, a working implementation of these algorithms (in Perl) is available as part of Cognition. The implementation is not released into the public domain, but is licensed under the GNU General Public License (version 3).
General Algorithm
- Make a copy of the DOM tree to operate on. All future references to DOM traversal and manipulation refer to this clone.
- Implement the include pattern by removing any nodes with
class="include"
and replacing them with the node which they point to. (Unless the node pointed to is a parent node of the node withclass="include"
!!) - Parse all properties that may contain nested microformats. For example within hCard, the agent property may contain a nested hCard. For each property
prop
which may contain a nested microformat:- Create an empty array to store the value(s) of
prop
in. Call thisA
. - Find all elements with
class="prop"
that are descended fromroot
. Call this listP
. - Create an empty list
E
. - For each element
p
inP
:- Let
ok
be true. - Let
a
by the parent node ofp
. - While
a
is not the root element of this microformat:- If
a
has a class attribute which indicates that it is a nested microformat (e.g.class="vevent"
) then setok
to false - Set
a
to the parent ofa
.
- If
- If
ok
is true, then pushp
ontoE
.
- Let
- OUTER: For each element
e
inE
:- INNER: For each microformat root class name that might be present (e.g. within an hCalendar event's
location
property you might reasonably expect to find an hCard, and adr or a geo!):- Create an empty list
F
. - Search for any elements within
e
which have the microformat root class name. Bear in mind that perhaps this element might bee
— this is allowed. For each such element,e2
:- Parse
e2
as an embedded microformat and place the result inF
if it is valid. - Run the DESTROY_ELEMENT function on
e2
- Parse
- If
F
is not empty:- Move the first item in
F
toA
- Jump out of the INNER loop.
- Move the first item in
- Create an empty list
- If
A
is not empty:- Change the
class
attribute one
, removingprop
from the class list. - If property
prop
is singular, jump out of the OUTER loop.
- Change the
- INNER: For each microformat root class name that might be present (e.g. within an hCalendar event's
- If
prop
is a singular property, letA[0]
be its value. If plural, letA
be the list of its values.
- Create an empty array to store the value(s) of
- Run the DESTROYER function on
root
.- Depending on what microformat you're parsing, you will want to pass a further parameter to DESTROYER indicating a list of microformats to "save" from destruction. This allows for the simple string/url/datetime/etc properties to be included within nested microformats. So far, the only case I've found where this is beneficial is when parsing hCard, it is useful to save adr and geo from destruction. This enables the
fn
property to be set on address components, e.g.:<div class="vcard">
- Depending on what microformat you're parsing, you will want to pass a further parameter to DESTROYER indicating a list of microformats to "save" from destruction. This allows for the simple string/url/datetime/etc properties to be included within nested microformats. So far, the only case I've found where this is beneficial is when parsing hCard, it is useful to save adr and geo from destruction. This enables the
<p class="adr"> <span class="org"> <strong class="fn organization-unit extended-address">Chemistry Library</strong>, <span class="organization-name extended-address">Fictional Institute of Science</span>, </span> <span class="street-address">123 Example Street</span>, <span class="locality">Testville</span>. </p>
</div>
- Parse all properties. There are three different categories of property — singular, plural and concatenated. Most properties are either singular or plural, but a handful are concatenated, such as
entry-summary
in hAtom. For each propertyprop
withinroot
:- Create an empty array to store the value(s) of
prop
in. Call thisA
. - Find all elements with
class="prop"
that are descended fromroot
. - For each element
e
, run this:- Find the value of
e
, using the techniques in the section below. - If the value of
e
is not NULL, add it toA
- If the
prop
is a singular property andA
is not empty, jump out of this foreach loop.
- Find the value of
- If
prop
is a singular property, then its value isA[0]
. - If
prop
is a plural property, then its values areA
. - If
prop
is a concatenated property, then its values are formed by concatenating the values ofA
together.
- Create an empty array to store the value(s) of
Finding Values
There are at least five different types of property that can be parsed, each of which requires different techniques:
- HTML properties, such as
entry-content
in hAtom - URI properties, such as
url
in hCard - ID properties, such as
uid
in hCard - Datetime properties, such as
dtstart
in hCalendar - Plain text properties, such as
title
in hCard
Arguments can be made for duration properties and numeric properties to also have variations in the algorithm, but for now, we'll just treat them as plain text properties.
Generally speaking, the mechanism for going from an element e
to a value is to use the first "hit" from the following:
- Look at relevant attributes (e.g.
datetime
if we're looking for a date, orhref
if we're looking for a URI). - Look for any descendants with
class="value"
. - Look at the node contents.
This is described in more detail below, for each type of property.
HTML Properties
These are the easiest to parse. Given an element e
, just use the HTML representation of its DOM node. Some DOM implementations make this available as .outerHTML
.
URI Properties
Certain HTML elements are capable of linking to other resources. The most obvious is <a>
though there are many others. The following list of linking elements is derived from Perl's HTML::Tagset module:
{ 'a' => ['href'], 'applet' => ['codebase', 'archive', 'code'], 'area' => ['href'], # 'base' => ['href'], 'bgsound' => ['src'], 'blockquote' => ['cite'], # 'body' => ['background'], 'del' => ['cite'], 'embed' => ['src', 'pluginspage'], 'form' => ['action'], 'frame' => ['src', 'longdesc'], 'iframe' => ['src', 'longdesc'], # 'ilayer' => ['background'], 'img' => ['src', 'lowsrc', 'longdesc', 'usemap'], 'input' => ['src', 'usemap'], 'ins' => ['cite'], 'isindex' => ['action'], # 'head' => ['profile'], 'layer' => ['src'], # 'background' 'link' => ['href'], 'object' => ['data', 'classid', 'codebase', 'archive', 'usemap'], 'q' => ['cite'], 'script' => ['src', 'for'], # 'table' => ['background'], # 'td' => ['background'], # 'th' => ['background'], # 'tr' => ['background'], 'xmp' => ['href'], }
Note that some are commented out as they might be too counter-intuitive to implement!
If we're parsing an element e
and looking for a URI, here is the algorithm we use:
- Set variable
u
to NULL. - Search
e
for any descendent elements withclass="value"
. Call this listV
. - Add the element
e
itself to the listV
, at the front of the list. - OUTER: for each element
v
from listV
:- If
v
is a linking element from the above list- INNER: for each attribute
a
associated that the tag name ofv
in the above list- If
a
is set- Set
u
to the contents ofa
- Jump out of the OUTER loop.
- Set
- If
- INNER: for each attribute
- If
- If
u
is not null, and is a relative URI, convert it to an absolute URI.
The URI has hopefully been found in u
. If no URI has been found, then fall back to plain text parsing.
UID Properties
UID properties are parsed similarly to URL properties, but with a slightly modified algorithm, allowing for UIDs to be specified in the id
attribute. The following example has a UID of "http://example.com/page#foo".
<base href="http://example.com/page" /> <div class="uid" id="foo">...</div>
The modified algorithm used is:
- Set variable
u
to NULL. - Search
e
for any descendent elements withclass="value"
. Call this listV
. - Add the element
e
itself to the listV
, at the front of the list. - OUTER: for each element
v
from listV
:- If
v
is a linking element from the above list- INNER: for each attribute
a
associated that the tag name ofv
in the above list- If
a
is set- Set
u
to the contents ofa
- Jump out of the OUTER loop.
- Set
- If
- INNER: for each attribute
- If
v
has anid
attribute set- Set
u
to the contents ofid
, with the character "#" prepended - Jump out of the OUTER loop.
- Set
- If
- If
u
is not null, and is a relative URI, convert it to an absolute URI.
Again, if no u
has been found by the algorithm, then fall back to parsing it as a plain text property.
Datetime Properties
Parsing property prop
, if class="prop"
is found on element e
.
- If element
e
has an attributedatetime
, then the content of that attribute is the value and the rest of these steps should be skipped. - Create a list
D
, which is empty. - Create a list
V
of elements withclass="value"
. - For each element
v
inV
:- If
v
has an attributedatetime
, then add the content of that attribute toD
- Otherwise, run the STRINGIFY function on
v
and add the result toD
- If
- If
D
is empty, then run the STRINGIFY function one
and let the result be the value, and skip the rest of these steps. - If
D
contains only one item, and it looks like an ISO date or ISO datetime, then let that be the value, and skip the rest of these steps. - If
D
contains two items, and the first looks like an ISO date, and the second like a time, concatenate them, joining with an upper case 'T', let that be the value, and skip the rest of these steps. - If
D
contains three items, and the first looks like an ISO date, the second like a time, and the last like a timezone (may need normalisation), concatenate them, joining the first two with an upper case 'T' and the last one with no intervening character, let that be the value, and skip the rest of these steps. - Concatenate all the items in
D
and let that be the value.
The final value should be interpreted as liberally as possible with regards to punctuation as an ISO date or ISO datetime.
Normalizing Timezones
Where S is a sign (+ or -) and the letters a, b, c, d are numerals, then:
- Sa → S0a00
- Sab → Sab00
- Sabc → S0abc
- Sa: → S0a00
- Sab: → Sab00
- Sa:b → S0ab0
- S:ab → S00ab
- Sa:bc → S0abc
- Sab:c → Sabc0
- Sab:cd → Sabcd
Plain text Properties
To obtain the value of the property, run STRINGIFY on the property node.
Stringification
The STRINGIFY function performs a text serialisation of an HTML node, with a few adjustments to implement the ABBR pattern. It uses a helper function, _STRINGIFY.
STRINGIFY
- First parameter: element to stringify,
e
. - Second parameter: whether to perform value excerpting - default yes.
- Third parameter: whether to perform abbr pattern - default yes.
- If
e
is an<abbr>
or<acronym>
element, and has atitle
attribute, then return that attribute. - If you want to implement any proposed alternatives to the ABBR pattern, then here is the place to do so.
- If value excerpting is enabled:
- Create an empty list
S
- Search for any descendant elements of
e
withclass="value"
. Put these into a listV
. - For each element
v
inV
- Recursion: call STRINGIFY on
v
, disabling value excerpting but enabling the ABBR pattern. Add the result toS
.
- Recursion: call STRINGIFY on
- Concatenate the items in
S
to form a string. If this string is not empty, then return the string.
- Create an empty list
- Run _STRINGIFY on
e
, trim excess white space from the result and return it.
_STRINGIFY
This is a somewhat simplified version of the real algorithm that I use. You probably want to refine it by adding better whitespace handling rules (e.g. line breaks after block elements, asterisks for list items, etc).
_STRINGIFY is called with one parameter, the element e
to be stringified.
- If
e
is text node (not an element), then return it. - If
e
is an<img>
tag, return thealt
text. - If
e
is an<input>
tag, return the text of thevalue
attribute. - If
e
is an<br>
tag, return a linebreak character. - If
e
is an<del>
tag, return a zero-length string. - Otherwise, create an empty list
S
. - For each direct child node
c
ofe
:- Run _STRINGIFY on
c
and add the result toS
.
- Run _STRINGIFY on
- Concatenate the items in list
S
and return them.
Destruction
In some cases it is necessary to render an element and its children opaque to later microformat processing. The two functions DESTROYER and DESTROY_ELEMENT deal with this.
DESTROYER
This function aims to find any microformats within an element and make them opaque to later parsing.
- First parameter: element to operate on,
e
. - Second parameter: list of microformats to "save" from destruction,
S
.
- Create a list
M
of all known compound microformat root classes. This list should include any microformats you know about, even if your parser does not include support for them. A sample list is included below. - For each item in
S
: remove fromM
. - For each descendent element
d
ofe
(not includinge
as a descendent of itself):- If the class list of
d
includes one or more of the class names inM
, then:- Run the DESTROY_ELEMENT function on
d
. - Modify the
class
attribute ofd
, removing any classes which appear inM
.
- Run the DESTROY_ELEMENT function on
- If the class list of
Compound microformat root classes
- mfo
- vcard
- adr
- geo
- vcalendar
- vevent
- vtodo
- valarm
- vfreebusy
- hfeed
- hentry
- hslice
- hreview
- hresume
- xfolkentry
- biota
- haudio
- hmeasure
- hangle
- hmoney
- hlisting
Note that XOXO and XMDP are excluded from this list, as they are not compound microformats.
DESTROY_ELEMENT
The aim of this function is to make the innards of a particular element opaque to microformat parsing. The algorithm for "destroying" element e
is as follows:
- Search for all elements which descend from
e
. For each such elementd
:- Set the
class
attribute to the empty string. - Set the
rel
attribute to the empty string. - Set the
rev
attribute to the empty string.
- Set the
Examples of Parsable HTML
URL Examples
The following are all parsed as the same URL.
<a class="url" href="http://example.com/page">Page</a>
<p class="url"> <a href="http://example.com/not-this">Not this</a> <a class="value" href="http://example.com/page">Page</a> </p>
<p class="url"> <a class="value" href="http://example.com/page">Page</a> <a class="value" href="http://example.com/not-this">Not this</a> </p>
<p class="url"> <span class="value">http://example.com/</span> Not this <span class="value">page</span> </p>
<img class="url" alt="foo" src="http://example.com/page" longdesc="http://example.com/not-this">
<!-- (invalid, but works) --> <img class="url" longdesc="http://example.com/page">
<!-- (strange, but true) --> <p class="url"> <img src="http://example.com/not-this" alt="http://example.com/page"> </p>
Datetime Examples
<time class="dtstart" datetime="2008-07-21">Monday</time>
<p class="dtstart"> <time class="value" datetime="2008-07-21">Monday</time> at <time class="value" datetime="21:30">9:30pm</time>. </p>
<p class="dtstart"> <time class="value" datetime="2008-07-21">Monday</time> at <time class="value" datetime="21:30">9:30pm</time> <time class="value" datetime="+1">(UK)</time>. </p>
<p class="dtstart"> <abbr class="value" title="2008-07-21">Monday</time> at <abbr class="value" title="T21:30">9:30pm</time> <abbr class="value" title="+0100">(UK)</time>. </p>
Combination Examples
<ins class="rev url" datetime="2008-07-21T21:30:00+0100"> I launched my <a href="http://example.com/" class="value">new website</a> today. </ins>
Parsed as:
- rev = 2008-07-21T21:30:00+0100
- url = http://example.com/