|LR Parser Combinator? email@example.com (Alex Rubinsteyn) (2007-05-11)|
|Re: LR Parser Combinator? firstname.lastname@example.org (2007-05-15)|
|Re: LR Parser Combinator? email@example.com (Sylvain Schmitz) (2007-05-16)|
|From:||firstname.lastname@example.org (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)|
|Date:||Tue, 15 May 2007 10:33:14 +0200|
|Organization:||Department of Computer Science, University of Copenhagen|
|Posted-Date:||16 May 2007 03:03:51 EDT|
Alex Rubinsteyn <email@example.com> writes:
> Is it possible to compose LR(k) shift/reduce parsers the same way
> LL(k) parsers are combined in libraries like Parsec? Has this been
> implemented before?
You could make parser combinators that at runtime would build up a
representation of a grammar (with actions) that can subsequently (at
runtime) be converted to a parse table which is then used for the
actual parsing. So, unlike LL parser combinators, there is a staging
of the process. To avoid choking on conflicts, you can backtrack or
use GLR parsing.
I suppose you could make the generation of the parse table lazy,
generating the entries as you need them, thus avoiding a time and
space consuming initial generation stage at the cost of slower parsing
initially (until you have most of the table entries you need). A bit
like JIT versus traditional compilation.
I'm not aware of any implementations, but I haven't looked very hard.
Return to the
Search the comp.compilers archives again.