В рассматриваемой нами модели компилятора, на начальной стадии анализируется исходный текст и создаётся промежуточное представление. На заключительной стадии из промежуточного представления, возможно после преобразований, не изменяющих результат (называемых оптимизацией), генерируется целевой код. В идеале, детали исходного языка ограничены начальной стадией компиляции, а детали целевого языка – заключительной. Тогда при наличии достаточно общего промежуточного представления, при наличии начальной стадии для языка L и заключительной стадии для целевого языка М, компилятор из L в M может быть сделан просто соединением этих стадий, и тогда можно получить m×n компиляторов, просто написав m начальных стадий и n заключительных.

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

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

Промежуточным кодом в общем называется некоторое внутреннее представление, используемое компилятором при переходе от начальной стадии компиляции к заключительной. Следует отметить, что в общем случае компилятор может иметь несколько промежуточных представлений различного уровня абстракции. Так, высокоуровневое промежуточное представление, генерируемое на основе синтаксического анализа, может быть ближе к исходному коду, а промежуточное представление, на основе которого генерируется целевой код, может быть ближе к целевому.

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

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

Один из вариантов промежуточного представление – представление исходного кода в виде абстрактных синтаксических деревьев. Слово “абстрактные” здесь означает только то, что вид синтаксического дерева не привязан, в отличие от деревьев разбора, к синтаксису языка, и скорее отражает его семантику.

В целом, если грамматика языка спроектирована с учётом семантики, и грамматическая структура отражает в той или иной мере структуру семантическую, абстрактное синтаксическое дерево может быть построено из дерева разбора переупорядочиванием поддеревьев и удалением “лишней” (т.е. не влияющей прямо на семантику) синтаксической информации.

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

\[\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) мы получим следующее дерево разбора:

Связанные с терминалом \(val\) значения показаны рядом с узлами.

Структура грамматики отражает семантическую структуру, в частности, что приоритет умножения выше приоритета сложения, и приоритет операций в скобках всегда выше. Практически, однако, оно содержит много избыточной информации: с точки зрения семантики арифметических выражений, нам совершенно не важно, что левый операнд операции “+” является порождением вида \(E \Rightarrow T \Rightarrow F \Rightarrow val\), где токен, связанный с терминалом \(val\) имеет атрибут, равный 1. Также нам не слишком интересны терминалы, соответствующие скобкам, поскольку они используются только для группировки. Тогда, удалив из дерева разбора скобки, символы бинарных операций, линейные деревья, и пометив узлы, соответствующие бинарным операциям, символом этих бирарных операций, а узлы \(val\) соответствующим им значением, получим значительно более простое представление того же выражения:

(последовательное применение операций рассмотрено здесь)

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

Для этого, для каждой продукции грамматики объявляется т.н. “семантическое действие”, смысл которого – описать, как построить внутреннее представление для данного правила.

Применение семантических действий будет несколько отличаться для восходящего и нисходящего анализа.

LL-анализ применяет продукции до того, как разобрана строка, соответствующая телу продукции. Как следствие, при LL-анализе, структура, соответствующая какому-то поддереву, должна быть создана до разбора этого поддерева, что может быть нетривиально.

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

Метод анализа рекурсивным спуском позволяет проще всего совершать семантические действия до, после, или непосредственно во время разбора тела какой-либо продукции.

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

Построение деревьев разбора в процессе анализа выглядит несколько по-разному при LL-, LR-анализе и анализе методом рекурсивного спуска. Наиболее гибкий вариант построения дерева возможен при анализе методом рекурсивного спуска. LL(1) и LR(1) без значительных модификаций позволяют сравнительно легко создавать узлы дерева разбора только в момент применения соответствующих продукций.

При LL(1)-анализе

При LL(1) - анализе, промежуточный узел дерева разбора создаётся каждый раз при применении продукции – в момент применения продукции, одновременно известны её заголовок и тело, которые в дальнейшем отбрасываются в процессе LL-анализа.

Поскольку в момент создания промежуточного узла его “содержимое” (т.е. дочерние элементы) ещё не существуют, необходимо использовать такую структуру, которая поддерживает в некотором роде “частичное определение”. Следует отметить, что, поскольку в момент создания промежуточного узла точно известно число его дочерних элементов (соответствующее числу символов в теле продукции), возможно отслеживать момент, когда завершается построение поддерева, ориентируясь на полноту определения всех дочерних элементов промежуточных узлов.

В качестве примера такой структуры данных, рассмотрим следующий класс С++:

class Node {
public:
  Node(std::string label, std::size_t numChldElems): label(label) {
    numDefinedChildren = 0;
    children.resize(numChldElems);
  }
  ~Node() {
    for(auto &a : children) {
      delete a;
    }
  }
  void addChild(Node* child) {
    if (numDefinedChildren >= children.size()) {
      throw new std::runtime_exception(
        "Trying to add children to Node beyond capacity");
    }
    children[numDefinedChildren] = child;
    numDefinedChildren += 1;
  }
  bool isComplete() {
    return children.size() == numDefinedChildren;
  }
protected:
  std::string label;
  std::vector<Node*> children;
  std::size_t numDefinedChildren;
}

Для удобства так же добавим класс листа дерева, создающего лист на основе токена:

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)-анализа можно записать в следующем виде, где treestack – это стек, в котором хранятся указатели на Node, a root – корневой узел дерева.

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)-анализе

При LR(1)-анализе построение дерева разбора несколько проще в том смысле, что все дочерние поддеревья уже существуют на момент создания промежуточного узла, и его нужно только создать. Воспользуемся той же структурой, что и в предыдущем разделе, но отметим, что метод isComplete не используется, и введём одну поправку, в методе addChild будем добавлять дочерние элементы с последнего:

  void addChild(Node* child) {
    if (numDefinedChildren >= children.size()) {
      throw new std::runtime_exception(
        "Trying to add children to Node beyond capacity");
    }
    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();
  }
}

При анализе методом рекурсивного спуска

Поскольку метод рекурсивного спуска предполагает вызов функций/методов, совершающих разбор для каждого нетерминала, и структура тела этого метода совпадает со структурой тела продукций, можно добавить произвольный код в любой точке разбора тела продукции. Обычно, методы, совершающие разбор, возвращают поддерево, соответствующее разбираемому нетерминалу. Тогда общий псевдокод можно представить в виде:

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;
}

Аналогично случаю LR-разбора, метод isComplete здесь не используется. Более того, этот метод анализа с точки зрения построения дерева разбора является наиболее гибким и позволяет использовать практически произвольную структуру данных.

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

Одна из достаточно простых оптимизаций представления промежуточного кода в виде абстрактного синтаксического дерева – представление в виде ориентированного ациклического графа.

Главное отличие такого графа от дерева в том, что некоторые узлы могут иметь несколько родительских, но циклы невозможны.

Идея состоит в том, чтобы для выражений исходного языка, использующих одинаковые подвыражения, создавать узлы для этих подвыражений только один раз.

Например, для выражения a+a*(b-c)+(b-c)*d можно построить такое абстрактное дерево:

Но в таком дереве довольно много повторов. Более эффективно выразить то же самое в виде ациклического графа:

Если хранение графа реализовано в виде списка связности (т.е. роль указателей на дочерние элементы играют индексы в массиве), то реализовать подобное построение достаточно легко, если промежуточные узлы создаются когда уже разобраны их дочерние элементы (т.е. при LR(1)-анализе или анализе методом рекурсивного спуска) – тогда достаточно вместо создания нового узла искать сперва в массиве уже существующий узел с такой же меткой и такими же номерами дочерних элементов и возвращать его вместо создания нового.

Вообще говоря, поиск в массиве – не слишком эффективный подход, и более удачным будет использование словаря на основе, например, хэш-таблицы.

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

Другой популярный метод представления промежуточного кода – т.н. трёхадресный код или вариация на тему.

По сути, трёхадресный код представляет из себя своего рода “абстрактный язык ассемблера” – последовательность простых команд, использующих один унарный или бинарный оператор, и не более трёх адресов в памяти: один для результата, и два для аргументов.

Трёхадресный код позволяет вводить новые адреса (переменные) по мере необходимости и не задаётся вопросами ограниченности объёма памяти или числа регистров.

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

t1 = y * z
t2 = x + t1

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

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

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

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

Команды присваивания вида x = y op z, где op – некая бинарная операция, x, y и z – адреса.
Команды присваивания вида x = op y, где op – некая унарная операция, x, y – адреса.
Команды копирования вида x = y, где x, y – адреса.
Безусловный переход goto L, где L – номер (метка) какой-то команды.
Условный переход вида if x goto L и ifNot x goto L.
Вызов процедур, передача параметров и возврат из процедур. Реализуются командами param x для параметров, call p, n, где p – адрес процедуры, n – число параметров, и return x для возврата из процедуры.
Индексированные присваивания x = y[i] и y[i] = x, где i – адрес числовой переменной или константы.
Присваивание адресов вида x = &y
Присваивание указателей вида x = *y и *x = y.

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

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

Четвёрки используют четыре поля для представления трёхадресных команд: адрес результата, адреса операндов и идентификатор операции.

Недостатком четвёрок является необходимость явно отслеживать адреса временных значений.

Тройки не определяют явно адрес результата. Вместо этого, считается, что результат размещается во временной переменной, соответствующей номеру команды в массиве команд. Этот номер называется номером значения.

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

Косвенные тройки вместо номера команды используют адрес структуры, представляющей соответствующее выражение, и в массиве команд аналогично используются указатели. Тогда ссылки на значения не связаны с порядком команд.

Это, возможно, наиболее удобный вариант, сочетающий достоинства троек (отсутствие необходимости явно отслеживать временные переменные) и четвёрок (лёгкость переупорядочивания команд).

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

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

Однако есть обратная сторона: в императивных программах, в зависимости от того, по какому пути пойдёт поток управления, переменные могут принимать разные значения, например

1: if flag goto 4
2: x = 2
3: goto 5
4: x = 1
5: y = x * x

Если flag = true, то x = 1 и y = 1. Иначе, x = 2 и y = 4. Для разрешения этой неоднозначности, представление в виде статически единственных присваиваний вводит функцию φ, которая может быть использована вместо адреса, и которая выбирает аргумент в зависимости от того, по какому пути потока управления прошла программа:

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

Этот метод представления хорошо подходит для функциональных языков, поскольку в функциональных языках правила переменных примерно такие же – многократные присваивания одной переменной невозможны в исходном языке. Как следствие, определение φ-функции значительно упрощается.

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