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

"Лингвистическое обеспечение САПР"


1. Язык множеств и его реализация.
Разработать язык  манипулирования  конечными  множествами [1], обеспечиваящий: Правила конструирования  имен  множеств  -  те  же,  что  и правила конструирования имен переменных в языке СИ.
Элементы множеств - самоопределенные термы, сконструированные из множества символов  распознаваемых  функцией  isalnum  из стандартной библиотеки языка СИ.

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

2. Язык алгебры логики и его использование для решения задачи логической разрешимости.
Разработать язык алгебры логики [1], позволяющий:

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

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

3. Лингвистический процессор для символьного дифференцирования.
Разработать язык, который должен позволять:

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

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

4. Лингвистический процессор для численного интегрирования функций.
[Суханов РК6-73]
Разработать язык описания алгебраических выражений,  который должен обеспечивать:

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

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

5. [Собянин РК6-73] Транслятор nroff - html
Разработать транслятор документов в формате nroff в документы формата html.
Язык верстки текстовых документов nroff (и, соответственно, программа-верстатель nroff) широко используется в ОС UNIXдля представления документации на эту систему. Получить описание языка верстки nroff в любой версии ОС UNIX можно командой

man 5 man
Просмотреть образец размеченного директивами nroff документа мосжно командой
more /usr[/share]/man/man5/man.5
Язык html (hypertext markup language) является общепринятым языком верстки документов, предназначенных для просмотра через Internet.

Внимание. Данное задание обязательно должно быть реализовано средствами lex и yacc.
Примечание. Правильность работы транслятора будет проверяться сравнением облика результатов работы программы man и транслятора на реальных документах руководства ОС UNIX.

6. Верификатор описаний на языке VHDL
Разработать программу, осуществляющую проверку синтаксиса описаний на языке VHDL (Veryhighintegrated circiuts design language) цифровых устройств.
Неформальное описание языка VHDL дано в [2]. Описание языка VHDL также можно получить на дискете.
Примечание. Правильность работы верификатора будет проверяться путем сравнения с результатами работы реальной системы.

7. Транслятор VHDL - Пролог
Язык VHDL - язык описания цифровых систем (см. задание выше).
Язык Пролог (Prolog - programing in logic) имеет в качестве математической основы исчисление предикатов первого порядка и может быть использован, в частности, для вычисления значений логических выражений. Описание языка дано в [3, 4] и других источниках (например, http://rk6.bmstu.ru).
Необходимо разработать транслятор описаний комбинационных схем на языке VHDL в описания на языке Пролог. При разработке транслятора необходимо учесть следующие ограничения:

Пример. Ниже приводятся описания на языках VHDL и Пролог объекта unit и входящего в его состав объекта andno2.
Схема объекта andno2

 

Схема объекта unit

 

Описание на языке VHDL
-------------- Объект проекта 2И-НЕ --------------

entity andno2 is   -- Описание интерфейса 2И-НЕ
  port (
    x1, x2: in Bit;
    y1: out Bit);
end andno2;

architecture StructAndNo2 of andno2 is   -- Описание
                        -- архитектурного тела 2И-НЕ
  component and2  -- список используемых компонентов
    port(a1, a2: in Bit; b1 out Bit);
  component no
    port(a: in Bit; b out Bit);

  begin                        -- описание топологии
    c1: and2
      port map(x1, x2, z1);
    c2: no
      port map(z1, y1);
end StructAndNo2;

--------------- Объект проекта Unit -----------------

entity unit is   -- Описание интерфейса Unit
  port (
    x1, x2, x3: in Bit;
    y1, y2: out Bit);
end unit;

architecture StructUnit of unit is        -- Описание
                          -- архитектурного тела Unit
  component andno2 -- список используемых компонентов
    port(a1, a2: in Bit; b1 out Bit);
  component and2
    port(a1, a2: in Bit; b1 out Bit);
  component or2
    port(a1, a2: in Bit; b1 out Bit);

  begin                        -- описание топологии
    c1: andno2
      port map(x1, x2, z1);
    c2: and2
      port map(x2, x3, z2);
    c3: andno2
      port map(z1, z2, y1);
    c4: or2
      port map(y1, z2, y2);

end StructUnit;
Описание на языке Пролог
andno2(x1, x2, y1) :- and2(x1, x2, z1),
  no(z1, y1).

unit(x1, x2, x3, y1, y2) :- andno2(x1, x2, z1),
  and2(x2, x3, z2),
  and2(z1, z2, y1),
  and2(y1, z2, y2).

8. Транслятор SQL-Пролог
Разработать транслятор разнообразных форм оператора SELECT языка SQL в предложение языка Пролог.
SQL (Structured Query Language - структурированный язык запросов) является стандартным языком описания и манипулирования данными в реляционных СУБД. Основным оператором языка является оператор SELECT - оператор выборки данных из таблиц реляционной БД (таблица есть одна из форм представления отношения (relation)). Краткое описание языка SQL можно найти по адресу http://fedoruk.comcor.ru или http://rk6.bmstu.ru.
Язык Пролог (см. выше) можно рассматривать как средство представления и оперирования отношениями (абстрактными или имеющими смысл в некоторой предметной области). С математической точки зрения исчисление предикатов первого порядка (ИППП), лежащее в основе языка Пролог, является более мощным аппаратом, чем реляционное исчисление, составляющее основу реляционных БД и языка SQL. Это обеспечивает возможность однозначной трансляции оператора выборки SELECT языка SQL в правило языка Пролог (исключение составляют "модификаторы" оператора SELECT типа ORDER BY, не вписывающиеся в реляционную модель данных). Описание языка Пролог можно найти в [3, 4].

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

Пример. Пусть есть две следующие таблицы реляционной БД.

students
id name bdate
12345 Sidorov I.P. 1980-04-01
... ... ...
mlist
id discipline mark
12345 physics 3
... ... ...
Следующий оператор SELECT
SELECT s.name, s.id, m.discipline
  FROM students s, mlist m
  WHERE s.id = m.id AND s.name = 'Ivanov I.P.' AND m.mark > 3;
транслируется в такое правило языка Пролог
select(s_name, s_id, m_discipline) :-
  students(s_id, s_name, s_bdate), mlist(m_id, m_discipline, m_mark),
  s_id = m_id, s_name = 'Ivanov I.P.', m_mark > 3, fail.

9. Транслятор произвольных логических выражений в ДНФ
Разработать язык описания логических выражений [1], позволяющий :
описывать сложные логические выражения,  учитывая приоритет логических операций и используя скобочную форму записи;
допустимыми логическими операциями являются И,  ИЛИ, НЕ и ИМПЛИКАЦИЯ;
операндами логических операций могут быть константы (0 или 1) и  переменные.
При конструировании имен логических переменных использовать правила для аналогичных объектов языка СИ.
Разработать программу-транслятор вводимых пользователем (на предложенном языке) логических выражений в дизъюнктивную нормальную форму (ДНФ).   При этом должны производиться исключение констант и минимизация элементарных конъюнкций. Обязательно должен проверяться синтаксис вводимых выражений.
Алгоритм приведения произвольного логического выражения к ДНФ можно найти в [1, с.62].

10. Транслятор формул ИППП в множество предложений
Разработать способ "машинного" представления (т.е. представления линейной последовательностью символов кодировки ASCII) языка исчисления предикатов первого порядка (ИППП) (см. [1, с. 228]). При этом правила построения атомарных формул заимствовать из языка Пролог [3, 4].
Разработать программу, осуществляющую преобразование вводимых пользователем (на предложенном языке) формул ИППП в множество предложений.
Примечание. Такое преобразование имеет много общего с преобразованием произвольных логических формул в конъюктивную нормальную форму.

Алгоритм преобразования состоит из следующих шагов [7].

  1. Исключение из исходной формулы символов импликации, для чего используется ~F|G вместо F->G (где F и G - любые формулы ИППП, ~ - знак отрицания, | - символ дизъюнкции, & - символ коньюнкции).
  2. Ограничение области действия отрицания только атомарными формулами, для чего используются правила деМоргана:
  3. ~F|~G вместо ~(F&G)
    ~F&~G вместо ~(F|G)
    При внесении отрицания в область действия квантора используются следующие правила:
    E-1x~F вместо ~A-1xF
    A-1x~F вместо ~E-1xF
  4. Разделение переменных - переименование их с тем, чтобы каждый квантор имел свою переменную.
  5. Исключение кванторов существования введением сколемовских констант и функций. Здесь формула вида

  6. E-1y(...P(y)...) заменяется формулой ...P(a)...
    А формула вида
    A-1x(E-1y(...P(x,y)...)) заменяется формулой Ax(...P(x,f(x))...)
    где A обозначает квантор всеобщности, E - квантор существования, a - сколемовская константа, f(x) - сколемовская функция.
  7. Вынесение кванторов всеобщности в начало формулы и их исключение из формулы.
  8. Приведение формулы ("очищенной" от кванторов) в конъюктивную нормальную форму. Используется (F|G)&(F|H) вместо F|(G&H).
  9. Исключение символа коньюнкции &, в результате образуется множество дизъюнктов, называемых также предложениями.
Описание языка ИППП и пример приведения формулы к виду предложений можно найти здесь.

11. Транслятор Бэйсик-СИ
Разработать транслятор текстов программ на языке мини-Бэйсик в программы на языке СИ.
Язык мини-Бэйсик представляет собой подмножество "классического" языка Бэйсик, предназначенное для работы только с числовыми данными. Описание синтаксиса подобного языка можно найти в [8].

12. [Сычева РК6-73] Транслятор Фортран-СИ
Разработать транслятор текстов программ на "ограниченном" языке Фортран в программы на языке СИ.
Ограниченная версия языка Фортран характеризуется следующими свойствами:
13. Дешифратор SNMP-сообщений
Разработать программу, осуществляющую перевод в символьное представление SNMP-сообщений.
SNMP (Simple Network Managment Protocol - простой протокол управления сетью) предназначен для управления сетевыми устройствами. Идеология протокола предполагает наличие в каждом сетевом устройстве (маршрутизаторе, коммутаторе, ЭВМ и др.) SNMP-агента, понимающего запросы к нему на языке протокола SNMP и умеющего (по крайней мере) отвечать на них.
Особенностью протокола SNMP является опора на стандарт ASN.1 (Abstract Syntax Notation 1), одобренный международной стандартизирующей организацией ISO. Стандарт ASN.1 позволяет избежать фиксированности формата сетевых сообщений, кодируя в теле сообщения синтаксис и семантику пересылаемых единиц информации.
Стандарт ASN.1 определяет ряд примитивных (INTEGER, OCTET STRING, OBJECT IDENTIFIER и др.) и составных (constructed) (SEQUENCE, SEQUENCE OF, SET, SET OF) типов данных, достаточных для представления разнообразной диагностической информации, характеризующей свойства и состояния сетевых устройств.
Со стандартом ASN.1 описания данных тесно связана спецификация BER (Basic Encoding Rules for Abstract Syntax Notation), определяющая правила трансляции символьного описания передаваемых данных в формат сетевого сообщения и обратно.
Сутью предлагаемого задания является создание программного продукта, обеспечивающего расшифровку тела SNMP-сообщения в символьный вид (в нотации ASN.1) на базе правил кодирования, задаваемых спецификацией BER.
Протокол SNMP, стандарт ASN.1 и спецификация BER неформально описаны в [5, 6].
Для облегчения понимания документов [5] ниже дается краткое описание элементов спецификации BER.
Каждая единица информации (поле) кодируется согласно BER следующей структурой:

<идентификатор-типа><длина-содержимого><содержимое>
Идентификатор типа содержимого задает тип данных (семантику) содержимого поля данных. Кодируется октетом (octet - 8 бит - байт), имеющим следующий формат (в описании биты нумеруются слева направо, начиная с 0): Примеры некоторых идентификаторов типов данных даны в следующей таблице.
 
Идентификатор Тип данных
Универсальные примитивные типы
02 INTEGER
03 BIT STRING
04 OCTET STRING
05 NULL
06 OBJECT IDENTIFIER
Универсальные составные типы
30 SEQUENCE
Примитивные типы для TCP/IP
40 IP-адрес
41 Counter (счетчик)
42 Gauge
43 TimeTicks (тики временной шкалы)
47 UInteger32 (бесзнаковое целое)
Составные типы, опр. контекстом
A0 GetRequest-PDU
A1 GetNextRequest-PDU
A2 GetResponse-PDU
...
 
Примеры кодирования
Пример кодирования INTEGER (универсальный (002) примитивный (02) тип данных с кодом 000102)
 
Число Идентификатор 
типа
Длина Содержимое
1110 0216 0116 0B16
50010 0216 0216 01F416
Пример кодирования IP-адреса (определяемый приложением(012) примитивный (02) тип данных с кодом 000002)
 
IP-адрес Идентификатор типа Длина Содержимое
212.45.0.15 4016 0416 D42D000F16
Идентификатор объекта (OBJECT IDENTIFIER) - единственный из примитивных типов данных, чье правило кодирования не столь очевидно.
Во-первых, первые два числа идентификатора объекта для краткости кодируются в одно шестнадцатиричное число по формуле 4010*n+m, где n - первое число, а m - второе.
Во-вторых, остальные числа идентификатора кодируются следующим образом: Например
 
Идентификатор объекта 
(OBJECT IDENTIFIER)
Закодированное представление
1.3.6.1.1.4.134.129 2B060101048106810116
Здесь первая пара чисел (1.3) закодирована одним октетом 2B16 (1*4010+3=4310=2B16).
Число 13410 представлено двумя октетами 8116 и 0616, число 12910 также представлено двумя октетами 8116 и 0116.

Кодирование типа данных NULL (пусто) осуществляется только одним октетом идентификатора типа с кодом 0516. Тем самым этот тип данных представляет собой единственное исключение из общего правила кодирования.

Пример дешифрации SNMP-сообщения типа get-request (запрашивается количество сетевых интерфейсов у устройства) приведен ниже

3026     SEQUENCE(38) = ...
  020100     INTEGER(1) = 0
  0405636973636F  OCT-STR(5) = "cisco"
  A01A     GetRequest-PDU(26) = ...
    02022219     INTEGER(2) = 8729
    020100     INTEGER(1) = 0
    020100     INTEGER(1) = 0
    300E     SEQUENCE(14) = ...
      300C     SEQUENCE(12) = ...
        06082D06010201020100  OBJ-ID(8) = 1.3.6.1.2.1.2.1.0
        0500     NULL

    Требования к программной реализации

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

    Литература

    1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. -М.:Энергоатомиздат, 1988. - 420 с.
    2. Армстронг Дж. Р. Моделирование цифровых устройств на языке VHDL. - М.:Мир, 1992. - 175 с.
    3. Клоксин У., Мелиш К. Программирование на языке Пролог. - М.: Мир, 1987. - 336 с.
    4. Братко И. Программирование на языке Пролог для искусственного интеллекта. - М.:Мир, 1990. - 560 с.
    5. Sidnie Feit. SNMP: a guide to network management. - McGraw-Hill., Inc 1995. - 674p.
    6. Семенов Ю.А. Протоколы и ресурсы Internet. - М.: Радио и связь, 1996. - 320 с.
    7. Нильсон Н. Принципы искусственного интеллекта. - М.: Мир, 1986. - 270 с.
    8. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. - М.: Мир, 1979.