Разработка компиляторов
Свертка
увеличить изображение
После того, как приведенным алгоритмом была построена разметка, необходимо извлечь из нее оптимальный вывод. Этот шаг называется сверткой.
Извлечение оптимального вывода происходит следующим образом. Разметка сопоставляет каждой вершине и каждому нетерминалу правило, которое входит в минимальный вывод поддерева данной вершины из данного нетерминала.
Предположим, что нетерминал, вывод из которого нас интересует, как-то задан. Тогда правило, которое возвращает нам разметка, однозначно определяет нетерминалы, из которых в минимальном выводе должны быть выведены поддеревья текущей вершины. В свою очередь, разметка для этих поддеревьев и этих нетерминалов доставляет правила, присутствующие в минимальном выводе этих поддеревьев, и так далее.
Теперь осталось заметить, что нас интересует вывод всего дерева из стартового нетерминала грамматики. Таким образом, сначала мы выбираем правило, которое начинает минимальный вывод дерева из стартового нетерминала, а затем поступаем так, как описано выше. Последовательность извлеченных таким образом правил и будет минимальным выводом данного дерева.
На иллюстрации последовательность выбора нетерминалов в оптимальном выводе отражена с помощью сплошных стрелок, а сами эти нетерминалы подчеркнуты.
