# Relationship between shift-reduce parsing and delimited continuations?

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?

• Interesting observation. – Dave Clarke Mar 28 '12 at 6:10
• 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. – Sylvain Mar 29 '12 at 17:01
• 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. – Noam Zeilberger Jan 17 '14 at 13:32