¿Relación entre el análisis por desplazamiento-reducción y las continuaciones delimitadas?

13

¿Alguien ha formalizado la relación entre técnicas de análisis de reducción de turnos y continuaciones delimitadas?

Al construir un analizador de abajo hacia arriba (p. Ej., Analizadores LR), tomamos una gramática y luego representamos estados de análisis como conjuntos de elementos : producciones aumentadas de la forma , donde α y β son secuencias de terminales y no terminales. El marcador representa qué tan lejos ha llegado el analizador a la cadena, donde α representa lo que se ha visto hasta ahora y β representa una predicción de lo que aún puede analizarse.UNαβαβαβ

Una acción de transferencia en una transición del autómata LR de análisis sintáctico coincide con un prefijo de la pila contra , y reemplazarlo con A . Una manipulación tan profunda de la pila se asemeja al efecto de un operador de control, pero esto es solo una observación cualitativa.αUN

¿Alguien ha estudiado la conexión entre el análisis de reducción de desplazamiento y los operadores de control delimitados, como cambio / restablecimiento?

Neel Krishnaswami
fuente
Interesante observación.
Dave Clarke
Uno podría haber esperado que Michael Sperber hubiera escrito en alguna parte sobre esta relación, dado su trabajo en el análisis de CPS LR y en las continuas delimitaciones, pero no he encontrado nada.
Sylvain
Recuerdo que Ken Shan me mencionó esta conexión en 2004 y sugirió que sería una gran oportunidad para jugar juegos de palabras. Sin embargo, no sé si ha escrito / codificado nada al respecto desde entonces.
Noam Zeilberger

Respuestas:

4

Creo que el siguiente artículo explora parte de esta conexión, principalmente mediante el uso de continuaciones para retroceder cuando las cosas suceden en los analizadores. Pero definitivamente hay más que hacer aquí.

Retroceso modular a través del registro de control: un par de perlas gemelas funcionales

Olin Shivers, Aaron Turon , ICFP 2011.

Sam Tobin-Hochstadt
fuente