Процесс распознавания лексем

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

1. неупорядоченная таблица – поиск в этом случае требует сравнения с каждым элементом таблицы. (Метод линейного списка) Этот способ не эффективен.

2. упорядоченная таблица. Элементы таблицы упорядочены в естественном (напр., алфавитном) порядке. В упорядоченном списке из n элементов эффективным методом поиска является бинарный или логарифмический поиск. Слово S, которое нужно найти, сравнивается с аргументом в середине таблицы. Если S “больше”, то требуется просмотреть нижнюю половину таблицы, если S “меньше” – верхнюю. Далее S сравнивается со средним аргументом в соответствующей половине таблицы, и т.д. (Метод упорядоченного списка)

3. хешированная таблица. Начальный индекс элемента в таблице, с которого следует начинать поиск, получается «хешированием» символов искомого слова, т.е. выполнением над элементами таблицы некоторых простых арифметических или логических операций. Простейшая хеш-функция возвращает первый символ слова (подробнее об организации хеш-таблиц можно почитать в «Искусстве программирования» Д.Кнута). (Метод расстановки).

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

Конечный автомат представляет собой вычислительное устройство, которое может находиться в конечном количестве состояний и обрабатывает конечное множество входных символов (в компиляторе конечный автомат реализуется программно). Конечный автомат описывается пятеркой объектов (S, A, d, s_H, F). S ={s₁, s₂, … s _n } – множество состояний автомата, s_H – начальное состояние, принадлежащее множеству S. Конечных состояний может быть несколько, они образуют множество F Ì S. Автомат переходит из одного состояния в другое под действием очередного прочитанного символа. Возможные входные символы образуют входной алфавит A ={a₁, a₂, … a _m }. Входной алфавит лексического анализатора совпадает с алфавитом языка программирования. Закон, определяющий, куда перейдет автомат при получении любого символа из входного алфавита, описывается функцией переходов d. Функция переходов обычно записывается в виде матрицы переходов (см. ниже).

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

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

обозначается: (s_i, a_k)®s_j

Если КА оказался в ситуации, когда из вершины s_i не выходит дуги, помеченной очередным прочитанным символом, автомат останавливается. В этом случае говорят, что цепочка вызвавшая остановку, является недопустимой.

Функция переходов КА обычно описываются таблицей, которая называется матрицей переходов. Строки матрицы соответствуют состояниям, столбцы – символам входного алфавита. Начальное состояние s_H записывается в первой строке таблицы. Строки, соответствующие выходным состояниям, помечаются справа знаком “+” или “1”. Остальные строки помечаются справа знаком “–” или “0”. На пересечении строки s_i и столбца a_k ставится состояние s_j, если разрешен переход (s_i, a_k)®s_j. Если перехода из s­_i под действием a_k нет, то в соответствующем элементе таблицы либо ничего не ставится, либо ставится переход на состояние ошибки Е (соответственно, добавляется в матрицу переходов добавляется новая строка, соответствующая выходному состоянию Е).

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

Пример 2. Рассмотрим на примере процесс построения конечного автомата для идентификации слов некоего языка программирования. При этом действуют следующие правила:

· Алфавит языка программирования образуют большие латинские буквы A…Z, цифры 0…9 и спецсимволы: +­*–/(){}[],~:; и пр.

· Ключевые слова состоят только из букв. Идентификаторы начинаются с буквы и могут содержать буквы и цифры.

· Лексемы, принадлежащие классу цифровых констант, состоят только из цифр 0…9.

· Слова разделяются одним или более пробелами, символами табуляции или одним из символов-разделителей +­*–/(){}[],~:; и пр.

· Комментарий помещается между парами символов /* и */.

Введем обозначения. LIT – буквы A…Z; DIG – цифры 0…9; SEP – символы-разделители из множества +­*–/(){}[],~:; и пр. Символы по мере их поступления накапливаются в символьном массиве-буфере. Когда слово сформировано, его дескриптор подается на выход лексического анализатора – на графе обозначено out (<тип>,<значение>) – после чего массив-буфер очищается для приема следующего слова.

Если над стрелкой ничего не написано, это означает «во всех остальных случаях».

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

Другой вариант организации блока идентификации ключевых слов – на базе конечного автомата. Рассмотрим на примере порядок построения такого КА.

Пример 3

1. Определить автоматный язык – т.е. множество ключевых слов, которые переводят автомат из начального в одно из конечных состояний. Для нашего примера автомат допускает три слова { inc, input, output }

2. Определить автоматный алфавит – множество символов, из которых состоят допустимые слова. A={ i,n,c,p,u,t,o,┤}, где символ ┤ означает признак конца цепочки (пробел или иной разделитель).

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

S₀ – начальное состояние, соответствующее пустому массиву-буферу, в котором будем накапливать поступающие символы.

I₁ – буква i в inc;

I₂ – буква i в input;

N₁ – буква n в inc;

N₂ – буква n в input;

C – буква c в inc;

P₁ – буква p в input;

P₂ – буква p в output;

U₁ – буква u в input;

U₂ – первая буква u в output;

U₃ – вторая буква u в output;

T₁ – буква t в input;

T₂ – первая буква t в output;

T₃ – вторая буква t в output;

O – буква o в output;

S₁, S₂, S₃ – выходные состояния, соответствующие приему слов inc, input, output соответственно.

Диаграмма состояний имеет вид:

Недетерминированность автомата проявляется в том, что из вершины S₀ выходит две дуги, помеченные символом i.

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

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

Переход от недетерминированного конечного автомата (НКА) к детерминированному происходит следующим образом: объединяют состояния НКА, соответствующие одним и тем же начальным и конечным подцепочкам слова. Для нашего примера такими подцепочками являются “ in” и “put ┤”.

Новые состояния детерминированного КА:

I = {I₁, I₂}, N={N₁, N₂}, P={P₁, P₂}, U={U₁, U₃}, T={T₁, T₃}, S_ВЫХ={S₁, S₂, S₃}

Если быть точными, сейчас мы построили конечный распознаватель, т.к. выходное состояние одно, и в него переходит КА, если входная цепочка допустима. Для того, чтобы построить детерминированный конечный автомат, не нужно было объединять конечные подцепочки (put ┤).

Матрица переходов имеет вид:

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

Поиск по сайту: