Языки программирования

Язык программирования – это искуственный язык, созданный для взаимодействия с машиной, в частности, с компьютером. ЯП используются для написания программ, которые управляют машиной и/или выражают алгоритмы.

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

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

Некоторые языки определяются стандартом (C,C++,Haskell, и др.). Другие не имеют формального описания, и наиболее широко распространенная реализация используется в качестве эталона.

Описание ЯП обычно делится на две части: синтаксис, т.е. форма, и семантика, т.е. значение.

Синтаксис в свою очередь подразделяется на лексику и грамматику.

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

Не все синтаксически корректные программы являются семантически корректными. Например:

complex *p = nullptr;
complex abs_p = sqrt(*p>>4 + p->im);

Здесь *p не определено, *p >> 4 не определено, даже если определено *p, и p->im так же не определено. Тем не менее, синтаксически это корректная программа.

Семантика же подразделяется на статическую, динамическую, и систему типов.

Статическая семантика

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

Динамическая семантика

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

Система типов

определяет каким образом ЯП классифицирует значения и выражения, как эти типы взаимодействуют и каким образом ЯП может манипулировать ими. Система типов является практическим приложением теории категорий. Цель системы типов – проверка программы на корректность (до какой-то степени). Любая система типов, отвергая некорректные программы, будет так же отвергать некоторый процент корректных (хотя вероятно необычных) программ. Чтобы обойти это ограничение, ЯП обычно имеют некие механизмы для выхода из ограничений системы типов. В большинстве случаев, указание корректных типов ложится на совесть программиста. Однако некоторые ЯП (обычно функциональные) умеют выводить типы исходя из семантики, и таким образом освобождают программиста от необходимости явно указывать типы.

Динамическая семантика может определяться различными способами. Наиболее распространёнными являются операционная семантика и денотационная семантика.

Операционная семантика

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

Денотационная семантика

способ описания семантики, при котором выражениям языка ставятся в соответствие какие-то математические объекты с априори известной семантикой, т.е. смысл языковых конструкций ставится в соответствие конструкциям математическим.

Введение в компиляцию

Компиляция – это трансляция (преобразование) текста программы, написанного на одном языке (исходном), в эквивалентный (сохраняющий семантику) текст на другом языке (целевом).

Компилятор – это программа, читающая текст программы на исходном языке и компилирующая его.

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

Интерпретатор – программа, читающая исходный текст, и интерпретирующая его.

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

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

Условная схема компиляции

Условная схема интерпретации

Условная схема компиляции в байт-код

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

Структура компилятора. Процесс компиляции

Процесс компиляции обычно разделяется на две фазы: анализ и синтез.

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

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

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

Лексический анализ

Первая фаза компиляции называется лексическим анализом или сканированием.

Лексический анализатор соответственно так же называется лексером или сканером.

Лексический анализатор сканирует входной поток символов (исходного текста программы) и выделяет значащие последовательности символов, называемые лексемами.

Для каждой лексемы анализатор выводит токен, представляющий из себя комбинацию абстрактного символа (названия типа токена) и произвольного набора атрибутов. Часто в качестве “набора атрибутов” выступает ссылка в глобальную таблицу, называемую таблицей символов.

Синтаксический анализ

Вторая фаза – синтаксический анализ или разбор, парсинг (от англ. parsing).

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

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

Например, синтаксическое дерево арифметического выражения \(1+2*3\) может иметь вид:

А у выражения \((1+2)*3\)

Семантический анализ

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

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

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

Генерация промежуточного кода

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

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

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

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

На этом этапе обычно принимаются решения о распределении памяти для хранения значений переменных.

Машинно-независимая оптимизация

На фазе машинно-независимой оптимизации, промежуточный код преобразуется с целью “улучшения” без изменений наблюдаемого поведения (в соответствии со спецификацией языка¹). Под “улучшением” обычно понимается “ускорение”, но иногда возможны другие критерии, например “код меньшего размера” или “меньшее потребление памяти”.

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

Объём работы, проделываемый различными компиляторами на этом этапе может сильно отличаться. Большинство распространённых на рынке компиляторов являются “оптимизирующими” и значительная часть времени компиляции уходит именно на оптимизацию (обычно есть способ отключить оптимизацию при необходимости).

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

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

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

Машинно-зависимая оптимизация

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

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