[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Getting started with Guile Parser Combinators

From: Thompson, David
Subject: Re: Getting started with Guile Parser Combinators
Date: Mon, 20 Jun 2016 13:34:12 -0400

On Sun, Jun 19, 2016 at 2:57 PM, Amirouche Boubekki
<address@hidden> wrote:
> Héllo,
> There is an implementation of guile parser combinators available here [1].
> Here's my attempt at explaining how it works:

This was lovely, thanks!  Glad to see someone using my parser
combinator library.

Knowing that someone is actually using this library makes me a bit
embarrassed about its naive implementation.  I said some of these
things on IRC, but I'd like to list some desired future improvements
here too in the hope that maybe some interested hackers will read it
and jump in to help:

- Stop using SRFI-41 streams. It's very elegant, but wrapping each
character in a stream-pair is inefficient. In order to replace it, we
need another abstraction around a port that allows for backtracking
across the entire text without all of the allocation.

- Temporarily memoize parse results.  It happens often enough that the
same parser will be used on the same character of the stream, so
memoization would improve performance.  The usual memoize
implementation uses a hash table that will not be GC'd as long as the
procedure is alive.  This unbounded memory growth would be a big
problem for a parsing library, so it would be better if the hash table
could be cleared once parsing a file has completed.

- Unlock GLL parsing abilities. With some control-flow hackery[0], it
is possible to handle left-recursive grammars without entering an
infinite loop.  Would be cool to have this ability while also
preserving the purely functional semantics of the current design.

- Dave


reply via email to

[Prev in Thread] Current Thread [Next in Thread]