Implementation in C# (.NET).

[prh...@gmail.com]

I've been a long time lurker ever since watching the FLOSS Weekly interview with Andrew Rodland. I have always been curious about parsing and decided to try and implement the algorithm in c#. I'd like to thank the community for being so open with documentation and implementation detail as it has been great in doing research in the implementation.

During parse tree creation, I ended up getting stuck on recreating the parse forest for leo items.

Posting on stackoverflow got the attention of Jeffrey who led me to a solution with his comment on some marpa documentation. I actually implemented the sparsely packed parse forest using leo items directly and thought this implementation may be of interest. Jeffrey mentioned that using leo semantics may be too complicated, but it turned out to be fairly straightforward. I look at leo items like chains that form the right spine of a SPPF tree. The SPPF is implemented using Elizabeth Scott's algorithm. Virtual nodes help in keeping the recognition time O(n), and during creation top of the leo chain is passed into the virtual node. A index pointer to the top of the chain is passed from leo item to leo item during the optimization phase, forward pointers are maintained when returning from the recursive leo optimization.

I think the implementation is at a point where I'm ready to let the marpa community see it and give some critique. Here is the github repo. It still needs a lot of work, but I'm pretty sure the SPPF with leo items is working properly. If there are any test cases that you know are particularly challenging for the marpa parser, I'd be interested in implementing them to make sure my implementation is correct.

[Ruslan Shvedov]

On Mon, Jul 13, 2015 at 4:30 AM, <prh...@gmail.com> wrote:

I think the implementation is at a point where I'm ready to let the marpa community see it and give some critique. Here is the github repo. It still needs a lot of work, but I'm pretty sure the SPPF with leo items is working properly. If there are any test cases that you know are particularly challenging for the marpa parser, I'd be interested in implementing them to make sure my implementation is correct.

I once ran into a straightforward, but highly ambiguous case [1], for which Marpa::R2::ASF was able to report ambiguities correctly [2] -- perhaps you could use it as a stress test for your parse forest implementation.

It's in perl, but the grammar and source are easy to find. 

The grammar is in SLIF, but convertable to BNF, e.g. + means one-or-more sequence, which is implemented in Marpa as left recursion and lexemes (~) allow character classes.

Otherwise (not necessarily related to parse forests), there is Marpa::R2 test suite (also in perl).

Hope it helps.

[1] https://gist.github.com/rns/d0ad3dea7dbead99e64d

[2] https://gist.github.com/rns/cb9f19989565309de914#file-output

 

--
You received this message because you are subscribed to the Google Groups "marpa parser" group.
To unsubscribe from this group and stop receiving emails from it, send an email to marpa-parser...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Patrick Huber]

Great, thanks for the links. I wrote a temporary bnf style interface that closely resembles SLIF, so this should be pretty easy to consume.

[Jeffrey Kegler]

Thanks for your interest.

Did I discourage using the Leo optimization?  I don't remember doing that.  I'm usually pushing folks to try it.

If you found Leo implementation straight-forward, you might try writing it up in blog form, or whatever.  A lot of folks are interested in implementing  it, but find it hard to understand.

--

[Patrick Huber]

Not Leo optimization, it was using the leo items directly to create the ASF instead of expanding them into earley items. Here is the article I'm referring to:

https://metacpan.org/pod/release/JKEGL/Marpa-PP-0.005_006/pod/Advanced/Algorithm.pod#Leo-Semantics:-Indirect-and-Lazy

In the article, you mention that the direct approach may be too complicated because it interweaves leo logic into Marpa's semantics. I ended up dynamically generating the SPPF node for the leo items which borrows from the ideas of Lazy, but uses the leo items directly instead of first converting them. It pushes the complexity into ASF child creation and out of the main algorithm abstracting the dynamic vs standard through a standard interface.

I'm glad you mentioned blogging, I definitely plan on writing a series on the algorithm now that I've reached a stable point with the implementation. I think its the Marpa Algorithm is very elegant and needs as much marketing as possible. I'll post here when I have something to review.