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

РГ6 од

О 3

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

ЛЕКАРЕВ Михаил Фёдорович

Организация программного обеспечения и вычислительных процессов ЭВМ на базе визуального формализма

Спец "атность 05.13.13: Вычислительные машины, комплексы, системы и сети

Специальность 05.13.11: Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат диссертации на соискание учёной степени

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

Санкт-Петербург - 1998

Работа выполнена в Санкт-Петербургском государственном техническом университете.

Официальные

оппоненты: Александров А.М., Игнатьев М.Б., Новиков Г.И.

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

Ведущая организация:

Санкт-Петербургский институт информатики и автоматизации РАН

заседании диссертационного совета Д 063.38.04 Санкт-Петербургского государственного технического университета по адресу: 195251 г.Санкт-Петербург, Политехническая ул. 29, корпус 9, аудитория 325.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского государственного технического университета по адресу: 195251 г. Санкт-Петербург, Политехническая ул. 29.

Защита состоится

1998 г. в 1£

часов на

Автореферат разослан

1998 г.

Учёный секретарь диссертационного совета

Дурандин К.П.

Общая характеристика работы

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

Несмотря на интеЕгсивную работу в области совершенствования методологии разработки ПО, специалисты-практики констатируют наличие фундамент&чьного несоответствия между состоянием теории и запросами повседневной практики программирования: так называемого методологического разрыва. Ведущие специалисты считают основными причинами этого разрыва внутреннюю сложность ПО, его невидимость и необходимость приспособления к меняющимся в ходе разработки и эксплуатации требованиям и спецификациям.

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

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

Логической сложностью ПО называют его существенную сложность, которая обусловлена многовариантностью: количество вариантов работы программы, содержащей проверку N условий, может составить до 2К. Другой вид существенной сложности ПО -функциональная сложность; она возникает, если для решения задачи необходимо использовать специальный математический аппарат.

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

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

Концептуальной основой новых подходов остаётся иерархическая декомпозиция. Но форма её использования, как правило, далеко не очевидна. Более того, техника структурирования, которая подходит в одной ситуации, может оказаться непригодной в другой.

Важным успехом в области преодоления существенной сложности

ПО стало изобретение в конце 1950-х годов языков третьего поколения (Third Generation Languages, 3GL). Использование 3GL повышает производительность работы программиста не менее, чем в 5 раз.

Однако, система абстракций 3GL была приспособлена к отображению особенностей аппаратуры ЭВМ, которая считалась наиболее дорогостоящей частью вычислительного комплекса. Возникшее понимание того, что наибольшие затраты связаны с ПО, привело к обратной ситуации: сегодня схемотехники предлагают аппаратную поддержку всё новых особенностей ПО. Но абстракции 3GL, отражающие особенности исчезнувшей аппаратуры, остаются прежними.

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

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

Успешное использование визуальных и иконных сред проектирования ПО продемонстрировало конструктивность визуальных методов. Тем не менее, остаётся немало открытых проблем, в частности, разработка для программ и структур данных комплексного тексто-графического представления.

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

Таким образом, перспективными направлениями работ по решению проблемы преодоления методологического кризиса в области разработки ПО являются следующие, взаимосвязанные направления.

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

• Разработка новых методов взаимодействия человека с ЭВМ, ориентированных на проектировщика и обеспечивающих повышение эффективности преодоления сложности ПО.

Решение поставленной проблемы согласуется:

2

с планом работ по комплексной программе АН СССР,

Минэлектронпрома СССР и Минвуза РСФСР "Повышение эффективности примеиения средств вычислительной техники в научных исследованиях, производстве и в учебном процессе", проводимых по приказу Минвуза РСФСР №810 от 26.12.1985 г.;

- с планом работ по Федеральной инновационной программе "Российская инжиниринговая сеть технических нововведений" ("Инжинирингсеть России"), проводимых по постановлению Правительства Российской Федерации №396 от 13.07.1991, проект 1.1.3.03, 1991-1995 гг.;

- с приоритетными направлениями развития науки и техники, утверждёнными Правительственной комиссией Российской Федерации по научно-технической политике №2727п-П8 от 21.07.1996, направление "Фундаментальные исследования", раздел "Информационная, вычислительная техника, автоматизация";

- с планом работ Санкт-Петербургского государственного технического университета по грантам Госкомитета РФ по высшему образованию по фундаментальным исследованиям в области вычислительной техники, информатики, кибернетики "Графическая технология проектирования программных средств и архитектура ЭВМ, ориентированная на программное обеспечение" (1994-1995 гг.) и "Методология проектирования программных средств и организации вычислительных процессов на базе фафических моделей" (1996-1997 гг.).

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

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

Достижению этой цели должно способствовать решение следующих задач.

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

сложности решаемой задачи и существенно сокращают количество ошибок при разработке ПО.

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

3. Практическая проверка разработанных визуальных средств в ходе проектирования ПО с логическим характером сложности в различных операционных средах на ЭВМ различных архитектур.

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

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

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

3. Предложены новые средства визуализации операций управления данными, включённые в модель Ь-сети. Дано обоснование того, что эти средства способны обеспечить те же возможности, что и связь через аргументы-параметры в распространённых ЗвЬ.

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

для учёта контекстно-зависимых свойств. Доказано, что мощность модели L-сети эквивалентна мощности машины Тьюринга.

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

С использованием разработанной технологии выполнены сложные программные проекты (объёмом до 130.000 строк). Практика показала высокую эффективность использования формализма L-сети как на ЕС ЭВМ, так и на ПЭВМ IBM PC в сочетании с различными языками программирования, прежде всего - PL/1, С, С++.

Использование модели способствует сокращению сроков проектирования в 10-20 раз по сравнению со сроками на основе широко известной научной системы оценок Б.У.Боэма, низкому уровню ошибок, высокой степени портируемости ПО.

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

Таким образом, формализм L-сети оказывается проверенным на практике инструментом визуализации ПО, который основан на структурной декомпозиции и допускает простую интеграцию с другими методологиями, в частности, объектно-ориентированными.

Достоверность результатов. Обоснованность и достоверность результатов и выводов, полученных в диссертационной работе, подтверждается приведённым в работе теоретическим обоснованием модели L-сетгг; 20-летней практикой её использования в проектах ПО с высоким уровнем логической сложности (трансляторы формальных языков, САПР дискретных устройств) общим объёмом свыше 500.000 строк исходных текстов, причём объём отдельных проектов составил до 130.000 строк; а также результатами апробации на международных, всесоюзных, республиканских конференциях и за рубежом (ФРГ).

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

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

2. Доказательства теоретической мощности L-сети.

3. Реализация в форме компилируемого или интерпретируемого кода.

5

4. Методы использования модели L-сети при организации конфигурируемого ПО контроля синтаксиса языка SQL.

5. Архитектурные решения по организации конфигурируемых программных средств контроля синтаксиса языка SQL.

Внедрение результатов. Результаты проведённых исследований нашли применение в ряде проектов ПО, выполненных либо лично автором, либо под его руководством и при непосредственном участии. Наиболее значимыми из них являются следующие.

1. Конфигурируемые программные средства контроля синтаксиса языка SQL (СПб, фирма "Эквилибр", 1996-1997гт.).

2. Пакет прикладных программ автоматизированного синтеза цифровых устройств (Ассоциация Центров Инжиниринга и Автоматизации, 1993г.).

3. Язык JIM для описания дискретных устройств на совмещённом уровне логических схем и регистровых передач и система ИМ моделирования дискретных устройств (СПбГТУ, версия 2: 1990г.).

4. Учебный машинно-ориентированный язык (СПбГТУ, 1987г.).

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

Реализация работы выразилась также в использовании модели L-сети и спроектированных с её использованием программных средств в учебном процессе для студентов специальностей 210100 - Управление и информатика в технических системах и 220100 - Вычислительные машины, комплексы, системы и сети, в дисциплинах "Теория и технология программирования", 'Теоретическая информатика", "Проектирование СУ ГПС", "Проектирование ЭВМ", "Современная программотехника".

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

1. 3-я Всесоюзная конференция "Применение ЭВМ серии МИР в расчётах по радиотехнике и электронике" (Киев, 1975).

2. Всесоюзный семинар "Опыт эксплуатации и математическое обеспечение ЭВМ серии МИР" (Киев, 1977).

3. Всесоюзная конференция "Автоматизация проектных и конструкторских работ" (Москва, 1979).

4. Республиканский семинар 'Технология программирования" в Институте Кибернетики АН УССР (Киев, 1983).

5. Всесоюзная научно-техническая конференция "Программные средства как продукция производственно-технического назначения" (Калинин, 1985).

6. Научный семинар в Fachhochschule Hamburg (ФРГ, Гамбург, 1993).

7. Международная конференция 'Технологии и системы сбора, обработки и

представления информации" (Рязань, 1993).

8. 3-я Международная научно-методическая конференция "Высокие интеллектуальные технологии образования и науки" (СПб, 1995).

9. Российская научно-техническая конференция "Инновационные наукоёмкие технологии для России" (СПб, 1996).

Публикации. По материалам диссертации опубликованы 33 печатные работы, в том числе одна монография, 2 книги (в соавторстве), 3 учебных пособия (два из них - в соавторстве) и 1 статья в зарубежном научном журнале (ФРГ)-

Структура и объём работы. Диссертация состоит из введения, пяти глав, заключения, приложения и списка литературы из 211 наименований. Общий объём диссертации составляет 238 страниц машинописного текста, который включает 62 рисунка.

Краткое содержание работы

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

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

Одним из перспективных методов преодоления сложности ПО продолжает оставаться визуализация ПО. Рассмотрены классические визуальные формализмы: форматирование исходного текста, схемы алгоритмов, диаграммы Нэсси-Шнейдермана, расширенные сети переходов (Augmented Transition Networks), Р-технология программирования. Проанализированы ограничения, связанные с существующими формализмами.

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

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

Потребность в разработке модели L-сети была осознана в результате работы автора над сложными проектами ПО. Эти проекты, связанные с разработкой трансляторов и другого ПО с логическим

7

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

Приведён анализ наиболее близких к Ь-сети моделей: расширенной сети переходов В.А.Вудса и методов анализа естественных языков Т.Винограда.

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

Модель Ь-сети включает следующие элементы, каждый из которых предложен автором.

1. Визуальное представление управления последовательностью действий с помощью сети, составленной из множества графических примитивов, на котором введён частичный порядок. В результате появляется возможность введения понятия "шаг к следующему по порядку примитиву Ь-сети".

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

3. Система понятий, связанных с определением точки возобновления вычислений после завершения работы модуля с двумя выходами.

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

5. Предопределённый регистр Ь№1Уаг, который содержит один из операндов, участвующих в проверке обособленных условий. Введение этого регистра повышает уровень визуализации.

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

7. Предопределённый регистр ЬЫеКЖве!, который содержит целое значение, определяющее выбор ветви при мультиветвлении. Введение этого регистра повышает уровень визуализации.

8. Система понятий, определяющих управление данными при связывании модулей с обрабатываемыми данными.

9. Комплект визуальных примитивов, ориентированный на визуализацию управления данными.

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

Практичная модель с ясным графическим представлением -конечный автомат (КА). Как известно, в теории формальных языков конечным автоматом называется пятёрка

M = ( Q, 2, 5, q0, F ) где Q - конечное множество состояний;

S - конечное множество допустимых входных символов;

8 - функция переходов, т.е. отображение множества QxE в множество всех подмножеств множества Q; qoeQ - начальное состояние; FcQ - множество заключительных состояний.

Модель L-сети предоставляет следующие изобразительные средства, основанные на модели КА с некоторыми дополнениями.

Определим понятие "дуга L-сети" как тройку Е = ( с, f, t ) где с - обособленное условие (Condition spécial);

f - функциональный модуль, вызываемый при истинности с;

t - переход к следующей дуге (Transition). Из дуг конструируются сложные ветвления Bj, которые представляют собой упорядоченные комплексы дуг:

Bi = ( eu, ei2, ... ejm ) где ejj - дуга L-сети (Edge). Одно из сложных ветвлений

Bs е { В, }

выделено и называется начальным сложным ветвлением.

Будем считать, что сложные ветвления упорядочены произвольным образом. Тогда каждой дуге соответствует некоторый номер в этом порядке, который далее обозначается как Indcx( ец ).

В качестве обособленного условия будем использовать только предикат, устанавливающий отношение эквивалентности, поскольку другое отношения имеют не чисто логическую, а отчасти арифметическую природу. Модель L-сети позволяет использовать в качестве обособленного условия проверку двоичного вектора V на полное или частичное совпадение с константой С: CONDs ::= (VsC)

где s - операция проверки на полное или частичное совпадение.

При истинности CONDs происходит активация функционального модуля (ФМодуля) f, который может завершиться одним из двух способов (рис.1):

Trans - по окончании работы ФМодуля происходит переход по дуге сети;

Step - по окончании работы ФМодуля происходит шаг

к следующей по порядку дуге сложного ветвления.

^ Trais

Рис.1. Дуга L-сети

Если элемент f дуги принимает специальное значение Null, то никакой ФМодуль не активируется, а сразу происходит переход по дуге.

При ложности CONDs происходит шаг к следующей по порядку дуге сложного ветвления, т.е. выполняется операция Step (рис.1). Если элемент дуги CONDs принимает специальное значение nil, то никакое условие не проверяется, а сразу происходит активация ФМодуля f.

Множество возможных значений перехода t к следующей дуге определяется так:

t е I о { Success, Unsuccess } где I = { Index( еу ) ].

Для использования при дальнейшем рассмотрении введём частично определённую функцию Edge. Пусть В; = ( еи, ei2, ... eim ) - сложное ветвление. Тогда

Edge( Bj, j ) = Index( ey,)

при j e [ 1, m ], и

Edge( Bj, j ) не определено при j ё [ 1, m ]. Неформально, функция Edge позволяет выяснить, какой номер в общем порядке дуг всех сложных ветвлений имеет дуга сложного ветвления Bj, которая имеет в этом ветвлении порядковый номер j.

Далее показано, как для произвольного детерминированного КА построить эквивалентную L-сеть. Включим в множество ФМодулей модуль GetChar, который ведёт себя следующим образом. При активации, модуль GetChar делает попытку прочитать очередной

10

символ входной цепочки. Если попытка успешна, то GetChar помещает прочитанный символ в LNetVar и выполняет операцию Step. Если же попытка неудачна, то GetChar выполняет операцию Trans.

Введём однозначное отображение RA детерминированного КА на L-сеть, которое определим следующим образом.

( 1 ) Каждому состоянию q, е Q-F КА сопоставить сложное ветвление В| = Ra ( q, ), В, = ( elb ei2, ... eim ) en = ( nil, GetChar, Unsuccess ) eim = ( nil, Null, Unsuccess ) ( 2 ) Каждому значению функции переходов 5 из множества

{ 8( q, aj) = q, I q = q; } сопоставить одну из остальных дуг полученного сложного ветвления:

еу = (aj, Null, tj), j е [ 2, m-1 ] ( 3 ) Определить значение каждого перехода

tj, j е [ 2, m-1 ] полученного сложного ветвления но правилу:

( q, е Q-F ) => tj = Edge( RA( q,), 1 ); ( qt e F ) => tj = Success.

a).

b). B, = RA(q,)

else

Рис.2. Фрагмент графа переходов транслирующего КА и сложное ветвление L-сети

Этот способ позволяет построить L-сеть, соответствующую распознающему КА. Если же требуется транслирующий КА, то в каждую дугу вида

еу = (aj, Null, tj), j е [ 2, m-1 ] вместо пустого ФМодуля Null следует включить непустой ФМодуль, соответствующий семантической программе (рис.2).

Для сокращения количества альтернатив перехода проверяют принадлежность av некоторому подмножеству множества Е: синтерму. Теоретически, множество синтермов Sj - это множество всех подмножеств множества 2. На практике обычно выполняется:

SP с ST, #SP « #ST где # - мощность множества. Представим множество Sp в форме SP = Si u Sn, Si n SN = 0 Si= { Si I3j,j*i, S,nSj*0 } SN={ Si I Vj,j*i, SinSj = 0 } Назовём множество Si множеством синтермов с пересечениями, а множество Sn - множеством синтермов без пересечений. Очевидно, справедливы следующие утверждения:

( а е Sj I S; е Si) => ( a g Sj I Vj, Sj е SN )

( a e Sj I Sj e SN ) => ( a g Ss I Vi, Sj e Si) Предикат a e Si, где Sj 6 Si или S; g Sn, можно эффективно вычислить следующим способом. ( 1 ) Сопоставим каждому Si е Si порядковый номер

i = 1, 2, ... ^ а каждому Sj е Sn - порядковый номер

j = 1, 2, ... nN

где ni = #Si, nN = #Sn- Будем считать, что каждое множество однозначно идентифицируется своим порядковым номером. ( 2 ) Сопоставим каждому а е Е двоичный характеристический вектор Т( а ):

( 2.1 ) ( а е Sj I Si е Si) =>

Т( а ) = О II (а е Si( n )) II (а е Si( n-1 )) II ... И (а е Si( 1 )) где II - операция конкатенации;

Si( i) - множество S, б Sj, определяемое порядковым номером i. ( 2.2 ) ( а е Sj I Sj е SN ) => Т( а ) = 1 II В( j) где В( j) - отображение натурального числа j в двоичный вектор, представляющий запись j в двоичной системе счисления.

Предикат ( а е Sj I Si е Si) можно представить в форме ( Т( а ) * Mi) = Q

где = 1 II М|( щ ) II М(( пи ) II ... II 1 );

С; = О II М,( П[) II МК Пи ) II ... II М,( 1 );

М,( к ) =1, если к = ^

М,( к ) =0, если к *

* - операция поразрядной конъюнкции; а предикат ( а е »Я] I е ) можно представить в форме

Т( а ) =

где С] = 1 II В( ] ). Таким образом, вычисление указанных предикатов можно представить в форме проверки двоичного вектора V на полное или частичное совпадение с константой С. Поэтому в Ь-сети обособлено условие V = С.

Обособление в качестве CONDs фиксированного условия продиктовано желанием обеспечить максимально высокий уровень визуализации, как и в модели КА: текстом представлен только операнд (С), или операнды (С, М), а остальное подразумевается.

Если ФМодуль реализован без использования модели Ь-сети, то такой модуль называется простым ФМодулем или операционным модулем (ОМодулем). Если же для реализации ФМодуля использована Ь-сеть, то такой модуль называется сложным ФМодулем или сетевой программой (СПрограммой).

Когда ФМодуль, который активируется в дуге Ь-сети, оказывается СПрофаммой, то Ь-сеть ведёт себя иначе, чем при вызове ОМодуля. Активация СПрофаммы приводит к. тому, что точка активации (т.е. 1пс1ех( еу ) ) запоминается в стеке возвратов Ь-сети, а затем происходит переход к начальному сложному ветвлению СПрофаммы.

СПрограмма может завершиться одним из двух способов. Возврат с переходом ТЯеШгп (ТгашЯеШгп) означает возврат в точку активации СПрофаммы с последующим переходом по дуге. Возврат с шагом БКеШгп ^ерКешгп) означает возврат в точку активации СПрофаммы с последующим шагом по сложному ветвлению (рис.3).

Определим Ь-сеть с сетевыми профаммами как пару Ь№1 = ( N11, N1^ ) где N11 - множество сетевых профамм;

N1*5 е N11 - начальная сетевая профамма; а каждая сетевая программа N11, е N11 определяется как пятёрка

N11 = ( В, Е, Е, В5, И ) где В - множество сложных ветвлений;

2 - конечное множество пар (С, М ), определяющих

обособленные условия;

Е - множество дуг;

В8 е В - начальное сложное ветвление;

Б = { ТЯетш, БИеШт }.

В каждой сетевой программе N1^, множество допустимых значений переходов дуг определяется так:

{ ^ I 3], ej е ^ е е; } = I и { ТИешгп, БЯешгп } где I = { Index( ец ) I е^ е N1*, }.

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

в = ( N. Е, Р, Б ) где N - конечное множество нетерминалов;

Е - конечное множество терминалов, причём I о N = 0;

Р - конечное множество правил подстановки вида А ::= а, ще А е N. а е ( N и Е )*;

Б - начальный символ, Б е N. Предварительно выполним преобразования исходной грамматики в. Преобразование 1. Добавим к алфавиту Е терминальных символов терминал #, соответствующий маркеру конца входной цепочки, и перепишем правила граммитики так, чтобы они требовали наличия терминала # в конце любой корректной цепочки языка Цв), определяемого грамматикой в. Это преобразование тривиально.

14

Преобразование 2. По заданной КС-грамматике G построим эквивалентную ей КС-грамматику G' без левой рекурсии. Это всегда можно сделать.

Преобразование 3. По полученной КС-грамматике G' без левой рекурсии построим эквивалентную КС-грамматику G" в нормальной форме Хомского. Каждое правило из Р примет один из видов: ( 1 ) А ::= ВС где А е N, В е N. С е N; ( 2 ) А ::= а где а е Е;

( 3 ) S ::= s где е - пустая цепочка, если е е L(G), причём S

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

Введём магазин Bw, обеспечивающий возвраты назад по входной цепочке. ФМодуль Push вталкивает в Bw текущую позицию, ФМодуль Back осуществляет возврат к позиции, верхней в Bw , а ФМодуль Pop выталкивает из Bw верхний элемент.

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

А ::= СХ] I а2 I ... I а„ - все А-правила фамматики G, то припишем некоторый порядок альтернативам aj. Пусть А) - индекс i-й альтернативы нетерминала А. Например, если альтернативы упорядочены так, как записаны, то А) -индекс альтернативы а/, А2 - индекс альтернативы а2, и т.д.

Для каждой А, построим сетевую профамму NR(Aj) по правилам. ( 1 ) Если альтернатива А, имеет вид

Ai ::= а

то СПрофамма NR( А, ) имеет вид, показанный на рис.4 (ФМодуль GetChar выполняет ввод очередного символа входной цепочки).

C=>NR(A)

SReturnJ

—( а )-(jReturn)

SReturnj

Рис.4. Сетевая программа для альтернативы Aj ::= а

GetChar

Back

( 2 ) Если альтернатива А; имеет вид

А; ::= В С

то СПрограмма ЫЩ А; ) имеет вид, показанный на рис.5,а, причём каждая А], Bj) имеет вид, показанный на рис.5,Ь,

а).

—1| мя(а,, в,) |—(тяетгп)

Ь).

-1| М^Ау В,) |-(тНеШгп")

-1| Ш{А,. В„) |-(ткетт)

—| Баск |-( )

А,. В,)

-1| N«1 В,) [-.-Ц N^0) |-(ТР^)

--—(БВеКл-п)

А )

СПрограмма Б )

-(эйеишт)

Рис.5. Сетевая программа для альтернативы А; ::= В С

где Bj) - сетевая программа для альтернативы Bj нетерминала В;

С ) - сетевая программа для нетерминала С, сконструированная по правилу 3.

( 3 ) Для каждого нетерминала А, А * Б, СПрограмма имеет вид, показанный на рис.6,а. ( 4 ) Для начального символа грамматики Б имеет вид, показанный на рис.6,Ь.

Докажем теперь следующие две теоремы. Теорема 1.1. Построенная по правилам ( 1 )-( 4 ) Ь-сеть всегда порождает вывод заданной цепочки если такой вывод существует в грамматике в, по которой построена Ь-сеть.

Для доказательства теоремы нужно показать, что для каждого нетерминала А в частично построенном синтаксическом дереве происходит полный перебор всех сочетаний его непосредственных потомков прежде, чем СПрограмма А ) выполнит неуспешный возврат БНеШт. Доказательство проведём методом математической индукции по глубине вершины в синтаксическом дереве (глубина -длина пути от корня дерева до вершины).

Базис индукции. Пусть на первом шаге вывода делается попытка

использовать альтернативу вида

А В С, А = Б Соответственно, сетевая программа ЫК(А) сначала запоминает в стеке В„ позицию, соответствующую началу входной цепочки (будем обозначать эту позицию 1А), а затем активирует ИЩА]). СПрограмма ) сначала пытается использовать первую альтернативу В: нетерминала В, вызывая Ы^В]). Это соответствует части синтаксического дерева, показанной на рис.7,а. Треугольник ниже В1 соответствует пока ещё не построенному поддереву с корнем в В].

а).

> ^(А,)

МГ!(А, ) |-| Рор |--(т5£п)

N14^) }-| Рор |--(тР!е1игп)

ЫЯ(АП) [-| Рор |--(т*^)

]--(^КййггГ)

Ь).

Э )

N1^ ) )-| Рор |-1-СтПе1ит')

--11 ^> "Н Р°Р [-¡-('тКеШгп')

Рор

Рис.б. Сетевые программы для нетерминалов грамматики

Теперь возможны два случая. Случай 1. Если из В] выводится какой-либо префикс цепочки \у, то 1) сообщает об успехе, выполняя возврат ТКеШгп. Тогда вызывается NR(C), которая запоминает свою позицию для возврата Тс и пытается вывести суффикс цепочки всеми возможными способами (рис.7,Ь). Если все попытки вывести суффикс \у потерпели неудачу, то ЫЯ(С) удаляет из стека В«, позицию Тс и выполняет операцию Васк, т.е. возвращается к позиции ТА. Тогда N11^0 пытается

17

использовать альтернативу В2 нетерминала В (рис.7,с), и т.д. Случай 2. Если из В1 не выводится никакой префикс цепочки XV, то перебор всех альтернатив для нетерминала С

С], Сг, ... С]

не может привести к построению синтаксического дерева для и его можно не выполнять. Поэтому, если СПрограмма ЫЩВ]) терпит неудачу, то она возвращается к позиции Та и сообщает о неуспехе, выполняя возврат ЗЯеШгп. Тогда ИЩА]) опять-таки пытается использовать вторую альтернативу Вг нетерминала В (рис.7,с), и т.д.

с„ с2, ... с,

14

ргеАх of \Л/

БиТЯХ О? \Л/

Рис.7. Перебор альтернатив вида А ::= В С

Пусть теперь на первом шаге вывода делается попытка использовать альтернативу вида

А ::= а, А = Б В силу преобразования 1, в исходной КС-грамматике в для начального символа Б фамматики эта альтернатива может иметь только форму

Б ::=#

если язык Ц в ) допускает пустую входную цепочку. Очевидно, если предъявляемая цепочка V/ содержит только символ #, то будет

выполнен возврат ТЯеШгп, а в противном случае - возврат БЛетт.

Шаг индукции. Пусть В - корень поддерева глубины п, п>0, получен в результате применения правила вида

А ::= В С

По предположению индукции, обеспечивается полный перебор всех альтернатив В; нетерминала В. При выводе префикса оставшейся части цепочки ы из нетерминала В возможны два случая. Случай I. Для В используется альтернатива вида В ::= Э Е, Б е N. Е е N Тогда, в силу приведённого выше рассмотрения, будет выполнен полный перебор всех возможных комбинаций альтернатив Ц Ек. Случай 2. Для В используется альтернатива вида

В ::= а, а е £

Если префикс оставшейся части цепочки совпадает с терминалом а, то будет выполнен возврат ТИеШт, а в противном случае - возврат БИетгп.

Таким образом, теорема доказана.

Теорема 1.2. Для произвольной КС-грамматики можно построить эквивалентную ей Ь-сеть.

Доказательство: непосредственно следует из теоремы 1.1.

Таким образом, в форме Ь-сети можно представить общий алгоритм нисходящего разбора с возвратами. В главе 2 показано, что известные формализмы для нисходящего разбора с возвратами - язык нисходящего разбора с ограниченными возвратами (ЯНРОВ) и обобщённый ЯНРОВ (ОЯНРОВ) являются частными случаями Ь-сети, причём Ь-сеть обеспечивает их наглядное представление. В тех случаях, когда КС-грамматика допускает детерминированный разбор, построение Ь-сети, очевидно, также всегда возможно. Такая Ь-сеть соответствует, например, детерминированному КС-диаграммеру.

Рассмотренный комплекс изобразительных средств модели Ь-сети, в основу которого положены модели конечного автомата и автомата с магазинной памятью, называется средой разветвлённого управления (РУ). Но для многих задач использование этих автоматных моделей не особенно естественно. Для таких задач целесообразно исключить проверку обособленного условия №N05 и использовать набор примитивов с преимущественно последовательной организацией потока управления (рис.8). Этот набор изобразительных средств называется средой последовательного управления (ПУ).

Части программы, представленные с помощью средств среды ПУ, чисто внешне похожи на схему алгоритма. Но среда ПУ модели Ь-сети имеет нетривиальное отличие от схем алгоритма: ФМодуль с двумя

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

Далее показано, что наличие в модели Ь-сети этого расширения продиктовано запросами практики.

1

Step )—Г

(Trans )—»

^TReturn)—«

—( Mull )—

1

-L^MRelum)—

Рис.8. Изобразительные средства среды последовательного управления

Модель L-сети позволяет использовать в одной и той же программе как среду РУ, так и среду ПУ. При этом важное значение приобретают понятия "успешного" и "неуспешного" завершения функциональных модулей. В среде РУ "успех" означает переход по дуге сети, т.е. Trans (или TReturn). В среде ПУ "успех" означает шаг к следующей дуге (операции), т.е. Step (или SReturn). Модель L-сети обеспечивает также следующие способы завершения, ориентированные на использование модулей в любой среде с соблюдением принятых в точке вызова соглашений об успехе и неуспехе:

NormEnd ( NORMal END) Trans при вызове из среды РУ, Step при вызове из среды ПУ

AbEnd ( AB normal END ) Step при вызове из среды РУ, Trans при вызове из среды ПУ

Return TReturn при вызове из среды РУ, SReturn при вызове из среды ПУ

AB Return ( ABnormal RETURN ) SReturn при вызове из среды РУ, TReturn при вызове из среды ПУ.

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

Далее, в главе 2 предложена модель вычислительного процесса виртуальной вычислительной машины, которая предоставляется L-сетыо (виртуальной L-машины). Этот вычислительный процесс состоит из последовательности шагов. Действие Exec виртуальной L-машины предполагает, что определена четвёрка

( A, D, S, Т )

где А - алгоритм выполнения операции; D - множество данных, используемых алгоритмом; S - точка продолжения с шагом; Т - точка продолжения с переходом. Оно применяет к данным D алгоритм А, а затем выполняет переход либо к точке продолжения с шагом, либо к точке продолжения с переходом (рис.9).

Рис.9. Шаг работы виртуальной машины

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

1. Управление действиями: совокупность операций вида Bind( А ).

2. Управление данными: совокупность операций вида Bind( D ).

3. Управление последователностъю действий: совокупность операций вида Bind( S ) и Bind( Т ).

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

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

Затем приведён анализ управления данными, т.е. операции связывания Bind(D). На основе детального анализа вычислительного процесса, который соответствует операции Bind(D) в современных архитектурах ЭВМ, введено понятие интерфейса: совокупности данных, доступных (или потенциально доступных) двум или более подпрограммам. Показано, что аргументы подпрограммы можно считать временным интерфейсом.

Тем не менее, между интерфейсами и списками аргументов существует нетривиальное различие. Спецификации подпрограмм в 3GL ограничены рамками использования предусловий и постусловий, а также инвариантами. Предусловия, постусловия и инварианты - это гарантии надёжности. В модели L-сети модули играют роль поставщиков и потребителей услуг.

В работе Lam S.S. Udaya Shankar A. A theory of interfaces and modules. I - composition theorem // IEEE Transactions on Software Engineering, Vol.20, No.l, January 1994.-pp.55-71 предложена и математически обоснована новая теория интерфейсов и модулей, которая рассматривает модули под таким углом зрения. Как указано в этой работе, понятие предоставления услуги не может быть охвачено гарантиями надёжности. То, что требуется вместо этого - гарантии прогресса, или, в более общей форме, условные гарантии прогресса.

Далее рассмотрены предложенные автором средства визуализации динамического связывания с данными (рис.10,а). Временный интерфейс, создаваемый в процессе вызова модуля, имеет предопределённое имя PARM. Заполнение интерфейса аргументами выполняет отдельный функциональный модуль. Источники заполнения интерфейса - другие интерфейсы, видимые в точке вызова.

Рис.10. Вызов функционального модуля с параметрами

Операция заполнения интерфейса PARM аргументами не может иметь нескольких точек продолжения. Какие-либо "неуспехи" (например, переполнение стека) должны обрабатываться системой. Именовать эту операцию также излишне. Поэтому соответствующий прямоугольник можно "свернуть" в горизонтальную линию (рис.10,Ь). Прямоугольник "заполнение интерфейса" можно сильно сжать, поскольку записать в него текст, специфицирующий детали заполнения интерфейса PARM, нереально (рис. 10,с). IDE раскрывает этот прямоугольник в окно с необходимыми сведениями (рис. 10,d).

В среде вызова возможны два варианта.

1. Интерфейс PARM размещен в памяти независимо от активизации модуля и не уничтожается при завершении работы модуля. Назовем такой интерфейс независимым.

2. Интерфейс PARM размещается в памяти в связи с запуском модуля и уничтожается при завершении его работы. Назовем такой интерфейс временным.

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

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

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

Автором предложены две существенно различные формы реализации L-сети: одна - на основе компилируемого кода, другая - на основе интерпретируемого кода.

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

Рассмотрены особенности реализации, выполненной автором с использованием распространённого стандартного макропроцессора: препроцессора языка C/C++. В этой реализации C/C++ использован также в качестве операционного языка. Представлен комплект макросов для автоматизии получения текста на языке C/C++ на основе рисунка, изображающего сетевую программу L-сети. В отсутствие графики, текст на макроязыке не отличается высокой наглядностью. Но, при одновременном наличии рисунка, текст воспринимается как наглядный, а его соответствие (или несоответствие) рисунку легко просматривается.

Подход, основанный на представлении L-сети в форме компилируемого кода успешно использован автором и его сотрудниками при работе над рядом сложных проектов ПО на ПЭВМ IBM PC в среде операционных систем MS DOS, MS Windows, OS/2 в сочетании с операционньми языками Си и С++.

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

24

реализацию модели на основе интерпретатора (L-машины).

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

1. LCC_NULL: вызов пустого ОМодуля.

2. LCC_OM: вызов ОМодуля в среде ПУ.

3. LCC_NR: вызов СПрограммы в среде ПУ.

4. LCC_CONDS: проверка обособленного условия без использования маски.

5. LCC_MCONDS: проверка обособленного условия с использованием маски.

6. LCC_ROM: вызов ОМодуля в среде РУ.

7. LCC_RNR: вызов СПрограммы в среде РУ.

8. LCC_SRETURN: возврат из СПрограммы с последующим шагом.

9. LCC_TRETURN: возврат из СПрограммы с последующим переходом.

10. LCC_RETURN: возврат из СПрограммы с успешным продолжением.

11. LCC_ABRETURN: возврат из СПрограммы с неуспешным продолжением.

12. LCC_MRETURN: возврат из СПрограммы с последующим мультиветвлением.

13.LCC_STOP: завершение функционирования L-машины. Рассмотрены особенности интерпретируемого кода L-сети и

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

В ходе работы над различными проектами ПО, автором выполнено несколько реализаций L-машины и компилятора L-сети, ориентированных на использование различных операционных языков на различных ЭВМ. В главе 4 приведён документированный текст реализации L-машины на языке C/C++. В условиях полного отсутствия средств отладки, L-сеть обеспечивала наблюдаемое поведение ПО и позволяла эффективно преодолевать проблемы тестирования.

Далее выполнена оценка эффективности использования L-сети. Отмечено, что в настоящее время единый общепризнанный подход к оценке затрат на разработку ПО отсутствует. Один из наиболее широко применяемых методов оценки затрат - это метрологический подход, который разработал Б.У.Боэм.

Приведённое сопоставление с данными Боэма показывает, что использование L-сети привело к повышению производитеьности профаммирования на 1-2 порядка.

В пятой главе рассмотрено использование модели L-сети при

25

разработке сложного проекта ПО, выполненного автором и его сотрудниками: конфигурируемого ПО контроля синтаксиса языка SQL. Эта задача возникла в связи с использованием значительного количества диалектов SQL, что серьёзно препятствует портированию текстов на языке SQL между различными базами данных. Цель проекта состояла в разработке гибкого и конфигурируемого ПО проверки синтаксиса SQL, способного работать под управлением операционных систем MVS, OS/2, Windows NT и, возможно, других.

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

ПО, которое позволяет определить диалект SQL, называется конфигуратором (SQL configuration tool). ПО, которое может проверять SQL-текст, используя определённый с помощью конфигуратора диалект SQL, называется программой проверки синтаксиса (SQL syntax checker).

Конфигуратор должен использоваться только образованным и ответственным лицом: администратором базы данных. Поскольку круг потенциальных пользователей конфигуратора сравнительно узок, необходимо поддержать сравнительно небольшое количество платформ: OS/2 и Windows NT на ПЭВМ IBM PC.

Программа проверки синтаксиса задумана как инструмент проблемного программиста, использующего язык SQL. Этот программист может работать либо на ПЭВМ, либо на мэйнфрейме. Поэтому диалект SQL, определённый с помощью конфигуратора, должен быть портируемым на мэйнфрейм, а программа проверки синтаксиса должна работать как в среде OS/2 и Windows NT на ПЭВМ IBM PC, так и в среде MVS на мэйнфрейме.

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

Наиболее нестандартным требованием к проекту является конфигурирование синтаксиса через оконный интерфейс в форме синтаксических диаграмм. Показано, что реализация синтаксического анализатора SQL в форме исполняемого кода, а также в форме LR(1)-или LL(l)-тaблиц не обеспечивает решения поставленной задачи

Предложенное автором решение основано на модели L-сети и

26

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

JI j01n

А

! | Oval J

i

h 1 •*» 1

Рис. 11. Внутренняя реализация синтаксической диаграммы

Каждому синтаксическому элементу соответствует узел многомерного списка. Связи узла с соседними узлами отражают структуру синтаксической диаграммы; их количество может достигать четырёх. Для удобства работы со списком в целом, все узлы связаны в линейный список. Кроме того, каждый узел содержит указатель на окно своего синтаксического элемента и указатель на узел списка, представляющего конфигурируемый диалект SQL. Таким образом, для поддержки диаграммы требуется семимерный (!) список.

Внутренний формат диалекта SQL, разработанный автором, состоит из записей переменной длины. В отношении представления синтаксиса, модель L-сети обеспечивает прямое соответствие между синтаксическими элементами и дугами L-сети. Например, овалу (нотационной константе) соответствует дуга L-сети, в которой эта константа использована в обособленном условии (рис.12).

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

которым можно управлять при загрузке кода диалекта SQL в программу проверки синтаксиса.

ON/OFF

|—Q SELECT Л

Рис.12. Связь между синтаксическим элементом и дугой Е-сети

Наиболее простым способом реализации приведённой идеи конфигурирования синтаксиса оказывается интерпретируемая Е-сеть.

Рис.13. Архитектура программных средств проверки синтаксиса SQL

28

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

Dialect Compiler разработан автором с помощью компилируемой модели L-сети.

Проект разработан под руководством и при участии автора, с помощью многоплатформенного компилятора: IBM Visual Age С++. Архитектура ПО проверки синтаксиса SQL показана на рис.13.

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

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

Основные результаты и выводы

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

Основной результат диссертационной работы состоит в том, что предложен и теоретически обоснован новый визуальный формализм для разработки ПО: модель L-сети, использование которой позволяет эффективно преодолевать сложность разработки ПО с логическим характером сложности, в среднем более чем в 10 раз повысить производительность труда программиста за счёт использования новых методов взаимодействия человека с ЭВМ и новых способов организации обработки информации в ЭВМ, в том числе, организации и управления вычислительным процессом.

При этом получены следующие результаты: 1. Выполнено теоретическое обоснование мощности модели L-сети. Доказано, что модель L-сети без сетевых программ может быть построена по произвольному конечному автомату, и при этом допускает важные для практического программирования

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

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

3. Расширено представление об управлении последовательностью действий в ходе вычислительного процесса. Новое визуальное представление управления последовательностью действий в L-сети основано на использовании модулей с двумя выходами и с возможными побочными эффектами. Предложена новая система понятий, связанных с определением точки возобновления вычислений после завершения работы модуля с двумя выходами: возвраты и окончания с шагом, с переходом, с успехом, с неуспехом, с мультиветвлением.

4. Расширено представление об управлении данными при вызовах-возвратах. Предложены средства визуализации операций управления данными. Дано обоснование того, что связь через интерфейсы способна обеспечить те же возможности, что и связь через аргументы-параметры в распространённых языках программирования третьего поколения (3GL). Показано, как соединить графические примитивы управления последовательностью действий L-сети с предложенными графическими примитивами управления данными.

5. Разработаны реализации модели L-сети в форме компилируемого и интерпретируемого кода. С использованием модели L-сети, лично автором, а также под его руководством и при непосредственном участии выполнен ряд больших проектов ПО в средах операционных систем MS DOS, Windows 3.1, OS/2 Warp, IBM OS/370, подтверждающих практичность и эффективность модели. К

. ним относятся, в частности, конфигурируемое ПО проверки синтаксиса языка SQL, пакет прикладных программ . автоматизированного синтеза цифровых устройств, язык JIM для описания дискретных устройств на совмещённом уровне логических схем и регистровых передач и система моделирования дискретных устройств. При разработки конфигурируемого ПО проверки

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

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

Публикации

Основное содержание диссертации опубликовано в 33-х печатных

работах. Важнейшие из них следующие.

1. Лекарев М.Ф. Визуальный формализм для разработки программного обеспечения.-СПб:СПбГТУ,1997.-95с.

2. Лекарев М.Ф. Методика табличного управления работой программного обеспечения // Управляющие Системы и Машины, 1985, №4.-с.61-66.

3. Lekarev M.F. Das grafische Verfahren der Software-Entwicklung für logisch komplizierte Anwendungen // Technische Berichte der Fachhochschule Hamburg, №25 (August 1993), s.36-38.

4. Лекарев М.Ф. Графические средстна разработки программного обеспечения // Вычислительные, измерительные и управляющие системы (Труды СПбГТУ №462).-СПб:СПбГГУ,1996.-с. 100-108.

5. Лекарев М.Ф. Управление данными при связывании программных модулей // Вычислительные, измерительные и управляющие системы (Труды СПбГТУ №462).-СПБ:СПбГТУ,1996.-с. 108-115.

6. Лекарев М.Ф. Методика автоматизированного проектирования программного обеспечения // Всесоюзн.науч.-тех.конф. "Программные средства как продукция производственно-технического назначения", тез. докл. секц. "Технология разработки программных средств".-Калинин:1985.-с.97-100.

7. Лекарев М.Ф. Управление действиями и данными в языке ПЛ/1: Учебное пособие.-Л:ЛПИ, 1986.-80с.

8. Лекарев М.Ф., Мелехин В.Ф. Автоматизированное проектирование структур цифровых устройств: Учебное пособие.-Л.ЛПИ, 1984.-76с.

9. Лекарев М.Ф., Мелехин В.Ф., Пьшшш Е.В. Автоматизированный синтез комбинационных схем на задаваемом наборе логических элементов // Вычислительные, измерительные и управляющие системы: Сб.научных трудов (Труды СПбГТУ №452).-СПб:СПбГТУ, 1995.-е. 193-206.

Ю.Алексеев В.Н., Колосов В.Г., Лекарев М.Ф. и др. Микропроцессорные средства производственных систем.-Л.¡Машиностроение, 1988.-287с.

11. Многоцелевые системы ЧПУ гибкой механообработкой / Под общ. ред. проф. Колосова В .Г.-Л/Машиностроение, 1984.-224с.

12.Лекарев М.Ф. Принципы автоматизации программирования для специализированной микро-ЭВМ нижнего уровня АСУТП и ГАП механообработки // Межвуз.сб.трудов "Анализ и синтез элементов и структур управляющих ЭВМ"-Омск: 1986.-c.36-41.

13.Лекарев М.Ф., Мелехин В.Ф. Автоматизация проектирования дискретных устройств: Учебное пособие.-Л.ЛПИ, 1978.-80с.

Н.Горячев C.B., Лекарев М.Ф., Шелонин Ю.В. Программная реализация управляющих алгоритмов в специализированных ЭВМ с табличными методами преобразования информации // Автоматизация анализа и синтеза структур ЭВМ и вычислит, алгоритмов. Сб.статей.-Омск: Омский политех, инст., 1984.-C.10-15

15. Горячев Е.В., Лекарев М.Ф., Мелехин В.Ф. Принципы построения вычислительной системы, ориентированной на поддержку разветвленного управления программным обеспечением // Вычислительная техника, автоматика и радиоэлектроника: Сб.научных трудов.-Л.:ЛГТУ,1990.-с.80-84.

16. Горячев Е.В., Лекарев М.Ф., Петренко A.A. Организация аппаратного и программного обеспечения ЭВМ на базе сетевой модели II Вычислительные, измерительные и управляющие системы: Сб.научных трудов.-Л.:ЛГТУ,1990.-с.31-34.

17.Давыдов В.Г., Лекарев М.Ф. Проектирование WINDOWS-приложений с использованием графической технологии программирования // Российская научно-техническая конференция "Инновационные наукоемкие технологии для России".-Тез.докл.,ч.8.-СПб:СПбГТУ,-с.22.

18.Лекарев М.Ф., Мелехин В.Ф. Табличный язык описания структур вычислительных устройств на совмещённом уровне логических схем и регистровых передач // Системы автоматизации проектирования и научных исследований.-Л. ЛПИ, 1984.-c.97-102

19.Лекарев М.Ф. Графическая технология проектирования программных средств // Международная конференция "Технологии и системы сбора, обработки и представления информации".-Тез.докладов.-Рязань:Русское слово, 1993г.-с.50.

20. Лекарев М.Ф. Опыт внедрения графической технологии программирования в преподавание информатики // III Международная научно-методическая конференция "Высокие интеллектуальные технологии образования и науки".-Тезлокл.-СПб:СПбГТУ,1995.-с.209.

21. Лекарев М.Ф. Графическая технология программирования для решения задач с логическим характером сложности // Российская научно-техническая конференция "Инновационные наукоемкие технологии для России".-Тез.докл.,ч.8.-СПб:СПбГТУ,1996-с.10.

22. Мелехин В.Ф., Лекарев М.Ф. Анализ методов моделирования дискретных учтройств автоматики//Труды ЛПИ,№377,1981.-с.91-95.

23.Мелехин В.Ф., Лекарев М.Ф., Давыдов В.Г.,Пышкин Е.В. Система автоматизации синтеза цифровых устройств // Российская научно-техническая конференция "Инновационные наукоемкие технологии дня России".-Тез.докл.,ч.8.-СПб:СПбГТУ,1995.-с.23.

24.Лекарев М.Ф., Мелехин В.Ф. Опыт применения мини-ЭВМ в учебном процессе для задач автоматизации проектирования // Тез. докл. Всесоюзн. конф. "Автоматизация проектных и конструкторских работ", Москва,1979.- с.399-400.

25. Лекарев М.Ф., Давыдов В.Г. Применение учебного машинно-ориентированного языка.-СПб:СПбГТУ, 1992.-27С.