Урок 6: Построение дерева разбора

Вступление

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

Выполнение

Основы дерева разбора

Итак, чтобы лучше понимать что мы собираемся делать, рассмотрим наглядный пример:

$ cat tests/in/correct/1.1.x
/* Минимальная корректная программа на языке X */

int main()
{
    return 0;
}

$ ./bin/debug/x_d tests/in/correct/1.1.x
 <NODE_MODULE_T: "tests/in/correct/1.1.x">
  <NODE_FUNCTION_T: "main">
   Аргументы функции:
    Отсутствуют
   Тело функции:
    <NODE_RETURN_T: >
     Возвращаемое выражение:
      <NODE_LITERAL_T: "0">

Мы можем видеть что компилятор начал выдавать уже не просто применённое грамматическое правило, а вполне себе древовидное представление программы. По сути нам нужно будет выполнить две вещи: создать структуру дерева и научиться строить дерево во время разбора. Начнём с создания структуры дерева разбора.

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

-------------
|  Модуль   |
-------------
    |          -------------  nextNode  ------------- nextNode
    ---------->| Функция 1 |----------->| Функция 2 |-----------> ...
    firstFunc  -------------            -------------

Теперь воплотим это описание узла в коде. Сам код для описания дерева будем хранить в файлах x-node.c и x-node.h:

typedef enum
{
    NODE_MODULE_T,          /*!< Узел, содержащий модуль */
    NODE_END
} NodeType_t;

typedef struct Node_s
{
    NodeType_t      type;           /*!< Тип узла */
    struct Node_s   * nextNode;     /*!< Следующий узел */
    
    /* Здесь располагаются указатели на различные дочерние узлы */
    union
    {
        /* Поля модуля */
        struct Node_s       * firstFunc;    /*!< Первая функция модуля */
    };
} Node_t;

Проведём небольшой разбор увиденного. Объект типа Node_t должен представлять любой узел компилируемой программы. Сейчас мы сделали набросок только для описания модуля и последовательности узлов. Множество NodeType_t описывает типы узлов, и сам объект узла имеет поле type соответствующего типа. Наиболее непонятным моментом может показаться неименованное объединение, содержащее в себе всего одно поле firstFunc. Это поле указывает на объект первой функции модуля, т.е. по сути является дугой к первому дочернему узлу. Зачем же было помещать его в объединение? Разные типы узлов содержат разные ссылки на дочерние узлы, более того один узел может иметь несколько разных дочерних узлов, которые не могут идти один за другим. Например, узел функции будет содержать три дуги на дочерние узлы: узел первого формального аргумента, узел тела функции и узел, содержащий тип возвращаемого значения (с последним есть особенности). Рассмортим пример определения функции и его представления в дереве разбора:

int[] f1(int a, int b)
{
   ...
}

-------------
|  Модуль   |
-------------
    |          -------------
    ---------->|     f1    |
    firstFunc  -------------
                  |  |  |
                  |  |  |        -------------           -------------
                  |  |  -------->|   int a   |---------->|   int b   |
                  |  |  firstArg ------------- nextNode  -------------
                  |  |
                  |  |                       -------------
                  |  ----------------------->|   int[]   |
                  |       retTypeNode        -------------
                  |
                  |                                            ----------------
                  -------------------------------------------->| Тело функции |
                             funcBody                          ----------------

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

typedef enum
{
    NODE_MODULE_T,          /*!< Узел, содержащий модуль */
    NODE_FUNCTION_T,        /*!< Узел, содержащий функцию */
    NODE_END
} NodeType_t;

typedef struct Node_s
{
    NodeType_t      type;           /*!< Тип узла */
    struct Node_s   * nextNode;     /*!< Следующий узел */

    /* Значения, характерные для разных типов узлов */
    union
    {
        char        * moduleName;   /*!< Имя модуля */
        char        * funcName;     /*!< Имя функции */
    };

    /* Здесь располагаются указатели на различные дочерние узлы */
    union
    {
        /* Поля модуля */
        struct Node_s       * firstFunc;    /*!< Первая функция модуля */

        /* Поля функции */
        struct
        {
            struct Node_s   * firstArg;     /*!< Объявление первого аргумента */
            struct Node_s   * funcBody;     /*!< Тело функции */
            struct Node_s   * retTypeNode;  /*!< Узел возвращаемого значения */
        };
    };
} Node_t;

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

Рассмотрим работу с узлами дерева разбора. Напомню что доступ к полям структуры мы осуществляем ТОЛЬКО через функции чтения/записи соответствующих значений. Таким образом, нигде кроме файла x-node.c обращений к полям структуры Node_t быть не может. Итак, вот пример создания узла модуля:

static Node_t * node_CreateNode(NodeType_t  type)
{
    Node_t  * node; /* Создаваемый узел */

    node = calloc(1, sizeof(Node_t));
    assert(node != NULL);

    node->type = type;

    return node;
}

Node_t * node_CreateModuleNode(const char * moduleName)
{
    Node_t  * node;

    node = node_CreateNode(NODE_MODULE_T);

    node->moduleName    = strdup(moduleName);

    return node;
}

Здесь у нас есть внутренняя функция node_CreateNode по созданию и обнулению узла произвольного типа, и функция node_CreateModuleNode, по созданию непосредственно узла модуля с инициализацией соответствующих полей.

Также стоит показать пример функции удаления узла:

void node_DeleteNode(Node_t * node)
{
    switch(node_GetNodeType(node))
    {
      case NODE_MODULE_T:
      {
        free(node->moduleName);

        Node_t * func = node_GetModuleFirstFunc(node);
        if( func != NULL)
        {
            /* Удаляем все функции модуля */
            node_DeleteNode(func);
        }
        break;
      }
// LCOV_EXCL_START
      default:
      {
        assert(!"Неизвестный тип удаляемого узла");
      }
// LCOV_EXCL_STOP
    }

    /* Запускаем удаление следующих узлов */
    Node_t  * nextNode = node_GetNextNode(node);
    if( nextNode != NULL )
    {
        node_DeleteNode(nextNode);
    }

    free(node);
}

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

Ещё одним примером, который стоит рассмотреть заранее является функция получения значения поля. Например:

const char * node_GetModuleName(const Node_t * node)
{
    assert(node_GetNodeType(node) == NODE_MODULE_T);
    return node->moduleName;
}

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

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

Действия в грамматике

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

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

    Node_t  * node; /* Узел модуля, от которого всё растёт */

    node = node_CreateModuleNode(argv[1]);
    yyparse(node);

Функцию создания узла модуля мы уже знаем, а вот новым в этом примере является то что в функцию yyparse подаётся аргумент. Изменить сигнатуру этой функции можно специальным указанием в файле грамматики:

%parse-param {Node_t * moduleNode}

Это указание также изменит нам сигнатуру функции yyerror:

void yyerror (Node_t * moduleNode, char const * s);

Корень дерева в наш разбор грамматики мы передать смогли, как создать узлы после применения правила грамматики мы знаем, и теперь возникает вопрос а как, собственно, все эти узлы соединить в дерево?

В bison каждое правило можно представить в виде функции, обладающей своим типом возврата. Соответственно, мы можем возвращать созданные узлы из продукции в правило, из которого был вывод и таким образом обеспечивать построение дерева. Для обозначения переменной, хранящей возвращаеомое значение применяется специальная конструкция $$. А для того чтобы прочитать значение, которое вернула та или иная часть продукции можно использовать специальные обозначения $1, $2, ..., где число - порядковый номер части правила. Например (для упрощения возьмём пример калькулятора):

/* $1   $2  $3 */
| expr '+' expr { $$ = $1 + $3; }

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

/*
 * Объявление %union содержит все возможные типы значений токенов.
 */
%union
{
   Node_t   * nodeVal;
   char     * strVal;
}

/*
 * Ключевое слово %type служит для объявления нетерминала грамматики и задания
 * его типа
 */
%type<nodeVal> input func_def func_sign sign_arg_cons sign_arg_list func_body

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

program:
  input {
    node_SetModuleFirstFunc(moduleNode, $1);
  }
;

/* Здесь идут входные выражения. Выражением может быть только определение функции */
input:
  func_def          { $$ = $1;}
| func_def input    {
    $$ = $1;
    node_SetNextNode($1, $2);
  }

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

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

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

%destructor { if($$ != NULL) node_DeleteNode($$); } <nodeVal>
%destructor { free($$); } <strVal>

Объявление деструктора - это специальное указание, которое пишется для своего типа возврата из правила. Теперь проблема утечки памяти при возникновении ошбок решена, и у нас есть понимание как строить дерево во время разбора грамматики.

Прочие элементы дерева разбора

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

/**
 * @brief Тип узла в дереве разбора
 */
typedef enum
{
    NODE_MODULE_T,          /*!< Узел, содержащий модуль */
    NODE_FUNCTION_T,        /*!< Узел, содержащий функцию */
    NODE_OBJECT_T,          /*!< Узел, содержащий объект */
    NODE_EXPRESSION_T,      /*!< Узел, содержащий выражение */
    NODE_LITERAL_T,         /*!< Узел, содержащий литерал */
    NODE_IF_T,              /*!< Узел условной конструкции */
    NODE_FOR_T,             /*!< Узел цикла */
    NODE_CONTINUE_T,        /*!< Узел перехода на следующую итерацию */
    NODE_BREAK_T,           /*!< Узел выхода из цикла */
    NODE_RETURN_T,          /*!< Узел возврата */
    NODE_DELETE_T,          /*!< Узел удаления массива */
    NODE_END
} NodeType_t;

Типов узлов у нас совсем немного, но можно пояснить отдельные моменты. Рассмотрим структуру конструкций if-elif-else:

        struct
        {
            struct Node_s   * condExpr;     /*!< Выражение вычисления условия */
            struct Node_s   * ifBodyNode;   /*!< Тело условия (по истинному значению) */
            struct Node_s   * elifNode;     /*!< Узел альтернативного ветвления */
        };

Данная конструкция имеет три специфические дуги: condExpr - выражение, вырабатывающее предикат, по которому переходим на нужную ветвь; ifBodyNode - первый узел в теле перехода по истинной ветви; elifNode - уход на следующий if-узел если языковая конструкция содержит elif.

Условная конструкция довольно простая, дополнительных пояснений не требует. Аналогичным образом будет строиться и конструкция цикла, приводить её пример мы здесь не будем. А вот про что стоит поговорить более пристально - так это про массивы. Мы уже могли заметить что во множестве возможных узлов про массивы нет ни слова. Это связано с тем что любой массив является объектом. Но помимо самого объекта у нас существует также и доступ к элементу массива. Этот доступ будет считаться выражением, т.е. узлом типа NODE_EXPRESSION_T. Выражение - это обычное арифметическое действие, соответственно оно может иметь один или два аргумента:

        /* Поля выражения */
        struct
        {
            struct Node_s   * leftArg;      /*!< Левый аргумент выражения */
            struct Node_s   * rightArg;     /*!< Правый аргумент выражения */
        };

Для целостности повествования приведём множество возможных типо выражений:

/**
 * @brief Тип выражения в узле
 */
typedef enum
{
    EXPR_ASSIGN_T,  /*!< Присваивание */
    EXPR_ADD_T,     /*!< Сложение */
    EXPR_SUB_T,     /*!< Вычитание */
    EXPR_MUL_T,     /*!< Умножение */
    EXPR_DIV_T,     /*!< Деление */
    EXPR_GRT_T,     /*!< Отношение больше */
    EXPR_LES_T,     /*!< Отношение меньше */
    EXPR_GEQ_T,     /*!< Отношение больше или равно */
    EXPR_LEQ_T,     /*!< Отношение меньше или равно */
    EXPR_EQ_T,      /*!< Отношение равно */
    EXPR_NEQ_T,     /*!< Отношение не равно */
    EXPR_LOR_T,     /*!< Логическое или */
    EXPR_LAND_T,    /*!< Логическое и */
    EXPR_LNOT_T,    /*!< Логическое не */
    EXPR_UMIN_T,    /*!< Унарный минус */
    EXPR_DECOMP_T,  /*!< Декомпозиция массива */
    EXPR_CALL_T,    /*!< Вызов процедуры */
    EXPR_END
} ExprType_t;

Самым интресным здесь будет обращение к элементу массива, которое называется декомпозиция массива. Для примера рассмотрим дерево, получающееся при объявлении двумерного массива int[sizeX][sizeY] res;

                              ---------------------
                              | NODE_EXPRESSION_T |
                              |   EXPR_DECOMP_T   |
                              ---------------------
                                 /            \
               ---------------------        ---------------------
               | NODE_EXPRESSION_T |        |   NODE_OBJECT_T   |
               |   EXPR_DECOMP_T   |        |     "sizeY"       |
               ---------------------        ---------------------
                  /              \
---------------------        ---------------------
|   NODE_OBJECT_T   |        |   NODE_OBJECT_T   |
|       "res"       |        |     "sizeX"       |
---------------------        ---------------------

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

Возможны случаи когда у нас в выражении декомпозиции не будет размера. Такое может возникать в случае работы с типом возврата из функции и при непосредственно при инициализации массива значением из функции. Кроме того при работе с типом возврата у нас также не будет и объекта функции. Пожалуй, на текущий момент это всё что надо проговорить про работу с массивами.

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

void node_SetFunctionFirstArg(Node_t * funcNode, Node_t * objNode)
{
    assert(node_GetNodeType(funcNode) == NODE_FUNCTION_T);
    assert(node_GetFunctionFirstArg(funcNode) == NULL);
    assert(node_GetNodeType(objNode) == NODE_OBJECT_T ||
           (node_GetNodeType(objNode) == NODE_EXPRESSION_T &&
            node_GetExpressionType(objNode) == EXPR_DECOMP_T));
    assert(node_IsDeclaration(objNode) ||
           (node_GetNodeType(objNode) == NODE_EXPRESSION_T &&
            node_GetExpressionType(objNode) == EXPR_DECOMP_T));

    funcNode->firstArg = objNode;
}

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

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

Итог

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