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

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

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

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

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

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

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

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

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

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

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

• Цель – проверка программы на корректность
• Любая С.Т., отвергая некорректные программы, будет также отвергать некоторый процент корректных программ.
• Для обхода этого ограничения – механизмы для игнорирования системы типов.
• Указание корректных типов – обычно на совести программиста.
• Некоторые – типовыводящие – ЯП могут выводить типы (почти) без участия программиста

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

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

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

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

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

Интерпретатор

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

Целевой язык может быть

• машинным языком
• другим языком программирования (транс-компиляция)
• машинным языком для некой виртуальной машины (байт-кодом)

Анализ

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

На этой фазе также возможен статический анализ исходного текста.

Cинтез

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

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

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

• Первая фаза компиляции
• Также известна как сканирование
• анализатор – лексер или сканер
• сканирует входной поток символов (исходного текста программы)
• выделяет значащие последовательности символов – лексемы
• Для каждой лексемы анализатор выводит токен
• токен – комбинация абстрактного символа (названия) и произвольного набора атрибутов
• “набор атрибутов” – часто ссылка в глобальную таблицу символов

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

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

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

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

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

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

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

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

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

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

• отображает каждую команду промежуточного кода в одну или несколько команд целевого
• занимается задачей распределения регистров исполнительного устройства

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

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

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

Основных причин для разделения фаз лексического и снитаксического анализа несколько. Из них основные:

1. Упрощение разработки.
2. Увеличивается переносимость компилятора.
3. Разделение фаз анализа соответствует разделению лексики и синтаксиса в модели языка.

Язык

Любое счётное множество строк над некоторым фиксированным алфавитом.

• Определение достаточно широкое. Например, \(\varnothing\) и \(\{\varepsilon\}\) – языки. Множество всех синтаксически-корректных программ, скажем, на C – язык.
• Определение не требует, чтобы строки языка имели какой-то смысл.

Конкатенация

Если \(x\) и \(y\) – строки, то \(xy\) или \(x.y\) – конкатенация строк. Результат – строка, образованная добавлением последовательности символов в \(y\) к \(x\).

Пустая строка – нейтральный элемент конкатенации.

Повтор

Если \(s\) – строка, то \(s^i\) соответствует конкатенации \(i\) экземпляров строки \(s\).

Индуктивное определение можно записать так: \[\begin{align} s^0 & \overset{def}{=} \varepsilon \\ s^i & \overset{def}{=} s^{i-1}.s \end{align}\]

Операции над языками

Конкатенация языков

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

Конкатенация \(L . M\) языков \(L\) и \(M\) – это язык, образуемый конкатенациями всех строк, входящих в \(L\) со всеми строками, входящими в \(M\): \[L . M = \{ s . t | s\in L, t \in M\}\]

• \(\varepsilon \in L^*\) всегда включает пустую строку
• \(\varepsilon \in L^+\) – только если \(\varepsilon \in L\)
• \(L^+ = L . L^*\)

Пример

• Пусть \(L\) все строки длины 1 над латинским алфавитом, \(D\) – над цифрами. Тогда:

1. \(L\cup D\) – язык строк, состоящих из одной буквы или цифры.
2. \(L.D\) – язык строк длины 2, каждая из которых на первом месте имеет букву, на втором – цифру.
3. \(L^4\) – множество всех строк из букв длины \(4\).
4. \(L^*\) – множество всех строк любой длины (включая 0) из букв
5. \(L(L\cup D)^*\) – множество всех строк из букв и цифр, начинающихся с буквы.
6. \(D^+\) – множество всех строк из одной или нескольких цифр.

Базис

1. \(L(/\varepsilon/) = \{\varepsilon\}\)
2. \(\forall a \in \Sigma, L(/a/) = \{a\}\)

Индукция

Если \(/r/\) и \(/s/\) – регулярные выражения, то:

1. \(L(/r | s/) = L(/r/) \cup L(/s/)\)
2. \(L(/rs/) = L(/r/) . L(/s/)\)
3. \(L(/r^*/) = L(/r/)^*\)
4. \(L(/(r)/) = L(/r/)\)

• \(|\) – оператор альтернативы
• \(*\) – оператор замыкания
• Скобки – для группировки и избежания неоднозначности

1. Оператор \(^*\) левоассоциативен и имеет наивысший приоритет.
2. Конкатенация левоассоциативна и имеет второй приоритет.
3. Оператор \(|\) левоассоциативен и имеет наименьший приоритет.

Регулярные определения

Для алфавита \(\Sigma\), регулярное определение представляет из себя последовательность определений вида \[\begin{align} d_1 & \to /r_1/ \\ d_2 & \to /r_2/ \\ & \ldots \\ d_n & \to /r_n/, \\ \end{align}\] где \(d_i \neq d_j\), если \(i\neq j\), \(d_i \notin \Sigma\) и \(/r_i/\) – регулярные выражения над \(\Sigma \cup \{\d_i\}\), \(i, j \in \{1, \ldots, n\}\).

Законы регулярных выражений

1. \(|\) коммутативен: \(r | s = s | r\)
2. \(|\) ассоциативен: \(r|(s|t) = (r|s)|t = r|s|t\)
3. \(r|r = r\)
4. Идемпотентность \(|\): \((r|s)|s = r|s\)
5. Конкатенация ассоциативна: \((rs)t = r(st) = rst\)
6. Конкатенация дистрибутивна над \(|\): \(r(s|t) = rs|rt\)
7. \(\varepsilon\) – нейтральный элемент конкатенации, \(\varepsilon r = r \varepsilon = r\)
8. \(\varepsilon\) входит в замыкание: \(r^* = (r | \varepsilon)^* = r^*|\varepsilon\)
9. Идемпотентность \(^*\) : \(r^{**} = r^*\)

Расширения регулярных выражений

1. Оператор позитивного замыкания: \(/r^+/ = /rr^*/\)
2. Оператор 0 или 1: \(/r?/ = /\varepsilon|r/\)
3. Классы символов. Для \(a_i \in \Sigma\), \(i\in\{1,\ldots, n\}\): \(/[a_1\ldots a_n]/=/(a_1|\ldots|a_n)/\)

• если алфавит \(\Sigma\) упорядочен, то класс идущих подряд символов \([a_1\ldots a_n]\) этого алфавита можно записать через тире, как \([a_1 - a_n]\).

1. Недетерминированные (НКА) не имеют ограничений на вид графа переходов. В том числе, из одного состояния могут вести несколько дуг, помеченных одним входным символом, или помеченных пустой строкой.
2. Детерминированные (ДКА) для каждого состояния и каждого символа входного алфавита имеют ровно одно выходящее ребро графа переходов. Рёбра, помеченные пустой строкой, запрещены.

Недетерминированный конечный автомат

1. Множества состояний \(S\)
2. Входного алфавита \(\Sigma\). Считаем, что символ \(\varepsilon\), обозначающий пустую строку, не входит в \(\Sigma\).
3. Функции переходов \(T: (S, \Sigma \cup \{\varepsilon\}) \to S\)
4. Состояния \(s_0 \in S\), называемого начальным.
5. Подмножества состояний \(F \subset S\), называемых конечными или принимающими.

• Алфавит \(\Sigma\) полагается конечным
• Тогда \(T\) можно представить в виде таблицы
• в строках – состояния, в столбцах – символы алфавита или \(\varepsilon\).
• будем называть её таблицей переходов

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

Построение НКА на основе регулярных выражений

1. Для регулярного выражения \(/\varepsilon/\) строим НКА

   \(i\) – новое состояние, \(f\) – новое принимающее состояние

2. Для регулярного выражения \(/a/,\) где \(a\in\Sigma\), строим НКА

   \(i\) – новое состояние, \(f\) – новое принимающее состояние

Индукция

1. Для \(r = /s|t/\), строим НКА

   где \(i\) – новое состояние, \(f\) – новое принимающее состояние, переходы из \(i\) осуществляются к начальному состоянию \(N(s)\) и \(N(t)\), а переходы к \(f\) происходят из принимающих состояний \(N(s)\) и \(N(t)\).

2. Для \(r = /st/\), строим НКА

   где \(i\) – новое состояние, \(f\) –новое принимающее состояние. На самом деле ε-переходы можно опустить, отождествив \(i\) с начальным состоянием \(N(s)\), принимающие состояния \(N(s)\) с начальным состоянием \(N(t)\) и принимающие состояния \(N(t)\) с \(f\).

3. Для \(r=/s^*/\), строим НКА

   где \(i\) – новое состояние, \(f\) –новое принимающее состояние.

4. Для \(r=/(s)/\), просто используем \(N(r)=N(s)\).

Моделирование НКА

Определим некоторые вспомогательные функции:

1. \(ε^+(s)\) – множество состояний НКА, достижимых из \(s\) за счёт ε-переходов
2. \(ε^+(T)\) – множество состояний НКА, достижимых из \(\forall s\in T\) за счёт ε-переходов; \(ε^+(T) = \bigcup_{s\in T}ε^+(s)\)
3. \(move(T,a)\) – множество состояний НКА, в которые имеется переход из какого-то состояния \(s\in T\) при входном символе \(a\).

Распознавание шаблонов при помощи НКА

• Задача распознавания шаблонов – выделить из входного потока лексемы и классифицировать их соответственно токенам.
• Если построить НКА, соответствующий альтернативе всех шаблонов токенов, такой автомат сможет распознать одну лексему языка.

Чтобы выделить множество лексем:

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

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

Моделирование ДКА

s = s₀;
c = nextChar();
while (c != eof) {
  s = move(s, c);
  c = nextChar();
}
if (s ∈ F) accept();
else reject();