Государственный комитет Российской Федерации

по общему и высшему образованию 

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

Кафедра "ПОВТ и АС". 
 
 
 
 
 
 
 
 

ЛАБОРАТОРНАЯ  РАБОТА.

По дисциплине "теория вычислительных процессов и структур"

На  тему:

«Реализация алгоритма по устранению цепных продукций» 
 
 
 

Выполнил:

студенты  группы Иc-3-39

.

ЦВЕТКОВ А.Е.

ГОЛОВАНЬ  С.

Проверил:

Деундяк В.М. 
 
 
 
 
 
 
 
 
 
 
 

Ростов - на - Дону

- 2002 Г. - 
 

Содержание. 
 
 

1. Постановка  задачи…………………………………………………………3
2. Структурная схема программы (Алгоритм.)…………….………………4
3. Выбор языка и средств……………………………………………………4
4. Тестовый пример…………………………………………………………..5
5. Руководство оператора…..………………………………………………..5
6. Руководство программиста……………………………………………….7
7. Текст программы…………………………………………………………...8

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Постановка  задачи. 

1 Введение.

Наименование  программного продукта - "программа по устранению цепных продукций".

2 Основания для разработки:

    Задание для лабораторной работы  по дисциплине "теория вычислительных процессов и структур. Условное обозначение разработки - лабораторная  работа.

3 Постановка задачи.

      Разработать программу, реализующую алгоритм устранения цепных продукций в не укорачивающейся КС–грамматики G(N,E,P,S).

  

4 Требования к программе и программному изделию:

4.1 Требования к функциональным характеристикам:

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

4.2 Требования к надежности:

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

4.3 Условия эксплуатации:

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

4.4 Требования к составу и параметрам технических средств:

Программе требуется компьютер фирмы IBM или  совместимый с ним, с процессором  не ниже 80286 фирмы INTEL или с ним совместимый.

4.5 Требования к информационной и программной совместимости:

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

4.6 Требования к маркировке и установке:

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

4.7 Требования к транспортировке и хранению:

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

     4.8 Требования к программной документации:

       Документация к ПО:

- постановка задачи.

- структурная схема программы.

– выбор  языка программирования и средств.

– руководство  пользователя.

- руководство программиста.

– текст  программы. 
 
 

5 Технико-экономические показатели:

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

6 Стадии и этапы разработки:

- постановка задачи

- построение математической модели

- машинный алгоритм

- программа

- тестирование (общее и экстремальных случаев)

- документация

Разработчиками  являются : студенты ДГТУ группы Ис-3-39 Цветков А.Е,

Головань  С

7 Порядок контроля и приемки:

Визуальное  ознакомление и запуск с тестовыми  примерами заказчика.

Ознакомление  с документацией. 
 
 

Алгоритм.

(Устранение  цепных продукций  в КС-грамматики).

Вход: Не укорачивающаяся КС-грамматика G=(N, S, P, S).

Выход: Не укорачивающаяся КС-грамматика G’=(N’, S, P’, S’), без цепных продукций, у которой L(G’)=L(G).

Метод: Для каждого А из N строится подмножество N^D={B|AÞ^*B} Множества N и, на основе этого, конструируется новая грамматика.

Шаг 1: Для каждого А из N построить N^D={B|AÞ^*B}.

Шаг 1.1: Положить N₀={A} и i=1.

Шаг 1.2: Положить

Шаг 1.3: Если N_i¹N_i-1, то положить i=i+1 и повторить Шаг 1.2, в противном случае положить N^D=N_i.

Шаг 2: Построить P’ так: если продукция B®a принадлежит Р и не является цепной, то включить в Р’ продукцию (A®a) для всех таких A, что BÎN^D.

Шаг 3: Построить  грамматику G’=(N, S, P’, S).

 
 

Выбор языка и средств

                 Delphi. Основные характеристики .

Delphi - это комбинация  нескольких важнейших технологий:

• Высокопроизводительный компилятор в машинный код
• Объектно-ориентированная модель компонент
• Визуальное (а, следовательно, и скоростное) построение приложений из программных прототипов

Компилятор  в машинный код

Компилятор, встроенный в Delphi, обеспечивает высокую производительность, необходимую для построения приложений в архитектуре "клиент-сервер". Этот компилятор в настоящее время  является самым быстрым в мире, его скорость компиляции составляет свыше 120 тысяч строк в минуту на компьютере 486DX33. Он предлагает легкость разработки и быстрое время проверки готового программного блока, характерного для языков четвертого поколения (4GL) и в то же время обеспечивает качество кода, характерного для компилятора 3GL. Кроме того, Delphi обеспечивает быструю разработку без необходимости писать вставки на Си или ручного написания кода (хотя это возможно).

В процессе построения приложения разработчик выбирает из палитры компонент готовые компоненты как художник, делающий крупные мазки кистью. Еще до компиляции он видит результаты своей работы - после подключения к источнику данных их можно видеть отображенными на форме, можно перемещаться по данным, представлять их в том или ином виде. В этом смысле проектирование в Delphi мало чем отличается от проектирования в интерпретирующей среде, однако после выполнения компиляции мы получаем код, который исполняется в 10-20 раз быстрее, чем то же самое, сделанное при помощи интерпретатора. Кроме того, компилятор компилятору рознь, в Delphi компиляция производится непосредственно в родной машинный код, в то время как существуют компиляторы, превращающие программу в так называемый p-код, который затем интерпретируется виртуальной p-машиной. Это не может не сказаться на фактическом быстродействии готового приложения.

Объектно-ориентированная  модель программных  компонент

Основной упор этой модели в Delphi делается на максимальном реиспользовании кода. Это позволяет  разработчикам строить приложения весьма быстро из заранее подготовленных объектов, а также дает им возможность создавать свои собственные объекты для среды Delphi. Никаких ограничений по типам объектов, которые могут создавать разработчики, не существует. Действительно, все в Delphi написано на нем же, поэтому разработчики имеют доступ к тем же объектам и инструментам, которые использовались для создания среды разработки. В результате нет никакой разницы между объектами, поставляемыми Borland или третьими фирмами, и объектами, которые вы можете создать.

В стандартную  поставку Delphi входят основные объекты, которые образуют удачно подобранную  иерархию из 400 базовых классов. Для начала - неплохо. Но если возникнет необходимость в решении какой-то специфической проблемы на Delphi, советуем, прежде чем попытаться начинать решать проблему "с нуля", просмотреть список свободно распространяемых или коммерческих компонент, разработанных третьими фирмами, количество этих фирм в настоящее время превышает число 250, хотя, возможно, я не обо всех знаю. Скептики, возможно, не поверят мне, когда я скажу, что на Delphi можно одинаково хорошо писать как приложения к корпоративным базам данных, так и, к примеру, игровые программы. Тем не менее, это так. Во многом это объясняется тем, что традиционно в среде Windows было достаточно сложно реализовывать пользовательский интерфейс. Событийная модель в Windows всегда была сложна для понимания и отладки. Но именно разработка интерфейса в Delphi является самой простой задачей для программиста.Диапазон разработанных при помощи Delphi программных продуктов также поражает - от игровых программ до мощнейших банковских систем. Прошло всего полгода - и столько результатов. Delphi как продукт имеет версию 6.0, уже имееются сведения о том, что предполагается реализовать в следующей версии Delphi, и поскольку Delphi разрабатывается на Delphi, можем быть уверены, что разработка новой версии ведется действительно скоростными методами. 
 
 

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

       Тестовый пример возят из учебного  пособия: «Элементы теории формальных  языков» В.М. Деундяк,    г.  Ростов-на-Дону 1997год.

       

         Пример: Рассмотрим не укорачивающуюся  КС– грамматику G=({W,S,A,B},{0,1},P,W)  где состоит P из продукций Применим к грамматике G алгоритм и получим не укорачивающуюся КС- грамматику G’==({W,S,A,B},{0,1},P’,W), где Р’ состоит из продукций(РИС 1)