Разработка компиляторов
Динамическое программирование (окончание)
Можно доказать, что приведенный алгоритм действительно строит разметку, обладающую заявленными свойствами. Его сложность также пропорциональна произведению числа правил на количество вершин дерева.
Отсюда следует, что если дерево выводимо в данной грамматике, то разметка сопоставляет паре (корень дерева, стартовый нетерминал) стоимость минимального вывода и правило, которое этот вывод начинает.
