Home > Archive > Compilers > May 2007 > LR Parser Combinator?
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
LR Parser Combinator?
|
|
| Alex Rubinsteyn 2007-05-13, 4:26 am |
| 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?
Thanks,
Alex
| |
| Torben Ęgidius Mogensen 2007-05-16, 4:20 am |
| 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
| |
| Sylvain Schmitz 2007-05-17, 4:21 am |
| Alex Rubinsteyn wrote:
> 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?
Combinators are out of the grasp of deterministic LR parsing, and one
would need to resort to nondeterminism. Thus the improvement wrt LL
combinators is perhaps not that big. Nonetheless, here are two
approaches that I know of:
The Essence implementation of Sperber and Thiemann constructs an LR
parser no-the-fly for a grammar and a input, and IIRC simply stops if it
encounters an LR conflict---no warning before run-time.
Sperber, M. and Thiemann, P.: The Essence of LR Parsing. In Scherlis,
W. (Ed.): Proceedings of the ACM SIGPLAN Symposium on Partial Evaluation
and Semantics-Based Program Manipulation PEPM'95, pages 146-155,
LaJolla, CA, June 1995. ACM Press.
Doaitse Swierstra's parser combinators also look a bit like
(nondeterministic) LR parsers.
Swierstra, S.D. (2001). Combinator Parsers: From Toys to Tools. In
Hutton, G. (Ed.): Electronic Notes in Theoretical Computer Science.
Elsevier Science Publishers.
--
Hope that helps,
Sylvain
| |
|
|
|
|
|