Разработка компиляторов
Свертка (продолжение)
void Reduce (N: Nonterminal; root: Tree) { (R=N:p,c)=C[root][N];
if (p = 'K') then Reduce (K, root); else if (p = 'b(K 1,…,K n)') then for i=1 to |sons(root)| do Reduce (K i, son(root,i));
-- do some actions here -- }
Конечно, при генерации кода нас интересует не столько сам минимальный вывод, сколько его интерпретация с точки зрения машинных команд. Поэтому фактически наряду с восстановлением вывода должны быть предприняты какие-то действия по конструированию машинных команд и их операндов.
На иллюстрации приведен алгоритм свертки, который после восстановления вывода производит некоторые неформальные действия, призванные сконструировать машинный код. Суть этих действий мы разберем ниже, а пока прокомментируем коротко этот алгоритм.
Как и было объявлено, построение вывода определяется для корня дерева и некоторого предзаданного нетерминала. Первым делом извлекается правило, которое начинает вывод минимальной стоимости дерева из этого нетерминала (то, что такое правило всегда существует, будет видно по индукции из дальнейшего). Затем разбираются случаи устройства образца в правой части этого правила. Если правило было цепным, то производится светртка того же поддерева по нетерминалу в правой части правила, если нет, то выполняется свертка поддеревьев данной вершины по тем нетерминалам, которыми помечены соответствующие листья образца в правой части.
Наконец, изначально корень дерева сворачивается по стартовому нетерминалу.
