<p>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. <a href="https://metacpan.org/pod/release/JKEGL/Marpa-PP-0.005_006/pod/Advanced/Algorithm.pod#Leo-Semantics:-Indirect-and-Lazy" rel="nofollow">https://metacpan.org/pod/release/JKEGL/Marpa-PP-0.005_006/pod/Advanced/Algorithm.pod#Leo-Semantics:-Indirect-and-Lazy</a></p>

<p>Snippit that really helped:</p>

<blockquote>
  <p>Leo Semantics: Indirect and Lazy</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>Marpa optimizes by using a lazy implementation of the indirect
  approach. Only those Leo completions useful for the semantics are
  expanded.</p>
  
  <p>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.</p>
</blockquote>

<p>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. </p>

CC BY-SA 3.0
2015-04-30T00:19:22.317Z
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 http://irclog.perlgeek.de/ and https://groups.google.com/forum/?hl=en&fromgroups#%21forum/marpa-parser
Jeffrey Kegler
CC BY-SA 3.0
2015-04-24T14:28:41.423Z
2015-04-24T14:28:41.423Z
Patrick Huber
<p>Using the Earley Algorithm we can use the Leo enhancement to create cached items for recognition. </p>

<p><a href="http://www.sciencedirect.com/science/article/pii/030439759190180A">http://www.sciencedirect.com/science/article/pii/030439759190180A</a></p>

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

<p><a href="http://www.sciencedirect.com/science/article/pii/S1571066108001497">http://www.sciencedirect.com/science/article/pii/S1571066108001497</a></p>

<p>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. </p>

<p>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? </p>

<fl.formal-languages><parsing>
Is there any research or findings on creating parse forests on Earley parsers with Leo Joop Enhancements?
Patrick Huber
# Is there any research or findings on creating parse forests on Earley parsers with Leo Joop Enhancements?

(Asked by: username_0 on 2015-04-17)

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

<http://www.sciencedirect.com/science/article/pii/030439759190180A>

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

<http://www.sciencedirect.com/science/article/pii/S1571066108001497>

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?

**Tags:** fl.formal-languages, parsing


---

## 1 answers

### Answer by username_0 on 2015-04-24. Score: 2

I ended up getting a hint on how to accomplish this by reading the leo semantics post from username_1'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.

> **Comments:**
> **username_1**: 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 http://irclog.perlgeek.de/ and https://groups.google.com/forum/?hl=en&fromgroups#%21forum/marpa-parser  

---

