Разработка компиляторов
Динамическое программирование
Наша задача теперь заключается в построении вывода минимальной стоимости. Поскольку стоимость вывода аддитивна относительно стоимостей правил, входящих в него, можно воспользоваться принципом динамического программирования, составляя оптимальный вывод для текущей вершины путем выбора среди всех применимых правил и оптимальных выводов для соответствующих поддеревьев (заметим, что это возможно в силу неотрицательности функции стоимости).
Код алгоритма восходящего переписывания деревьев приведен на иллюстрации. Теперь функция проверки соответствия поддерева образцу возвращает стоимость вывода этого поддерева из этого образца. Кроме того, вывод попадает в разметку только в том случае, если он минимален относительно всех выводов данного поддерева из данного нетерминала.
