Урок 4: Синтаксический анализатор, часть 1

Вступление

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

-------------               --------------                  -----------                 ----------------
|           |  Лексический  |            |  Синтаксический  | Дерево  |  Семантический  |    Дерево    |
| Программа |    ----->     |   Токены   |      ----->      | разбора |      ----->     | абстрактного |
|           |  анализатор   |            |    анализатор    |         |   анализатор    |  синтаксиса  |
-------------               --------------                  -----------                 ----------------

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

Как и в предыдущем уроке, для создания синтаксического анализатора мы воспользуемся специальным инструментом под названием «генератор синтаксических анализаторов» bison. Этот инструмент хорошо работает в связке с flex и позволяет довольно легко выполнить разбор грамматики.

На практике инструмент bison применяется чаще чем flex. Файлы с правилами для bison можно встретить в интерпретаторах perl, ruby. Более того, если посмотреть в код синтаксического анализатора gcc, то в нём можно разглядеть следы былого использования bison. Былого потому что в какой-то момент всю лицевую часть gcc переписали без использования генераторов ради скорости и расширения возможностей.

Для наших же целей (по крайней мере в первом семестре) и скорости и возможностей bison более чем достаточно, поэтому мы воспользуемся именно им.

Выполнение

Кратко про `bison`

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

Стурктура файла bison тоже похожа на структуру файла flex, хотя само наполнение будет различаться достаточно сильно:


%{

 Пролог

 

 Сюда помещается код на языке Си, необходимый для работы анализатора.

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

%}



Объявления



Здесь располагаются объявления токенов и типов данных,

с которыми работает анализатор



%%



Правила грамматики



Здесь содержится описание грамматики в БНФ (Бэкус-Нуровская Форма). Правила

выглядят примерно следующим образом:



нетерминал: правило_1 {действия}

           | правило_2 {действия}

           ...

           ;



%%



Эпилог



Сюда можно помещать код на языке Си как если бы это был обычный файл

исходного кода

Обычно код для bison расположен в файлах с расширениями .y или .yy. Для примера можно создать минимальный файл на bison и выполнить трансляцию в язык Си. Рассмотрим содержимое файла x-grammar.y в каталоге src:


%%

program:;

%%

Теперь соберём этот файл:


$ bison src/x-grammar.l



$ ls x-grammar.tab.c

x-grammar.tab.c

Помимо разделителей секций %% нам пришлось добавить строчку program:;. Это пустое правило, без которого файл грамматики не оттранслируется. Сам по себе файл x-parser.tab.c бесполезен, его можно удалить но любопытствующие могут поизучать его внутренности.

Интеграция модуля в проект

Компиляция модуля

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

---------------          ---------------
|             |   bison  |             |
| x-grammar.y |  ----->  | x-grammar.c |
|             |          |             |\
---------------          --------------- \
                                          \  gcc
---------------          ---------------   \----->  ---------------
|             |   flex   |             |            |             |
|  x-lexer.l  |  ----->  |  x-lexer.c  |    ----->  |   x_d.out   |
|             |          |             |            |             |
---------------          ---------------   /----->  ---------------
                                          /
                         --------------- /
                         |             |/
                         |    main.c   |
                         |             |
                         ---------------

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


$ bison src/x-grammar.y --defines=gen/x-grammar.h -o gen/x-grammar.c

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


%{

  #include "x-lexer.h"



  void yyerror (char const * s);

%}



%%



program:;



%%



/**

 * @brief Реакция на ошибку

 *

 * @param [in] msg Печатаемое сообщение

 *

 * Данная функция автоматически вызывается bison'ом если на вход поступает

 * токен, не удовлетворяющий ни одному правилу

 */

void yyerror(char const * msg)

{

}

Во-первых в прологе появилось включение заголовочного файла лексического анализатора. Оно нам необходимо из-за описания функции yylex внутри файла. Во-вторых мы добавили описание и определение функции yyerror. Эта функция вызывается автоматически при возникновении ошибки разбора, и её определение обязательно для работы синтаксического анализатора. На всякий случай приведём правила сборки:

x-grammar.c: x-lexer.c
	mkdir -p $(GEN_DIR)
	bison $(SRC_DIR)/x-grammar.y --defines=$(GEN_DIR)/x-grammar.h -o $(GEN_DIR)/x-grammar.c

x-grammar.o: x-grammar.c
	$(CC) $(CFLAGS) $(GEN_DIR)/x-grammar.c -I$(GEN_DIR) -o $(OBJ_DIR)/x-grammar.o -c

Взаимодействие модуля с остальным кодом

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


yyin    = f;

res     = yyparse();

Здесь переменная yyin описана в модуле анализатора и содержит в себе указатель на входной файл. Кроме того, необходимо не забыть подключить заголовочный файл от нашего синтаксического анализатора:


#include "x-grammar.h"

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

Взаимодействие `bison` и `flex`

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

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


%token TMP_UNIVERSAL

Теперь следует доработать правило грамматики так чтобы оно принимало любое количество этих токенов:


program: TMP_UNIVERSAL program

| %empty

;

Такая запись должна быть понятна всем, знакомым с формальными грамматиками, но напомню что означает она примерно следующее: нетерминал program допускает либо пустую последовательность токенов %empty либо токен TMP_UNIVERSAL, после которого идёт нетерминал program.

Следующей нашей задачей станет доработать файл лексического анализатора (можно взять какое-нибудь одно правило) и добавить возврат класса токена:


if { printLexeme("IF"); return TMP_UNIVERSAL; }

Чтобы лексический анализатор видел объявление токена TMP_UNIVERSAL, нужно не забыть подключить заголовочный файл x-grammar.h. Для того чтобы убедиться что всё это действительно работает, в синтаксическом правиле можно сделать выдачу какого-нибудь сообщения при применении правила грамматики:


program: TMP_UNIVERSAL program { printf("Правило 1\n"); }

| %empty { printf("Правило 2\n"); }

;

Если наше тестирование лексического анализатора было составлено хорошо, то оно поломается, но мы увидим что на программах без if у нас добавилась строка «Правило 2», а на программах с if будет также добавлена строка «Правило 1».

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

Отладочные печати

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


/**

 * @brief Печать считанного терминального токена

 *

 * @param [in] tokName  Название класса токена

 */

static void printTerminal(const char * tokName)

{

    printf("<%s, \"%s\", %d:%d, %d:%d>\n",

           tokName,

           yytext,

           yylloc.first_line,

           yylloc.first_column,

           yylloc.last_line,

           yylloc.last_column);

}



/**

 * @brief Печать выявленного нетерминала

 *

 * @param [in] tokName  Название класса токена

 *

 * Нетерминальные токены не имеют прямого отображения в исходном коде, поэтому

 * для их печати мы не будем выводить положение в исходнике (хотя могли бы)

 */

static void printNonTerminal(const char * tokName)

{

    printf("<%s>\n",

           tokName);

}

Мы разделим печать терминалов и печать нетерминалов, т.к. для терминалов легко определить положение в тексте, а для нетерминалов нам этого пока что не понадобится. Мы видим что для печати позиции в тексте применяется переменная yylloc, которая в bison работает полу-автоматически при включении директивы %locations. Для печати лексемы используется переменная yytext, а класс токена tokName будет задаваться внутри самих правил.

Составляем грамматику языка

Принимаем простые литералы

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

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


%token TOK_CHAR TOK_INT TOK_TRUE TOK_FALSE

Отдельным образом объявлять нетерминалы нам сейчас не нужно. Теперь составим простые правила для принятия любой последовательности литералов:


program: const_token program { printNonTerminal("const_token program"); }

| %empty

;



const_token:

  TOK_INT       { printTerminal("TOK_INT"); }

| TOK_TRUE      { printTerminal("TOK_TRUE"); }

| TOK_FALSE     { printTerminal("TOK_FALSE"); }

| TOK_CHAR      { printTerminal("TOK_CHAR"); }

;

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


\'\\?.\'                { return TOK_CHAR; }

{INTEGER}               { return TOK_INT; }

true                    { return TOK_TRUE; }

false                   { return TOK_FALSE; }

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


/**

 * @brief Автоматическое действие при чтении лексемы

 */

#define YY_USER_ACTION { \

    yylloc.first_line   = line(); \

    yylloc.last_line    = line(); \

    yylloc.first_column = colomn(); \

    yylloc.last_column  = colomn() + yyleng - 1; \

    incrColomn(yyleng); }

Принимаем пары операндов

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


program: expr program { printNonTerminal("expr program"); }

| %empty

;



expr:

  const_token '/' const_token    { printNonTerminal("const_token '/' const_token"); }

;



const_token:

  TOK_INT       { printTerminal("TOK_INT"); }

| TOK_TRUE      { printTerminal("TOK_TRUE"); }

| TOK_FALSE     { printTerminal("TOK_FALSE"); }

| TOK_CHAR      { printTerminal("TOK_CHAR"); }

;

Данная грамматика принимает на вход тройки выражений «операнд, действие, операнд». При этом если раньше наш анализатор просматривал все тестовые файлы до конца, то сейчас он будет завершаться на первой попавшейся ошибке (например если после литерала идёт не /, а другой литерал).

Принимаем много операндов

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


expr:

  const_token                                 { printNonTerminal("const_token"); }

| expr '/' expr                               { printNonTerminal("expr '/' expr"); }

Теперь мы сможем принять на вход любое выражение со сложениями. Обратим внимание что символ '/' использовался напрямую в качестве класса токена. Такое возможно если токеном является один символ. Теперь рассмотрим для примера разбор выражения 8 / 2 / 2:

|-----------  expr  --------|
|                           |
const  '/'  |----  expr  ---|
  |     |   |               |
  |     |   const  '/'  const
  |     |     |     |     |
  8     /     2     /     2

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

|-----------  expr  --------|
|                           |
const  '/'  |----   1    ---|
  |     |
  |     |
  |     |
  8     /

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

|-----------  expr  --------|
|                           |
|----  expr  ---|  '/'  const
|               |   |     |
const  '/'  const   |     |
  |     |     |     |     |
  8     /     2     /     2

Здесь мы видим лево ассоциативный разбор. Если мы начнём вычислять результат этого дерева разбора, то получим ответ 2. При этом такой разбор выражения тоже будет правильным. Грамматика, допускающая для заданной строки более одного варианта построения дерева разбора называется неоднозначной и может приводить к проблемам разного вычисления одинаковых выражений. Чтобы решить эту проблему следует определить ассоциативность операции и всегда разбирать их по одному правилу. Сделать это можно при помощи директивы %left '/' в секции объявлений.

Добавляем сложения

Разобравшись с ассоциативностью, попробуем добавить действие сложения:


expr:

  const_token                                 { printNonTerminal("const_token"); }

| expr '/' expr                               { printNonTerminal("expr '/' expr"); }

| expr '+' expr                               { printNonTerminal("expr '+' expr"); }

Теперь построим дерево разбора для выражения 2 + 4 / 2:

|-----------  expr  --------|
|                           |
|----  expr  ---|  '/'  const
|               |   |     |
const  '+'  const   |     |
  |     |     |     |     |
  2     +     4     /     2

У нас принят лево ассоциативный разбор, поэтому дерево выражений будет построено таким образом что сначала выполнится сложение, а потом деление. Чтобы избежать такого эффекта можно поступить несколькими способами: переписать грамматику или задать приоритеты операций. Мы поступим вторым способом, т.к. для нас он проще и понятней:


%left '+'

%left '/'

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

|-----------  expr  --------|
|                           |
const  '+'  |----  expr  ---|
  |     |   |               |
  |     |   const  '/'  const
  |     |     |     |     |
  2     +     4     /     2

Унарные операции

Пока что мы рассматривали операции от двух аргументов, однако представим что нам надо работать с отрицательным числом, например -1. Анализатору необходимо каким-либо образом понять что в данном случае речь идёт не об операции вычитания, а о части знаке конкретного литерала. Для этих целей существует понятие унарных операций. Они задаются при помощи директивы %precedence, например унарный минус будет выглядеть таким образом: %precedence TOK_UMIN. Далее правила с унарным минусом задаются следующим образом:


| '-' expr  %prec TOK_UMIN      { printNonTerminal("'-' expr  %prec TOK_UMIN");

Теперь мы можем использовать отрицательные числа в наших выражениях. Дальнейшей задачей для самостоятельного решения будет добавление в разбор выражения прочих операций, работы со скобками и идентификаторами: -, *, >, <, &&, ||, ==, !=, >=, <=, !.

Последовательность выражений

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


assign_expr:

  ident_token '=' expr  { printNonTerminal("ident_token '=' expr"); }

;

Здесь ident_token - правило, допускающее идентификатор, которое мы вполне можем составить без лишних подсказок. Кстати, не забудем что идентификатор также допустим и внутри правила expr.

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


single_statement:

  assign_expr       { printNonTerminal("assign_expr"); }

;

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


statement:

  single_statement ';'  { printNonTerminal("single_statement ';'"); }

;

Теперь покажем что эти выражения идут друг за другом:


func_body:

  func_body statement   { printNonTerminal("func_body statement"); }

| %empty                { /* А тут ничего не будем писать */ }

;

И доработаем начальное правило:


program: func_body { printNonTerminal("func_body"); }

;

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


a = b + 10 / c + 3;

d = 456 / f + e + g;

Далее мы попытаемся добавить в нашу грамматику понятие функции.

Добавление функций

Функция состоит из двух частей: сигнатуры с идентификатором, то есть описания параметров с типом возврата и непосредственно телом, заключённым в фигурные скобки. Кроме того, в нашем языке есть понятие объявления функции - сигнатуры с идентификатором без тела функции. Определение понадобится в следующих уроках для упрощения семантического анализа. В языке функции выглядят так:


bool f1(int a, int & b); /* Объявление */



bool f1(int a, int & b)  /* Определение */

{

    /* Тело функции */

}

Можно видеть что синтаксически функции не сильно отличаются от таковых в языке Си. Однако у нас есть элемент, который встречается только в языке C++ - ссылка на объект. Наш язык не поддерживает указателей, однако необходимость в модификации объектов, передаваемых как параметр функции сохраняется. Для этого мы говорим компилятору что передаём параметром не значение объекта, а его адрес. Рассмотрим правила для распознавания функций:


func_def:

  func_sign '{' func_body '}'   { printNonTerminal("func_sign '{' func_body '}'"); }

| func_sign ';'                 { printNonTerminal("func_sign ';'"); }

;

Пока что мы сделаем наиболее простой вариант сигнатуры функций, который не учитывает массивы:


func_sign:

  type_token ident_token sign_arg_cons                  {

      printNonTerminal("type_token ident_token sign_arg_cons");

  }

;

Обратим внимание что возврат ссылки на объект у нас невозможен. Правило type_token должно просто принимать названия типов, его мы описывать не будем. А вот правило sign_arg_cons будет уже более сложным, его мы рассмотрим отдельно:


/* Список аргументов */

sign_arg_cons:

  '(' ')'               { printNonTerminal("'(' ')'"); }

| '(' sign_arg_list ')' { printNonTerminal("'(' sign_arg_list ')'"); }

;



/* Непосредственно перечисление аргументов */

sign_arg_list:

  type_token obj_modifier ident_token                                    {

      printNonTerminal("type_token obj_modifier ident_token");

  }

| type_token obj_modifier ident_token ',' sign_arg_list                  {

      printNonTerminal("type_token obj_modifier ident_token ',' sign_arg_list");

  }

;



/* Это опциональные объектов */

obj_modifier:

  '&'       {  printTerminal("&"); }

| %empty    { /* Ничего не пишем */ }

;

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


program:

  input { printNonTerminal("input"); }

;



input:

  func_def          { printNonTerminal("func_def"); }

| func_def input    { printNonTerminal("func_def input"); }

;

Теперь наша грамматика будет принимать на вход строки объявлений, обрамлённые в функции:


int f1()

{

    a = b + 10 / c + 3;

}



void f2(int d, bool b)

{

  d = 456 / fg + e + f;

}

Итог

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

2020-11