Re: Algorithms

haberg@matematik.su.se (Hans Aberg)
13 Apr 2002 23:05:31 -0400

          From comp.compilers

Related articles
Algorithms ACA99SRV@sheffield.ac.uk (Steve Vernon) (2002-04-10)
Re: Algorithms haberg@matematik.su.se (2002-04-13)
Re: Algorithms joachim_d@gmx.de (Joachim Durchholz) (2002-04-16)
Re: Algorithms rboland@unb.ca (Ralph Boland) (2002-04-17)
Re: Algorithms vmakarov@redhat.com (Vladimir Makarov) (2002-04-17)
Re: Algorithms joachim_d@gmx.de (Joachim Durchholz) (2002-04-19)
Re: Parsing Algorithms idbaxter@semdesigns.com (Ira D. Baxter) (2002-04-19)
Re: Parse Algorithms address@in.sig (John Mapley) (2002-04-24)
| List of all articles for this month |

From: haberg@matematik.su.se (Hans Aberg)
Newsgroups: comp.compilers
Date: 13 Apr 2002 23:05:31 -0400
Organization: Mathematics
References: 02-04-069
Keywords: parse, functional
Posted-Date: 13 Apr 2002 23:05:31 EDT

"Steve Vernon" <ACA99SRV@sheffield.ac.uk> wrote:
> Working on a compiler compiler for my third year project, I am
>experimenting with one that should handle any grammar by getting
>combinations of the input tokens...
>
> If the tokens are say:
>
> [if,true,then,somecode,else,somecode]
>
> The algorithm (in Java hopefully) would return all combinations, given
>the number of splits this rule has. So for example with 2 splits:
>
> [[ [if],[true,then,somecode,else,somecode] ] ,
>[if,true],[somecode,else,somecode].........
>
> I have made one, but it is very slow for even small inputs.
>
> Does anyone have any ideas or knpow of any URL's that would be helpful.


I know that such parsers that produce all the combinations have been
used by the Haskell people http://haskell.org. For example, the
Mini-Prolog that comes with Hugs uses such a parser, and I recall
Wadler wrote some papers with parser monads (though I do not recall
which ones). (You might inquiry in the Haskell mailing list.)


It is very slow, though: I translated the above mentioned Mini-Prolog
into C++, and it was about as slow as when interpreted by Hugs. Then I
changed the parser to a Flex/Bison generated lexer/parser, and all of
a sudden, it was lightning fast!


So it seems that once one steps off the road of deterministic parsers,
one should not count on high speed. (This is a theme in Tomita
parsers, etc: Trying to make non-deterministic parsers that still are
fairly efficient.)


    Hans Aberg * Anti-spam: remove "remove." from email address.
                                    * Email: Hans Aberg <remove.haberg@member.ams.org>
                                    * Home Page: <http://www.matematik.su.se/~haberg/>
                                    * AMS member listing: <http://www.ams.org/cml/>


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.