13
$\begingroup$

Has anyone formalized the relationship between shift-reduce parsing techniques and delimited continuations?

When constructing a bottom-up parser (eg, LR parsers), we take a grammar and then represent parse states as sets of items: augmented productions of the form $A \to \alpha \bullet \beta$, where $\alpha$ and $\beta$ are sequences of terminals and nonterminals. The marker $\bullet$ represents how far the parser has gotten into the string, with $\alpha$ representing what has been seen so far, and $\beta$ representing a prediction of what yet may be parsed.

A shift action in a transition of the LR parse automaton matches a prefix of the stack against $\alpha$, and replace it with $A$. Such a deep manipulation of the stack resembles the effect of a control operator, but this is just a qualititative observation.

Has anyone studied the connection between shift-reduce parsing and delimited control operators such as shift/reset?

$\endgroup$
  • $\begingroup$ Interesting observation. $\endgroup$ – Dave Clarke Mar 28 '12 at 6:10
  • $\begingroup$ One could have expected Michael Sperber to have written somewhere about this relationship, given his work on CPS LR parsing and on delimited continuations, but I haven't found anything. $\endgroup$ – Sylvain Mar 29 '12 at 17:01
  • $\begingroup$ I remember Ken Shan mentioning this connection to me back in 2004, and suggesting that it would make for a great pun opportunity. I don't know that he's written/coded anything up about it since, though. $\endgroup$ – Noam Zeilberger Jan 17 '14 at 13:32
4
$\begingroup$

I believe that the following paper explores some of this connection, mostly by using continuations to backtrack when things happen in parsers. But there's definitely more to do here.

Modular rollback through control logging: A pair of twin functional pearls

Olin Shivers, Aaron Turon, ICFP 2011.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.