Re: LR Parser Combinator?

Alex Rubinsteyn <alex.rubinsteyn@gmail.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.


Torben

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