Напишем компилятор, часть 5: Генератор кода

Напишемкомпиляторчасть5Генераторкода

академик, разработчик, с прицелом на более яркую техно-социальную жизнь



[next]
20210814 – 22 – 29

Давайте напишем компилятор, часть 5: Генератор кода

Все исходники код для этого сообщения в блоге можно найти

здесь .

A PL / 0 валидатор кода, комбинация лексера и парсер в полноценный интерфейс для компилятора, на удивление полезно. Но он также не так полезен, как полноценный компилятор PL / 0, поскольку полный компилятор будет делать все, что может делать валидатор плюс вывести новое представление этого кода, которое, будем надеяться, ближе к машинный код , чем при запуске. Или, если не ближе к машинному коду, в представлении, которое можно передать компилятору, который у нас уже есть для другого языка.

У нас есть такой язык и компилятор, сидящий без дела: C . Это имеет смысл, поскольку сам компилятор написан на C, и мы использовали компилятор C для компиляции нашего компилятора. Наличие нашего целевого компилятора PL / 0 C наверняка упростит для нас многие вещи, но это будет происходить за счет того, что мы обойдем некоторые очень интересные проблемы. С учетом сказанного, я являюсь поклонником каждого из этих сообщений в блоге, когда мы завершаем что-то, результаты которого мы можем использовать немедленно. Серверная часть генерации переменного тока позволит нам сделать это сегодня. Мы всегда можем вернуться позже и позже написать сборку, генерирующую серверную часть. Кроме того, это наш первый компилятор, поэтому я могу сделать что-то простое, что работает. Кроме того, стоит оставить для всех этих учебников по компиляторам хоть какие-то интересные задачи! По крайней мере, сейчас.

После сегодняшнего дня мы будем способен сгенерировать правильный (хотя, возможно, не очень красивый) код C для всего кода PL / 0 в нашей грамматике в том виде, в котором он существует прямо сейчас. К сожалению, это не включает такие вещи, как базовый ввод и вывод. Мы займемся этим завтра, потому что в конечном итоге это будет немного отличаться от генерации кода, с которым мы будем иметь дело сегодня.

Код организации

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

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

Дополнительно , Я собираюсь добавить префикс ко всем функциям генератора кода, которые использует синтаксический анализатор cg _ , чтобы мы могли немного упростить чтение кода парсера, указав, какие функции относятся к работе синтаксического анализа, а какие нет.

Запись в стандартный вывод

Все функции генератора кода будут вызывать функцию с именем aout () Хотя бы один раз. Это единственная функция, которая выполняет запись в стандартный вывод . Это выглядит так:

 /Генератор кода.  / static void aout (const char fmt, ...) {va_list ap;  va_start (ap, fmt);  (пусто) vfprintf (stdout, fmt, ap);  va_end (ap);  }  

Это в основном сокращение для (void) fprintf (stdout, "% s", ...); , потому что мы собираемся использовать aout () очень много, и так набирать короче. Это единственная функция, полностью внутренняя по отношению к генератору кода. Все остальные функции, которые мы пишем сегодня, будут иметь префикс cg _ и таким образом вызывается синтаксическим анализатором.

Наша первая генерация кода

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

 static void cg_end (void) {aout ("https://briancallahan.net/PL / 0 compiler% s /  n ", PL0C_VERSION);  } 
 

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

# define PL0C_VERSION «1.0.0» в вверху исходного кода. Мы будем увеличивать это число по мере дальнейшего развития компилятора в будущих выпусках. cg_end () вызывается в самом конце парсер:

 статический анализ void (void) {next ();  блокировать();  ожидать (TOK_DOT);  if (type! = 0) error («лишние токены в конце файла»);  cg_end ();  } 
  Рабочий процесс написания генератора кода 

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

+ ------- + | Старт | + ------- + | Нет + - + --------------------------------- + | | V | + ----------- + + ---------- + ------------ | Выполнить | | Магазин | / Готовы к | парсер | ---> | | ---> | | | заявление | | метаданные | выдать код? / + ----------- + + ---------- + ------------ ^ | | | Да | | | --------- V | Нет / конец + ----------- + + ---------- | |

| Конец | + ----- +

 

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

Генерация кода для констант

После парсера сверху первый реальный код, с которым мы имеем дело находится в блок () . И внутри block () , первое, с чем мы имеем дело, это константы. В этом есть смысл, поскольку на самом деле мы просто следуем грамматике PL / 0. Первое, что мы делаем, это проверяем, есть ли у нас TOK_CONST , и если мы это сделаем, мы войдем в раздел объявления констант. Предположим, что это произойдет. Затем мы запускаем ожидать (TOK_CONST) ; , чтобы использовать TOK_CONST и пусть лексер получит и вернет следующий токен. Это должен быть TOK_IDENT , имя константы.

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

В случае, если у нас нет TOK_IDENT здесь эта "проверка генератора кода" завершится неудачно, а затем ожидать (TOK_IDENT); сразу после этого также выйдет из строя и выдаст ошибку. Так что все останется правильно.

Можно сказать, что это немного неэффективно. Но цель здесь не в том, чтобы получить награды за эффективность. Это правильно. Кроме того, я не думаю, что у кого-то возникнет проблема со скоростью, с которой этот компилятор сможет компилировать код PL / 0. И если они это сделают, эти дополнительные простые целочисленные сравнения не будут виноваты.

Посмотрим, как это выглядит в действии:

if (type == TOK_CONST) {ожидать (TOK_CONST); если (type == TOK_IDENT) cg_const (); ожидать (TOK_IDENT); ожидать (TOK_EQUAL); ожидать (TOK_NUMBER); while (type == TOK_COMMA) {ожидать (TOK_COMMA); если (type == TOK_IDENT) cg_const (); ожидать (TOK_IDENT); ожидать (TOK_EQUAL); ожидать (TOK_NUMBER); } ожидать (TOK_SEMICOLON); }
 

Не забудьте поставить cg_const () в обоих местах, потому что у вас может быть несколько констант.

Итак, какой код, как мы знаем, мы можем здесь выводить? Мы знаем, что можем (и должны) вывести C-версию объявления константы! Однако мы еще не знаем, чем будет инициализирована константа. Это нормально. Нам не нужно знать весь оператор перед выводом кода C. Нам просто нужно быть в положении, когда существует единственная, недвусмысленная возможность того, каким может быть вывод кода C. Как только мы окажемся в этом положении, мы должны написать этот код C, именно этот код C и ничего, кроме этого кода C. Мы всегда можем вернуться к генератору кода позже, чтобы закончить оператор, если он не завершен.

Какой здесь C-код имеет смысл? cg_const () функция должна писать объявление константы без номера константа будет инициализирована. Тот выглядит так:

 static void cg_const (void) {aout ("const long% s =", токен);  } 
 

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

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

 $ pl0c file.pl0 |  clang-format 
 

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

Закончим генерировать код для констант. Здесь та же идея: у нас есть вся информация, необходимая для завершения этой строки кода C после того, как мы поглотили знак равенства. Потому что теперь, если это действительный код PL / 0, у нас есть номер. Мы сделаем то же самое прямо перед тем, как ожидать (TOK_NUMBER); , мы выполним «проверку генератора кода» для TOK_NUMBER , а если true, выведите число.

Все вместе это выглядит так:

 if (type == TOK_CONST) {ожидать (TOK_CONST);  если (type == TOK_IDENT) cg_const ();  ожидать (TOK_IDENT);  ожидать (TOK_EQUAL);  если (type == TOK_NUMBER) {cg_symbol ();  cg_semicolon ();  } ожидать (TOK_NUMBER);  while (type == TOK_COMMA) {ожидать (TOK_COMMA);  если (type == TOK_IDENT) cg_const ();  ожидать (TOK_IDENT);  ожидать (TOK_EQUAL);  если (type == TOK_NUMBER) {cg_symbol ();  cg_semicolon ();  } ожидать (TOK_NUMBER);  } ожидать (TOK_SEMICOLON);  } 
 

Я использовал две функции генерации кода для завершения вывода C: cg_symbol () а также cg_semicolon () . cg_semicolon () , где нам нужна точка с запятой. Чтобы предотвратить появление очень длинных строк и, по крайней мере, дать нам некоторое подобие нормального вывода кода C, он выводит точку с запятой, за которой следует новая строка:

static void cg_semicolon (void) {aout ("; п"); }

 

А также cg_symbol () - это уловка для печати любого текущего символа. Для TOK_IDENT а также TOK_NUMBER , это строка токена. Во всем остальном это C-эквивалент токена PL / 0:

static void cg_symbol (void) {switch (type) {case TOK_IDENT: case TOK_NUMBER: aout ( «% s», токен); перерыв; case TOK_BEGIN: aout ("{ n"); перерыв; case TOK_END: ​​aout ("; n} n"); перерыв; case TOK_IF: aout ("если ("); перерыв; case TOK_THEN: case TOK_DO: aout (")"); перерыв; case TOK_ODD: aout ("("); перерыв; case TOK_WHILE: aout ("while ("); перерыв; case TOK_EQUAL: aout ("=="); перерыв; case TOK_COMMA: aout (","); перерыв; case TOK_ASSIGN: aout ("="); break; case TOK_HASH: aout ("! ="); break; case TOK_LESSTHAN: aout ("<---| Emit code | parser? / +-----------+ --------- | |Yes +-----+ +---> "); перерыв; case TOK_PLUS: aout (" + "); break; case TOK_MINUS: aout ("-"); перерыв; case TOK_MULTIPLY: aout ("*"); перерыв; case TOK_DIVIDE: aout ("/"); перерыв; case TOK_LPAREN: aout ("("); перерыв; case TOK_RPAREN: aout (" ) ");}}
 

В этом списке есть несколько странно выглядящих например, TOK_ODD , но мы поговорим о них, когда мы доберемся до них.

Вот, мы хотим вывести текущий символ, так как мы знаем, что это число. Затем мы хотим вывести точку с запятой, чтобы завершить состояние C.

Теперь мы генерируем правильный код C для любого и все константные разделы.

Таблица символов

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

Быстрая демонстрация на английском языке:

<");break;case TOK_GREATERTHAN:aout(">
    «Профессор на лекции». Правила синтаксиса английского языка требуют наличия глагола в этом предложении, но его нет. Анализ этого предложения должен вызвать синтаксическую ошибку.
  • «Автомат для игры в пинбол поливал лекцию». Это предложение удовлетворяет синтаксическим правилам английского языка, но не имеет значения. Семантическая проверка должна пометить это как непонятное.

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

Да, если бы мы хотели быть действительно небрежными, мы могли бы передайте все эти знания компилятору C. Но это действительно плохой стиль, и он не сработает, когда мы вернемся позже и напишем бэкенд сборки. Мы должны написать компилятор, который выводит только правильный код C. Итак, нам понадобится таблица символов.

Наша таблица символов должна будет отслеживать следующую информацию: имя символа, если символ представляет TOK_CONST , TOK_VAR или TOK_PROCEDURE , а уровень глубины символа (чтобы учесть затенение переменных ). Ему нужно будет добавлять константы и переменные по мере их обнаружения. Также потребуется добавлять процедуры по мере их обнаружения. Однако таблица символов должна будет уничтожить все локальные константы и переменные внутри каждой процедуры, когда процедура завершается анализатором. Это потому, что вы должны иметь возможность повторно использовать одни и те же имена локальных переменных в разных процедурах, поскольку эти переменные находятся в разных областях. Но таблица символов никогда не должна забывать имена самих процедур, так как это может привести к ситуации, когда две процедуры будут иметь одно и то же имя, и будет невозможно устранить неоднозначность вызова этого имени.

Тьфу, сложно.

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

 + --------------- + + --------------- + + ---------- ----- + + --------------- + |  Sentinel |  |  Sentinel |  |  Sentinel |  |  Sentinel |  + --------------- + + --------------- + + --------------- + + --------------- + |  Глобальные константы |  |  Глобальные константы |  |  Глобальные константы |  + --------------- + + --------------- + + --------------- + |  Глобальные вары |  |  Глобальные вары |  |  Глобальные вары |  + --------------- + + --------------- + + --------------- + |  Процедура |  |  Процедура |  + --------------- + + --------------- + |  Локальные константы |  + --------------- + |  Местные вары |  + --------------- + 

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

 struct symtab {int depth;  тип int;  название символа;  struct symtab next;  };  статическая структура symtab head;  

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

I я собираюсь инициализировать таблицу символов с помощью sentinel еще до того, как мы войдем в парсер, который всегда будет первым узлом в списке. Этот дозорный будет представлять «основную» процедуру, в которую вложены все наши процедуры. Я сделаю это буквально процедурой с именем main; это предотвратит создание процедуры с таким именем, что вызовет проблемы, когда компилятор C. Это также избавляет нас от необходимости танцевать «пуста таблица символов или нет» всякий раз, когда мы добавляем символы. Мы будем знать, что в таблице символов всегда есть хотя бы один символ:

static void initsymtab (void) {struct symtab new; if ((new = malloc (sizeof (struct symtab))) == NULL) error («сбой malloc»); новое-> глубина = 0; новый-> тип = TOK_PROCEDURE; new-> name = "main"; новый-> следующий = NULL; head = new; }

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

static void addymbol (int type) {struct symtab curr, new; curr = голова; while (1) {if (! strcmp (curr-> name, token)) {if (curr-> depth == (depth - 1)) error ("повторяющийся символ:% s", токен); } if (curr-> next == NULL) break; curr = curr-> следующий; } if ((new = malloc (sizeof (struct symtab))) == NULL) error («сбой malloc»); новое-> глубина = глубина - 1; новый-> тип = тип; if ((new-> name = strdup (token)) == NULL) error («сбой malloc»); новый-> следующий = NULL; curr-> следующий = новый; }

Читаем весь связанный список. Если есть совпадение имени символа, мы проверяем, чтобы уровень глубины не совпадал. Если это так, то это ошибка повторяющегося символа. Вы заметите, что мы всегда это делаем глубина - 1 вещь; это потому, что в block () , мы сразу увеличиваем уровень глубины после проверки, чтобы убедиться, что у нас нет вложенных процедур, и поэтому переменная глубины всегда на один уровень выше, чем мы находимся сейчас.

Когда мы дойдем до последнего элемента в списке и проверим отсутствие дубликатов, мы создаем новый символ. Записываем строку токена, имел ли этот идентификатор TOK_CONST , TOK_VAR , или TOK_PROCEDURE и уровень глубины. Поскольку мы находимся в конце списка, для этого символа нет следующего. Затем мы присоединяем этот новый символ к следующему из текущего последнего символа.

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

Поскольку TOK_PROCEDURE символ всегда является первым записанным символом и его локальным TOK_CONST и

TOK_VAR символы идут после, мы можем перейти к конец списка и проверьте, является ли этот символ TOK_PROCEDURE . Если это не так, мы должны уничтожить его, так как это местный TOK_CONST или

TOK_VAR . Мы должны продолжать уничтожать символы, пока не найдем TOK_PROCEDURE в конце из списка:

static void destroyymbols (void) {struct symtab curr, prev; снова: curr = head; в то время как (текущий-> следующий! = NULL) {prev = curr; curr = curr-> следующий; } если (текущий-> тип! = TOK_PROCEDURE) {бесплатно (текущий-> имя); бесплатно (curr); предыдущая-> следующая = NULL; перейти снова; }}

Опять же, если у вас аллергия на перейти к, вы можете поместить это в цикл.

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

Действительно чистовая обработка постоянных участков

Хорошо, теперь мы можем разместить addymbol () в парсер и покончим с константными секциями навсегда. Вот, наконец, наш завершенный код секции констант:

if (type == TOK_CONST) {ожидать (TOK_CONST); if (type == TOK_IDENT) {добавляет символ (TOK_CONST); cg_const (); } ожидать (TOK_IDENT); ожидать (TOK_EQUAL); если (type == TOK_NUMBER) {cg_symbol (); cg_semicolon (); } ожидать (TOK_NUMBER); while (type == TOK_COMMA) {ожидать (TOK_COMMA); if (type == TOK_IDENT) {добавляет символ (TOK_CONST); cg_const (); } ожидать (TOK_IDENT); ожидать (TOK_EQUAL); если (type == TOK_NUMBER) {cg_symbol (); cg_semicolon (); } ожидать (TOK_NUMBER); } ожидать (TOK_SEMICOLON); }

  Генерация кода для переменных разделов 

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

if (type = = TOK_VAR) {ожидать (TOK_VAR); if (type == TOK_IDENT) {добавляет символ (TOK_VAR); cg_var (); } ожидать (TOK_IDENT); while (type == TOK_COMMA) {ожидать (TOK_COMMA); if (type == TOK_IDENT) {добавляет символ (TOK_VAR); cg_var (); } ожидать (TOK_IDENT); } ожидать (TOK_SEMICOLON); cg_crlf (); }

Одна новая функция генерации кода, предназначенная только для стиля: cg_crlf () , который добавляет новую строку к выходному коду C:

static void cg_crlf (void) {aout (" п"); }

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

Вот код для cg_var () , который на удивление похож на cg_const () , которую мы только что написали:

static void cg_var (void) {aout ("long% s ; n ", токен); }

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

Генерация кода для процедур

Дела начнут усложняться. У нас есть эта странная ситуация с точки зрения C, где в PL / 0 все процедуры технически находятся внутри того, что мы можем считать главный(), которой нет в C. Кроме того, сама основная процедура не имеет имени. Нам понадобится какой-то способ отслеживать, находимся ли мы в именованной процедуре или в безымянной основной процедуре. Мы создадим новую глобальную переменную с именем proc для отслеживания этой информации.

В остальном процедура почти так же, как мы делали для констант и переменных:

while (type == TOK_PROCEDURE) {proc = 1; ожидать (TOK_PROCEDURE); if (type == TOK_IDENT) {добавляет символ (TOK_PROCEDURE); cg_procedure (); } ожидать (TOK_IDENT); ожидать (TOK_SEMICOLON); блокировать(); ожидать (TOK_SEMICOLON); proc = 0; уничтожает символы (); } если (proc == 0) cg_procedure ();

Помните: в конце каждой процедуры нам нужно уничтожить все TOK_CONST а также TOK_VAR символы, локальные для этой процедуры. Нам также необходимо сбросить глобальный proc обратно к 0, потому что в какой-то момент мы введем это main () и нужно чтобы справиться с этим.

Код для генерации функции в C выглядит так:

 static void cg_procedure (void) {if (proc == 0) {aout ("int  n");  aout ("main (int argc, char argv [])  n");  } else {aout ("пустота  п");  aout ("% s (void)  n", токен);  } aout ("{ п");  } 

Наконец, я завершу каждую функцию C небольшим эпилогом, закрывающим все, и если мы в главный() добавляет приятный return 0; линия:

static void cg_epilogue (void) {aout ("; "); если (proc == 0) aout ("возврат 0;"); aout (" п} п п"); }

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

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

 static void block (void) {if (depth ++> 1) error («Превышена глубина вложенности»);  if (type == TOK_CONST) {ожидать (TOK_CONST);  if (type == TOK_IDENT) {добавляет символ (TOK_CONST);  cg_const ();  } ожидать (TOK_IDENT);  ожидать (TOK_EQUAL);  если (type == TOK_NUMBER) {cg_symbol ();  cg_semicolon ();  } ожидать (TOK_NUMBER);  while (type == TOK_COMMA) {ожидать (TOK_COMMA);  if (type == TOK_IDENT) {добавляет символ (TOK_CONST);  cg_const ();  } ожидать (TOK_IDENT);  ожидать (TOK_EQUAL);  если (type == TOK_NUMBER) {cg_symbol ();  cg_semicolon ();  } ожидать (TOK_NUMBER);  } ожидать (TOK_SEMICOLON);  } если (type == TOK_VAR) {ожидать (TOK_VAR);  if (type == TOK_IDENT) {добавляет символ (TOK_VAR);  cg_var ();  } ожидать (TOK_IDENT);  while (type == TOK_COMMA) {ожидать (TOK_COMMA);  if (type == TOK_IDENT) {добавляет символ (TOK_VAR);  cg_var ();  } ожидать (TOK_IDENT);  } ожидать (TOK_SEMICOLON);  cg_crlf ();  } while (type == TOK_PROCEDURE) {proc = 1;  ожидать (TOK_PROCEDURE);  if (type == TOK_IDENT) {добавляет символ (TOK_PROCEDURE);  cg_prologue ();  } ожидать (TOK_IDENT);  ожидать (TOK_SEMICOLON);  блокировать();  ожидать (TOK_SEMICOLON);  proc = 0;  уничтожает символы ();  } если (proc == 0) cg_prologue ();  утверждение();  cg_epilogue ();  if (--depth <0) ошибка («глубина вложенности упала ниже 0»);  } 

  Генерация кода для операторов 

У нас все отлично. Давайте продолжим и погрузимся в генерацию кода для операторов. Если мы сможем это сделать, мы закончим с нашим компилятором!

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

Левая сторона в сравнении с правой

Всякий раз, когда идентификатор упоминается в операторе, нам нужно знать две вещи. Во-первых, нам нужно знать, был ли этот идентификатор ранее объявлен, поскольку мы можем ссылаться только на идентификаторы, которые были ранее объявлены. Мы всегда должны это знать, независимо от того, где в заявлении находится идентификатор. Нам также необходимо знать, имеет ли этот идентификатор семантический смысл для своего местоположения. Это примерно разделено на левую и правая часть оператора присваивания. С левой стороны мы можем иметь только идентификаторы, объявленные как TOK_VAR . С правой стороны у нас может быть TOK_VAR или TOK_CONST , но не TOK_PROCEDURE . Нам также необходимо убедиться, что, если у нас есть оператор вызова, идентификатор, который следует за ним, является TOK_PROCEDURE . Я собираюсь создать три новых #define s: CHECK_LHS , CHECK_RHS , а также CHECK_CALL , которую мы можем использовать в качестве параметра для новой функции, называемой symcheck () , который выполняет эту семантическую проверку за нас. Функция выглядит так:

/ Семантика. / static void symcheck (int check) {struct symtab curr, ret = NULL; curr = голова; в то время как (curr! = NULL) {если (! strcmp (токен, curr-> имя)) ret = curr; curr = curr-> следующий; } if (ret == NULL) error ("неопределенный символ:% s", токен); переключатель (проверка) {case CHECK_LHS: if (ret-> type! = TOK_VAR) error ("должна быть переменная:% s", токен); перерыв; case CHECK_RHS: if (ret-> type == TOK_PROCEDURE) error («не должно быть процедурой:% s», токен); перерыв; case CHECK_CALL: if (ret-> type! = TOK_PROCEDURE) ошибка («должна быть процедура:% s», токен); }}

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

Возврат к генерации кода для операторов

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

 переключатель (тип) {case TOK_IDENT: symcheck (CHECK_LHS);  cg_symbol ();  ожидать (TOK_IDENT);  if (type == TOK_ASSIGN) cg_symbol ();  ожидать (TOK_ASSIGN);  выражение();  перерыв;  

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

 case TOK_CALL: ожидать (TOK_CALL);  if (type == TOK_IDENT) {symcheck (CHECK_CALL);  cg_call ();  } ожидать (TOK_IDENT);  перерыв;  

Как уже упоминалось, нам нужна новая функция генератора кода для cg_call () :

static void cg_call (void) {aout ("% s (); n" , токен); }

Далее идет оператор начала ... конца. И начало, и конец обрабатываются в cg_symbol () , так что ничего нового функции генератора кода для написания. Нам также нужно помнить, что точка с запятой является разделителем операторов и выводит точку с запятой, когда мы встречаемся с ней:

case TOK_BEGIN: cg_symbol (); ожидать (TOK_BEGIN); утверждение(); while (введите == TOK_SEMICOLON) {cg_semicolon (); ожидать (TOK_SEMICOLON); утверждение(); } if (type == TOK_END) cg_symbol (); ожидать (TOK_END); перерыв;

Далее следует оператор if ... then. Как и begin и end, if and then обрабатываются в cg_symbol () , поэтому никаких новых функций генератора кода. Как выражение () , мы не будем беспокоиться о состояние(), пока мы не доберемся туда:

 case TOK_IF: cg_symbol ();  ожидать (TOK_IF);  состояние();  if (type == TOK_THEN) cg_symbol ();  ожидать (TOK_THEN);  утверждение();  перерыв;  

Последнее, что нужно сделать ... Он почти идентичен оператору if ... then:

case TOK_WHILE: cg_symbol (); ожидать (TOK_WHILE); состояние(); if (type == TOK_DO) cg_symbol (); ожидать (TOK_DO); утверждение(); перерыв;

Все вместе:

static void statement (void) {switch (type) {case TOK_IDENT: symcheck ( CHECK_LHS); cg_symbol (); ожидать (TOK_IDENT); if (type == TOK_ASSIGN) cg_symbol (); ожидать (TOK_ASSIGN); выражение(); перерыв; case TOK_CALL: ожидать (TOK_CALL); if (type == TOK_IDENT) {symcheck (CHECK_CALL); cg_call (); } ожидать (TOK_IDENT); перерыв; case TOK_BEGIN: cg_symbol (); ожидать (TOK_BEGIN); утверждение(); while (type == TOK_SEMICOLON) {cg_semicolon (); ожидать (TOK_SEMICOLON); утверждение(); } if (type == TOK_END) cg_symbol (); ожидать (TOK_END); перерыв; case TOK_IF: cg_symbol (); ожидать (TOK_IF); состояние(); if (type == TOK_THEN) cg_symbol (); ожидать (TOK_THEN); утверждение(); перерыв; case TOK_WHILE: cg_symbol (); ожидать (TOK_WHILE); состояние(); if (type == TOK_DO) cg_symbol (); ожидать (TOK_DO); утверждение(); перерыв; }} Генерация кода для условий

Теперь мы можем написать генерацию кода для условий. Нечетный из них TOK_ODD . Для этого потребуется новая функция генератора кода. Но аранжировка интересная. TOK_ODD символ обрабатывается в cg_symbol () , но он просто открывает круглые скобки, чтобы выражение могло жить внутри. Интересная часть необычного условия находится в конце:

статическое недействительное условие (void) {if (type == TOK_ODD) {cg_symbol (); ожидать (TOK_ODD); выражение(); cg_odd (); } else {выражение (); переключатель (тип) {case TOK_EQUAL: case TOK_HASH: case TOK_LESSTHAN: case TOK_GREATERTHAN: cg_symbol (); следующий(); перерыв; по умолчанию: ошибка («недопустимое условие»); } выражение(); }}

cg_odd () функция должна вывести код, который проверяет, является ли выражение четным или нечетным. Быстрый и простой способ сделать это - использовать выражение & 1 , чтобы проверить, равен ли последний бит 1 или 0. Это дает следующую функцию:

static void cg_odd (void) {aout (") & 1"); }

  Генерация кода для выражений 

Все, что нужно сделать выражению, - это написать + или a - в нужное время:

 статическое выражение void (void) {if (type == TOK_PLUS || type == TOK_MINUS) {cg_symbol ();  следующий();  } срок();  while (тип == TOK_PLUS || тип == TOK_MINUS) {cg_symbol ();  следующий();  срок();  }}   Генерация кода для терминов 

Как и в выражениях, все термины, которые нужно сделать, - это написать или / в нужное время:

 статический недействительный термин (недействителен) {фактор ();  while (тип == TOK_MULTIPLY || тип == TOK_DIVIDE) {cg_symbol ();  следующий();  фактор ();  }}   Генерация кода для факторов 

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

статический коэффициент пропускной способности (недействительный) {переключатель (тип) {регистр TOK_IDENT: проверка символов (CHECK_RHS); / Fallthru / case TOK_NUMBER: cg_symbol (); следующий(); перерыв; case TOK_LPAREN: cg_symbol (); ожидать (TOK_LPAREN); выражение(); if (type == TOK_RPAREN) cg_symbol (); ожидать (TOK_RPAREN); }}

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

Почему это работает

Хотя мы решили много интересных проблем, чтобы добраться сюда, есть еще больше проблем, которые нужно решить, если мы будем генерировать ассемблерный код. Если бы мы создавали сборку, нам нужно было бы решить интересные задачи, такие как преобразование инфиксную нотацию в постфикс обозначение для вывода сборки. Нам повезло: оказалось, что правильное выражение PL / 0 также является действительным выражением C, поэтому мы смогли просто записать то, что мы видели, когда мы это видели.

Если бы мы компилировали в сборку, нам также нужно было бы рассмотреть вопросы о ссылках на переменные, использовании стека, эффективном использовании регистров. , и, возможно, некоторая элементарная оптимизация.

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

Все вместе сейчас

Вот наш полный компилятор:

 #включают  #включают  #включают  #включают  #включают  #включают  #включают  #включают  #включают  #define PL0C_VERSION "1.0.0" #d  efine CHECK_LHS 0 #define CHECK_RHS 1 #define CHECK_CALL 2 #define TOK_IDENT 'I' #define TOK_NUMBER 'N' #define TOK_CONST 'C' #define TOK_VAR 'V' #define TOK_PROCEDURE 'c' # #define TOK_PROCEDURE 'TO' # #define TOK_PROCEDURE 'TO' #  ine TOK_BEGIN 'B' #define TOK_END 'E' #define TOK_IF 'i' #define TOK_THEN 'T' #define TOK_WHILE 'W' #define TOK_DO 'D' #define TOK_ODD 'O' #define TOK_DOT '.'  #define TOK_EQUAL '=' #define TOK_COMMA ',' #define TOK_SEMICOLON ';'  #define TOK_ASSIGN ':' #define TOK_HASH '#' #define TOK_LESSTHAN ' '#define TOK_PLUS' + '#define TOK_MINUS' - '#define TOK_MULTIPLY' '#define TOK_DIVIDE' / '#define TOK_LPAREN' ('#define TOK_RPAREN') '/ pl0c - компилятор PL / 0.  программа = блок "."  .  block = [ "const" ident "=" number { "," ident "=" number } ";" ] [ "var" ident { "," ident } ";" ] {"идентификатор процедуры"; "  блокировать ";"  } утверждение .  оператор = [ ident ":=" expression | "call" ident | "begin" statement { ";" statement } "end" | "if" condition "then" statement | "while" condition "do" statement ].  condition = "нечетное" выражение |  выражение ("=" | "#" | "<'#define TOK_GREATERTHAN'>" ) выражение .  выражение = [ "+" | "-" ] термин {("+" | "-") термин}.  термин = фактор {("*" | "/") фактор}.  коэффициент = идент |  номер |  "(" выражение ")" .  / static char raw, token;  static int depth, proc, type;  статический size_t line = 1;  struct symtab {int depth;  тип int;  название символа;  struct symtab next;  };  статическая структура symtab head;  статическое выражение void (void);  / Разное.  функции.  / static void error (const char fmt, ...) {va_list ap;  (void) fprintf (stderr, «pl0c: error:% lu:», строка);  va_start (ap, fmt);  (пусто) vfprintf (stderr, fmt, ap);  va_end (ap);  (пусто) fputc (' n', stderr);  выход (1);  } static void readin (символ файл) {int fd;  struct stat st;  if (strrchr (file, '.') == NULL) error ("файл должен заканчиваться на '.pl0'");  if (!! strcmp (strrchr (file, '.'), ".pl0")) error ("файл должен заканчиваться на '.pl0'");  if ((fd = open (file, O_RDONLY)) == -1) error («не удалось открыть% s», файл);  if (fstat (fd, & st) == -1) error ("не удалось получить размер");  if ((raw = malloc (st.st_size + 1)) == NULL) ошибка («сбой malloc»);  if (read (fd, raw, st.st_size)! = st.st_size) error ("не удалось прочитать% s", файл);  raw [st.st_size] = ' 0';  (пусто) закрыть (fd);  } / Лексер.  / static void comment (void) {int ch;  while ((ch = raw ++)! = '}') {if (ch == ' 0') error ("незавершенный комментарий");  if (ch == ' n') ++ строка;  }} статический int идентификатор (void) {char p;  size_t i, len;  p = необработанный;  while (isalnum  raw) || raw == '_') ++ raw;  len = raw - p;  --сырой;  бесплатно (токен);  if ((token = malloc (len + 1)) == NULL) error («сбой malloc»);  for (i = 0; i ': кейс ' + ': case' - ': case' ': case' / ': case' (': case') ': return  необработанный);  case ':': if  ++ raw! = '=') error ("неизвестный токен: ':% c'", raw);  вернуть TOK_ASSIGN;  case ' 0': вернуть 0;  по умолчанию: error ("неизвестный токен: '% c'", raw);  } return 0;  } /Генератор кода.  / static void aout (const char fmt, ...) {va_list ap;  va_start (ap, fmt);  (пусто) vfprintf (stdout, fmt, ap);  va_end (ap);  } static void cg_call (void) {aout ("% s ();  n", токен);  } static void cg_const (void) {aout ("const long% s =", токен);  } static void cg_crlf (void) {aout (" п");  } static void cg_end (void) {aout ("https://briancallahan.net/PL / 0 compiler% s /  n", PL0C_VERSION);  } static void cg_epilogue (void) {aout (";");  если (proc == 0) aout ("возврат 0;");  aout (" п}  п  п");  } static void cg_odd (void) {aout (") & 1");  } static void cg_procedure (void) {if (proc == 0) {aout ("int  n");  aout ("main (int argc, char argv [])  n");  } else {aout ("пустота  п");  aout ("% s (void)  n", токен);  } aout ("{ п");  } static void cg_semicolon (void) {aout (";  n");  } static void cg_symbol (void) {переключатель (тип) {case TOK_IDENT: case TOK_NUMBER: aout ("% s", токен);  перерыв;  case TOK_BEGIN: aout ("{ n");  перерыв;  case TOK_END: ​​aout (";  n}  n");  перерыв;  case TOK_IF: aout ("если ("); перерыв; case TOK_THEN: case TOK_DO: aout (")");  перерыв;  case TOK_ODD: aout ("("); перерыв; case TOK_WHILE: aout ("while ("); перерыв; case TOK_EQUAL: aout ("=="); перерыв; case TOK_COMMA: aout (","); перерыв; case TOK_ASSIGN: aout ("="); break; case TOK_HASH: aout ("! ="); break; case TOK_LESSTHAN: aout ("<---| Emit code |                   parser? /     +-----------+                   ---------                       |                       |Yes +-----+                       +---> "); перерыв; case TOK_PLUS: aout (" + "); break; case TOK_MINUS: aout ("-"); перерыв; case TOK_MULTIPLY: aout ("*"); перерыв; case TOK_DIVIDE: aout ("/"); перерыв; case TOK_LPAREN: aout ("("); перерыв; case TOK_RPAREN: aout (" ) ");}} static void cg_var (void) {aout (" long% s;  n ", token);} / Семантика. / static void symcheck (int check) {struct symtab curr, ret = NULL; curr = head; while (curr! = NULL) {if (! Strcmp (token, curr-> name)) ret = curr; curr = curr-> next;} if (ret == NULL) error (" неопределенный символ:% s ", токен); переключатель (проверка) {case CHECK_LHS: if (ret-> type! = TOK_VAR) error (" должно быть переменной:% s ", токен); break; case CHECK_RHS: if ( ret-> type == TOK_PROCEDURE) error ("не должно быть процедурой:% s", токен); bre  ак;  case CHECK_CALL: if (ret-> type! = TOK_PROCEDURE) ошибка («должна быть процедура:% s», токен);  }} / Парсер.  / static void next (void) {type = lex (); ();  ++ raw;  } static void expect (int match) {if (match! = type) error ("синтаксическая ошибка");  следующий();  } static void addymbol (int type) {struct symtab curr, new;  curr = голова;  while (1) {if (! strcmp (curr-> name, token)) {if (curr-> depth == (depth - 1)) error ("повторяющийся символ:% s", токен);  } if (curr-> next == NULL) break;  curr = curr-> следующий;  } if ((new = malloc (sizeof (struct symtab))) == NULL) error («сбой malloc»);  новое-> глубина = глубина - 1;  новый-> тип = тип;  if ((new-> name = strdup (token)) == NULL) error («сбой malloc»);  новый-> следующий = NULL;  curr-> следующий = новый;  } static void уничтожает символы (void) {struct symtab curr, prev;  снова: curr = head;  в то время как (текущий-> следующий! = NULL) {prev = curr;  curr = curr-> следующий;  } если (текущий-> тип! = TOK_PROCEDURE) {бесплатно (текущий-> имя);  бесплатно (curr);  предыдущая-> следующая = NULL;  перейти снова;  }} static void initsymtab (void) {struct symtab new;  if ((new = malloc (sizeof (struct symtab))) == NULL) error («сбой malloc»);  новое-> глубина = 0;  новый-> тип = TOK_PROCEDURE;  new-> name = "main";  новый-> следующий = NULL;  head = new;  } статический коэффициент недействительности (void) {переключатель (тип) {case TOK_IDENT: symcheck (CHECK_RHS);  / Fallthru / case TOK_NUMBER: cg_symbol ();  следующий();  перерыв;  case TOK_LPAREN: cg_symbol ();  ожидать (TOK_LPAREN);  выражение();  if (type == TOK_RPAREN) cg_symbol ();  ожидать (TOK_RPAREN);  }} статический недействительный термин (недействительный) {фактор ();  while (тип == TOK_MULTIPLY || тип == TOK_DIVIDE) {cg_symbol ();  следующий();  фактор ();  }} статическое выражение void (void) {if (type == TOK_PLUS || type == TOK_MINUS) {cg_symbol ();  следующий();  } срок();  while (тип == TOK_PLUS || тип == TOK_MINUS) {cg_symbol ();  следующий();  срок();  }} статическое недействительное условие (void) {if (type == TOK_ODD) {cg_symbol ();  ожидать (TOK_ODD);  выражение();  cg_odd ();  } else {выражение ();  переключатель (тип) {case TOK_EQUAL: case TOK_HASH: case TOK_LESSTHAN: case TOK_GREATERTHAN: cg_symbol ();  следующий();  перерыв;  по умолчанию: ошибка («недопустимое условие»);  } выражение();  }} статический оператор void (void) {переключатель (тип) {case TOK_IDENT: symcheck (CHECK_LHS);  cg_symbol ();  ожидать (TOK_IDENT);  if (type == TOK_ASSIGN) cg_symbol ();  ожидать (TOK_ASSIGN);  выражение();  перерыв;  case TOK_CALL: ожидать (TOK_CALL);  if (type == TOK_IDENT) {symcheck (CHECK_CALL);  cg_call ();  } ожидать (TOK_IDENT);  перерыв;  case TOK_BEGIN: cg_symbol ();  ожидать (TOK_BEGIN);  утверждение();  while (type == TOK_SEMICOLON) {cg_semicolon ();  ожидать (TOK_SEMICOLON);  утверждение();  } if (type == TOK_END) cg_symbol ();  ожидать (TOK_END);  перерыв;  case TOK_IF: cg_symbol ();  ожидать (TOK_IF);  состояние();  if (type == TOK_THEN) cg_symbol ();  ожидать (TOK_THEN);  утверждение();  перерыв;  case TOK_WHILE: cg_symbol ();  ожидать (TOK_WHILE);  состояние();  if (type == TOK_DO) cg_symbol ();  ожидать (TOK_DO);  утверждение();  перерыв;  }} static void block (void) {if (depth ++> 1) error («Превышена глубина вложенности»);  if (type == TOK_CONST) {ожидать (TOK_CONST);  if (type == TOK_IDENT) {добавляет символ (TOK_CONST);  cg_const ();  } ожидать (TOK_IDENT);  ожидать (TOK_EQUAL);  если (type == TOK_NUMBER) {cg_symbol ();  cg_semicolon ();  } ожидать (TOK_NUMBER);  while (type == TOK_COMMA) {ожидать (TOK_COMMA);  if (type == TOK_IDENT) {добавляет символ (TOK_CONST);  cg_const ();  } ожидать (TOK_IDENT);  ожидать (TOK_EQUAL);  если (type == TOK_NUMBER) {cg_symbol ();  cg_semicolon ();  } ожидать (TOK_NUMBER);  } ожидать (TOK_SEMICOLON);  } если (type == TOK_VAR) {ожидать (TOK_VAR);  if (type == TOK_IDENT) {добавляет символ (TOK_VAR);  cg_var ();  } ожидать (TOK_IDENT);  while (type == TOK_COMMA) {ожидать (TOK_COMMA);  if (type == TOK_IDENT) {добавляет символ (TOK_VAR);  cg_var ();  } ожидать (TOK_IDENT);  } ожидать (TOK_SEMICOLON);  cg_crlf ();  } while (type == TOK_PROCEDURE) {proc = 1;  ожидать (TOK_PROCEDURE);  if (type == TOK_IDENT) {добавляет символ (TOK_PROCEDURE);  cg_procedure ();  } ожидать (TOK_IDENT);  ожидать (TOK_SEMICOLON);  блокировать();  ожидать (TOK_SEMICOLON);  proc = 0;  уничтожает символы ();  } если (proc == 0) cg_procedure ();  утверждение();  cg_epilogue ();  if (--depth <0) ошибка («глубина вложенности упала ниже 0»);  } статический анализ void (void) {next ();  блокировать();  ожидать (TOK_DOT);  if (type! = 0) error («лишние токены в конце файла»);  cg_end ();  } /Главный.  / int main (int argc, char argv []) {if (argc! = 2) {(void) fputs ("использование: pl0c file.pl0  n", stderr);  выход (1);  } readin (argv [1]);  initsymtab ();  parse ();  возврат 0;  } 

  В следующем эпизоде: Ввод и вывод 

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

<':case '>



Leave a comment

Your email address will not be published. Required fields are marked *

one × four =