Синтез распознавателей языков компьютерного моделирования объектов с конечным числом состояний тема диссертации и автореферата по ВАК РФ 05.13.16, кандидат технических наук Муромцев, Виктор Владимирович

• Муромцев, Виктор Владимирович
• кандидат технических наук
• 1999

Оглавление диссертации кандидат технических наук Муромцев, Виктор Владимирович

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

1. СОСТОЯНИЕ ВОПРОСА И ПОСТАНОВКА ЗАДАЧИ

1.1.Математическое моделирование как метод научных исследований

1.2 . Формальные языки систем моделирования

1.3.Формальные языки автоматических систем диагностирования

1. 4 .Проектирование распознавателей КС-языков

1.5.Задачи исследования

2. РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ РАСПОЗНАВАТЕЛЕЙ КС-ЯЗЫКОВ И МЕТОДА АВТОМАТИЧЕСКОГО СИНТЕЗА ДАННОЙ МОДЕЛИ

2.1.Задание КС-языков КС-диаграммерами

2.2.Введение понятия С-автомата. Задача синтеза О-автома-та

2.3.Введение правил преобразования диаграмм

2 .3.1 .Правила подстановки

2 .3 .2 .Правила устранения рекурсии

2 .3 .3 .Правила устранения неоднозначности

2. 4. Синтез 6-автоматов

2 .5 .Выводы

3.ПРОГРАММНЫЙ КОМПЛЕКС СИНТЕЗА РАСПОЗНАВАТЕЛЕЙ КС-ЯЗЫКОВ

3.1.Алгоритм преобразования БНФ в КС-грамматику

3.2.Алгоритм преобразования КС-грамматики в КС-диаграм-мер

3.3.Алгоритм удаления из КС-диаграммера непродуктивных и недостижимых КС-диаграмм

3.4.Алгоритм удаления из КС-диаграммера избыточных и однотипных КС-диаграмм

3.5.Алгоритм синтеза О-автомата

3.6.Алгоритм преобразования символического описания 6-авто-мата в структуру хранения 6-автомата в памяти ЭВМ

3.7. Выводы

4.ПРИМЕНЕНИЕ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОГО ИССЛЕДОВАНИЯ ПРИ МОДИФИКАЦИИ АВТОМАТИЧЕСКОЙ СИСТЕМЫ ДИАГНОСТИРОВАНИЯ ЦИФРОВЫХ СХЕМ

4.1.Языки контроля и диагностирования. Язык описания тестовых воздействий

4.2.Синтез распознавателя языка описания тестовых воздействий по традиционной методике

4.3.Синтез распознавателя языка описания тестовых воздействий на основе G-автомата

4.4.Сравнение времени работы распознавателей КС-языков построенных по различным методикам

4 . 5.Выводы

5. ЗАКЛЮЧЕНИЕ

ЛИТЕРАТУРА

ПРИЛОЖЕНИЕ 1.1. ЯЗЫК ЗАДАНИЯ АЛГОРИТМОВ ФУНКЦИОНИРОВАНИЯ

СЛУ

ПРИЛОЖЕНИЕ 1.2. ТРАНСЛЯЦИЯ ЯЗЫКОВ, ИСПОЛЬЗУЕМЫХ В ППП

"SIMOL-02" В ЯЗЫК VHDL

ПРИЛОЖЕНИЕ 2.1. МОДИФИКАЦИИ АЛГОРИТМА СВЕРТКИ КС-ПУТИ

В КС-ДИАГРАММЕ

ПРИЛОЖЕНИЕ 2.2. ПРИМЕРЫ СИНТЕЗА G-ABTOMATOB ДЛЯ ДЕТЕРМИНИРОВАННЫХ КС-ЯЗЫКОВ РАЗЛИЧНЫХ КЛАССОВ..168 ПРИЛОЖЕНИЕ 2.3. ПРОЯВЛЕНИЕ АЛГОРИТМИЧЕСКОЙ НЕРАЗРЕШИМОСТИ ПРОБЛЕМЫ ОПРЕДЕЛЕНИЯ ДЕТЕРМИНИРОВАННОСТИ ЯЗЫКА ЗАДАННОГО КС-ГРАММАТИКОЙ В ПРОИЗВОЛЬНОЙ ФОРМЕ

ПРИЛОЖЕНИЕ 3.1. СИНТЕЗ G-АВТОМАТА ДОПУСКАЮЩЕГО ЯЗЫК БНФ.181 ПРИЛОЖЕНИЕ 3.2. СИНТЕЗ G-АВТОМАТА ДОПУСКАЮЩЕГО ЯЗЫК КС-

ГРАММАТИК

ПРИЛОЖЕНИЕ 3.3. СИНТЕЗ G-АВТОМАТА ДОПУСКАЮЩЕГО ЯЗЫК

ДИАГРАММЕРОВ

ПРИЛОЖЕНИЕ 4.1. ТЕКСТ ПРОГРАММЫ НА ЯЗЫКЕ Turbo Pascal 6

РЕАЛИЗУЮЩЕЙ LL(1)-РАСПОЗНАВАТЕЛЬ ЯЗЫКА ОПИСАНИЯ ТЕСТОВЫХ ВОЗДЕЙСТВИЙ МЕТОДОМ РЕКУРСИВНОГО СПУСКА

ПРИЛОЖЕНИЕ 4.2. ТЕКСТ ПРОГРАММЫ НА ЯЗЫКЕ Turbo Pascal 6

РЕАЛИЗУЮЩЕЙ РАСПОЗНАВАТЕЛЬ ЯЗЫКА ОПИСАНИЯ ТЕСТОВЫХ ВОЗДЕЙСТВИЙ ПОСТРОЕННЫЙ НА ОСНОВЕ

МОДЕЛИРОВАНИЯ С-АВТОМАТА

ПРИЛОЖЕНИЕ 4.3. О-АВТОМАТ, ¡ДОПУСКАЮЩИЙ ЯЗЫК ОПИСАНИЯ

СТРУКТУРНЫХ МОДЕЛЕЙ ЦИФРОВЫХ СХЕМ

ПРИЛОЖЕНИЕ 4.4. ИСПОЛЬЗОВАНИЕ ЯЗЫКА ОПИСАНИЯ ТЕСТОВЫХ

ВОЗДЕЙСТВИЙ ПРИ ПОИСКЕ ТЕСТОВ ПУТЕМ

МОДЕЛИРОВАНИЯ НЕИСПРАВНОСТЕЙ

УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ

УКАЗАТЕЛЬ СОКРАЩЕНИЙ И ОПРЕДЕЛЕНИЙ

УКАЗАТЕЛЬ УТВЕРЖДЕНИЙ И ТЕОРЕМ

-5-

Введение диссертации (часть автореферата) на тему «Синтез распознавателей языков компьютерного моделирования объектов с конечным числом состояний»

ВВЕДЕНИЕ

Среди исследований в области информатики важное место занимают задачи интерпретации структур данных. Часто в качестве структур данных, используемых в системах моделирования, выступают цепочки символов, сформированные по определенным правилам. Все такие цепочки составляют формальный язык. Обычно в системах моделирования используются проблемно-ориентированные языки моделирования относящиеся к классу контекстно-свободных (КС).

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

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

С практической точки зрения интерес представляют детерминированные распознаватели. Детерминированные распознаватели могут быть построены не для всех КС-языков, а только для детерминированных КС-языков.

Вопросам разработки распознавателей посвящено большое число как отечественных, так и зарубежных работ. Известны работы А.Ахо и Дж.Ульмана [1,22], Р.Хантера [2], В.М.Глушкова [4], В.К.Водопьянова [81,82] и других авторов. Вместе с тем современные процедуры синтеза распознавателей представляются недостаточно совершенными, так как требуют от разработчиков высокой квалификации и больших временных затрат. Эти обстоятельства затрудняют создание новых языков, которые бы обладали более широкими возможностями при моделировании различных процессов и устройств.

-б- ■

Целью работы является совершенствование процедуры автоматизированного синтеза распознавателей КС-языков и её использование в задачах компьютерного моделирования объектов с конечным числом состояний.

Математической моделью распознавателей КС-языков является автомат с магазинной памятью (МП-автомат) . Математической моделью задания КС-языков является КС-грамматика. В настоящее время хорошо, изучены специальные формы КС-грамматик, порождающих как детерминированные КС-языки, так и языки, составляющие различные подклассы детерминированных КС-языков. Имея исходную грамматику в одной из таких форм, легко получить детерминированный распознаватель. Однако исходные грамматики, как правило, записаны в произвольной форме.

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

Краткое содержание работы по главам

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

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

Во второй главе рассматриваются математические модели задания и распознавания КС-языков. В качестве математической Модели задания КС-языков предложено использовать графовое представление КС-грамматики - совокупность КС-диаграмм (КС-диаграммер). В качестве математической модели распознавателей КС-языков разработана новая математическая модель - С-автомат. 6-автомат является одной из разновидностью классический МП-автомата. Для задания КС-диаграммеров и 6-автоматов определен язык диаграммеров. Разработаны правила преобразования диаграмм и методика синтеза 6-автоматов. Процесс синтеза 6-автоматов рассматривается как вывод в формальной системе, множество разрешимых слов которой составляет язык диаграммеров. Правилами вывода являются правила преобразования диаграмм. Показано, что методика синтеза 6-автоматов и распознавателей КС-языков, основанных на их моделировании, не приводит к возникновению тупиковых ситуаций.

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

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

В приложениях приведены примеры реальных языков, используемых в системах моделирования, рассмотрены примеры синтеза

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

В начале каждой главы приводится более подробное содержание материала рассматриваемого в данной главе.

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

Научная новизна:

1.Разработана математическая модель распознавателей КС-языков - С-автомат.

2.Предложен язык диаграммеров, позволяющий описывать КС-диаграммеры, являющиеся графовым представлением КС-грамматик, и С-автоматы.

3.Разработаны правила преобразования диаграмм.

4.Задача синтеза С-автоматов рассматривается как задача вывода в формальной системе, множество разрешимых слов которой составляет язык диаграммеров, а правилами вывода являются правила преобразования диаграмм, что позволило строго сформулировать алгоритм синтеза 6-автоматов.

5.Разработана процедура автоматизированного синтеза 6-автоматов и распознавателей КС-языков, основанных на их моделировании и показано, что эта процедура не приводит к возникновению тупиковых ситуаций.

Практическая ценность работы:

1.Разработана методика, позволяющая строить распознаватели КС-языков на основе С-автоматов.

2.Разработаны алгоритмы, реализующие этапы автоматизированного синтеза распознавателей КС-языков, основанных на моделировании соответствующих в-автоматов.

3.Разработан и программно реализован алгоритм моделирования однозначного С-автомата, позволяющий получать детерминированные распознаватели КС-языков с высоким быстродействием.

4.Созданы трансляторы языков моделирования цифровых ройств. Языки моделирования, используемые в АСД "И^Я?* 1012С.01", транслируются в современный язык моделирования цйф-^ ровых устройств VHDL. Также созданы распознаватели и трансля-_ торы проблемно-ориентированных языков включаемых в лингвисЫ-"

- , s.,

ческое обеспечение АСД "ИЗОТ 1012С.01" во время её моди-ф-iijfca-■ ции.

Реализация и внедрение работы. Основные результаты работы '^используются :

- при модификации АСД "ИЗОТ 1012С.01" (отчет о I- Р "Исследование и разработка методов моделирования и автомат зь-рованного проектирования дискретных систем управления на - чзе программируемых средств", номер гос.per. 018800138 62, г. Бь -город, БТИСМ),

- при обнаружении ошибок в'описании тестовых сигналов сетей телефонной связи,

- при выполнении проекта №96-01-00934 РФФИ,

- в учебном процессе на кафедре Программного обеспечения:.:' вычислительной техники и автоматизированных систем (ПО ВТАС); Белгородской государственной технологической академии строительных материалов (БелГТАСМ) в дисциплинах "Дискретная математика" и "Теория вычислительных процессов и структур", а также при проведении курсового и дипломного проектирования.

Основные положения, выносимые на защиту;

1.Процедура автоматизированного синтеза распознавателей КС-языков. J

а)математическая модель распознавателей КС-языков - G-автомат.

б)правила преобразования математической модели задания КС-языков (КС-диаграммера) в G-автомат.

в)алгоритм моделирования G-автомата, позволяющий получить распознаватель некоторого КС-языка на основе G-автомата, допускающего данный язык.

г)процедура автоматического синтеза G-автоматов.

X г

2.Алгоритмы и программ^ компьютерной реализации про автоматизированного синтеза распознавателей КС-языков.

а)концепция программной системы автоматизированного с^те

С'

за распознавателей КС-языков основанных на моделирований]-автоматов.

г?

б)алгоритмы программной системы автоматизированного срй|те1 за распознавателей КС-языков. ' |

3.Применение разработанной процедуры синтеза распознавате-? лей КС-языков при решении задач моделирования. 2

Апробация работы. Основные результаты, полученные в диссертационной работе, докладывались на конференциях:

1) "Математическое моделирование и информационные технологии" (Белгород, 1997);

2) "Микроэлектроника и информатика - '98" (Зеленоград, 1998);'

3) "Теория и техника передачи, приема и обработки информации" (Харьков-Туапсе,. . 1996) ;

4) "Ресурсо- и энергосберегающие технологии строительных материалов изделий и конструкций" (Белгород, 1995).

Связь с научно-техническими программами. Диссертационные исследования проводились в рамках проекта №96-01-00934 РФФИ, а также хоздоговорной тематики.

Публикация работы. По теме диссертации опубликовано 8 работ [83-90].

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав, заключения, списка используемой литературы (90 наименований), изложенных на 13 6 страницах машинописного текста и приложения на 58 страницах. В работе содержится 48 рисунков и 18 таблиц.

-111. СОСТОЯНИЕ ВОПРОСА И ПОСТАНОВКА ЗАДАЧИ

В данной главе показано, что одним из путей повышения эффективности использования вычислительной техники в научных исследованиях является включение в лингвистическое обеспечение систем моделирования и АСД проблемно-ориентированных языков. Отмечено, что данные языки, как правило, относятся к классу КС-языков. Рассмотрена задача распознавания КС-языков и перечислены проблемы автоматизации её решения. Сформулированы задачи исследования.

В разд.1.1 показано, что моделирование является одним из основных инструментов научных исследований. Отмечено, что при моделировании широко используется вычислительная техника и повышение эффективности её использования может быть достигнуто путем создания удобных программных систем.

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

Основное внимание уделено логическому моделированию цифровых

/

схем.

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

В разд.1.4 отмечено, что реальные проблемно-ориентированные языки, используемые в системах моделирования и АСД, относятся к классу КС-языков. Математической моделью распознавателей КС-языков является МП-автомат. Автоматический синтез детерминированного МП-автомата возможен только в том случае, если исходная КС-грамматика задана в определенной форме. Если это условие не выполнено, то часто автоматический синтез не возможен из за алгоритмической неразрешимости проблемы преобразования грамматики в требуемую форму. Это влечет

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

1.1. Математическое моделирование как метод научных исследований

Моделирование - это исследование объектов познания на их моделях [6] . В зависимости от характера моделей выделяют ряд видов моделирования [64]: предметное моделирование, физическое моделирование, предметно-математическое моделирование, знаковое моделирование.

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

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

Вычислительный эксперимент не только не отвергает традиционные математические методы, но и, напротив, предполагает их самое активное использование. Кроме того, вычислительные машины оказывают влияние на саму математику. Так некоторые математики полагают, что с помощью ЭВМ можно строить математические

доказательства в тех случаях, когда требуется исследовать большие, но конечные множества объектов. Примером может служить доказательство гипотезы четырех красок, полученное в 1976 году коллективом математиков и программистов, под руководством К.Аппеля и В.Хейкена [18].

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

Обобщенная схема вычислительного эксперимента приведена на рис.1.1 [бб] . Из схемы видно, что вычислительный эксперимент использует данные натурного эксперимента. Если натурный эксперимент предполагает подачу на объект большого числа тестов, то его проведение не мыслимо без использования АСД в состав которых, как правило, также входят ЭВМ.

Рис.1.1. Схема вычислительного эксперимента

Для составления качественной модели и проведения вычислительного эксперимента необходимы усилия многих специалистов: математиков теоретиков и математиков статистиков, специалистов по построению моделей и алгоритмов, программистов, инженеров-испытателей и т.д. Успех зависит от согласованного взаимодействия всех участников вычислительного эксперимента. Организация такого взаимодействия требует определенных временных и материальных затрат [63,72].

Для сокращения затрат можно ряд работ по программированию передать специалистам в других областях. В связи с этим существует острая проблема создания удобных и простых в обращении программных систем, которые дали бы возможность конечным пользователям решать свои задачи.' Особенно актуальной эта проблема становится в связи с распространением персональных ЭВМ [67-70].

При создании таких программных систем особое внимание следует уделять лингвистическому обеспечению, то есть языкам, на которых осуществляется общение пользователя с ЭВМ. Языкам, используемым в системах моделирования и автоматического диагностирования, посвящены разд.1.2 и 1.3 соответственно. В разд.1.4 указаны проблемы, возникающие при создании лингвистического обеспечения, и сформулированы задачи исследования.

1.2. Формальные языки систем моделирования

Как было отмечено в разд.1.1, при моделировании широко применяются ЭВМ. Для задания математических моделей с последующей их реализацией на ЭВМ требуется ввести некоторый формальный язык, с помощью которого можно представить описание реального объекта в терминах, понятных вычислительной машине.

Для различных задач моделирования используются те или иные языки. Это могут быть как обычные алгоритмические языки, так и языки моделирования. Языки моделирования подразделяются на универсальные и проблемно-ориентированные. Использование проблемно-ориентированных языков в данной предметной области более предпочтительно [76].

На Пражской конференции по компьютерной симуляции и моделированию 1995 года был представлен широкий ряд систем моделирования использующих проблемно-ориентированные языки. Приведем два из них.

Графический язык ТКЗЪ/'Ш-Пс1оу73 [58] . Этот язык предназначен для высокоточного численного решения дифференциальных уравнений-. В качестве конструкций языка используются аналоговые диаграммы, широко известные в теории аналоговых и гибридных компьютеров. Среди них - интеграторы, инверторы, суммато-

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

УЦ - язык управления базами данных для моделирования событий города [59] . Этот язык был разработан в лаборатории кафедры инженерии окружающей среды университета города Осака в Японии с целью иметь хорошо развитое средство для описания и оперирования с архитектурными и городскими объектами. На протяжении с 1983 года, когда была разработана его первая версия, он широко использовался для моделирования процессов в разных городах, а кроме того, для моделирования нескольких исторических, в наше время не существующих памятников древних цивилизаций.

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

Рассмотрим задачу описания математической модели.

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

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

Математическая модель, отражающая только структурные свойства объекта (геометрическую форму, размеры, связи между элементами и т.д.), называется структурной [7].

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

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

Для задания функциональных моделей используют языки функционального описания. Обычно функциональное описание осуществляют независимо от структурного и модели элементов выносят в отдельную библиотеку [8]. Однако некоторые языки имеют средства организации как структурного так функционального описания .

Типичным примером языков структурного и функционального описания являются языки М-Багмл-П и М-Яед^э соответственно, также представленные на пражской конференции [60] . Эти языки предназначены для моделирования параллельных дискретных событий и были созданы для эффективной разработки программного обеспечения, моделирующего большие распределенные многопроцессорные системы.

М-Кед±з используется для описания отдельного компонента самой нижней части иерархии - "черного ящика", а М-Багм±п из этих "черных ящиков" собирает иерархическую систему.

Структура системы в М-Багм1п'е представляет собой иерархическое дерево связанных компонент, каждая из которых также может являться деревом и т.д. Синтаксис этого языка похож на синтаксис алгоритмических языков высокого уровня с тем различием, что все конструкции ветвления, циклов и т.д. здесь используются не для изменения порядка выполнения инструкций, а для описания дерева. Язык построен по принципу, согласно кото-

рому каждый элемент структурно не зависит от окружающих его элементов, и взаимодействует с ними путем посылки сообщений.

В приложении 1.1 рассматривается проблемно-ориентированный язык, предложенный в [10] для описания алгоритмов функционирования систем логического управления (СЛУ). Данный язык также может использоваться для описания функциональных моделей на автоматном уровне.

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

Получение функциональных моделей элементов в общем случае - неформальная процедура. Методы получения функциональных моделей делят на теоретические и экспериментальные. Теоретические методы основаны на изучении физических закономерностей протекающих в элементе, определении соответствующего этим закономерностям математического описания, обосновании и принятии упрощающих предположений, выполнении необходимых выкладок и приведении результата к принятой форме представления модели. Экспериментальные методы основаны на использовании внешних проявлений свойств элементов фиксируемых при проведении целенаправленных экспериментов или при эксплуатации однотипных элементов [7,63].

Наличие в методике получения функциональных моделей эвристических и формальных операций делает целесообразной разработку моделей элементов в диалоговом режиме работы с ЭВМ [62]. Обычно такой диалог классифицируется как диалог, управляемый пользователем. При таком диалоге инициатива принадлежит пользователю, то есть он непосредственно подает команду на выполнение нужного на данном этапе задания [9] . Таким образом, при получении функциональных моделей с использованием ЭВМ для организации человеко-машинного интерфейса часто применяются командные языки.

Рассмотрим более подробно задачу логического моделирования цифровых схем. Логическое моделирование представляет собой

процедуру реализации работы цифровой схемы с помощью ЭВМ. Логическое моделирование используется:

1) Для проверки правильности или верификации проектируемой схемы без её физическои реализации.

2) В качестве средства анализа неисправностей. Для этого в моделируемую схему вводят предполагаемую неисправность и анализируют влияние неисправности путем моделирования.

3) Вместо аппаратуры как инструмент разработки программного обеспечения устройства, связанного вместе с этой аппаратурой .

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

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

1) наличие иерархической модульной структуры (аналогично процедурам и функциям в алгоритмических языках);

2) возможность присваивать каждому сигналу уникальное имя, которое является глобальной или локальной переменной по отношению к модулю;

3) наличие формальных параметров (имен сигналов) в определениях модулей (аналогично формальным параметрам в программных процедурах и функциях);

4) наличие средств ведения библиотек моделей элементов (обычно для моделей определенного типа ведется отдельная библиотека) .

Моделирование является неотъемлемой частью систем автоматического проектирования цифровых схем и сверх больших интегральных схем [30]. В данных системах используются языки к ко-

торым выдвигаются требования аналогичные перечисленным [8,29,31,32,77-80].

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

Итак, системы моделирования используют языки для описания объекта моделирования, языки организации диалога с ЭВМ и языки описания входных воздействий. Как правило, эти языки являются проблемно-ориентированными. Перевод с проблемно-

ориентированного языка на машинный язык - трудоемкая задача, которая требует существенных временных затрат. Поэтому при проектировании системы моделирования возникает задача разработки автоматических трансляторов и распознавателей проблемно-ориентированных языков.

1.3. Формальные языки автоматических систем диагностирования

Одной из актуальных проблем науки является создание эффективных методов диагностики и контроля сложных систем. Вопросы диагностики широко освещены в литературе. Фундаментальные основы теории тестов впервые были развиты в работе [47]. Вопросам диагностики сложных систем посвящена работа [48] . Важным направлением является развитие теории тестов как теории вопросников [46,45].

Усложнение объектов диагностирования и повышение требований к их надежности приводит к усложнению алгоритмов диагностирования и невозможности их реализации ручными методами. Эта проблема решается путем применением АСД. Современные АСД, как правило, работают под управлением ЭВМ, программное обеспечение которых позволяет автоматически получать тесты на моделях объ-

ектов диагностирования. Таким образом АСД включают в себя подсистемы моделирования.

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

Лингвистическое обеспечение АСД должно удовлетворять следующим требованиям [71] :

1) ясность и доступность языковых средств,

2) простота и эффективность реализации языковых средств на различных вычислительных установках,

3) гибкость настройки языковых средств при изменениях в составе АСД и изменениях вида объекта контроля,

4) минимальная трудоемкость создания новых языковых Средств при изменении класса задач контроля.

Одним из путей создания лингвистического обеспечения удовлетворяющего перечисленным требованиям является разработка узкоспециализированных языков и трансляторов данных языков в базовый язык АСД. При этом лингвистическое обеспечение имеет трехуровневую иерархическую структуру, представленную на рис.1.2 [71]. Такой подход может использоваться и при создании лингвистического обеспечения систем моделирования.

Рассмотрим АСД предназначенные для тестирования цифровых схем. Вопросы технической диагностики цифровых схем широко освещены в литературе [49-56,8,42]. В этих работах изложены основы диагностики, методы построения и анализа математических моделей диагностирования и методы построения алгоритмов диагностирования .

Множество задач, решаемых в АСД цифровых схем, содержит задачи, решаемые в системах логического моделирования. Для решения данных задач в АСД используются языки структурного и функционального описания; языки описания тестовых воздействий,

схемных ошибок, параметров тестера, процесса диагностирования и т.д.

Итак, при проектировании новой или модернизации существующей АСД возникает задача разработки лингвистического обеспечения. Если лингвистическое обеспечение имеет трехуровневую иерархическую структуру (рис.1.2), то его разработка сводится к выбору базового языка и созданию проблемно-ориентированных языков, набор которых в дальнейшем может расширяться. При этом общей задачей является не задача разработки конкретных проблемно-ориентированных языков, а задача создания средств, позволяющих облегчить получение распознавателей данных языков и трансляторов этих языков в базовый язык АСД.

Специализированные языки для решения задач класса 1

Язык l.Mi

Язык 1.2

Язык 1.1

Специализированные языки для решения задач класса 2

Язык 2.М2

Язык 2.2

| Язык 2. 1

Специализированные языки для решения задач класса N

Язык N .Мм

Язык N. 2

Заключение диссертации по теме «Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (по отраслям наук)», Муромцев, Виктор Владимирович

4.5. Выводы

На примере языка описания тестовых воздействий, использующегося в реальной АСД, показано,- при построен; ш ЬЬ(1)-распознавателя этого языка традиционными методами возит необходимость ручных преобразований исходной грамма гтхки, и что при построении аналогичного распознавателя на основе автомата ручные преобразования не требуются. Таким образом, при разработке лингвистического обеспечения данной АСД использование процедуры автоматизированного синтеза распознавателей КС-языков, предложенной в этой работе, сокращается число ошбок и время проектирования. При этом распознаватель, построенный на основе моделирования С-автомата, не заступает в быстродействии ЬЬ(1)-распознавателю, который в свою очередь является самым быстродействующим из детерминированных распознавателей КС-языков,

Список литературы диссертационного исследования кандидат технических наук Муромцев, Виктор Владимирович, 1999 год

Список связей между МС Б СЬТБ tз

Описание связи Е ^ 4

Наименование сигнала Е *1 ^ 5

Источник сигнала С *0 t6

Приемник сигнала Н

КС-грамматика в не является ЪЬ(1)-грамматикой, так как множества направляющих символов для правил в—И:5п | t5n@ совпадают. Заменив в КС-грамматике 6 правила

12)6-И:5п|1:5П@|1

на правила

(З-^пК.|I В.->@|8

получим эквивалентную ЪЪ(1)-грамматику.

Язык Ъ(Б) допустим С-автоматом А, представленным на рис.П4.1. Синтез С-автомата А осуществлен по методике предложенной в данной работе. Автомат А является детерминированным С-автоматом. Однозначный С-автомат Ах эквивалентный автомату А представлен на рис.П4.2. Отметим, что автомат А выродился в НКА, а автомат Ах - в ДКА.

На основе однозначного С-автомата Ах легко построить детерминированный распознаватель языка описания структурных моделей цифровых схем (см. прил.4.2, гл.4.3).

1 ; 1 -Ю—

в_ Е $, =$

1 I; П @ \ е Г, ^ п \и2 * I

О—О—Ю—►О—О—О—Ю—-Ю—►о——

•гут .ч^т, I

(У—о

о-^о

Рис.П4.1. Детерминированный в-автомат, допускающий язык описания структурных моделей цифровых схем

^ 1 а)-О

-г '

п \ @

ю—-ю—-с^—о

у — 1

о—ю—

Рис.П4.2. Однозначный С-автомат, допускающий язык описания структурных моделей цифровых схем

приложение 4.4 использование языка описания тестовых воздействий при поиске тестов путем моделирования неисправностей

В гл. 1.3 рассматривалась АСД "ИЗОТ 1012С.01" и задача её модификации. В качестве управляющей ЭВМ данной АСД используется морально устаревший мини-компьютер MCIб, в состав программного обеспечения которого входит ППП "SIMOL-02".

В ППП "SIMOL-02" для описания тестов используется специализированный язык TDL. Основными операторами данного языка являются следующие операторы:

/п - номер шага тестирования, где п - целое число;

IH - высокий входной уровень;

IL - низкий входной уровень;

ОН - высокий выходной уровень;

OL - низкий выходной уровень.

Использовать эти операторы для описания последовательностей входных наборов иногда бывает неудобно. Например, если изменение некоторого разряда в последовательности входных наборов носит периодичный характер, то для его описания целесообразней применять соответствующий оператор. Также при описании больших последовательностей входных воздействий иногда удобно использовать операторы копирования, масштабирования и т.д. Данные операторы имеются в языке описания тестовых воздействий LTEst (см. гл.4.1). Язык LTEST входит в состав модифицированного лингвистического обеспечения АСД "ИЗОТ 1012С.01".

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

Моделирование неисправностей заключается в следующем. Проводится логическое моделирование исправной и неисправной схемы для некоторого входного набора. Если выходные значения исправной и неисправной схемы различаются, то входной набор считается тестовым набором для данной неисправности, в противном слу-

чае изменяется входной набор и продолжается процесс моделирования .

Рассмотрим цифровую схему представленную на рис.П4.3. Пусть требуется найти тест для неисправности "постоянная единица на связи f" (обозначение "f/1"). Для решения такой задачи будем подавать на вход схемы все возможные наборы, и проводить моделирование исправной и неисправной схемы. Процесс завершим либо когда результаты моделирования будут различными (найден тест), либо когда будут проанализированы все входные наборы (заданная неисправность является не обнаруживаемой).

Последовательность входных наборов и результаты моделирования представлены на рис.П4.4. Набор а=0, b=0, с=1, d=0 является тестом для неисправности f/1.

При описании входной последовательности на языке TDL необходимо явно задать каждый входной набор. Таким образом, основная часть описания будет содержать 24 операторов IH или IL, в зависимости от того, какой входной уровень 0 или 1 подразумевается по умолчанию. Оба варианта основной части описания входной последовательности на языке TDL представлены на рис.П4.5. В языке LTESt для описания периодических сигналов предусмотрены специальные операторы, что существенно сокращает объем текста (рис.П4.б).

Рис.П4.3. Цифровая схема

№ а ь с с1

1 0 0 0 0

2 1 0 0 0

3 0 1 0 0

4 1 1 0 0

5 ; 0 0 ; шёж тйж

1

ВХОДНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ

I 2 3 4

а

8

ТЕСТ ДЛЯ НЕИСПРАВНОСТИ Г/1

7

РЕЗУЛЬТАТ МОДЕЛИРОВАНИЯ

ш ИСПРАВНАЯ СХЕМА НЕИСПРАВНОСТЬ £/1

е £ ь д 1 3 к е £ Ь д ± j к

1 1 1 6 6 0 6 6 1 1 6 6 6 0 0

2 1 1 0 0 1 0 1 1 1 0 0 1 0 1

3 1 1 0 0 0 0 0 1 1 0 0 0 0 0

4 1 1 0 0 1 0 1 1 1 0 0 1 0 1

5 0 0 1 1 0 1 ар 0 1 1 0 0 0 ■ —¡ — -

РАЗЛИЧНАЯ ВЬ ш ш 'Щф

Рис.П4.4. Последовательность входных наборов и результаты моделирования исправной и неисправной схемы представленной на рис.П4.3

ЯЗЫК TDL

1 ВАРИАНТ 2 ВАРИАНТ

/1 /1

/2 IL 1-4

IH 1 /2

/3 IL 2-4

IH 2 /3

/4 IL 1,3,4

IH 1,2 /4

/5 IL 3,4

IH 3 /5 IL 1,2,4

Рис.П4.5.Описание входных воздействий на языке TDL

ЯЗЫК Ltest

1 ВАРИАНТ 2 ВАРИАНТ

MEANDR PERIOD

Ml:1,1,1 ; Pi:LO*l+HI*l;

М2:2,2 ,2 ; P2:L0*2+HI*2;

МЗ :4,4,4; P3:LO*4+HI*4;

М4:8,8 , 8 P4:L0*8+HI*8

Е MEANDR E PERIOD

BEGIN TEST BEGIN TEST

1=М1;2=М2; 1=P1:1-16;2=P2:1-16;

3=M3;4=M4; 3=P3:1-16;4=P4:1-16

END TEST END TEST

Рис.П4.б.Описание входных воздействий на языке LTEST

-214-

УКАЗАТЕЛЬ ОБОЗНАЧЕНИЙ

ОБОЗНАЧЕНИЕ стр.

(N,T,D,S), N, Т, D 25,36

(K,R,M,P,W,AH,AK) J, А, р + , р~, (pvs)-, {#>}-, К, =$ 40 40, 41

Р* г ip)r Р + 41,46,56

К h-% (Р) $, А, N 42, 43 41, 42

(Р, Р; Р), (Рг Р; Рг Р) 36 36, 40

Ер, vp U, + , - 36 51 108

(p^-p) p: = p->p, p: = p-^&p 37 50

51,53

В ( fp) Ъ(р) M (p) First (p), p (p->p), pm(p,p) 41 43 51 49,55,55

Ld LTEST Gtest/- Gtest' 46 125 128,130

D<=St, St<=p, [p] 101

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

В таблице символ " р" обозначает любую букву.

-215-

указатель сокращений и определений

АСД п 1

БК 125

БНФ 24

ДКА 27

КС 5

МС 159

МП-автомат 6

НКА 27

ОКиД 125

ПК 98

ППП 21

СЛУ 17

ТП 125

G-автомат....................................40

— недетерминированный........................44

— детерминированный..........................44

— однозначный................................44

G-диаграмма..................................48

— без рекурсии...............................48

G-диаграммер.................................48

Дерево процесса разбора......................44

Граф G-автомата..............................45

Задача синтеза G-автомата....................47

Конфигурация G-автомата......................42

— — начальная................................42

— — заключительная...........................42

— — тупиковая................................42

КС-диаграмма.................................35

— избыточная.................................107

— недостижимая...............................105

— непродуктивная.............................104

— однотипная.................................107

КС-диаграммер................................3 6

Правила подстановки..........................49

— устранения рекурсии........................63

— свертки....................................74

— устранения неоднозначности.................8 0

Неоднозначность работы G-автомата............43

— — с магазином..............................44

— перемещения считывающей головки............44

Приоритет правила подстановки................61

Свертка КС-диаграммы.........................70

— пути в КС-диаграмме........................70

Свободный магазинный символ..................51

Спонтанный (безусловный, пустой) переход.....41

Структурный граф.............................2 6

Эквивалентность грамматик, диаграммеров,

автоматов и диаграмм.........................48

Язык диаграммеров............................4 6

-216-

указатель утверждений и теорем

Номер Синоним утверждения стр. Номер Синоним утверждения стр.

учгвержде (соответствующее утвержде (соответствующее

ния правило вывода) ния правило вывода)

2.1 - -- 45 2 .13 --- 68

2.2 Правило Р0 50 2.14 Правило N5 77

2.3 - — 56 2 .15 Правило N6 78

2.4 - — 57 2.16 Правило N7 78

2.5 Правило N1 58 2.17 Правило N8 78

2 . б Правило Р2 59 2 .18 Правило N9 79

2.7 Правило Ы0 63 2 .19 Правило Б1 80

2.8 Правило Я1 63 2 .20 Правило Б2 81

2.9 Правило Я2 64 2 .21 Правило БЗ 81

2.10 Правило N2 64 2.22 Правило Б4 81

2.11 Правило N3 бб 2 .23 Правило Б5 82

2.12 Правило N4 бб

Номер теоремы Синоним теоремы (соответствующее правило вывода) стр. Номер теоремы Синоним теоремы (соответствующее правило вывода) стр.

2.1 Правило Р1 59 2.2 Правило РЗ 60 2.3 Правило Б4 85 2.4 Правило N10 8 5 2.5 Правило N11 8 6 2.6 Правило N12 8 7

Правило стр. Правило стр. Правило стр. Правило стр. Правило стр.

D1 80 N3 66 N10 85 R0 63 S5 74

D2 81 N4 66 N11 86 R1 63 S6 74

D3 81 N5 77 N12 87 R2 64 S7 74

D4 81, 85 N6 78 Р0 50 S1 74 S8 74

D5 82 N7 78 Р1 59 S2 74

N1 58 N8 78 Р2 59 S3 74

N2 64 N9 •79 РЗ 60 S4 74