Re: LR Parser Combinator?

Sylvain Schmitz <schmitz@i3s.unice.fr>
Wed, 16 May 2007 11:07:01 +0200

          From comp.compilers
Related articles
LR Parser Combinator? alex.rubinsteyn@gmail.com (Alex Rubinsteyn) (2007-05-11)
Re: LR Parser Combinator? torbenm@app-2.diku.dk (2007-05-15)
Re: LR Parser Combinator? schmitz@i3s.unice.fr (Sylvain Schmitz) (2007-05-16)
| List of all articles for this month |
From: Sylvain Schmitz <schmitz@i3s.unice.fr>
Newsgroups: comp.compilers
Date: Wed, 16 May 2007 11:07:01 +0200
Organization: Compilers Central
References: 07-05-042
Keywords: parse, LR(1)
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,


      Sylvain


Post a followup to this message

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