Re: LR Parser Combinator? (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Tue, 15 May 2007 10:33:14 +0200

          From comp.compilers

Related articles
LR Parser Combinator? (Alex Rubinsteyn) (2007-05-11)
Re: LR Parser Combinator? (2007-05-15)
Re: LR Parser Combinator? (Sylvain Schmitz) (2007-05-16)
| List of all articles for this month |

From: (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Newsgroups: comp.compilers
Date: Tue, 15 May 2007 10:33:14 +0200
Organization: Department of Computer Science, University of Copenhagen
References: 07-05-042
Keywords: parse
Posted-Date: 16 May 2007 03:03:51 EDT

Alex Rubinsteyn <> 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.


Post a followup to this message

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