Программная часть

В данном разделе описаны два задания для текстовой контрольной работы или лабораторных работ. Если в учебном плане имеется одна контрольная работа или лабораторная работа, то в ее рамках необходимо выполнить оба задания. Если же в учебном плане две контрольные работы или лабораторные работы, то задание № 1 выполняется в рамках первой работы, и задание № 2 – в рамках второй работы.

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

По итогам выполнения контрольной работы оформляется отчет.

Выбор вариантов заданий осуществляется по общим правилам с использованием следующей формулы:

V = (N × K) div 100,

где V – искомый номер варианта,

N – общее количество вариантов,

K – код варианта,

div – целочисленное деление,

при V = 0 выбирается максимальный вариант.

ЗАДАНИЕ № 1

Тема задания: «Синтаксический анализ с использованием конечных автоматов и регулярных выражений».

Цель: научиться применять на практике такие средства синтаксического анализа, как детерминированные конечные автоматы (ДКА), ДКА с магазинной памятью (ДМПА) и регулярные выражения (РВ).

Написанная программа должна читать входные данные из текстового файла (например, имеющего имя «input.txt») и выдавать результат работы в текстовый файл (например, имеющий имя «output.txt»).

Для ввода и вывода данных допускается использование в программе визуального интерфейса вместо файлового ввода/вывода.

Вариант 1. На вход программы подается описание переменных на выбранном языке (Pascal, C++, C# и т. д.). Программа должна проанализировать его при помощи ДКА или ДМПА и выдать результат проверки. Это может быть:

1. Сообщение о том, что описание корректное.

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

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

Вариант 2. На вход программы подается единственная строка символов. Данная строка задает присваивание переменной значения арифметического выражения в виде

ПЕРЕМЕННАЯ = ВЫРАЖЕНИЕ.

Выражение может включать:

– знаки сложения и умножения («+» и «*»);

– круглые скобки («(» и «)»);

– константы (например, 5; 3.8; 1e+18, 8.41E-10);

– имена переменных (последовательности букв и цифр, начинающиеся с буквы).

Программа должна с помощью ДКА или ДМПА построить дерево, соответствующее заданному во входном файле выражению, и выдать для данного выражения:

1) таблицу имен;

2) неоптимизированный код;

3) оптимизированный код.

Вариант 3. На вход программы подается описание переменных на выбранном языке (Pascal, C++, C# и т. д.). Программа должна проанализировать его при помощи регулярного выражения и выдать результат проверки. Это может быть:

1. Сообщение о том, что описание корректное.

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

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

Вариант 4. На вход программы подается единственная строка символов. Данная строка задает присваивание переменной значения арифметического выражения в виде

ПЕРЕМЕННАЯ = ВЫРАЖЕНИЕ.

Выражение может включать:

– знаки сложения и умножения («+» и «*»);

– круглые скобки («(» и «)»);

– константы (например, 5; 3.8; 1e+18, 8.41E-10);

– имена переменных (последовательности букв и цифр, начинающиеся с буквы).

Программа должна с помощью регулярного выражения построить дерево, соответствующее заданному во входном файле выражению, и выдать для данного выражения:

1) таблицу имен;

2) неоптимизированный код;

3) оптимизированный код.

ЗАДАНИЕ № 2 

Тема задания: «Синтаксический анализ с использованием КС-грамматик».

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

Написанная программа должна читать входные данные и описание грамматики из текстовых файлов (например, имеющих имена «input.txt» и «grammar.txt» соответственно) и выдавать результат работы в текстовый файл (например, имеющий имя «output.txt»).

Для ввода и вывода данных допускается использование в программе визуального интерфейса вместо файлового ввода/вывода.

Вариант 1. На вход программы подается описание процедур и функций на выбранном языке (Pascal, C++) либо делегатов на языке C#, а также описание LL(1)-грамматики. Необходимо проверить, является ли описание процедур/функций/делегатов корректным с точки зрения заданной грамматики и не содержатся ли в нем конфликты имен.

Таким образом, задание разбивается на две части:

1. Проверка синтаксиса.

2. Проверка семантики.

Семантика зависит от выбранного языка, и поэтому ее проверка жестко привязана к анализатору (в данном случае – вашей программе). Грамматика же должна быть универсальной, т. е. должна позволять задавать любые правила для разбора процедур/функций/делегатов (и не только). Например, должны быть доступны изменения: ключевых слов, знаков пунктуации, правил разбора идентификаторов, а также добавление новых языковых конструкций и т. п.

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

1. Сообщение о том, что грамматика во входном файле не является LL(1)-грамматикой.

2. Сообщение о том, что описание корректное.

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

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

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

Вариант 2. На вход программы подается описание структур (записей) на выбранном языке (Pascal, C++, C#), а также описание LL(1)-грамматики. Необходимо проверить, является ли описание структур/записей корректным с точки зрения заданной грамматики и не содержатся ли в нем конфликты имен.

Таким образом, задание разбивается на две части:

1. Проверка синтаксиса.

2. Проверка семантики.

Семантика зависит от выбранного языка, и поэтому ее проверка жестко привязана к анализатору (в данном случае – вашей программе). Грамматика же должна быть универсальной, т. е. должна позволять задавать любые правила для разбора структур/записей (и не только). Например, должны быть доступны изменения: ключевых слов, знаков пунктуации, правил разбора идентификаторов, а также добавление новых языковых конструкций и т. п.

Программа должна проанализировать имеющееся описание структур/записей и выдать результат проверки. Это может быть:

1. Сообщение о том, что грамматика во входном файле не является LL(1)-грамматикой.

2. Сообщение о том, что описание корректное.

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

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

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

Вариант 3. На вход программы подается описание процедур и функций на выбранном языке (Pascal, C++) либо делегатов на языке C#, а также описание LR(1)-грамматики. Необходимо проверить, является ли описание процедур/функций/делегатов корректным с точки зрения заданной грамматики и не содержатся ли в нем конфликты имен.

Таким образом, задание разбивается на две части:

1. Проверка синтаксиса.

2. Проверка семантики.

Семантика зависит от выбранного языка, и поэтому ее проверка жестко привязана к анализатору (в данном случае – вашей программе). Грамматика же должна быть универсальной, т. е. должна позволять задавать любые правила для разбора процедур/функций/делегатов (и не только). Например, должны быть доступны изменения: ключевых слов, знаков пунктуации, правил разбора идентификаторов, а также добавление новых языковых конструкций и т. п.

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

1. Сообщение о том, что грамматика во входном файле не является LR(1)-грамматикой.

2. Сообщение о том, что описание корректное.

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

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

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

Вариант 4. На вход программы подается описание структур (записей) на выбранном языке (Pascal, C++, C#), а также описание LR(1)-грамматики.

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

Таким образом, задание разбивается на две части:

1. Проверка синтаксиса.

2. Проверка семантики.

Семантика зависит от выбранного языка, и поэтому ее проверка жестко привязана к анализатору (в данном случае – вашей программе). Грамматика же должна быть универсальной, т. е. должна позволять задавать любые правила для разбора структур/записей (и не только). Например, должны быть доступны изменения: ключевых слов, знаков пунктуации, правил разбора идентификаторов, а также добавление новых языковых конструкций и т. п.

Программа должна проанализировать имеющееся описание структур/записей и выдать результат проверки. Это может быть:

1. Сообщение о том, что грамматика во входном файле не является LR(1)-грамматикой.

2. Сообщение о том, что описание корректное.

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

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

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

Текстовая часть

Отчет по каждой контрольной или лабораторной работе должен включать следующие элементы:

1. Титульный лист. Образцы оформления титульного листа приведены в приложениях А и Б.

2. Оглавление. В оглавлении должны быть приведены заголовки всех разделов документа (вплоть до второго или третьего уровня) с указанием номеров страниц.

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

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

5. Результаты работы. В результаты работы включается формальное описание построенных синтаксических анализаторов, а также результаты тестовых прогонов программы.

6. Заключение (выводы). Здесь формулируются выводы по полученным результатам работы.

7. Список использованных источников. На приведенные источники в тексте документа должны быть расставлены ссылки.

8. Приложения (например, листинги программ и т. п.).

В целом отчет по контрольной или лабораторной работе должен быть оформлен согласно требованиям актуальной версии образовательного стандарта ОС ТУСУР для специальностей технического профиля. В настоящее время это стандарт ОС ТУСУР 01–2013 [7].