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

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

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

Кафедра ВТ

Расчётно-пояснительная записка

к курсовой работа по дисциплине

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

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

Группа: АМ-215

Студент: Манило А. С.

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

Вариант: 443331

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

Оглавнение

Задание.. 3

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

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

Введение.. 5

Описание языка.. 6

Пример тестовой программы... 8

Система регулярных выражений.. 9

Формальная грамматика.. 10

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

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

Результаты работы лексического анализатора.. 17

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

Результат преобразования последовательности лексем в постфиксную запись.. 22

Обработка блоков связей и заголовков.. 23

Результат создания таблицы связей.. 23

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

Результаты проверки лексически или синтаксически неверных программ и результаты работы семантических проверок. 26

Преобразование ПФЗ в последовательность пентад.. 29

Результаты преобразования ПФЗ в последовательность пентад.. 31

Разработка интерпретатора.. 34

Разработка работы интерпретатора.. 34

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

Литература.. 40

Задание

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

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

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

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

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

- формирование лексем,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-  описания общей памяти;

-  определения вычислений;

-  описания связей между блоками.

Структура блока:

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

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

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

II.2  Типы блоков: