Using the Earley Algorithm we can use the Leo enhancement to create cached items for recognition.


Scott's algorithm on building parse trees doesn't take into account this enhancement.


Leo notes in his paper his algorithm builds an effective recognizer, but ultimately leaves out information that would be needed to construct the parse forest. Building the parse forest would require the transition items omitted by the enhancement and therefore undo the complexity gains.

So I would like to know if there is research or findings on creating a parse forest that retains the complexity gains from the Leo enhancement without pushing the complexity from the recognizer to the parse forest generation. Basically, is there a linear time algorithm on LR(k) grammars for building sparsely packed parse forests?


I ended up getting a hint on how to accomplish this by reading the leo semantics post from Jeffrey Kegler's deprecated Marpa algorithm page. https://metacpan.org/pod/release/JKEGL/Marpa-PP-0.005_006/pod/Advanced/Algorithm.pod#Leo-Semantics:-Indirect-and-Lazy

Snippit that really helped:

Leo Semantics: Indirect and Lazy

Leo's hints about semantic processing, while brief, were insightful. The first decision to make with the Leo semantics was direct versus indirect. The direct approach does the semantic processing with the Leo items themselves, without converting them. This has the advantage that costs are incurred only for the Leo items that are actually used by the semantics. It has the very serious disadvantage of intertwining the Leo logic with the semantics. Dealing directly with Leo items would more than double the complexity of the logic for Marpa's semantics. Because of this, Marpa rejected the direct approach.

Leo 1991 suggests an indirect approach. The indirect approach is to expand the Leo completions into the stacks of Earley items for which Leo completions are a shorthand. However, in a naive implementation, the indirect approach eliminates every advantage of using the Leo speedups -- it merely moves processing from the recognizer into the semantic phase.

Marpa optimizes by using a lazy implementation of the indirect approach. Only those Leo completions useful for the semantics are expanded.

For a lazy and indirect implementation, in all cases, time complexity is the same as with a direct implementation. But for some ambiguous grammars, the space required grows from linear to quadratic with any indirect approach. This does not change the worst case time-complexity -- that was already quadratic. Fortunately, this worst case -- highly ambiguous parses where all the parse results are demanded -- is of limited practical interest.

I ended up using the lazy approach as well and did just in time evaluation for only items needed to complete the parse tree. This avoids the intermediate items that the normal algorithm adds.

  • $\begingroup$ Thanks for your interest in my work, and I'm glad my suggestion was useful. The indirect-and-lazy choice was one of those all-too-infrequent cases where my first guess was right. I did ask Joop Leo what he thought and he agreed, though Joop has been out of parsing theory for many years. There's a Marpa IRC channel and mailing list where I and other Marpa users can be reached for questions about Marpa's implementation: #marpa on irclog.perlgeek.de and groups.google.com/forum/?hl=en&fromgroups#%21forum/… $\endgroup$ – Jeffrey Kegler Apr 30 '15 at 0:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.