Balisage Paper: Translating imperative algorithms into declarative, functional terms

Introduction

Among XML users, it’s not unusual to find XSLT and XQuery being used as general-purpose, not special-purpose, programming languages. It is easier to use a language for general-purpose programming across a wide range of application areas if it has libraries of subroutines for different domains. To build up larger libraries of subroutines for general-purpose languages, it’s sometimes useful to re-implement standard algorithms in the new language.

One of the challenges of reimplementing standard algorithms in XSLT and XQuery is that standard algorithms are often described in imperative terms which cannot be translated directly into declarative functional languages. If we can understand the algorithms in a more declarative way, however, it may be possible to implement them straightforwardly in XSLT or XQuery. The difficulty and one path to resolving it are illustrated here with the parsing algorithm described by Jay Earley in 1970 (Earley 1970).

Earley parsing is a well-known technique for parsing input using context-free languages; unlike techniques like recursive descent and standard table-driven parsing it does not require special properties in the grammar, like being LL(1) or LALR(1): it will work for any input and any grammar, whether the grammar requires lookahead or not. But the algorithm as Earley describes it is quite low-level: routines called the predictor, the scanner, and the completer take turns changing global data structures until it can be seen from the data structures that the parse has succeeded or failed. In the case of success, one or more parse trees can be extracted from the data structure; in failures, one can identify the point at the input at which the attempt failed and generate diagnostic messages. It is not always immediately obvious to the reader, however, exactly why the predictor, the scanner, and the completer behave as they do, or why their interaction is guaranteed to find any and all legitimate parses of the input. And since XSLT and XQuery don’t allow the assignment of new values to variables, the data-structure manipulations used by Earley cannot be implemented as described.

The discussion below tries to step back and think about what the data structures described by Earley mean, in order to understand the algorithm in a purely declarative way. We proceed roughly as follows:

Re-thinking the Earley algorithm in this way not only makes it easier to implement it in XSLT and XQuery, but helps make it clear why the parser is both complete (it will always find a parse if there is one) and correct (any parse it finds will be a real parse).

The next two sections of this paper (section “Notation” and section “Earley items”) introduce some basic notation and the concept of the Earley item. We then (section “Earley trees”) define Earley trees; these are not defined by Earley, but prove useful in the later discussion. The nodes of Earley trees are sets of Earley items with certain parsing-relevant properties. We then proceed (section “Properties and relations of Earley items”) to identify some interesting properties of Earley items (truth, expectation, testability, usefulness, relevance), and some useful relations between items (advance, continuation, scan, prediction). Supplied with these relations, we can define the Earley algorithm using them and show how they guarantee that it is complete and correct (section “The Earley algorithm”).

The initial description of the algorithm applies to grammars given in Backus-Naur Form; the penultimate section (section “Two technical excursus”) contains discussions of two technical topics of practical importance: how to calculate the required sets in XSLT and XQuery, and how to extend the treatment of Earley parsing here to handle regular-right-part grammars like those specified for Invisible XML (section “Extension to EBNF”). The final section (section “Concluding remarks”) tries to draw some lessons for XSLT and XQuery translations of procedural algorithms from this example.

Notation

We assume a grammar G and an input string I of length n. A grammar is a four-tuple (VN, VT, P, S), where

For purpose of our exposition, we often wish to deal not with the grammar G as is, but with an augmented grammar G′ = (VN ∪ Goal, VT, P ∪ Goal → S, Goal), where Goal ∉ VN. This allows us to know that the start-symbol Goal has exactly one rule, whose form we know, and that it never appears on the right-hand side of any rule in G′. It should be clear that G and G′ define the same language.

We use the term string or string of characters when referring to I or substrings of I, or other sequences of terminal symbols. We use the term sequence when referring to sequences of symbols in V. There is no technical distinction between the terms string and sequence other than the restriction of strings to terminal symbols; they are distinguished here only in an attempt to make the argument easier to follow.

For any two sequences or strings α and β, α β denotes the concatenation of α and β. Where simple juxtaposition might be ambiguous, or where it is desired to emphasize the concatenation operator, the form α || β is used with the same meaning.

We write the empty string ε and the empty sequence either ε or ().

The expression I[i] refers to the character at position i in I; the expression I[x,y] refers to the substring from (just after) position x up to and including the character at position y. We use 0 to refer to the position before the first character.

For example, if I is the string a+b, then

Note that for any string I and any non-negative integers x, y, z all ≤ n, we have I[x, y] || I[y, z] = I[x, z], and for any x (0 < x ≤ n), I[x] = I[x-1, x].

The discussion which follows tries to make the line of argument as explicit and easy to follow as possible, but some basic knowlege of context-free grammars is inevitably assumed. (Ironically, any attempt to make an argument easier to follow by making the inference steps as small as possible has the follow-on effect of multiplying the number of formulas and such, so that at first glance the text will appear less accessible, not more accessible. Readers interested but uneasy with formalisms are encouraged to take a deep breath and persevere.)

Earley items

An Earley item is a triple (x, y, N → α · β), where

The third item in the triple is a location (sometimes referred to in parsing literature simply as an item); if we don’t care about the details of the location, we may write an Earley item (x, y, L).

If β is the empty sequence, so that the item has the form (x, y, N → α ·), then the item is called a completed item (or a completion) for N.

For example, given I as above (a+b), if G is the tuple (VN, VT, P, E), where

Informally, we understand an Earley item to mean that in grammar G, the string of symbols α generates the string I[x, y]. (A sequence of symbols generates a string if and only if the string can be produced from the symbols by applying a series of zero or more rewrites using rules of G. Since generation involves zero or more applications of the rewrite relation written →, it is not infrequently denoted ⇒*.) So the examples just given can be interpreted as saying

Note that since we normally use Earley items to keep track of where we are in recognizing input against a grammar, informally an Earley item may also suggest that we are expecting to see an instantiation of the sequence β that follows the dot. (See also the discussion of expectation, below.) But expectations are not relevant for the truth or falsehood of the item, and thus not part of the meaning of the item, narrowly construed.

Of these examples, (5), (7), and (10) are completed items.

Note that because they have a meaning, Earley items can be true or false.

For example, in the list just given, items (1), (3), (4), (7), and (9) are true statements, and the others are false.

Note that if x = y and α is the empty string, then we have an Earley item of the form (x, x, N → · β). The meaning of such an item is always that the empty sequence of grammar symbols derives the empty sequence of terminal symbols, and the item is accordingly always true.

Earley trees

These are not defined by Earley, but they prove helpful for later discussion.

An Earley tree for the start symbol S in a given grammar G, for a given input I, is an ordered tree of Earley items with the following properties:

Like an Earley item, an tree of Earley items has a meaning, and can be true or false.

It follows from the rules that all leaves in the tree are either of the form I[j] or else of the form I[j, j], for 1 ≤ j ≤ n. It also follows that for the leaves, taken in tree order, j is monotonically non-decreasing. For any two leaf of the form I[j], the immediately following leaf in tree order may be either I[k] or I[k, k], where k = j + 1. For a leaf of the form I[j, j], the next leaf in tree order may be either I[j, j], or I[k], again with k = j + 1.

The Earley tree is true (or correct) if and only if the concatenation of all the leaves, in order, is the input I. We say that such an Earley tree exhibits a derivation of I from G.

It should be evident that a conventional parse tree for the input I against the grammar G can be constructed from a correct Earley tree by (1) deleting each node (x, x, N → · α) for non-empty α; (2) replacing each node (x, y, N1 → α N2 · β) with N2; (3) replacing pre-terminal nodes (nodes with single leaf children) with their children; (4) replacing each leaf node with the string it denotes (I[j] with character j of I, I[j, j] with the empty string); and (5) retaining the parent-child relations and sequence of children.

It should also be evident that the parse tree implied by an Earley tree for a given I and G is correct if and only if every Earley item in the tree is true.

Brief digression

We note in passing that the job of any parser is to calculate an Earley tree for a given G and I; one way to think of it is as starting with the given information (I and G), calculating a set of Earley items, and then determining whether we can build an Earley tree from them.

The job of a correct parser is to ensure that all the items in the Earley tree are true (and thus that the tree is correct).

The job of an efficient parser is to do so with as little effort as possible (in particular, considering as few items as possible, and testing as few as possible for truth).

The job of an unrestricted parser is to calculate a correct Earley tree for any arbitrary G and I; restricted parsers (e.g. LL(1) or LR(k) parsers) do so only for some G.

Grune and Jacobs observe that the problem with some general parsing methods is that in the worst case they end up doing a lot of unnecessary work, such as calculating the truth of a lot of Earley items that turn out irrelevant to the construction of a correct parse tree.

The Earley algorithm is a way to calculate Earley trees for arbitrary context-free grammars while reducing the amoung of unnecessary work. To summarize the algorithm, we need to define some properties of Earley items, beyond truth and falsehood.

Properties and relations of Earley items

The first important property of Earley items has already been mentioned several times: Earley items can be true or false. This section describes some additional properties and relations.

The Earley algorithm

The Earley algorithm (as described in Earley 1970) is a procedural way of calculating a set of Earley items which are all true and are all relevant at the time they are added to the set. I believe (but have not proved) that it is in fact the set of all items which are both true and relevant by the definitions above.

The algorithm calculates a set of Earley items which obeys the following rules:

Or, more concisely, the set is the smallest set that contains (0, 0, Goal → · S) and is closed over the relations scan(i, j), pred(i, j), and comp(i, j, k).

Earley defines things procedurally, in terms of the following steps:

Each round of this procedure uses progressively higher values for the end-point in the search for instances of the scan() relation, so there are at most n rounds before we reach the end of the input.

It seems clear from this way of putting it that the procedure described by Earley calculates the transitive closure of (0, 0, Goal → · S) over the relations scan(), pred(), and comp().

It’s pretty clear, intuitively, that the starter item (0, 0, Goal → · S) is relevant and true, and that all of the relations scan(), pred(), and comp() produce new items for the set which are also relevant and also true. Producing only relevant items is what distinguishes Earley from some other algorithms, which work purely bottom-up and essentially try to calculate all true items with x ≠ y. I believe (but hesitate to say it’s intuitively obvious) that the set described contains all relevant items, as that term is defined above; that property distinguishes the Earley algorithm from things like recursive-descent and LR(1) parsing, which in the interests of simplicity and/or speed ignore some relevant items (which is why they can’t handle all grammars).

Earley describes his algorithm in terms of very small mechanical tasks; it’s obvious how to implement it, especially in a procedural language with mutation. It’s not at all obvious to me from E’s description how to do the same thing in a declarative language without mutation.

But by describing the set in terms of the relations, and defining the relations in terms of their properties, instead of in the imperative, procedural-pseudocode style used by Earley and by other descriptions, I think I have succeeded in defining the relevant sets and properties declaratively, which will make it easier to calculate them in a functional language.

Two technical excursus

  (: to take the transitive closure of some
     function f on some set $s, first define an
     equality function $eq, then specify a maximum
     number of recursive calls $n, and finally call
     my:transclos($eq, f, $n, $s)
     :)
  declare function my:transclos(
    $eq as function(*), (: equality test :)
    $r as function(*), (: unary function, for binary relation :)
    $maxcycles as xs:integer,
    $set as item()*
  ) as item()* {
    local:tc-helper($eq, $r, $maxcycles, $set, $set)
  };

  declare function local:tc-helper(
    $eq as function(*), (: equality test :)
    $r as function(*),
        (: unary function to calculate a binary
           relation :)
    $ttl as xs:integer,
    $queue as item()*,
    $accum as item()*
  ) as item()* {
    if (empty($queue)) then
       $accum
    else if ($ttl le 0) then
       error("Could not complete calculation, out of cycles.")
    else
       let $this := $queue[1],
           $rest := $queue[position() gt 1],
           $candidates := $r($this),
           $new := $candidates
	           [no $x in $accum
	           satisfies
	           $eq(., $x)]
       return local:tc-helper($eq, $r, $ttl - 1, 
                   ($rest, $new), ($accum, $new))
  };

Concluding remarks

What can be learned from the example of Earley parsing for the general problem of translating procedural algorithms into XSLT and XQuery?

Three basic ideas seems to stand out.