Взаимосвязь между анализом сдвига и уменьшением и продолжением с разделителями?

13

Кто-нибудь формализовал связь между методами синтаксического анализа с уменьшением сдвига и продолжением с разделителями?

При построении снизу вверх анализатора (например, LR парсеры), мы возьмем грамматику , а затем представляют синтаксический анализ состояние как совокупности элементов : дополненное произведение вида , где и является последовательности терминалов и нетерминалов. Маркер представляет, как далеко парсер попал в строку, где представляет то, что было замечено до сих пор, а представляет предсказание того, что еще может быть проанализировано.Aαβαβαβ

Акция сдвиг в переходе LR разбора автомата совпадает с префиксом стека против , и заменить его . Такое глубокое манипулирование стеком напоминает эффект управляющего оператора, но это всего лишь качественное наблюдение.αA

Кто-нибудь изучал связь между синтаксическим анализом сдвига-уменьшения и управляющими операторами с разделителями, такими как сдвиг / сброс?

Нил Кришнасвами
источник
Интересное наблюдение.
Дейв Кларк
Можно было ожидать, что Майкл Спербер где-то напишет об этих отношениях, учитывая его работу по разбору CPS LR и продолжениям с разделителями, но я ничего не нашел.
Сильвен
Я помню, как Кен Шан упомянул мне эту связь еще в 2004 году и предположил, что это создаст прекрасную возможность для каламбура. Я не знаю, что он написал / закодировал что-нибудь об этом с тех пор, хотя.
Ноам Цайлбергер

Ответы:

4

Я полагаю, что в следующей статье рассматриваются некоторые из этих связей, в основном с использованием продолжений для возврата, когда что-то происходит в синтаксических анализаторах. Но здесь определенно есть чем заняться.

Модульный откат через контрольное ведение журнала: пара двойных функциональных жемчужин

Олин Шиверс, Аарон Турон , ICFP 2011.

Сэм Тобин-Хохштадт
источник