Zależność między analizą składniową redukującą przesunięcie a ograniczonymi kontynuacjami?

Czy ktoś sformalizował związek między technikami analizy składniowej redukującej przesunięcie a ograniczonymi kontynuacjami?

Podczas konstruowania analizatora składniowego typu oddolnego (np. Parserów LR) bierzemy gramatykę, a następnie reprezentujemy stany analizy jako zestawy elementów : rozszerzone produkcje od postaci , gdzie i są sekwencje terminali i nieterminali. Marker reprezentuje, jak daleko parser dotarł do łańcucha, przy czym reprezentuje to, co do tej pory było widziane, a oznacza prognozę tego, co jeszcze może zostać przeanalizowane. $A \to \alpha \bullet \beta$ $\alpha$ $\beta$ $\bullet$ $\alpha$ $\beta$

Akcja przesunięcie w przejściu automatu LR parsowania odpowiada prefiks krawędzią stosu i zastąpić go . Tak głęboka manipulacja stosem przypomina działanie operatora sterującego, ale jest to tylko obserwacja jakościowa. $\alpha$ $A$

Czy ktoś badał związek między analizą składniową z redukcją zmiany i operatorami sterującymi z ograniczeniami, takimi jak shift / reset?

pl.programming-languages parsing

— Neel Krishnaswami
źródło

Ciekawa obserwacja.

— Dave Clarke

Można się było spodziewać, że Michael Sperber napisał gdzieś o tym związku, biorąc pod uwagę jego pracę nad analizowaniem CPS LR i ograniczonymi kontynuacjami, ale niczego nie znalazłem.

— Sylvain

Pamiętam, jak Ken Shan wspominał mi to połączenie w 2004 roku i sugerował, że byłby to świetna okazja do gry w kalambury. Jednak od tego czasu nie wiem, czy napisał / zakodował coś na ten temat.

— Noam Zeilberger

Uważam, że poniższy artykuł analizuje niektóre z tych powiązań, głównie za pomocą kontynuacji do cofania się, gdy coś dzieje się w parserach. Ale zdecydowanie jest tu więcej do zrobienia.

Modułowe cofanie poprzez rejestrowanie kontroli: para podwójnych funkcjonalnych pereł

Olin Shivers, Aaron Turon , ICFP 2011.

— Sam Tobin-Hochstadt
źródło