[Haskell-cafe] Parser left recursion

[Paul Callaghan]

Hi

Another alternative is this Haskell library: https://github.com/paulcc/xsaiga

This is a combinator library which is suitable for mid-scale NLP work,
so handles left recursion and (high amounts of) ambiguity to produce a
packed result (which can be decoded to a list of results if required).
It uses a technique similar to Danielsson's for termination.

The technical details (incl papers) can be found on
http://cs.uwindsor.ca/~hafiz/xsaiga/pub.html, particularly in the IWPT
paper http://cs.uwindsor.ca/~hafiz/pub/iwpt-07.pdf

I'd be interested to see a  GLL impl for Haskell, particularly for
comparison with the above. Did Roman C. publish some code for this a
while back?

Paul

On Wed, Feb 27, 2013 at 9:50 AM, Paul Callaghan <paulcc.two at gmail.com> wrote:
> Another alternative is this Haskell library: https://github.com/paulcc/xsaiga
>
> This is a combinator library which is suitable for mid-scale NLP work,
> so handles left recursion and (high amounts of) ambiguity to produce a
> packed result (which can be decoded to a list of results if required).
> It uses a technique similar to Danielsson's for termination.
>
> The technical details (incl papers) can be found on
> http://cs.uwindsor.ca/~hafiz/xsaiga/pub.html, particularly in the IWPT
> paper http://cs.uwindsor.ca/~hafiz/pub/iwpt-07.pdf
>
> I'd be interested to see a  GLL impl for Haskell, particularly for
> comparison with the above. Did Roman C. publish some code for this a
> while back?
>
> Paul
>
> On Tue, Feb 26, 2013 at 7:43 PM, Dominique Devriese
> <dominique.devriese at cs.kuleuven.be> wrote:
>> 2013/2/26 Martin Drautzburg <Martin.Drautzburg at web.de>:
>>> I wonder if I can enforce the nonNr property somehow, i.e. enforce the rule
>>> "will not consider the same nonterminal again without having consumed any
>>> input".
>>
>> You might be interested in this paper:
>>
>>   Danielsson, Nils Anders. "Total parser combinators." ACM Sigplan
>> Notices. Vol. 45. No. 9. ACM, 2010.
>>
>> Regards,
>> Dominique
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> Haskell-Cafe at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell-cafe