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



/СУ " <£? ф

БЕЛГОРОДСКАЯ ГОСУДАРСТВЕННАЯ ТЕХНОЛОГИЧЕСКАЯ АКАДЕМИЯ у СТРОИТЕЛЬНЫХ МАТЕРИАЛОВ

На правах рукописи

МУРОМЦЕВ ВИКТОР ВЛАДИМИРОВИЧ

СИНТЕЗ РАСПОЗНАВАТЕЛЕЙ ЯЗЫКОВ КОМПЬЮТЕРНОГО МОДЕЛИРОВАНИЯ ОБЪЕКТОВ С КОНЕЧНЫМ ЧИСЛОМ СОСТОЯНИЙ

Специальность 05.13.16 - Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях (технические науки, информатика и вычислительная техника)

г

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель:

доктор технических наук,

ВОДОПЬЯНОВ ВИТАЛИЙ КОНСТАНТИНОВИЧ

доктор технических наук, КОРСУНОВ НИКОЛАЙ ИВАНОВИЧ

Белгород - 1999

-2-

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ . . ..............................................5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 .5 .Выводы..............................................9 6

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

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

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

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

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

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

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

3.7. Выводы..............................................122

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

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

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

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

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

4 . 5.Выводы..............................................144

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

ЛИТЕРАТУРА..............................................148

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

СЛУ.....................................156

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

"SIMOL-02" В ЯЗЫК VHDL..................159

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

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

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

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

ГРАММАТИК...............................18 6

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

-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 отмечено, что реальные проблемно-ориентированн