<p>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. </p>

<blockquote>
  <p>Modular rollback through control logging: A pair of twin functional pearls</p>
  
  <p><em>Olin Shivers, Aaron Turon</em>, ICFP 2011.</p>
</blockquote>

CC BY-SA 3.0
2014-03-22T22:10:40.890Z
2014-03-22T22:10:40.890Z
Sam Tobin-Hochstadt
<p>Has anyone formalized the relationship between shift-reduce parsing techniques and delimited continuations? </p>

<p>When constructing a bottom-up parser (eg, LR parsers), we take a grammar and then represent parse states as sets of <em>items</em>: 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. </p>

<p>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. </p>

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

CC BY-SA 3.0
2012-03-28T06:10:13.377Z
Interesting observation.
Dave Clarke
CC BY-SA 3.0
2012-03-29T17:01:12.350Z
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
CC BY-SA 3.0
2014-01-17T13:32:17.670Z
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
<pl.programming-languages><parsing>
Relationship between shift-reduce parsing and delimited continuations?
Neel Krishnaswami
# Relationship between shift-reduce parsing and delimited continuations?

(Asked by: username_0 on 2012-03-28)

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?

**Tags:** pl.programming-languages, parsing

> **Comments:**
> **username_1**: Interesting observation.  
> **username_2**: 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.  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_4 on 2014-03-22. Score: 4

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.


---

