|LR Parser Combinator? firstname.lastname@example.org (Alex Rubinsteyn) (2007-05-11)|
|Re: LR Parser Combinator? email@example.com (2007-05-15)|
|Re: LR Parser Combinator? firstname.lastname@example.org (Sylvain Schmitz) (2007-05-16)|
|From:||Sylvain Schmitz <email@example.com>|
|Date:||Wed, 16 May 2007 11:07:01 +0200|
|Posted-Date:||17 May 2007 02:05:46 EDT|
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,
Return to the
Search the comp.compilers archives again.