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

Министерство образования и науки РФ

Новосибирский Государственный Технический Университет

Кафедра Вычислительной Техники

Курсовая работа по дисциплине

«Системное программное обеспечение»

Факультет: АВТ

Группа: АМ-215

Студент: Белоглазов А. В.

Преподаватель: Малявко А. А.

Вариант: 142133

Новосибирск, 2006 г.

Оглавление:

1. Задание на курсовую работу. 3

1.1. Содержание работы. 3

1.2. Краткое описание учебного языка, варианты заданий. 4

2. Введение. 5

3. Описание заданного варианта языка. 5

4. Система регулярных выражений и формальная грамматика. 7

5. Управляющая таблица нисходящего автомата с несколькими состояниями. 9

6. Тестовая программа. 13

7. Поиск в таблицах идентификаторов / констант и пополнение таблиц. 14

7.1. Описание алгоритма. 14

7.2. Результаты работы. 15

8. Преобразование последовательности лексем в постфиксную запись. 17

8.1. Описание алгоритма. 17

8.2. Результаты работы. 19

9. Результаты работы с ошибочными входными данными. 19

10. Преобразование постфиксной записи в последовательность пентад. 22

10.1. Описание алгоритма. 22

10.2. Результаты работы. 25

11. Семантический анализатор. 26

11.1. Построение таблицы связей. 26

11.2. Обработка семантических ошибок. 26

11.3. Выполнение последовательности пентад. 28

11.3. Результат выполнения последовательности пентад. 31

12. Заключение. 36

13. Список литературы. 36

1. Задание на курсовую работу.

1.1. Содержание работы.

1. Разработать словесное описание лексики, синтаксиса и семантики заданного варианта языка. Написать простую тестовую программу (программы), содержащую все заданные элементы языка. Вручную выполнить интерпретацию программы. Эту программу использовать впоследствии для проверки элементов разрабатываемого транслятора.

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

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

• поиск в таблицах идентификаторов / констант и пополнение таблиц;
• формирование лексем,

и построить лексический анализатор. Проверить его работоспособность.

4. Разработать формальную грамматику класса LL(1), определяющую синтаксис заданного языка. Используя пакет WebTransLab, построить автоматную реализацию нисходящего синтаксического акцептора.

5. Разработать формальную грамматику класса не выше, чем LALR(1). Используя пакет WebTransLab, построить автоматную реализацию восходящего синтаксического акцептора.

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

7. Разработать семантический анализатор и преобразователь ПФЗ в последовательность тетрад (триад, …).

8. Разработать интерпретатор (виртуальную машину), обеспечивающий (квази)параллельное исполнение сформированной последовательности тетрад.

9. Оформить расчетно-пояснительную записку следующего содержания:

·  Данное задание; Оглавление; Введение; Описание заданного варианта языка;

·  По каждому из пунктов 2, 4, 5:

o  система регулярных выражений ( п.2 ) или формальная грамматика ( п.п. 4,5 );

o  фрагменты управляющих таблиц конечных автоматов, построенные WebTransLab’ом или LexLab’ом/SyntLab’ом  (для построения фрагментов использовать выходные файлы построителей автоматов, но не печатать эти файлы целиком!). Пояснить содержание фрагментов, приведенных в записке.

o  примеры результатов работы автоматов с тестовыми примерами; объяснение и анализ результатов.

·  По каждому из пунктов 3, 6, 7, 8:

o  полное описание алгоритма, тексты разработанных программ (выборочно по усмотрению студента; не требуется включать в записку тексты всех программ).

o  примеры результатов работы компонент транслятора с правильными и ошибочными входными программами; объяснение и анализ результатов.

·  Заключение.

Объем записки не должен превышать 20-30 страниц.

1.2. Краткое описание учебного языка, варианты заданий.

Язык предназначен для программирования потоковых вычислений. Программа на таком языке состоит из совокупности блоков одного из назначений:

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

Структура блока: {<идентификатор блока> [{ <заголовок>}] <тело> [{<концевик> }] }

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

II.1  Идентификатор блока: <имя блока>:<тип блока>. Имя блока: