Компилятор

Разработка текстового редактора с функциями языкового процессора.

Оглавление

• Лабораторная работа №1: Разработка пользовательского интерфейса (GUI) для языкового процессора
• Лабораторная работа №2: Разработка лексического анализатора (сканера)
• Лабораторная работа №3: Разработка синтаксического анализатора (парсера)
• Лабораторная работа №4: Нейтрализация ошибок (метод Айронса)
• Лабораторная работа №5: Включение семантики в анализатор. Создание внутренней формы представления программы
• Лабораторная работа №6: Реализация алгоритма поиска подстрок с помощью регулярных выражений
• Лабораторная работа №7: Реализация метода рекурсивного спуска для синтаксического анализа

Лабораторная работа №1: Разработка пользовательского интерфейса (GUI) для языкового процессора

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

Цель работы: разработать приложение с графическим интерфейсом пользователя, способное редактировать текстовые данные. Это приложение будет базой для будущего расширения функционала в виде языкового процессора.

Язык реализации: C#, WPF.

Интерфейс текстового редактора

Получившийся текстовый редактор имеет следующие элементы:

1. Заголовок окна.

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

2. Меню

   Пункт меню	Подпункты
   Файл
   Правка
   Текст
   Пуск	—
   Справка

3. Панель инструментов

   

   • Создать
   • Открыть
   • Сохранить
   • Изменить размер текста
   • Отменить
   • Повторить
   • Копировать
   • Вырезать
   • Вставить
   • Пуск
   • Вызов справки
   • О программе

4. Область редактирования

   Поддерживаются следующие функции:

   • Изменение размера текста
   • Открытие файла при перетаскивании его в окно программы
   • Базовая подсветка синтаксиса
   • Нумерация строк

5. Область отображения результатов

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

   Поддерживаются следующие функции:

   • Изменение размера текста
   • Отображение ошибок в виде таблицы

6. Строка состояния

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

Справочная система

Разделы справочной системы открываются как HTML-документы в браузере.

Раздел	Изображение
Вызов справки
О программе

Вывод сообщений

Сообщение	Описание	Изображение
Закрытие окна программы	Появляется при закрытии программы нажатием крестика или комбинацией клавиш при наличии несохраненных изменений
Сохранение изменений	Появляется при попытке открыть существующий файл или создать новый при наличии несохраненных изменений

Лабораторная работа №2: Разработка лексического анализатора (сканера)

Тема: разработка лексического анализатора (сканера).

Цель работы: изучить назначение лексического анализатора. Спроектировать алгоритм и выполнить программную реализацию сканера.

№	Тема	Пример верной строки	Справка
42	Объявление и инициализация целочисленной константы в СУБД PostgreSQL	DECLARE product_price CONSTANT INTEGER := 150;	ссылка

В соответствии с вариантом задания необходимо:

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

Входные данные: строка (текст программного кода).

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

Примеры допустимых строк

DECLARE product_price CONSTANT INTEGER = +150;

DECLARE total_amount CONSTANT INTEGER := -150;

DECLARE productPrice CONSTANT INTEGER := +150;

DECLARE expense_1_amount CONSTANT INTEGER := -50;

DECLARE product_price CONSTANT INTEGER := -150; DECLARE total_2 CONSTANT INTEGER := 50;

DECLARE productPrice3 CONSTANT INTEGER := 150; DECLARE expense_amount_4 CONSTANT INTEGER := -50;

Диаграмма состояний сканера

Тестовые примеры

1. Тест №1. Пример, показывающий все возможные лексемы, которые могут быть найдены лексическим анализатором.

   

2. Тест №2. Сложный пример.

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

   

3. Тест №3. Сложный пример.

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

   

Лабораторная работа №3: Разработка синтаксического анализатора (парсера)

Тема: разработка синтаксического анализатора (парсера).

Цель работы: изучить назначение синтаксического анализатора, спроектировать алгоритм и выполнить программную реализацию парсера.

№	Тема	Пример верной строки	Справка
42	Объявление и инициализация целочисленной константы в СУБД PostgreSQL	DECLARE product_price CONSTANT INTEGER := 150;	ссылка

Примеры допустимых строк

В соответствии с вариантом задания на курсовую работу необходимо:

1. Разработать автоматную грамматику.
2. Спроектировать граф конечного автомата (перейти от автоматной грамматики к конечному автомату).
3. Выполнить программную реализацию алгоритма работы конечного автомата.
4. Встроить разработанную программу в интерфейс текстового редактора, созданного на первой лабораторной работе.

Грамматика

G[<ЦК> = <целочисленная константа>]:

V_T = { ‘DECLARE’, ‘CONSTANT’, ‘INTEGER’, ‘a’…’z’, ‘A’…’Z’, ‘0’…’9’, ‘:’, ‘;’, ‘+’, ‘-‘, ‘=’, ‘_’ }

V_N = { <ЦК>, E, CONST, INT, ASSIGN, NUMBER, SIGN, UNSIGNEDINT, END, Б, Ц }

P = {

1. <ЦК> → ‘DECLARE’ E
2. E → Б { Б | Ц | ‘_’ } CONST
3. CONST → ‘CONSTANT’ INT
4. INT → ‘INTEGER’ ASSIGN
5. ASSIGN → ‘:=’ NUMBER | ‘=’ NUMBER
6. NUMBER → SIGN UNSIGNEDINT
7. SIGN → [ ‘+’ | ‘-‘ ]
8. UNSIGNEDINT → Ц { Ц } END
9. END → ‘;’
10. Б → ‘a’ | ‘b’ | … | ‘z’ | ‘A’ | ‘B’ | … | ‘Z’
11. Ц → ‘0’ | ‘1’ | … | ‘9’

}

Классификация грамматики

Согласно классификации Хомского, грамматика G[Z] является полностью автоматной.

Граф конечного автомата

Тестовые примеры

1. Тест №1. Все выражения написаны корректно.

   

2. Тест №2. Пример ошибок.

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

   • Нажатие кнопки справа от количества ошибок позволяет их автоматически исправить.

   

3. Тест №3. Пример ошибок.

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

   • Нажатие кнопки справа от количества ошибок позволяет их автоматически исправить.

   

Лабораторная работа №4: Нейтрализация ошибок (метод Айронса)

Тема: нейтрализация ошибок (метод Айронса).

Цель работы: реализовать алгоритм нейтрализации синтаксических ошибок и дополнить им программную реализацию парсера.

Метод Айронса

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

Этот алгоритм был мной уже реализован в Лабораторной работе №3. В таблице ошибок выводятся их местоположение и текст ошибки, содержащий информацию об отброшенном фрагменте.

Тестовые примеры

1. Тест №1. Пример ошибок.

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

   • Нажатие кнопки справа от количества ошибок позволяет их автоматически исправить.

   

2. Тест №2. Пример ошибок.

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

   • Нажатие кнопки справа от количества ошибок позволяет их автоматически исправить.

   

Лабораторная работа №5: Включение семантики в анализатор. Создание внутренней формы представления программы

Тема: включение семантики в анализатор, создание внутренней формы представления программы, используя польскую инверсную запись (ПОЛИЗ).

Цель работы: дополнить анализатор, разработанный в рамках лабораторных работ, этапом формирования внутренней формы представления программы.

Тестовые примеры

1. Тест №1. Вычисление значения арифметического выражения.

   

2. Тест №2. Обработка деления на 0.

   

3. Тест №3. Обработка недопустимых символов.

   

Лабораторная работа №6: Реализация алгоритма поиска подстрок с помощью регулярных выражений

Тема: реализация алгоритма поиска подстрок с помощью регулярных выражений.

Цель работы: реализовать алгоритм поиска в тексте подстрок, соответствующих заданным регулярным выражениям.

Задачи

1. (I.3) Построить РВ для валидации российских номеров городских телефонов (7 цифр, разделенных пробелами или символами -, без кода города).

(?:\b\d{3}[-\s]?\d{2}[-\s]?\d{2}\b)

2. (II.16) Построить РВ, описывающее ФИО человека на русском языке (фамилия, имя и отчество полностью).

\b[А-ЯЁ][а-яё]*\s+[А-ЯЁ][а-яё]*\s+[А-ЯЁ][а-яё]*\b

3. (III.17) Построить РВ, описывающее широту (учесть диапазон корректных значений).

(?<!\d)[-]?(?:(?:0*[0-8]\d?)|(?:90))(?:\.\d+)?(?!\d)

Лабораторная работа №7: Реализация метода рекурсивного спуска для синтаксического анализа

Тема: реализация метода рекурсивного спуска для синтаксического анализа.

Цель работы: разработать для грамматики алгоритм синтаксического анализа на основе метода рекурсивного спуска.

Для грамматики G[<While>] разработать и реализовать алгоритм анализа на основе метода рекурсивного спуска.

G[<While>]:

1. <While> → while <Cond> do <Stmt> end ;
2. <Cond> → <LogExpr> {or <LogExpr>}
3. <LogExpr> → <RelExpr> {and <RelExpr>}
4. <RelExpr> → <Operand> [rel <Operand>]
5. <Operand> → var | const
6. <Stmt> → var as <ArithExpr>
7. <ArithExpr> → <Operand> {ao <Operand>}

Примечание: while, do, end, and, or – ключевые слова. В тип rel объединили операции сравнения <,<=, >=, >, != и ==, в тип ao арифметические операции + и -, в тип as оператор присваивания =, тип var – название переменной (только буквы), тип const – числа. Причина, по которой не объединены в один тип логические операции and и or заключается в том, что эти операции имеют различный приоритет.

По классификации Хомского данная грамматика относится к КС.

Тестовые примеры

while a < b do b = b - 20 end;
while a < b and c != d or e == f or g <= h and i > j do abc = cde - 20 + 40 - 8 + efg end;
while a < b do b = a + ? end