Elkhound Algorithm

This page describes some of the details of the variant of GLR that Elkhound uses, placing it in context with some of the other GLR variants that have been proposed.


First, the primary goals of Elkhound:

  1. It must have the capability to execute arbitrary user-provided reduction actions. Building a parse tree isn't good enough, it takes too much time and space.
  2. Reductions and merges should be performed bottom-up (unless the grammar is cyclic).
  3. It should be competitive with Bison for LALR (fragements of) grammars, and degrade gracefully from there. On the scale of grammar nondeterminism, from none (LALR) to some to lots, "some" is the niche Elkhound is going after.

These goals are driven by Elkhound's primary application, the Elsa C++ Parser. In essence, Elkhound came about because I wanted to apply automatic parsing technology to parsing C++, but found exiting systems inadequate.


The approximate algorithm descendency sequence:

Right Nulled GLR

At the CC04 conference I became acquainted with Adrian Johnstone and his work. He and his coathors have not only more thoroughly documented the history of GLR, but also proposed a novel alternative solution to the problem Farshi originally addressed, which they call "Right Nulled GLR Parsing".

The basic idea of Right Nulled GLR is, rather than re-examining work already done to check for newly exposed reduction opportunities (as Farshi does), do those reductions that would be found by the search earlier in the parse, namely as soon as the rule in question only has nullable components remaining to recognize.

However, while this approach is certainly appealing, I still have questions about exactly how to adapt it to use user-defined reduction actions. At some point I want to implement the right-nulled variant in Elkhound to experiment more with it, but haven't gotten around to it.

Algorithm Features

The Technical Report has most of the details, so I'll just point out some key distinguishing characteristics here.