Доказано, что любой недетерминированный КА может быть преобразован в детерминированный КА так, чтобы их языки совпадали [3, 7, 26] (говорят, что эти КА эквивалентны).
Кроме преобразования в детерминированный КА любой КА может быть минимизирован – для него может быть построен эквивалентный ему детерминированный КА с минимально возможным количеством состояний. Алгоритмы преобразования КА в детерминированный КА и минимизации КА подробно описаны в [3, 7, 26].
Можно написать функцию, отражающую функционирование любого детерминированного КА. Чтобы запрограммировать такую функцию, достаточно иметь переменную, которая бы отображала текущее состояние КА, а переходы из одного состояния в другое на основе символов входной цепочки могут быть построены с помощью операторов выбора. Работа функции должна продолжаться до тех пор, пока не будет достигнут конец входной цепочки. Для вычисления результата функции необходимо по ее завершении проанализировать состояние КА. Если это одно из конечных состояний, то функция выполнена успешно и входная цепочка принимается, если нет, то входная цепочка не принадлежит заданному языку.
Однако в общем случае задача лексического анализатора шире, чем просто проверка цепочки символов лексемы на соответствие ее входному языку. Он должен правильно определить конец лексемы (об этом было сказано выше) и выполнить те или иные действия по запоминанию распознанной лексемы (занесение ее в таблицу лексем). Набор выполняемых действий определяется реализацией компилятора. Обычно эти действия выполняются сразу же при обнаружении конца распознаваемой лексемы.
Во входном тексте лексемы не ограничены специальными символами. Определение границ лексем – это выделение тех строк в общем потоке входных символов, для которых надо выполнять распознавание. Если границы лексем всегда определяются (а выше было принято именно такое соглашение), то их можно определить по заданным терминальным символам и по символам начала следующей лексемы. Терминальные символы – это пробелы, знаки операций, символы комментариев, а также разделители (запятые, точки с запятой и др.). Набор таких терминальных символов может варьироваться в зависимости от входного языка. Важно отметить, что знаки операций сами также являются лексемами и необходимо не пропустить их при распознавании текста.
Таким образом, алгоритм работы простейшего сканера можно описать так:
• просматривается входной поток символов программы на исходном языке до обнаружения очередного символа, ограничивающего лексему;
• для выбранной части входного потока выполняется функция распознавания лексемы;
• при успешном распознавании информация о выделенной лексеме заносится в таблицу лексем, и алгоритм возвращается к первому этапу;
• при неуспешном распознавании выдается сообщение об ошибке, а дальнейшие действия зависят от реализации сканера: либо его выполнение прекращается, либо делается попытка распознать следующую лексему (идет возврат к первому этапу алгоритма).
Работа программы-сканера продолжается до тех пор, пока не будут просмотрены все символы программы на исходном языке из входного потока.
Требования к выполнению работы
Порядок выполнения работы
Для выполнения лабораторной работы требуется написать программу, которая выполняет лексический анализ входного текста в соответствии с заданием и порождает таблицу лексем с указанием их типов и значений. Текст на входном языке задается в виде символьного (текстового) файла. Программа должна выдавать сообщения о наличии во входном тексте ошибок, которые могут быть обнаружены на этапе лексического анализа.
Длину идентификаторов и строковых констант можно считать ограниченной 32 символами. Программа должна допускать наличие комментариев неограниченной длины во входном файле. Форму организации комментариев предлагается выбрать самостоятельно.
Лабораторная работа должна выполняться в следующем порядке:
1. Получить вариант задания у преподавателя.
2. Построить описание КА, лежащего в основе лексического анализатора (в виде набора множеств и функции переходов или в виде графа переходов).
3. Подготовить и защитить отчет.
4. Написать и отладить программу на ЭВМ.
5. Сдать работающую программу преподавателю.
Требования к оформлению отчета
Отчет должен содержать следующие разделы:
• Задание по лабораторной работе.
• Описание КС-грамматики входного языка в форме Бэкуса-Наура.
• Описание алгоритма работы сканера или граф переходов КА для распознавания цепочек (в соответствии с вариантом задания).
• Текст программы (оформляется после выполнения программы на ЭВМ).
• Выводы по проделанной работе.
Основные контрольные вопросы
• Что такое трансляция, компиляция, транслятор, компилятор?
• Из каких процессов состоит компиляция? Расскажите об общей структуре компилятора.
• Какую роль выполняет лексический анализ в процессе компиляции?
• Что такое лексема? Расскажите, какие типы лексем существуют в языках программирования.
• Как могут быть связаны между собой лексический и синтаксический анализ?
• Какие проблемы могут возникать при определении границ лексем в процессе лексического анализа? Как решаются эти проблемы?
• Что такое таблица лексем? Какая информация хранится в таблице лексем?
• В чем разница между таблицей лексем и таблицей идентификаторов?
• Что такое грамматика? Дайте определения грамматики. Как выглядит описание грамматики в форме Бэкуса-Наура.
• Какие классы грамматик существуют? Что такое регулярные грамматики?
• Что такое конечный автомат? Дайте определение детерминированного и недетерминированного конечных автоматов.
• Опишите алгоритм преобразования недетерминированного конечного автомата в детерминированный.
• Какие проблемы необходимо решить при построении сканера на основе конечного автомата?
• Объясните общий алгоритм функционирования лексического анализатора.
Варианты заданий
1. Входной язык содержит арифметические выражения, разделенные символом; (точка с запятой). Арифметические выражения состоят из идентификаторов, десятичных чисел с плавающей точкой (в обычной и логарифмической форме), знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.
2. Входной язык содержит логические выражения, разделенные символом; (точка с запятой). Логические выражения состоят из идентификаторов, констант true и false, знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.
3. Входной язык содержит операторы условия типа if … then … else и if … then, разделенные символом; (точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, десятичные числа с плавающей точкой (в обычной и логарифмической форме), знак присваивания (:=).
4. Входной язык содержит операторы цикла типа for (…; …; …) do, разделенные символом; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, десятичные числа с плавающей точкой (в обычной и логарифмической форме), знак присваивания (:=).
5. Входной язык содержит арифметические выражения, разделенные символом; (точка с запятой). Арифметические выражения состоят из идентификаторов, римских чисел, знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.
6. Входной язык содержит логические выражения, разделенные символом; (точка с запятой). Логические выражения состоят из идентификаторов, констант 0 и 1, знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.
7. Входной язык содержит операторы условия типа if … then … else и if … then, разделенные символом; (точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, римские числа, знак присваивания (:=).
8. Входной язык содержит операторы цикла типа for (…; …; …) do, разделенные символом; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, римские числа, знак присваивания (:=).
9. Входной язык содержит арифметические выражения, разделенные символом; (точка с запятой). Арифметические выражения состоят из идентификаторов, шестнадцатеричных чисел, знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.
10. Входной язык содержит логические выражения, разделенные символом; (точка с запятой). Логические выражения состоят из идентификаторов, шестнадцатеричных чисел, знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.
11. Входной язык содержит операторы условия типа if … then … else и if … then, разделенные символом; (точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, шестнадцатеричные числа, знак присваивания (:=).
12. Входной язык содержит операторы цикла типа for (…; …; …) do, разделенные символом; (точка с запятой). Операторы цикла содержат идентификаторы, знаки сравнения <, >, =, шестнадцатеричные числа, знак присваивания (:=).
13. Входной язык содержит арифметические выражения, разделенные символом; (точка с запятой). Арифметические выражения состоят из идентификаторов, символьных констант (один символ в одинарных кавычках), знака присваивания (:=), знаков операций +, -, *, / и круглых скобок.
14. Входной язык содержит логические выражения, разделенные символом; (точка с запятой). Логические выражения состоят из идентификаторов, символьных констант Т и 'F', знака присваивания (:=), знаков операций or, xor, and, not и круглых скобок.