Обзор компилятора | Кодементор

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

На фронтенде есть парсер, а на бэкенде — генератор кода.

Они связаны через структуру данных, которая в общем случае называется IDS, что означает Intermediate или Internal Data Structure, и, как правило, это дерево, часто Абстрактное синтаксическое дерево (AST)хотя иногда похожие, но гораздо более подробные Дерево синтаксического анализа, также известное как конкретное синтаксическое дерево (CST). Синтаксический анализатор считывает входные данные и создает IDS, а генератор кода считывает IDS и выдает язык ассемблера, машинный код или что-то другое (например, C).

Мы также можем приравнять синтаксический анализатор к десериализатори генератор кода для сериализатора.

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

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

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

Семантика языка на самом деле не является частью синтаксического анализа: как только ввод распознается как синтаксис входного языка, он становится объектом семантики входного языка.

Обработка ошибок

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

Что такое сканер или лексер и зачем его использовать?

Лексер или сканер используются, чтобы помочь синтаксическому анализатору распознавать более мелкие компоненты языка.

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

Тем не менее, серьезный язык, возможно, будет предлагать несколько перекрывающихся конструкций: есть сам основной язык, а затем есть другие, второстепенные функции, такие как пробелы, комментарии и условное соответствие (например, #ifdef в C и #if в C#). . Эти другие функции почти подобны наличию языка внутри языка. Они мешают и усложняют синтаксический анализ основного языка — вот где лексер сияет: он потребляет (анализирует) эти вторичные конструкции, позволяя синтаксическому анализатору сосредоточиться только на основном языке. Хранение лексера отдельно от парсера может упростить и то, и другое.

Лексер обычно выводит некоторое понятие токенов и промежуточное представление всех возможных входных данных, сжатых — однако это не является строго необходимым, и (по моему скромному мнению) это ненужное промежуточное отображение. Когда я пишу сканер/парсер, у меня есть сканер, который обрабатывает пробелы, условия, #ifdefs, идентификаторы, строковые литералы и числовые константы, а в противном случае передает символы, такие как +, -, ., и т. д., непосредственно парсеру для интерпретации без сопоставление с токенами.

Как упоминалось ранее, IDS обычно представляет собой своего рода граф объектов: обычно это древовидная структура данных, такая как AST, которая фиксирует синтаксическое распознавание входной программы на входном языке.

Например, a = b + c представлен в дереве AST как:

      =
    /    \
   a      +
        /   \
       b     c

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

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

Контекст оценки: LHS, RHS, Branch

Когда мы используем IDS для генерации машинного кода, существует несколько различных контекстов оценки, два из них: левая и правая стороны.

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

Например, в a = b + cоцениваем значение b а также cдобавьте их вместе, а затем свяжите или сохраните результат в a. Здесь b а также c имеют контекст, который мы называем правой стороной — b а также c находятся на правая часть (задания)тогда как a имеет левосторонний контекст — a на левая часть задания. Нам нужно значение b а также c но местонахождение a для сохранения результата.

Сложное левостороннее выражение само по себе также будет включать некоторое правостороннее вычисление. Например, a[i] = 5 требует оценки a а также i как значения (как бы правая часть), и только сама индексация массива оценивается как левая часть (для места хранения). 5разумеется, понимается как правая часть.

Оценка отрасли

Другой контекст оценки — ветвление для потока управления. Например, в операторе if мы хотим знать, выполнять ли часть then или пропустить ее. Таким образом, чего мы действительно хотим добиться, так это возможного изменения потока управления. Наивный способ сделать это состоит в том, чтобы оценить условное выражение в операторе if для его значения (т. е. используя оценку правой стороны), а затем выполнить часть then, если значение истинно (или ненулевое, в зависимости от языка). ) и пропустить часть then, если значение равно false (или нулю). Хотя это и работает, но генерирует неоптимальный код даже для очень простых выражений. Например, в if ( a == b ) ... наивный подход сравнил бы a с b, сгенерируйте логическое значение true/false, затем выполните тест и разветвитесь по этому логическому значению. Однако в большинстве языков машинного кода мы можем перейти непосредственно к результату сравнения, минуя создание промежуточного логического значения. Когда мы оцениваем условное выражение для ветвления, мы предоставляем оценщику цель ветвления.

Оптимизация

После создания промежуточной структуры данных мы можем проанализировать ее на предмет возможной оптимизации. Классические оптимизации включают в себя устранение общих подвыражений, движение кода, не изменяющееся в цикле, и уменьшение силы переменных индукции. Некоторые компиляторы предпочитают выполнять такую ​​оптимизацию после генерации кода, потому что при генерации кода возникает больше возможностей для этих оптимизаций, например в A[i] = B[i]компилятор может расширить это до
t1 = i*4
t2 = B[t1]
t3 = i*4
A[t3] = t2
Как видите, при повторном использовании подвыражений есть общая возможность. t1 вместо создания второго i*4 в t3. Некоторые компиляторы понижают AST до другого промежуточного уровня (называемого понижением, поскольку этот другой промежуточный уровень более подробный и ближе к машинному коду). Некоторые также выбрали оптимизацию как в AST, так и в промежуточном состоянии, а также во время и после генерации машинного кода.

Поток управления

Многие компиляторы переводят из какого-либо структурного программирования в язык ассемблера или машинный код. Машинный код (и язык ассемблера) использует стиль потока управления if-goto вместо структурированных операторов. Требуется преобразование, которое включает в себя отрицание условных выражений и управление ветвями и целевыми метками ветвей. В то время как структурное программирование использует такие конструкции, как «если это, то сделайте то», язык ассемблера (и машинный код) использует конструкции, такие как «если не это, то пропустите это». См. другую мою статью «Условная логика на языке ассемблера» для получения дополнительной информации по этому вопросу.

Тип аппарата

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

Эта статья защищена авторским правом (c) 2019, Эрик Л. Эйдт.