Системное программное обеспечение. Лабораторный практикум - [16]

Таким образом, алгоритм работы простейшего сканера можно описать так:

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

• для выбранной части входного потока выполняется функция распознавания лексемы;

• при успешном распознавании информация о выделенной лексеме заносится в таблицу лексем, и алгоритм возвращается к первому этапу;

• при неуспешном распознавании выдается сообщение об ошибке, а дальнейшие действия зависят от реализации сканера: либо его выполнение прекращается, либо делается попытка распознать следующую лексему (идет возврат к первому этапу алгоритма).

Работа программы-сканера продолжается до тех пор, пока не будут просмотрены все символы программы на исходном языке из входного потока.

Требования к выполнению работы

Порядок выполнения работы

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

Длину идентификаторов и строковых констант можно считать ограниченной 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, разделенные символом; (точка с запятой). Операторы условия содержат идентификаторы, знаки сравнения <, >, =, римские числа, знак присваивания (:=).