Промежуточный код. Ориентированные ациклические графы. Трёхадресный код

Промежуточный код

Абстрактные синтаксические деревья

Рассмотрим грамматику арифметических выражений

\[\begin{align} E & \to E + T | T\\ T & \to T * F | F \\ F & \to val | ( E ) \\ \end{align}\]

LR-анализ, строка 1+2*(3+4)+(5+6):

Удалим скобки:

Свернём узлы с одним потомком:

Пометим узлы \(E\) и \(T\) соответствующей бинарной операцией и удалим терминалы \(+\) и \(*\):

Заменим ветки узлов \(val\) на значения:

Построение деревьев разбора

LL(1)-анализ

Рассмотрим класс, реализующий узел дерева:

class Node {
protected:
  std::string label;
  std::vector<Node*> children;
  std::size_t numDefdChildren = 0;
public:
  Node(std::string label, std::size_t numChldElems): label(label) {
    children.resize(numChldElems);
  }
  ~Node() { for(auto &a : children) delete a; }
  void addChild(Node* child) {
    children[numDefdChildren++] = child;
  }
  bool isComplete() { return children.size() == numDefdChildren; }
}

Для удобства, лист дерева на основе токена:

class Leaf : public Node {
public:
  Leaf(const Token& tok): Node(tok.name, 0), token(tok) {
  }
private:
  Token tok;
}

Считая, что Token имеет вид:

struct Token {
  std::string name;
  SomeType attributes;
};

SomeType – какой-то тип атрибутов токена.

Псевдокод LL(1)-анализа:

stack.push($);
stack.push(S);
X = stack.top(); // == S
a = getNextToken();
while(X != $) {
  if (X == a) {
    a = getNextToken();
    stack.pop();
    /////////////////////////
    treestack.top().addChild(new Leaf(a));
    while(treestack.top().isComplete()) {
      treestack.pop();
    }
  }
  else if(X -- терминал) reportError();
  // далее X -- нетерминал
  else if(M[X, a] == Y₁ Y₂ … Yₖ) {
    print("X -> Y₁ Y₂ … Yₖ");
    stack.pop();
    if(M[X, a] != ε) {
      for(l in k…1) stack.push(Yₗ); // k == length(M[X, a])
    }
    /////////////////////////
    node = new Node(X, k); // k == length(M[X, a])
    if(treestack.size() > 0) {
      treestack.top().addChild(node);
    } else {
      root = node;
    }
    treestack.push(node);
    while(treestack.top().isComplete()) {
      treestack.pop();
    }
  }
  // нет записи M[X, a]
  else reportError();
  X = stack.top();
}

LR(1)-анализ

Изменение в класс Node, добавление дочерних элементов с конца:

  void addChild(Node* child) {
    children[children.size() - numDefinedChildren - 1] = child;
    numDefinedChildren += 1;
  }

(связано с порядком снятия элементов со стека)

Псевдокод LR(1)-разбора с построением дерева:

a = getNextToken();
while(true) {
  s = stack.top();
  if(ACTION[s, a] = перенос) {
    stack.push(GOTO[s, a]);
    a = getNextToken();
    //////////////////////////////
    treestack.push(new Leaf(a));
  } else if (ACTION[s, a] = свёртка A -> β) {
    for (i in 1…|β|) stack.pop();
    t = stack.top();
    stack.push(GOTO[t, A]);
    print("A -> β");
    //////////////////////////////
    node = new Node("A", |β|);
    for (i in 1…|β|) node.addChild(treestack.pop());
    treestack.push(node);
  } else if (ACTION[s, a] = принятие) {
    root = treestack.pop();
    break;
  } else { // ACTION[s, a] = ошибка
    reportError();
  }
}

Рекурсивный спуск

Разбор нетерминала A с построением дерева:

function A() {
  выбрать продукцию A -> X₁…Xₙ;
  node = new Node("A", n); // n == |X₁…Xₙ|
  for (k in 1…n) {
    if (Xₖ -- нетерминал) {
      kthChild = Xₖ();
      node.addChild(kthChild);
    } else if (Xₖ -- терминал и Xₖ == входному символу) {
      переход к следующему входному символу;
      node.addChild(new Leaf(Xₖ));
    } else {
      обработка ошибки;
    }
  }
  return node;
}

Ориентированные ациклические графы

Оптимизация синтаксических деревьев

Синтаксическое дерево для a+a*(b-c)+(b-c)*d:

Более эффективно в виде ациклического графа:

Трёхадресный код

Другой популярный метод представления промежуточного кода. По сути “высокоуровневый псеводассемблер”

Выражение \(x+y*z\) может быть транслировано в трёхадресный код, например, как

t1 = y * z
t2 = x + t1

здесь * и + суть команды трёхадресного кода.

Адреса в свою очередь могут являться:

  • Каким-то именем в исходном тексте
  • Временной переменной, созданной в процессе генерации кода
  • Константой (числовой, строковой, etc)

Распространённые виды трёхадресных команд:

  1. Команды присваивания вида x = y op z, где op – некая бинарная операция, x, y и z – адреса.
  2. Команды присваивания вида x = op y, где op – некая унарная операция, x, y – адреса.
  3. Команды копирования вида x = y, где x, y – адреса.
  4. Безусловный переход goto L, где L – номер (метка) какой-то команды.
  5. Условный переход вида if x goto L и ifNot x goto L.

Распространённые виды трёхадресных команд (продолжение):

  1. Вызов процедур, передача параметров и возврат из процедур. Реализуются командами param x для параметров, call p, n, где p – адрес процедуры, n – число параметров, и return x для возврата из процедуры.
  2. Индексированные присваивания x = y[i] и y[i] = x, где i – адрес числовой переменной или константы.
  3. Присваивание адресов вида x = &y
  4. Присваивание указателей вида x = *y и *x = y.

Существуют три основных способа представления трёхадресного кода в структурах данных:

  • Четвёрки
  • Тройки
  • Косвенные тройки

Представление в виде статически единственных присваиваний

Вариация на тему трёхадресного кода, запрещающая несколько присваиваний одной и той же переменной.

Вместо этого при каждом присваивании – новая переменная.

Проблема: зависимость результата от пути управления.

Трёхадресный код (слева) и СЕП (справа):

1: if flag goto 4
2: x = 2
3: goto 5
4: x = 1
5: y = x * x
1: if flag goto 4
2: x1 = 2
3: goto 5
4: x2 = 1
5: y = φ(x1,x2) * φ(x1,x2)