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

Вступление

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

Выполнение

Оператор возврата

Как и в любом другом языке наш оператор возврата будет называться return, и он сможет либо возвращать значение, либо не возвращать ничего:

void f1()
{
    return; // Функция не имеет возвращаемого значения
}

int f2()
{
    return 42; // Возвращаем целое число
}

Ничего сложного с данным оператором нет - он делается в простые два правила грамматики:

/* Выражение завершения процедуры */
return_expr:
  TOK_RET return_expr_tail { printNonTerminal("TOK_RET return_expr_tail"); }
;

/* Завершение процедуры может быть либо по значению, либо пустое */
return_expr_tail:
  expr      { printNonTerminal("expr"); }
| %empty    { /* Ничего не пишем */ }
;

Само правило return_expr следует добавить продукции для правила single_statement. Думаю, тут каких-либо дополнительных объяснений не требуется, поэтому переходим далее.

Массивы

Примеры использования в языке

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

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

Ещё одной особенностью языка является отсутствие понятие указателя. Это приводит к тому что мы не можем работать с динамическими массивами так как это сделано в языке Си - в нашем случае идентификатор сразу во время объявления должен быть ассоциирован с массивом. И тут то мы можем вспомнить как в начале урока говорили про необходимость добавить правило инициализации во время объявления переменной.

Для того чтобы нам было понятнее как строить грамматику, сначала рассмотрим примеры работы с массивами:

int[10] arr; // Объявляем массив
arr[0] = 0;  // Делаем запись в элемент массива
delete arr;  // Удаляем массив

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

Следующие варианты работы с массивом - это передача массива в качестве аргумента функции:

void f1(int[][] matr, int cols, int rows) { /* ... */ }

void f2()
{
    int[10][10] matr; // Объявляем массив
    f(matr, 10, 10);  // Вызываем функцию с передачей массива в качестве аргумента
    delete matr;      // Удаляем массив
}

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

Далее следует рассмотреть случаи когда функция возвращает массив:

// Функция возвращает одномерный массив
int[] createArray(int size)
{
    int[size] arr;
    return arr;
}

void f()
{
    int[] arr = createArray(10); // Объект arr указывает на массив, созданный в createArray
    delete arr;                  // Удаляем созданный массив
}

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

Добавление в грамматику

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

/* Обращение к массиву по индексу либо выражение с указанием количества элементов */
arr_index_token:
  '[' expr ']'  arr_index_token { printNonTerminal("'[' expr ']'  arr_index_token"); }
| '[' expr ']'                  { printNonTerminal("'[' expr ']'"); }
;

В данном примере мы видим правило для указания элемента или размера массива, произвольной ненулевой размерности. В самом правиле нам всё знакомо, интересно будет найти все места куда это правило можно применить.

Во-первых указание индекса элемента массива может быть в обычном арифметическом выражении:

expr:
/* ... */
| ident_token arr_index_token   { printNonTerminal("ident_token arr_index_token"); }

Во-вторых мы можем производить запись в конкретный элемент массива:

assign_expr:
/* ... */  
| ident_token arr_index_token '=' expr  { printNonTerminal("ident_token arr_index_token '=' expr"); }
;

И в-третьих мы можем указывать размер массива при его объявлении:

decl_statement:
/* ... */
| type_token arr_index_token ident_token decl_list          {
      printNonTerminal("type_token arr_index_token ident_token decl_list");
  }

Также возникает необходимость использования квадратных скобок без указания индекса или размера внутри:

/* Объявление массива для случаев когда размер заранее неизвестен */
arr_decl_token:
  '[' ']' arr_decl_token { printNonTerminal("arr_decl_token"); }
| '[' ']' { printNonTerminal("'[' ']'"); }
;

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

func_sign:
/* ... */
| type_token arr_decl_token ident_token sign_arg_cons   {
      printNonTerminal("type_token arr_decl_token ident_token sign_arg_cons");
  }

Далее, без указания размера массивы обозначаются в сигнатурах функций:

sign_arg_list:
/* ... */
 type_token arr_decl_token ident_token                     {
      printNonTerminal("type_token arr_decl_token ident_token");
  }
| type_token arr_decl_token ident_token ',' sign_arg_list   {
      printNonTerminal("type_token arr_decl_token ident_token ',' sign_arg_list");
  }

И последний случай - объявление массива в случае когда инициализация происходит при помощи возвращаемого функцией значения:

decl_statement:
/* ... */
| type_token arr_decl_token ident_token '=' expr decl_list  {
      printNonTerminal("type_token arr_decl_token ident_token '=' expr decl_list");
  }

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

/* Выражение удаления массива */
delete_statement:
  TOK_DELETE ident_token { printNonTerminal("TOK_DELETE ident_token"); }
;

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

Тестирование

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

/* Минимальная корректная программа на языке X */

int main()
{
    return 0;
}

Получим следующую выдачу: 

<TOK_TYPE_INT, "int", 3:1, 3:3>
<TOK_IDENT, "main", 3:5, 3:8>
<'(' ')'>
<type_token ident_token sign_arg_cons>
<TOK_INT, "0", 5:12, 5:12>
<const_token>
<expr>
<TOK_RET return_expr_tail>
<return_expr>
<single_statement ';'>
<func_body statement>
<func_sign '{' func_body '}'>
<func_def>
<input>

Сам по себе сценарий тестирования пока что останется неизменным, однако нам придётся добавить довольно много тестовых примеров на различные комбинации условных конструкций и циклов. Не стоит забывать что каждая из них может быть вложенной. Также не стоит забывать про различные способы описания функций и объявления переменных. В моём эталонном проекте объём тестов корректных программ увеличился с 94 строк до 254.

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

void yyerror(char const * msg)
{
    fprintf (stderr,
             "Ошибка: %d:%d: %s\n",
             yylloc.first_line,
             yylloc.first_column,
             msg);
    exit(1);
}

Итог

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