Relação entre análise de redução por turno e continuações delimitadas?

13

Alguém formalizou a relação entre técnicas de análise de redução de turnos e continuações delimitadas?

Ao construir um analisador de baixo para cima (por exemplo, analisadores LR), pegamos uma gramática e, em seguida, representamos estados de análise como conjuntos de itens : produções aumentadas da forma , onde α e β são sequências de terminais e não terminais. O marcador representa até que ponto o analisador chegou à string, com α representando o que foi visto até agora eUMAαβαβα representando uma previsão do que ainda pode ser analisado.β

Uma acção de mudança de uma transição do autómato LR de análise corresponde a um prefixo da pilha contra , e substitui-lo com um . Uma manipulação tão profunda da pilha se assemelha ao efeito de um operador de controle, mas isso é apenas uma observação qualitativa.αUMA

Alguém estudou a conexão entre a análise de redução de turno e os operadores de controle delimitado, como shift / reset?

Neel Krishnaswami
fonte
Observação interessante.
31512 Dave
Poder-se-ia esperar que Michael Sperber tivesse escrito em algum lugar sobre esse relacionamento, dado seu trabalho na análise do CPS LR e em continuações delimitadas, mas não encontrei nada.
29412 Sylvain
Lembro-me de Ken Shan mencionando essa conexão comigo em 2004 e sugerindo que seria uma grande oportunidade para trocadilhos. Eu não sei se ele escreveu / codificou alguma coisa sobre isso desde então.
Noam Zeilberger

Respostas:

4

Acredito que o artigo a seguir explora parte dessa conexão, principalmente usando continuações para voltar atrás quando as coisas acontecem nos analisadores. Mas definitivamente há mais o que fazer aqui.

Reversão modular através do registro de controle: um par de pérolas funcionais duplas

Olin Shivers, Aaron Turon , ICFP 2011.

Sam Tobin-Hochstadt
fonte