Как уже говорилось ранее, первая фаза компиляции называется лексическим анализом или сканированием.
Лексический анализатор соответственно так же называется лексером или сканером.
Роль лексического анализатора
Основная задача лексического анализатора в том, чтобы прочитать входные символы исходного текста программы, сгруппировать их в лексемы, и вывести последовательность токенов для всех лексем исходного текста. Поток токенов подаётся на вход синтаксического анализатора.
Не следует думать, что фазы лексического и синтаксического анализа разнесены во времени. Напротив, как правило, синтаксический анализатор работает параллельно с лексическим, обрабатывая токены по мере их поступления.
Часто при работе лексический анализатор так же взаимодействует с таблицей символов: в некоторых случаях, лексический анализатор может получить из таблицы символов информацию (помещённую туда синтаксическим анализатором), и использовать её для более точного определения лексемы.
Поскольку лексический анализатор читает исходный текст, он может кроме, собственно, лексического анализа, производить и другие действия, в частности, удаление пробельных символов и комментариев.
Основных причин для разделения фаз лексического и снитаксического анализа несколько. Из них основные:
- Упрощение разработки. Разделение часто позволяет сильно упростить по крайней мере одну из частей. В частности, работу с комментариями в рамках синтаксического анализатора, как правило, реализовать значительно сложнее.
- Увеличивается переносимость компилятора.
- Разделение фаз анализа соответствует разделению лексики и синтаксиса в модели языка.
Токены, шаблоны, лексемы
При разговоре о лексическом анализе, важно понимать и разделять три связанных понятия.
- Токен
- Структура, состоящая из имени токена и набора необязательных произвольных атрибутов. Имя токена – абстрактный символ (идентификатор), представляющий тип лексической единицы, например, ключевое слово, название переменной, и т.п.
- Лексема
- представляет собой последовательность символов исходной программы, которая идентифицируется лексическим анализатором как экземпляр токена.
- Шаблон
- описание вида, который может принимать лексема токена. Лексический анализатор принимает решение о принадлежности лексемы токену на основе шаблона.
Распознавание шаблонов
Для спецификации шаблонов, широко используются регулярные выражения. Регулярные выражения достаточно мощны для выражения большинства практически значимых шаблонов и достаточно эффективны в реализации.
Прежде, чем переходить непосредственно к регулярным выражениям, обсудим понятие языка.
Языки
Введём несколько определений из теории языков.
- Алфавит
- Конечное множество символов.
- Строка над алфавитом
- Конечная последовательность символов, принадлежащих алфавиту.
В теории языков, термины “предложение” и “слово” часто используются как синонимы слова “строка”.
Длина строки \(s\) обозначается как \(|s|\), и равна количеству символов в строке. Пустая строка (содержащая 0 символов) обозначается \(\varepsilon\).
- Язык
- Любое счётное множество строк над некоторым фиксированным алфавитом.
Это определение языка является достаточно широким. Например, согласно этому определению, \(\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\}\]
Другие теоретико-множественные операции, такие, как объединение \(\cup\) и пересечение \(\cap\) получаются непосредственно из определения языка как множества строк.
Наконец, при обсуждении лексического анализа, нам потребуются операции замыкания
- Замыкание Клини
- Замыкание Клини \(L^*\) языка \(L\) – язык, образованный объединением всех повторов \(L^i\) языка \(L\) для всех \(i \in [0, \infty)\): \[L^* = \bigcup_{i=0}^\infty L^i\]
- Позитивное замыкание
- Позитивное замыкание \(L^+\) языка \(L\) – язык, образованный объединением всех повторов \(L^i\) языка \(L\) для всех \(i \in [1, \infty)\): \[L^+ = \bigcup_{i=1}^\infty L^i\]
Можно отметить, что \(L^*\) всегда включает пустую строку, а \(L^+\) – только если исходный язык \(L\) включает пустую строку. Так же можно заметить, что \[L^+ = L . L^*\]
Пользуясь этими операциями над языками, мы можем описывать языки композиционно, т.е. определив несколько простых конечных языков, на их основе определить возможно бесконечное множество других, более сложных языков.
Пусть язык \(L\) – это язык, состоящий из строк, содержащих одну букву латинского алфавита.
Пусть язык \(D\) – язык, состоящий из строк, содержащих одну арабскую цифру.
Тогда:
- \(L\cup D\) – язык строк, состоящих из одной (латинской) буквы или (арабской) цифры.
- \(L.D\) – язык строк длины 2, каждая из которых на первом месте имеет одну букву, на втором – одну цифру.
- \(L^4\) – множество всех строк из букв длины \(4\).
- \(L^*\) – множество всех строк любой длины (включая 0) из букв
- \(L(L\cup D)^*\) – множество всех строк из букв и цифр, начинающихся с буквы.
- \(D^+\) – множество всех строк из одной или нескольких цифр.