3.1.2. Принципы построения сканеров

Лексический анализатор (сканер) имеет дело с такими объектами как константы и идентификаторы.

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

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

– определение границ лексем;

– сохранение информации об обнаруженной лексеме (или выдача сообщения об ошибке, если лексем неверна).

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

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

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

Лекция 9

3.1.3. Сканер как конечный автомат

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

Пример 3.2.

Класс идентификаторов, если идентификатором является последовательность символов, состоящая из букв и цифр, и первым символом идентификатора может быть только буква, описывается грамматикой G<T, N, P, S>, в которой

T = {б, ц}, N = {I, K}, S = {I},

где б – буква, ц – цифра;

P:

1. I  б.

2. I  бK.

3. K  бK.

4. K  цK.

5. K  б.

6. K  ц.

Подтвердим состоятельность этой грамматики, получив идентификатор, состоящий из пяти символов, причем 3-й и 5-й символы – цифры.

2) 3) 4) 3) 6)

I  бK  ббK  ббцK  ббцбK  ббцбц

Надо отметить, что данная грамматика не единственная, которая описывает язык идентификаторов.

Однако основной задачей сканера является не порождение лексем, а их распознавание. Математической моделью процесса распознавания регулярного языка является вычислительное устройство, которое называется конечным автоматом (КА). Термин «конечный» означает, что устройство имеет фиксированный и конечный объем памяти и работает с конечным множеством символов.

Определение 3.1.

Конечным автоматом называется следующая пятерка:

A = V, Q, , q₀, F,

где V = {a₁, a₂, , a_m} – входной алфавит;

Q = {q₀, q₁, …, q_{n – 1}} – алфавит состояний (конечное множество символов);

: Q  V  Q – функция переходов (от состояния к состоянию);

q₀  Q – начальное состояние конечного автомата;

F  Q – подмножество заключительных состояний.

На содержательном уровне КА представляет собой распознаватель, устройство управления (УУ) которого начинает свою работу всегда в начальном состоянии q₀  Q, а завершает в одном из заключительных состояний F.

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

Отображение  (функцию переходов конечных автоматов) можно представить различными способами:

– совокупностью команд;

– диаграммой состояний;

– матрицей переходов.

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

(q_i, a_j)  q_k, где q_i, q_k  Q; a_j  V.

Данная команда означает, что конечный автомат находится в состоянии q_i, читает с ленты символ a_j и переходит в состояние q_k.

Графически команда представляется в виде дуги графа, помеченной символом a_j входного алфавита:

Рис. 3.1. Схема перехода КА из состояния q_i в состояние q_k

Графическое представление всего отображения  называют диаграммой состояний конечного автомата. Диаграмма состояний представляет собой ориентированный граф, вершинам которого поставлены в соответствие символы из множества Q, а дугам – команды отображения .

Если конечный автомат оказывается в ситуации (q_i, a_j), которая не является левой частью какой-либо команды, то он останавливается.

Если устройство управления считает все символы входной цепочки , записанной на ленте, и при этом перейдет в состояние q_r  F, то говорят, что цепочка  допускается конечным автоматом.

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

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

Пусть заданная регулярная грамматика G<T, N, P, S>, правила которой имеют вид: A_i  a_jA_k или A_i  a_j, где A_i, A_k  N, a_j  T.

Тогда конечный автомат A = V, q, , q₀ F, допускающий тот же самый язык, что порождает регулярная грамматика G, строится следующим образом:

1. V = T;

2. Q = N  {Z}, Z  N, Z  T, Z – заключительное состояние конечного автомата;

3. q₀ = {S};

4. F= {Z};

5. Отображение  строится в виде:

– каждому правилу подстановки в грамматике G вида A_i  a_jA_k ставится в соответствие команда (A_i, a_j)  A_k;

– каждому правилу вида A_i  a_j ставится в соответствие команда (A_i, a_j)  Z.

Пример 3.3.

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

A = V, q, , q₀ F, где

1. V = T = {б, ц};

2. Q = N{Z} = {I, K, Z};

3. q₀ = {S} ={I};

4. F = {Z}

5. :

а) в виде совокупности команд:

(I, б)  Z

(I, б)  K

(K, б)  K

(K, ц)  K

(K, б)  Z

(K, ц)  Z

б) в виде диаграммы состояний (рис. 3.2):

Рис. 3.2. Диаграмма состояний для примера 3.2

Вопрос слушателям. Как создается совокупность команд на основе правил грамматики? Как произвести переход от совокупности команд к диаграмме состояний?

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

Так, конечному автомату A = V, Q, , q₀, F можно поставить в соответствие G<T, N, P, S>, у которой:

1. T = V;

2. N = Q;

3. S = {q₀};

4. P: каждой команде автомата (q_i, a_j)  q_k ставится в соответствие правило q_i  a_j q_k, если q_k  Q и q_k  F, и q_i,  a_j, если q_k  F.

Различают детерминированные конечные автоматы (ДКА) и недетерминированные конечные автоматы (НДКА).

Конечный автомат называется НДКА, если в диаграмме его состояний из одной вершины исходит несколько дуг с одинаковыми пометками, и ДКА – если это условие не выполняется.

Вопрос слушателям. К какому типу относится КА, диаграмма состояний которого показана на рис. 3.2?

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

Для практических целей необходимо, чтобы КА играл более активную роль и сам определял момент окончания входной последовательности символов с выдачей сообщения о правильности или ошибочности входной цепочки. Для этих целей входная цепочка считается ограниченной справа концевым маркером ├ и в диаграмму состояний КА вводятся интерпретированные состояния: Z – «допустить входную цепочку»; O – «запомнена ошибка во входной цепочке»; E – «отвергнуть входную цепочку». Состояние Z и E  F, и в них КА переходит при прочтении ├ соответственно после обработки правильной и ошибочной входной цепочки.

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

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

Рис. 3.3. Модифицированная диаграмма состояния для примера 3.3