Главная страница Выбор входного языка Промежуточное представление Разработка Front-end'а Разработка Back-end'а Пара слов про оптимизацию



В данной главе рассматривается не только промежуточное представление, но и транслятотор входного языка в него (так называемый front-end).

В качестве промежуточного представления целесообразно использовать синтаксическое дерево разбора. Звучит страшно, но на самом деле все просто: операнды выражения - это "листья" бинарного дерева, а операции - "узлы". Вот пример для выражения "(a+b)*c":

Дерево разбора строится следующим образом: листья дерева - это либо перeменные, либо числа, узлы - как уже говорилось выше - это операции, причем те, которые должны выполняться в первую очередь, находятся ниже и левее(в предыдущем примере это операция "+"). Правые операнды находятся в правом поддереве (относительно узла-операции), левые в левом.

В качестве илюстрации к выше сказанному предлагаю поэкспериментировать (и набить руку в биективном отображении выражения в дерево разбора) с ON-LINE построителем синтаксических деревьев. Для простоты (не хотелось возиться с маштабированным выводом чисел в узлах) в предложенном ниже аплете число - это не последовательность цифр, а всего одна. Краснае черточки справа-сверху от узлов обозначают унарные минусы.

Структура синтаксического дерева

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

Ан, нет! Язык арифметических выражений настолько примитивен, что абстракции абсолютно ни к чему. Все элементарно: один тип записи и для листьев и для узлов, содержаций в себе информацию и о имени переменной, и о значениии числа, и об операции ... Но заполнять нужно только необходимые из них.
   Ниже приведен текст модуля для работы с синтаксическими деревьями.

(*Модуль для работы с синтаксическими деревьями*)
(*                              (C)2004, pm_kas*)
MODULE Tree;
IMPORT
   Scan;
TYPE
   pTree* = POINTER TO tTree;
   tTree* = RECORD

      Name*   : Scan.tName;(*Имя перменной *)
      Neg*    : BOOLEAN;   (*Унарный минус *)
      Regs*   : INTEGER;   (*      ??      *)
      Value*  : INTEGER;   (*Значение числа*)
      Oper*   : Scan.tLex; (*Операция      *)

      Left*   : pTree;
      Right*  : pTree;
   END;

   PROCEDURE AddToTree*(Left, Right : pTree) : pTree;
   VAR
      Tree : pTree;
   BEGIN
      NEW(Tree);
      Tree.Left:=Left;
      Tree.Right:=Right;
      RETURN (Tree);
   END AddToTree;
END Tree.

Из всех полей записи tTree требует оговорки только Regs. Пока его назначение не понятно, но для при оптимизации использования регистров и стека это поле сыграет главную роль.
   Процедура AddToTree создает новый узел с поддеревьями Left и Righ, переданными ей в качестве параметров, и возвращает указатель на вновь созданный узел.

(C) 2004, PM_KAS