[Off-topic]Functional parsing theory

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

[Off-topic]Functional parsing theory

Maurí­cio CA
Hi, all,

I've been working in a tool that reads a grammar with associated
actions and act on input based on that grammar. I would like to
rewrite it in a functional style, but I've not been able to find a
theory that would handle any possible grammar with cyclicity and
empty productions, and flexibility is more important for this tool
than performance.

Do you have a suggestion on that? What I'm using now is this
(non-functional) article on Earley method:

   http://www.springerlink.com/content/602270808666074p

Thanks,

Maurício

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: [Off-topic]Functional parsing theory

Stephen Tetley-2
Maybe Peter Ljunglöf's thesis will be useful?

http://www.ling.gu.se/~peb/pubs.html
http://www.ling.gu.se/~peb/pubs/Ljunglof-2002a.pdf

It covers chart, GLR and CYK parsing - isn't Earley's parsing method
related to either chart or CYK?
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: [Off-topic]Functional parsing theory

Dominique Devriese-2
In reply to this post by Maurí­cio CA
Mauricio,

2010/10/6 Maurí­cio CA <[hidden email]>:
> I've been working in a tool that reads a grammar with associated
> actions and act on input based on that grammar. I would like to
> rewrite it in a functional style, but I've not been able to find a
> theory that would handle any possible grammar with cyclicity and
> empty productions, and flexibility is more important for this tool
> than performance.
>
> Do you have a suggestion on that? What I'm using now is this
> (non-functional) article on Earley method:

I'm not sure what you're looking for exactly, but my
grammar-combinators library [1] might be interesting for you. It is
not yet industry-proof at the moment, but might benefit from some more
real-world use and comments. It is a novel functional parsing library
using an explicit representation of recursion which allows it to
support many different parsing algorithms and grammar transformations.

Anyway, in the functional world, parsing algorithms used are often LL
parsing algorithms, often used with parser combinators. Other
algorithms can sometimes be emulated in a functional style using a
top-down parsing algorithm on a transformed grammar (e.g. left-corner
transform, but I also suspect you can emulate LR parsing using what I
call the uniform Paull transformation). My library automates two such
important transformations (supporting for example left-recursion).

Dominique

Footnotes:
[1] http://projects.haskell.org/grammar-combinators/
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: [Off-topic]Functional parsing theory

bieniusa
In reply to this post by Maurí­cio CA
It's not entirely clear what you mean:

Do you want to describe grammars or parsers functionally:

In the first case, parser combinators are what you want (or some
encoding of them). There are many variations on these: LL(k),
context-free, dependent. Cyclicity (of what kind?) or empty productions
are not necessarily a problem.

If you already parsed the input to an abstract syntax tree, and want to
act on this input in terms of your grammar, then attribute grammars are
what you are looking for.

- Arie

Am 06.10.2010 17:43, schrieb Maurí­cio CA:

> Hi, all,
>
> I've been working in a tool that reads a grammar with associated
> actions and act on input based on that grammar. I would like to
> rewrite it in a functional style, but I've not been able to find a
> theory that would handle any possible grammar with cyclicity and
> empty productions, and flexibility is more important for this tool
> than performance.
>
> Do you have a suggestion on that? What I'm using now is this
> (non-functional) article on Earley method:
>
>   http://www.springerlink.com/content/602270808666074p
>
> Thanks,
>
> Maurício
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: [Off-topic]Functional parsing theory

Maurí­cio CA
After reading your message I found "Why Attribute Grammars
Matter" and a few other introductions, and it seems attribute
grammars are exactly what I'm trying to do. Do you know of
some place (mailing list etc.) where I can discuss attribute
grammars or ask for suggestions on design?

Thanks,

Maurício

2010/10/7, bieniusa <[hidden email]>:

> It's not entirely clear what you mean:
>
> Do you want to describe grammars or parsers functionally:
>
> In the first case, parser combinators are what you want (or some
> encoding of them). There are many variations on these: LL(k),
> context-free, dependent. Cyclicity (of what kind?) or empty productions
> are not necessarily a problem.
>
> If you already parsed the input to an abstract syntax tree, and want to
> act on this input in terms of your grammar, then attribute grammars are
> what you are looking for.
>
> - Arie
>
> Am 06.10.2010 17:43, schrieb Maurí­cio CA:
>> Hi, all,
>>
>> I've been working in a tool that reads a grammar with associated
>> actions and act on input based on that grammar. I would like to
>> rewrite it in a functional style, but I've not been able to find a
>> theory that would handle any possible grammar with cyclicity and
>> empty productions, and flexibility is more important for this tool
>> than performance.
>>
>> Do you have a suggestion on that? What I'm using now is this
>> (non-functional) article on Earley method:
>>
>>   http://www.springerlink.com/content/602270808666074p
>>
>> Thanks,
>>
>> Maurício
>>
>> _______________________________________________
>> Haskell-Cafe mailing list
>> [hidden email]
>> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe