Книга: Системное программное обеспечение. Лабораторный практикум

Описание конечного автомата для распознавания лексем входного языка

Описание конечного автомата для распознавания лексем входного языка

Задача лексического анализатора для описанного выше языка заключается в том, чтобы распознавать и выделять в исходном тексте программы все лексемы этого языка. Лексемами данного языка являются:

• шесть ключевых слов языка (if, then, else, or, xor и and);

• разделители: открывающая и закрывающая круглые скобки, точка с запятой;

• знак операции присваивания;

• идентификаторы;

• целые десятичные константы без знака.

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

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

• идентификатор – это произвольная последовательность малых и прописных букв латинского алфавита (от А до Z и от а до z), цифр (от 0 до 9) и знака подчеркивания (_), начинающаяся с буквы или со знака подчеркивания;

• целое десятичное число без знака – это произвольная последовательность цифр (от 0 до 9), начинающаяся с любой цифры.

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

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

Рис. 2.1. Фрагмент графа переходов КА для распознавания всех лексем, кроме ключевых слов.

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

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

Рис. 2.2. Фрагмент графа переходов КА для ключевых слов if и then.

На фрагментах графа переходов КА, изображенных на рис. 2.1 и 2.2, приняты следующие обозначения:

• А– любой алфавитно-цифровой символ;

• А(*) – любой алфавитно-цифровой символ, кроме перечисленных в скобках;

• П– любой незначащий символ (пробел, знак табуляции, перевод строки, возврат каретки);

• Б– любая буква английского алфавита (прописная или строчная) или символ подчеркивания (_);

• Б(*) – любая буква английского алфавита (прописная или строчная) или символ подчеркивания (_), кроме перечисленных в скобках;

• Ц– любая цифра от 0 до 9;

• F – функция обработки таблицы лексем, вызываемая при переходе КА из одного состояния в другое. Обозначения ее аргументов:

– v – переменная, запомненная при работе КА;

– d – константа, запомненная при работе КА;

– a – текущий входной символ КА.

С учетом этих обозначений, полностью КА можно описать следующим образом:

M(Q,?,?,q₀,F):

Q = {H, C, G, V, D, I1, I2, T1, T2, T3, T4, E1, E2, E3, E4, O1, O2, X1, X2, X3, A1, A2, A3, F}

? = А (все допустимые алфавитно-цифровые символы);

q ₀ = H;

F = {F}.

Функция переходов (?) для этого КА приведена в приложении 2.

Из начального состояния КА литеры «i», «t», «e», «o», «x» и «a» ведут в начало цепочек состояний, каждая из которых соответствует ключевому слову:

• состояния I1, I2 – ключевому слову if;

• состояния T1, T2, T3, T4 – ключевому слову then;

• состояния E1, E2, E3, E4 – ключевому слову else;

• состояния O1, O2 – ключевому слову or;

• состояния X1, X2, X3 – ключевому слову xor;

• состояния A1, A2, A3 – ключевому слову and.

Остальные литеры ведут к состоянию, соответствующему переменной (идентификатору), – V. Если в какой-то из цепочек встречается литера, не соответствующая ключевому слову, или цифра, то КА также переходит в состояние V, а если встречается граница лексемы – запоминает уже прочитанную часть ключевого слова как переменную (чтобы правильно выделять такие идентификаторы, как «i» или «els», которые совпадают с началом ключевых слов).

Цифры ведут в состояние, соответствующее входной константе, – D. Открывающая фигурная скобка ведет в состояние C, которое соответствует обнаружению комментария – из этого состояния КА выходит, только если получит на вход закрывающую фигурную скобку. Еще одно состояние – G – соответствует лексеме «знак присваивания». В него КА переходит, получив на вход двоеточие, и ожидает в этом состоянии символа «равенство».

Состояние H – начальное состояние КА, а состояние F – его конечное состояние. Поскольку КА работает с непрерывным потоком лексем, перейдя в конечное состояние, он тут же должен возвращаться в начальное, чтобы распознавать очередную лексему. Поэтому в моделирующей программе эти два состояния можно объединить.

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

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

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

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

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

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

Оглавление книги