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

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

Кузнецов Александр Сергеевич

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

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

Автореферат 5 [J f) f~] ?

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

Красноярск - 2009

003482473

Работа выполнена в Федеральном государственном образовательном учреждении высшего профессионального образования «Сибирский федеральный университет», г. Красноярск

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

Официальные оппоненты:

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

Ковалев Игорь Владимирович

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

Ченцов Сергей Васильевич

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

Моргунов Евгений Павлович

Ведущая организация Государственное образовательное

учреждение высшего профессионального образования «Томский государственный университет систем управления и радиоэлектроники»

Защита состоится 27 ноября 2009 года в 16.00 часов на заседании диссертационного совета ДК212.099.05 при Сибирском федеральном университете по адресу: 660074, г. Красноярск, ул. академика Киренского, 26, ауд. УЛК-115.

С диссертацией можно ознакомиться в библиотеке Сибирского федерального университета.

Автореферат разослан 26 октября 2009 года.

Ученый секретарь

диссертационного совета I Вейсов Е. А.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Среди специалистов, занимающихся вопросами надежности вычислительных и программных систем, можно выделить таких отечественных и зарубежных ученых как В.В.Липаев, В.Г.Хорошевский, И.В.Ковалев, М.М.Горбунов-Посадов, В.В.Воеводин, A.Avizienis, R.Glass, В.Воет, C.Breshears, A.Moralez, E.Lee.

Одним из подходов к созданию современных отказоустойчивых систем является мультиверсионная методология избыточности (MVP - Multi-Version Programming). Данная методология позволяет добиться программной избыточности, которая нацелена на предупреждение случайных ошибок и сбоев. Кроме того, работа системы защищена от ошибок, которые могли быть получены еще при проектировании и реализации программного обеспечения. Фактически, чем больше глубина мультиверсионности, то есть чем больше количество версий, обеспечивающих выполнение программных модулей, тем выше вероятность правильной работы программного обеспечения, полученного в рамках данной методологии.

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

• языки программирования модулей;

• алгоритмы решения задач;

• средства программирования;

• методы тестирования.

Фактически, реализация принципа разнообразия обеспечивает эффективность мультиверсионной методологии за счет независимости сбоев

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

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

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

б) кругозор и практический опыт опытных программистов не ограничивается единственным языком;

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

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

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

Более того, в большинстве случаев для создания версий применяются далеко не все возможности языков программирования, а лишь основные конструкции. При этом не совсем рационально используются возможности трансляторов «полноценных» языков. Разработчики в этом случае не всегда имеют возможность внести соответствующие изменения в системы трансляции, например, из-за отсутствия доступа к их исходным текстам и по другим причинам. Следовательно, возникает необходимость по разработке стандартных средств построения трансляторов, традиционно называющихся компиляторами компиляторов.

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

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

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

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

Для достижения поставленной цели решались следующие задачи:

• анализ современных методов повышения отказоустойчивости программного обеспечения и методик построения и повышения качества мультиверсионного программного обеспечения;

• анализ существующих методов построения трансляторов в контексте их применения для мультисинтаксических языков программирования;

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

• модификация существующих алгоритмов трансляции мультисинтаксических языков программирования;

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

Методы исследования. При выполнении работы были использованы методы компонентного проектирования сложных программных систем; объектно-ориентированного программирования; теории конечных автоматов; теории языков программирования и методы восходящего синтаксического анализа языков программирования.

Научная новизна результатов работы:

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

• разработано абстрактное устройство распознавания мультисинтаксических языков в виде множества автоматов с памятью магазинного типа;

• модифицирован алгоритм восходящего синтаксического анализа ЬАЬЩ1), на основе которого создан алгоритм шЬАЬЯ(1) восходящего синтаксического анализа мультисинтаксических языков программирования;

• разработана система построения трансляторов мультисинтаксических языков программирования мультиверсионных систем.

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

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

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

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на X и XII Международных научных конференциях «Решетневские чтения» в 2006 и 2008 гг., Второй, Третьей и Пятой Всероссийских конференций «Молодежь и наука: начало 21-го века» в 2006, 2007 и 2009 гг. Докладывались на научно-технических семинарах кафедры информатики Сибирского федерального университета, НИИ Систем управления, волновых процессов и технологий (2005-2008 гг.).

При использовании созданной автором системы построения трансляторов мультисинтаксических языков программирования мультиверсионных систем были реализованы два компилятора для диалектов языка программирования С с возможностью включения кода на других языках, которые были внедрены в эксплуатацию, соответственно, в ОАО «Информационные спутниковые системы» имени академика М.Ф. Решетнева (г. Железногорск) и Центре разработки программного обеспечения компании «Астрософт» (г. Красноярск).

Материалы диссертационной работы также внедрены в учебный процесс и используются при чтении лекций студентам кафедры «Информатика» Сибирского федерального университета по дисциплине «Теория языков программирования и методы трансляции».

На защиту выносятся:

• Формальное описание синтаксиса мультисинтаксических языков

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

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

• Алгоритм восходящего синтаксического анализа мультисинтаксических языков программирования шЬАЬЩ1).

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

Публикации. По материалам диссертации опубликовано 8 печатных работ, из них: статей в рецензируемых изданиях по списку ВАК - 4; статей в сборниках научных работ - 4. Осуществлена регистрация программной разработки в Отраслевом фонде алгоритмов и программ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и четырех приложений. Работа содержит 110 страниц текста, 20 рисунков и 3 таблицы. Список литературы содержит 118 наименований.

СОДЕРЖАНИЕ

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

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

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

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

Модель мультиверсионного программирования предполагает наличие специальной среды исполнения, которая осуществляет конкурентное

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

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

Рекомендуемые проектные спецификации V-Spec ориентированы на универсальные языки программирования, но в практическом программировании встречаются аналогичные средства, ориентированные на низкоуровневые языки, языки моделирования и/или проектирования, и т.д. Редко применяются языки предметной области (Domain Specific Languages), хотя ведущие разработчики ПО достигли в этом направлении хороших результатов: описаны языки, есть средства по их созданию, многие команды разработчиков активно используют подход Domain Driven Design.

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

Таблица 1. Уровни мультиверсионности сточки трения масштаба версии

Номер н название уровня Краткая характеристика

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

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

3. Версии основных программных конструкций Для ООП - это классы или типы. Пользователь (программист) может сравнительно легко реализовать разные версии таких конструкций.

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

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

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

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

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

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

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

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

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

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

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

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

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

Анализ ряда компиляторов различных языков, поддерживающих ассемблерные вставки (C/C++, Pascal, Delphi, Smalltalk и D), показал, что в общем виде синтаксис вставок можно описать двумя способами. При этом в качестве средства описания синтаксиса используется нотация, близкая к форме Бэкуса-Наура и используемая в программах типа YACC.

АссемблернаяВставка

: ОткрывающийАссемблернуюВставкуЭлемент НаборМашинноЗависимыхИнструкций ЗакрывающийАссемблернуюВставкуЭлемент I КлючевоеСловоОбозначающееАссемблернуюВставку ЕдинственнаяМашинноЗависимаяИнструкция

ОткрывающийАссемблернуюВставкуЭлемент

: КлючевоеСловоОбозначающееАссемблернуюВставку ОткрывающаяГруппуИнструкцийСкобка

ЗакрывающийАссемблернуюВставкуЭлемент : ЗакрывающаяГруппуИнструкцийСкобка

Рисунок 1. Синтаксис ассемблерных вставок

Первый способ дает возможность описывать несколько ассемблерных инструкций:

_asm

{

mov ЕАХ, value add value, ЕВХ

)

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

_asm mov ЕАХ, value

_asm add value, EBX

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

Одним из недостатков включений ассемблерного кода считается привязка к конкретной аппаратной платформе. Причем в этом случае речь, обычно, идет об архитектуре х86, но она не является единственной. Иначе говоря, реальные потребности разработчиков мультиверсионных систем должны удовлетворяться более широко. К настоящему моменту, как показал анализ, не существует компиляторов языков программирования мультиверсионных систем, допускающих включения ассемблерного кода более чем одной системы команд. Располагая такой возможностью, можно конструировать версии одного и того же модуля для разных платформ, в том числе, устаревших или вновь разрабатываемых, имея «под рукой» уже работающие версии. Кроме того, можно конструировать модули для одной платформы, но на ассемблерах разных стилей. В частности для архитектуры х86 известны два основных стиля - Intel и AT&T. В связи с этим синтаксис ассемблерных вставок изменяется, хотя и незначительно (рис. 2).

АссемблернаяВставка

: ОткрывающийАссемблернуюВставкуЭлемент НаборМашинноЗависимыхИнструкций ЗакрывающийАссемблернуюВставкуЭлемент I КлючевоеСловоОбозначающееАссемблернуюВставку ЕдинственнаяМашинноЗависимаяИнструкция

ОткрывающийАссемблернуюВставкуЭлемент

: ПервоеСловоОбозначающееАссемблернуюВставкуВерсии1

ОткрывающаяГруппуИнструкцийСкобка I ВтороеСлово0бозначающееАссемблернуюВставкуВерсии2 ОткрывающаяГруппуИнструкцийСкобка

ЗакрывающийАссемблернуюВставкуЭлемент : ЗакрывающаяГруппуИнструкцийСкобка

Рисунок 2. Синтаксис ассемблерных вставок

Далее приводится обзор языков написания сценариев, включаемых в HTML-страницы - JavaScript, JScript, VBScript, Tel и т.д и описывается общий синтаксис включения, который позволяет создавать надежные динамические страницы, поскольку можно определить несколько версий сценариев на разных языках на случай отсутствия в Web-браузере поддержки какого-либо языка, части и даже всего набора языков. Такая возможность делает функционирование Web-браузера детерминированным.

Далее приводится описание синтаксиса включений запросов к СУБД в код на высокоуровневых языках (технологии PL/SQL и LINQ).

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

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

Также с точки зрения поддержки мультиверсионности рассматривается концепция Domain Specific Languages - специальных проблемно-ориентированных языков. Можно отметить следующие аспекты:

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

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

3. На DSL можно реализовать мультиверсионность на уровнях программных фрагментов (LINQtoSQL) и основных программных конструкций (межъязыковое наследование классом из предметной области А класса из предметной области В). Однако такой подход зависит от используемой среды и в целом ограничен платформой .NET.

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

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

ВставкаКодаНаВторомЯзыке

: ОткрывающийВставкуЭлемент КодНаВторомЯзыке ЗакрывающийВставкуЭлемент I ОткрывающийВставкуЭлемент КодНаВторомЯзыке;

Рисунок 3. Сннтакснс включений в код на одном языке кода на другом языке

Завершается второй раздел формальным описанием мультисинтаксического языка программирования.

За основу программ трансляции языков обычно берутся контекстно-свободные грамматики (далее - КСГ), которые дополняются определенными механизмами. Один из самых ранних подходов использует понятие

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

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

Итак, формально синтаксис МСЯ £ можно описать следующим образом с использованием списка грамматик С, где N - количество грамматик «вспомогательных языков»:

.....с,.....ах), (1)

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

а^-рЛРАУ^.Р^,), (2)

где Г, Л/, Р, Б это, соответственно множества терминальных и нетерминальных символов, множество продукций и аксиома грамматики, Кт;к/1 - это множество особых лексем, которое является подмножеством множества терминальных символов Т.

Лине/. - это специально выделенное множество продукций для переключения между грамматиками, которое является подмножеством всего множества продукций. Фактически, это пары вида а->Л,/5, где а - левая часть продукции; /1/ - это специальный терминал (А, е Г„„(Ь), который вызывает временную смену грамматики с на С/; р - это хвост правой части продукции, который содержит специально выделенный нетерминал, именующий группу продукций грамматики О/.

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

Третий раздел посвящен синтезу абстрактного распознавателя МСЯ -мультиавтомату с магазинной памятью (далее МП-мультиавтомат).

Он описывается следующим образом:

= (3)

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

V _

Множество М = 0 или М = где = - это соответствующий

I

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

Аналогично, множество 5сО, также может быть пустым (5 = 0). В

А' _

общем случае, 5 = у5'/, где -\,К - это особое состояние из

I

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

МП-мультиавтомат задан ошибочно в следующих случаях:

а) Количество особых состояний меньше количества вспомогательных МПА (К < N), так как бессмысленно включать в устройство столь ресурсоемкий элемент без возможности переключиться на него. Однако, это ограничение можно снять, например, зарезервировав один или несколько вспомогательных МПА для дальнейшего использования.

б) Если множество м = 0, а множество 5*0, так как тогда исчезает необходимость в выделении особых состояний.

в) Если множество М ¿0, а множество 5 = 0 по тем же соображениям, что и в пункте а) данного списка.

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

Чтобы задать такую функцию, необходимо различать два случая: при наличии в МП-мультиавтомате вспомогательных МПА и без таковых. В первом случае должны быть указаны номер (неотрицательное целое число J^l) вспомогательного МПА из множества М и номер особого состояния из множества 5 (/,). В итоге получаем функцию <рПо1стР1У, принимающую пять аргументов и дающую на выходе результат в виде набора из трех элементов:

!> И)

где р - это новое состояние МПА; у - это цепочка магазинных символов, М^ - МПА с номером из множества М.

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

Теперь предположим, что М = 0 - в МП-мультиавтомате нет вспомогательных МПА. Тогда необходимо, чтобы функция ср вела себя так же, как функция переходов б обычного МПА. Получаем функцию Фетрц, которая отличается от функции переходов лишь своим названием:

<Р„,Р, (д,а,Х):{р,у} (5)

В общем виде функция переключений (р имеет вид:

[<Р,трАЯ,а,х)ЛР,УЬ если Л^ = 0 и 5 = 0 Далее дается формализованное описание МП-мультиавтомата с учетом выражений (4) и (5).

((2,1,Г есшМ*<2иВ*<г>и\М\< |5|,

рт„ = • (&е.если М = 0 и 5 = 0, (7)

Ошибка, в противном случае Эквивалентным для (7), принимая во внимание (6), будет следующее формальное определение МП-мультиавтомата, которое отличается от (3) лишь явным указанием на ошибку в описании:

™"'=\п к

[Ошибка, в противном случае

Далее дается определение конфигурации, или мгновенного описания Ют,!, МП-мультиавтомата Рти1. Поскольку в некоторый момент времени в выделенном состоянии может быть запущен вспомогательный МПА, то помимо текущего состояния, оставшейся части входа и содержимого своего магазина, МП-мультиавтомат описывается также через конфигурации каждого из содержащихся в нем МПА. Последнее является множеством /Ош в выражении (9).

Я>„„,=1М (9)

где N - количество вспомогательных МПА. Таким образом, получаем мгновенное описание МП-мультиавтомата - выражение (10).

(10)

в противном случае

Определим для МП-мультиавтомата также бинарное отношение перехода \-рт,,1. Если Рти/- это описанный МП-мультиавтомат, <p(q,a,XJl¡l,Js) содержит [р,а,МЛ,), то \-Рти! определяет отношение, которое для всех цепочек со из £ и /? из Г' такое, что [д,аш,Хр,М) \-pmui [р,ю,ар,М^).

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

Таким образом, если Рти1 - это МП-мультиавтомат, описанный выражением (8), тогда языком ЦРШ11), допускаемым МП-мультиавтоматом по заключительному состоянию является утверждение (11):

¿(0= Й(<7о.о>Л,/0„,„) |-/>и„,' (я.е.а.Ю^)} (П)

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

2. Далее предположим, что МП-мультиавтомат содержит единственный вспомогательный МПА. Поскольку передача ему управления осуществляется в одном из специально выделенных состояний МП-мультиавтомата, а после возврата управления последнему осуществляется переход к следующему «обычному» состоянию в соответствии с функцией перехода и никакого иного влияния на абстрактное устройство распознавания вспомогательный МПА не оказывает, то его можно удалить из МП-мультиавтомата. Тогда доказательство сходимости может быть сведено к п. 1. '

3. Теперь допустим, что МП-мультиавтомат имеет два вспомогательных МПА. Поскольку они друг на друга не влияют, то можно поочередно удалить их из МП-мультиавтомата. Тогда доказательство сходимости может быть сведено к п.2.

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

В следующей части главы приводится описание алгоритма тЬАЫ1(1), отвечающего за формирование таблицы, управляющей процессом синтаксического анализа. За основу взят алгоритм ЬАЬЯ(1), сложность которого для большинства языков составляет О(п), где п - длина анализируемой программы, и модифицирован с учетом особенностей МСЯ.

Установить указатель ip на первый символ w$;

Бесконечный цикл {

Пусть s - это состояние на вершине стека; Пусть а - символ, на который указывает ip if (action[s, а] == "St") 1

Втолкнуть в магазин а, затем t; Переместить ip к следующему входному символу

}

if (action[s, а] == "Et") {

Втолкнуть в магазин а, затем t;

Найти j индекс элемента а в таблице особых лексем; if (j != ОШИБКА)

Вызвать P[j] LALR(1)-анализа вложенного языка if (ОШИБКА) return ОШИБКА

Переместить ip к следующему входному символу

}

else if (action[s, а] == "Rt") {

Вытолкнуть из магазина N элементов,

где N - это длина правой части продукции t; Втолкнуть в магазин А (левую часть продукции t); Затем выполнить goto[текущее состояние. А]; ip присвоить значение на вершине стека

)

else if (action [s, a] == "Accept") return УСПЕХ else

return ОШИБКА

}

Рисунок 4. Алгоритм синтаксического анализа mLALR(l).

Построенная по такому алгоритму таблица синтаксического анализа состоит из элементов тех же четырех типов, что и в классическом LALR(l), для анализа вспомогательных языков. Для языка-лидера в ячейках таблиц указываются элементов пяти типов:

1. Элементы переноса. Они имеют вид Sk и означают: поместить в магазин символ, соответствующий столбцу; поместить в магазин состояние к и перейти к состоянию к\ если текущий символ - терминал, то принять его.

2. Элементы свертки. Они имеют вид Rm и означают: выполнить свертку с помощью правила т; удалить N символов и N состояний из магазина (N- это количество символов в правой части продукции); перейти к состоянию, находящемуся на вершине магазина. Нетерминал из левой части продукции т считать следующим входным символом.

3. Элементы ошибок. Они являются пустыми ячейками таблицы и соответствуют синтаксическим ошибкам.

4. Элементы остановки, которые имеет вид Accept. Ими завершается процесс синтаксического анализа (входная строка принимается).

5. Элементы запускающего переноса. Эти элементы имеют вид Ек и означают: поместить в магазин символ, соответствующий столбцу; поместить в магазин состояние к; найти и запустить анализатор вспомогательного языка; если он закончил анализ с ошибкой, то завершить анализ лидирующего языка с ошибкой; в противном случае перейти к состоянию к. Так как рассматриваемый символ - терминальный, принять его.

Далее дается описание метода расстановки этих элементов в таблицах. Сам алгоритм анализа, работающий под управлением этих таблиц, приведен на рисунке 4. Анализируемая последовательность обозначена как w, анализатор находится в состоянии so, а во входном буфере находится tv$

Сложность алгоритма mLALR(l) зависит не только от длины программы, но и от количества анализаторов вспомогательных языков (от). Поскольку во время работы оно не может измениться, то для наихудшего случая можно также говорить о сложности '0(т*п). На практике т « п, следовательно, значением т в большинстве случаев можно пренебречь.

Заканчивается данный раздел исследованием других аспектов трансляции МСЯ. В частности, отмечается, что для лексического анализа используется классические конечные автоматы.

В четвертом разделе описывается система MuYacc построения трансляторов МСЯ мультиверсионных систем. Для автоматизации лексического анализа используются регулярные выражения, как в системе flex, а для синтаксического анализа - наборы продукций как в BYacc/bison. Однако в отличие от них MuYacc объединяет и использует оба механизма в рамках одной входной спецификации, что позволяет программисту не переключаться при разработке транслятора между двумя задачами.

Для создания трансляторов система MuYacc учитывает следующее:

■ «Вспомогательные» синтаксические анализаторы не взаимодействуют, чтобы избежать петель вызовов программ анализа.

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

■ Действия по проверке семантических соглашений и действия этапа синтеза выполняются на языке программирования.

■ В качестве лидера используется язык С++.

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

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

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

%tokengroup name="arith_tokens"

%regexp letter [a-z]

%regexp digit [0-9]

Iregexp IDENT letter(letter I digit)*

%regexp NUM digit+

%token <str> IDENT

%tokefi <num> NUM

%endtokengroup

%switchtoken ARITH

analyzer :

I analyzer *\n' I expressions analyzer; expressions : ARITH '(' arith_expressions '}'; %syntaxgroup name="arith_expressions" kword=ARITH

tokengroup="arith_tokens" expr : expr '+' expr I '(' expr ')' I IDENT I NUM; %endsyntaxgroup

Рисунок 5. Пример спецификации с мультисннтаксисом для системы MuYacc

Описание мультисинтаксиса реализуется четырьмя новыми ключевыми словами %tokengroup, %endtokengroup, %syntaxgroup, %endsyntaxgroup, размещаемых, соответственно в первой и второй частях входной спецификации и обладающих описанными ниже свойствами. Ключевые слова %tokengroup и %endtokengroup играют роль операторных скобок, в которые заключаются группы регулярных выражений. Аналогично для групп продукций в качестве скобок выступают слова %syntaxgroup и %endsyntaxgroup. Обе «открывающие» скобки именуют начало группы и дают название процедурам, соответственно, лексического и синтаксического анализа для их дальнейшего использования (свойство пате). Для групп продукций также указывается название «особой лексемы» (свойство bvord), а также наименование соответствующей группы лексем и регулярных выражений (свойство tokengroup). Предусмотрена возможность импорта групп лексем и продукций из внешних файлов с проверкой наличия таковых. Вложенность групп запрещается.

Для «особой лексемы» во входной спецификации анализатора-лидера используется еще одно ключевое слово %switchtoken. Она обязана дважды присутствовать в спецификации: как обычная лексема и как «особая». Пример спецификации (без импорта из внешнего файла и действий по кодогенерации) приведен на рисунке 5.

Система МиУасс прошла регистрацию в Отраслевом фонде алгоритмов и программ и была апробирована в двух проектах по созданию трансляторов МСЯ программирования мультиверсионных систем. Апробирование проводилась в рамках выполнения двух проектов (IntegrAsm и МиК^иегу) по созданию и использованию экспериментального компилятора диалекта языка С с включением двух вспомогательных языков.

Результаты тестирования показывают двукратное снижение количества ошибок при формировании версии одного модуля на втором вспомогательном языке. Одновременно отмечается рост на 2-3% трудоемкости создания набора версий. Уменьшается количество состояний за счет выделения анализаторов вспомогательных языков.

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

В приложениях А и В приведены примеры входных спецификаций МиУасс. В приложениях С, О и Е - копии актов о внедрении в производственный процесс организаций г. Красноярска и г. Железногорска.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ.

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

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

• Модифицирован алгоритм восходящего синтаксического анализа ЬА1Л(1) с учетом особенностей мультисинтаксического языка программирования. Получен и протестирован алгоритм тЬАЬЯ(1); его вычислительная сложность незначительно превышает ЬАЬЯ(1).

• Разработана и внедрена в эксплуатацию система МиУасс построения трансляторов мультисинтаксических языков программирования мультиверсионных систем.

• Экспериментально показано, что применение мультисинтаксических языков программирования мультиверсионных систем позволяет снизить количество ошибок на этапе эксплуатации до 50%.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендованных ВАК РФ:

1. Кузнецов, A.C. Автоматизация процесса генерации компиляторов мультисинтаксических языков программирования [Текст] / A.C. Кузнецов, И.В. Ковалев, Е.А. Веретенников // Вестник Сиб. гос. аэрокосмич. ун-та. - 2007. - Вып. 3 (16). - С. 73-75.

2. Капчинский, И.А. Принципы формирования мультиверсионного программного комплекса [Текст] / И.А. Капчинский, A.C. Кузнецов, A.B. Штенцель // Вестник Сиб. гос. аэрокосмич. ун-та. - 2008. - Вып. 1 (18). -С. 18-23.

3. Кузнецов, A.C. Генерация компиляторов мультисинтаксических языков программирования мультиверсионных систем [Текст] / A.C. Кузнецов, И.В. Ковалев // Международный журнал «Программные продукты и системы». - 2008. - Вып. 4 (84). - С. 101-103.

4. Кузнецов, A.C. Моделирование распознавателей мультисинтаксических языков программирования мультиверсионных систем [Текст] / A.C. Кузнецов // Вестник Сиб. гос. аэрокосмич. ун-та. - 2009. - Вып. 3 (24). -С. 62-66.

Прочие публикации по теме диссертационного исследования:

5. Кузнецов, A.C. Инструментальное средство разработки трансляторов мультисинтаксических языков программирования [Текст] / A.C. Кузнецов // Вестник университетского комплекса: Сб. науч. трудов. Красноярск: НИИ СУВПТ, 2006. - №7(21). - С. 227-231.

6. Волков, В.А. Технологии программирования СОМ и СОМ+ для распределенных компьютерных систем [Текст] / В.А. Волков, A.C. Кузнецов, A.A. Чикизов // Вестник университетского комплекса: Сб. науч. трудов. Красноярск: НИИ СУВПТ, 2006. - № 9(23). - С. 79-87.

7. Кузнецов, A.C. Компилятор компиляторов мультисинтаксических языков программирования для создания мультиверсионного программного обеспёчения [Текст] / A.C. Кузнецов, Е.А. Веретенников // Вестник НИИ СУВПТ: Сб. науч. трудов. Красноярск: НИИ СУВПТ, 2007.-№24.-С. 35-42.

8. Кузнецов, A.C. Разработка мультиверсионных программ с использованием мультисинтаксических языков и технологий [Текст] / A.C. Кузнецов // Вестник НИИ СУВПТ: Сб. науч. трудов. Красноярск: НИИ СУВПТ, 2008. - № 26. - С. 25-42.

Разработка, зарегистрированная в Отраслевом фонде алгоритмов и

программ:

9. Кузнецов, A.C. Программа автоматизированной разработки трансляторов MuYacc vl.0. / A.C. Кузнецов, Е.А.Веретенников // Номер гос. регистрации 50200702091 от 27.09.2007 г. - М. : ВНТИЦ, 2007.

и

I

КУЗНЕЦОВ Александр Сергеевич

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

СИСТЕМ

Автореферат

Подписано в печать_._.2009. Формат 60x84/16.

Бумага писчая. Гарнитура Times New Roman. Усл. печ л. 1,39 Уч.-изд. л 0,85. Тираж 100 экз. Заказ №_

Отпечатано в ИПК СФУ 660074, г. Красноярск, ул. ак. Киренского, 28.

ВВЕДЕНИЕ.

1. ПРОБЛЕМЫ СОЗДАНИЯ НАДЕЖНОГО ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ.

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

1.2 Обнаружение ошибок.

1.3 Проблемы проектирования программных систем.

1.4 Методология мультиверсионного программирования как средство повышения надежности программного обеспечения.

1.5 Критические замечания по современному состоянию методологии мультиверсионного программирования.

1.6 Выводы по первой главе.

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

2.1 Неформальное определение мультисинтаксического языка.

2.2 Обзор современных мультисинтаксических средств.

2.2.1. Использование ассемблерных вставок при программировании на языках высокого уровня.

2.2.2. Скриптовые языки для создания динамических Web-страниц.

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

2.2.4. Концепция Domain Specific Languages.

2.2.5. Синтаксис включений в программы на одном языке кода на другом языке.

2.3 Формальное описание мультисинтаксического языка.

2.4 Выводы по второй главе.

3. МОДЕЛИРОВАНИЕ РАСПОЗНАВАТЕЛЕЙ

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

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

3.2 Формирование таблиц синтаксического анализа мультисинтаксических языков программирования.

3.3 Лексический анализ мультисинтаксических языков программирования.

3.4 Семантический анализ мультисинтаксических языков программирования и этап синтеза компилятора МСЯ.

3.5 Выводы по третьей главе.

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

4.1 Система построения трансляторов мультисинтаксических языков программирования мультиверсионных систем MuYacc.

4.2 Входная спецификация системы MuYacc.

4.3 Применение трансляторов МСЯ при разработке мультиверсионного ПО

4.3.1. Проект IntegrAsm - компилятор языка С, обеспечивающий вставки ассемблерного кода.

4.3.2. Проект MulQuery - компилятор языка С, обеспечивающий включение кода на языках запросов к СУБД.

4.3.3. Использование трансляторов MulQuery и IntegrAsm для разработки мультиверсионного ПО.

4.4 Выводы по четвертой главе.

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

Среди специалистов, занимающихся вопросами надежности вычислительных и программных систем, можно выделить таких отечественных и зарубежных ученых как В.В. Липаев, В.Г. Хорошевский, М.М. Горбунов-Посадов, В.В. Воеводин, А.Г. Мамиконов, Е.А. Микрин, A.M. Половко, И.В. Ковалев, A. Avizienis, R. Glass, В. Воет, С. Breshears, А. Moralez, Е. Lee.

Одним из подходов к созданию современных отказоустойчивых систем является мультиверсионная методология избыточности (MVP - Multi-Version Programming). Данная методология позволяет добиться программной избыточности, которая нацелена на предупреждение случайных ошибок и сбоев. Кроме того, работа системы защищена от ошибок, которые могли быть получены еще при проектировании и реализации программного обеспечения. Фактически, чем больше глубина мультиверсионности, то есть чем больше количество версий, обеспечивающих выполнение программных модулей, тем выше вероятность правильной работы программного обеспечения, полученного в рамках данной методологии.

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

• языки программирования модулей;

• алгоритмы решения задач;

• средства программирования;

• методы тестирования.

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

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

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

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

Более того, в большинстве случаев для создания версий применяются далеко не все возможности языков программирования, а лишь основные конструкции. При этом не совсем рационально используются возможности трансляторов «полноценных» языков. Разработчики в этом случае не всегда имеют возможность внести соответствующие изменения в системы трансляции, например, из-за отсутствия доступа к их исходным текстам и по другим причинам. Следовательно, возникает необходимость по разработке стандартных средств построения трансляторов, традиционно называющихся компиляторами компиляторов.

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

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

Для достижения поставленной цели решались следующие задачи:

• анализ современных методов повышения отказоустойчивости программного обеспечения и методик построения и повышения качества мультиверсионного программного обеспечения;

• анализ существующих методов построения трансляторов в контексте их применения для мультисинтаксических языков программирования;

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

• модификация существующих алгоритмов трансляции мультисинтаксических языков программирования;

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

Методы исследования. При выполнении работы были использованы методы компонентного проектирования сложных программных систем; объектно-ориентированного программирования; теории конечных автоматов; теории языков программирования и методы восходящего синтаксического анализа языков программирования.

Научная новизна результатов работы:

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

• разработано абстрактное устройство распознавания мультисинтаксических языков в виде множества автоматов с памятью магазинного типа;

• модифицирован алгоритм восходящего синтаксического анализа ЬА1Л(1), на основе которого создан алгоритм тЬАЫ1(1) восходящего синтаксического анализа мультисинтаксических языков программирования;

• разработана система построения трансляторов мультисинтаксических языков программирования мультиверсионных систем.

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

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

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

Апробация работы. Основные положения и результаты работы докладывались и обсуждались на X и XII Международных научных конференциях «Решетневские чтения» в 2006 и 2008 гг., Второй, Третьей и Пятой Всероссийских конференций «Молодежь и наука: начало 21-го века» в 2006, 2007 и 2009 гг. Докладывались на научно-технических семинарах кафедры информатики Сибирского федерального университета, НИИ Систем управления, волновых процессов и технологий (2005-2008 гг.).

При использовании созданной автором системы построения трансляторов мультисинтаксических языков программирования мультиверсионных систем были реализованы два компилятора для диалектов языка программирования С с возможностью включения кода на других языках, которые были внедрены в эксплуатацию, соответственно, в ОАО «Информационные спутниковые системы» имени академика М.Ф. Решетнева (г. Железногорск) и Центре разработки программного обеспечения компании «Астрософт» (г. Красноярск).

Материалы диссертационной работы также внедрены в учебный процесс и используются при чтении лекций студентам кафедры «Информатика» Сибирского федерального университета по дисциплине «Теория языков программирования и методы трансляции».

На защиту выносятся:

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

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

• Алгоритм восходящего синтаксического анализа мультисинтаксических языков программирования тЬАЫ1(1).

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

Публикации. По материалам диссертации опубликовано 8 печатных работ, из них: статей в рецензируемых изданиях по списку ВАК - 4; статей в сборниках научных работ - 4. Осуществлена регистрация программной разработки в Отраслевом фонде алгоритмов и программ.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы и четырех приложений. Работа содержит 110 страниц текста, 20 рисунков и 3 таблицы. Список литературы содержит 118 наименований.

4.4 Выводы по четвертой главе

Описанное в предыдущих разделах инструментальное средство при соблюдении ограничений, названных в параграфе 4.1, обладает следующими преимуществами:

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

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

3. Уменьшение времени на отладку программ трансляции, созданных на основе существующих спецификаций flex и BYacc/bison/Zubr изза тесной взаимосвязи фаз лексического и синтаксического анализа процесса трансляции и за счет их объединения в одной входной спецификации.

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

5. Возможное совмещение схем компиляции и интерпретации в одном и том же трансляторе для разных частей программы, написанной на мся.

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

ЗАКЛЮЧЕНИЕ

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

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

• Модифицирован алгоритм восходящего синтаксического анализа ЬАЫ1(1) с учетом особенностей мультисинтаксического языка программирования. Получен и протестирован алгоритм тЬАЫ1(1); его вычислительная сложность незначительно превышает ЬАЬЯ(1).

• Разработана и внедрена в эксплуатацию система МиУасс построения трансляторов мультисинтаксических языков программирования мультиверсионных систем.

• Экспериментально показано, что применение мультисинтаксических языков программирования мультиверсионных систем позволяет снизить количество ошибок на этапе эксплуатации до 50%.

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

1. Abbott, RJ. Resourceful Systems for Fault Tolerance, Reliability, and Safety / RJ. Abbott //ACM Computing Surveys, Vol.22, No.l, March 1990. R 35-68.

2. Avizienis, A. The Methodology of N-Version Programming, in R. Lyu, editor, Software Fault Tolerance, John Wiley & Sons, 1995. R 23-47.

3. Aycock, J. Practical Earley Parsing. / J. Aycock, R.N. Horspool // Computer Journal, vol. 45, 6 (2002). P. 620-630.

4. AT&T-Syntax электронный ресурс. http://sig9.com/articles/att-syntax.

5. Backus, J.W. Revised Report on the Algorithmic Language ALGOL 60. / J.W. Backus et al., in P.Naur editions. // Commun. ACM, vol. 6, no. 1, p. 1-17, January 1960.

6. Bell, J. Software design for reliability and reuse: a proof-of-concept demonstration. / J. Bell et al. // Proceedings of the Conference on TRI-Ada '94, ACM, ACM Press, New York, p. 396-404.

7. Bell, C. Learn to Tango with D. / C. Bell, L. I. Igesund, S. Kelly, M. Parker. Berkeley, CA: Apress, 2008. 208 p.

8. Boehm, B. Software Cost Estimation with COCOMO II. / B. Boehm, Ch. Abts,

9. A. Brown et al. Boston, MA: Addison-Wesley. - 544 p.

10. Boehm, B. Balancing Agility and Discipline: A Guide for the Perplexed. /

11. B. Boehm, R. Turner. Boston, MA: Addison-Wesley. - 268 p.

12. Card, D. "A Software Technology Evaluation Program". / D. Card // Information and Software Technology 29, no.6 (July/August), 1987. P. 291300.

13. Character sets электронный ресурс. http://www.iana.org/assignments/character-sets.

14. Code Generation Network электронный ресурс. -http://www.codegeneration.net.

15. DeMarco, Т. Peopleware: Productive Projects and Teams, 2d ed. / T. DeMarco, T. Lister. New York: Dorset House. - 246 p.

16. DeRemer, F. Efficient Computation of LALR(l) Look-Ahead Sets./ R DeRemer, T.J. Pennello // ACM Trans. Program. Lang. Syst. Vol. 4 (1982). -№4.-P. 615-649.

17. Standard ECMA-262. ECMAScript Language Specification электронный ресурс. http://www.ecma-international.org/publications/files/ECMA-ST7Ecma-262.pdf.

18. Standard ECMA-334. C# Language Specification электронный ресурс. -http://www.ecma-international.org/publications/files/ECMA-ST/Ecma-334.pdf.

19. Evans, E. Domain-Driven Design: Tackling Complexity in the Heart of Software. / E. Evans. Boston, MA: Addison-Wesley. — 576 p

20. Fowler, M. Domain Specific Languages электронный ресурс. — http://martinfowler.com/dslwip/.

21. FreeBasic электронный ресурс. — http://www.freebasic.net.

22. FreePascal электронный ресурс. — http://freepascal.ru/.

23. Glass, R. Modern Programming Practices: A Report from Industry. / R. Glass. — Engleewood Cliffs, NJ: Prentice Hall, 1982. 304 p.

24. Grady, R. Measuring and Managing Software Maintenance. / R. Grady // IEEE Software, Vol. 4 no 9 (September), 1987. P. 34-45.

25. Grune, D. Parsing Techniques: a practical guide. / D. Grune, C. Jakobs. Ellis Horwood, Chichester, 1990. - 334 p.

26. Hecht, H. Fault tolerant software. / H. Hecht // IEEE Trans. Reliability, Vol. R-28, 1979.-P. 227-232.

27. Johnson, S.C. Language development tools / S.C. Johnson, M. Lesk // Bell System Technical J. 57:6, 1978. P. 2155-2175.

28. Jones, C. Programming Productivity. / C. Jones. New York: McGraw-Hill, 1986-280 p.

29. Jones, C. Software Assessments, Benchmarks, and Best Practices. Reading. -Boston, MA: Addison-Wesley. 688 p.

30. Kasami, T. An efficient recognition and syntax analysis algorithm for context-free languages / T. Kasami // AFCRL-65-758, Air Force Cambridge Research Laboratory, Bedford, Mass, 1965.

31. Knuth, D. E. Semantics of context-free languages/ D.E. Knuth // Mathematical Systems Theory 2:2, 1968.-P. 127-145.

32. Korenjak, A.J. A practical method for constructing LR(k) processors/ A.J. Korenjak // Commun.ACM 12 (11), 1969. P. 613-623.

33. Kovalev, I.V. System of Multi-Version Development of Spacecrafts Control Software/ I.V. Kovalev. Berlin: Pro Universitate Verlag Sinzheim, 2001.-80 p.

34. Landin, P.J. "The next 700 programming languages". / P.J. Landin // Commun.ACM 9 (3). P. 157-166.

35. Lee, P.A. Fault Tolerance, Principles and Practice / P.A. Lee, T. Andreson. — Engleewood Cliffs, NJ: Prentice/Hall International, 1981. 370 p.

36. Lesk, M.E. Lex a lexical analyzer generator. / M.E. Lesk // Computing Science Technical Report 39, AT&T Bell Laboratories, Murray Hill, NJ, 1975.

37. Levine, J. lex & yacc, Second Edition / J. Levine, T. Mason, D. Brown. -Sebastopol, CA: O'Reilly Media, 1992.-384 p.

38. McLean, Ph. A Faster Earley Parser. / Ph. McLean, R.N. Horspool // Proceedings of Intl. Conference on Compiler Construction (CC'96), Linkoping, Sweden, April 1996, LNCS vol. 1060, Springer-Verlag, p. 281-293.

39. Mernik, M. When and How to Develop Domain-Specific Languages. / M. Mernik, J. Heering, A. Sloane. // ACM Computing Surveys, vol. 37, no. 4, p. 316-344, December 2005.

40. Mills, H. Software Productivity. / H. Mills. Boston, MA: Little Brown, 1983. - 274 p.

41. Nierstrasz, O. Squeak by Example. / O. Nierstrasz, S. Ducasse, D. Pollet,

42. Parr, Т. The Definitive ANTLR Reference Building Domain-Specific Languages. / T. Parr. Sebastopol, CA: O'Reilly Media, 2007. - 376 p.

43. Pradhan, D.K. Fault-tolerant computer system design. / D.K. Pradhan. Upper Saddle River, NJ: Prentice/Hall International, 1996. - 550 p.

44. Ramming, J.C (ed.). In: Proceedings of the USENIX Conference on Domain-Specific Languages, USENIX, Santa Monica, CA, USA, October 1997.

45. RFC 2278 IANA Charset Registration Procedures http://tools.ietf.org/html/rfc2278.

46. Schutzenberger, M.P. On context-free languages and pushdown automata / M.P. Schutzenberger // Information and Control 6:3 (1963). P. 246-264.

47. Shapiro, M. Purpose-Built Languages. / M. Shapiro //ACM Queue, Vol. 7, No. 1, January 2009. P. 18-24.

48. Silayeva, T. An Innovative Method for Program Reliability Evaluation / T. Silayeva, K.-E. Grosspietsch. Euromicro '95. Como (Italy), September 1995.

49. SQL Standard электронный ресурс.http://www.wiscorp.com/SQLStandards.html.

50. Spinellis, D. Notable design patterns for domain-specific languages. / D. Spinellis // The Journal of Systems and Software 56 (2001). P. 91-99.

51. Vallet, J. "A Summary of Software Measurement Experiences in the Software Engineering Laboratory". / J. Vallet, F.E. McGarry. // Journal of Systems and• Software 9 No 2 (February), 1989 P. 137-148.

52. V6lter, M. Model-Driven Software Development: Technology, Engineering, Management. / M. Volter, T. Stahl, J. Bettin et al. John Wiley & Sons, 2006. -444 p.

53. World Wide Web Consortium — Web Standards электронный ресурс. -http ://www. w3. org.

54. Windows 1251 электронный ресурс. -http://www.microsoft.com/globaldev/reference/sbcs/1251 .htm.

55. Wirth, N. The design of a Pascal compiler. / N. Wirth // Software Practice and Experience 1:4, 1971, p. 309-333.

56. Weber, S. Open Source Software in Developing Economies. / S. Weber . -http://www.ssrc.org/programs/itic/publications/ITSTmaterials/webernote2.pdf.

57. Yourdon, E. Modern Structured Analysis. / E. Yourdon. New York: Yourdon Press, 1989.-672 p.

58. Аниконов, A.B. Программно-аппаратное обеспечение отказо- и катастрофоустойчивых систем управления и обработки информации. / А.В. Аниконов, М.Ю. Слободин, Р.Ю. Царев. М.: Макс-пресс, 2006. -244 с.

59. Ахо, А. Компиляторы: принципы, технологии и инструментарий, 2 издание. / А. Ахо, М. Лам, Р. Сети, Дж. Ульман. М.: Издательский дом «Вильяме», 2008. - 1184с.

60. Баженова, И.Ю. Основы проектирования приложений баз данных. / И.Ю. Баженова. М.: «Бином. Лаборатория знаний», 2006. - 326 с.

61. Брукс, Ф. Мифический человеко-месяц или Как создаются программные системы. / Ф. Брукс. СПб.: Символ-Плюс, 2006. - 304 с.

62. Волков, В.А. Технологии программирования СОМ и СОМ+ для распределенных компьютерных систем / В.А. Волков, А.С. Кузнецов, А.А. Чикизов // Вестник университетского комплекса: Сб. науч. трудов.

63. Красноярск: НИИ СУВПТ, 2006. № 9(23). - С. 79-87.

64. Вольфенгаген, В.Э. Конструкции языков программирования. Приемы описания / В.Э. Вольфенгаген. М.: АО «Центр ЮрИнфоР», 2001. - 276 с.

65. Гантер, Р. Методы управления проектированием программного обеспечения: Пер. с англ/ Р. Гантер, Е. К. Масловский. М.: Мир, 1981. — 392 с.

66. Гриффитс, A. GCC. Настольная книга пользователей, программистов и системных администраторов / А. Гриффите. Киев: ООО «ТИД «ДС», 2004. - 624 с.

67. Глушаков, C.B. Программирование Web-страниц. JavaScript. VBScript / C.B. Глушаков, И.А. Жакин, Т.С. Хачиров. Харьков: Фолио, 2002. -390 с.

68. Горбунов-Посадов, М.М. Расширяемые программы. / М.М.Горбунов-Посадов. М.: Полиптих, 1999. - 336 с.

69. Губанов, Ю.А. Обзор перспективных технологий Microsoft.NET: Учебный курс. / Ю.А. Губанов СПб.: СПбГУ, 2006. - 106 с.

70. Дорошенко, А.Ю. Мультиасемблерна мова програмування. / А.Ю. Дорошенко, М.В. Котюк, С.С. Нжолаев // Проблеми програмування. — 2008.—N 1.—С. 26-36.

71. Игнатов, В.В. «Об одном методе построения LR(1) анализатора. / В.В. Игнатов. // Вестн. Моск. ун та. Сер. 15. N 1, 1987. С. 55-61.

72. Ирвин, К. Язык ассемблера для процессоров Intel. / К. Ирвин. М.: Издательский дом «Вильяме», 2005. - 912 с.

73. Капчинский, И.А. Принципы формирования мультиверсионного программного комплекса / И.А. Капчинский, A.C. Кузнецов, A.B. Штенцель // Вестник Сиб. гос. аэрокосмич. ун-та. 2008. - Вып. 1 (18).-С. 18-23.

74. Карпов, Ю.Г. Теория и технология программирования. Основы построения трансляторов. / Ю.Г. Карпов. СПб.: БХВ-Петербург, 2005. - 272с.

75. Кириллов, Д. Ориентация на язык. / Д. Кириллов. // Компьютерра. 2006.-№ 10.-С. 33-38.

76. Клини, C.K. Представление событий в нервных сетях. / С.К. Клини // Сб. «Автоматы». -М.:ИЛ, 1956. С. 15-67.

77. Ковалев, И.В. Система мультиверсионного формирования программного обеспечения управления космическими аппаратами: Диссертация на соискание ученой степени доктора технических наук / И.В. Ковалев // Красноярск: КГТУ, 1997. 228 с.

78. Кодовая страница — Википедия электронный ресурс. — http://ru.wikipedia.ore/wiki/KoflQBaH страница

79. Костельцев, A.B. Построение интерпретаторов и компиляторов. Использование программ Bizon, Вуасс, Zubr. / A.B. Костельцев. М.: Наука и техника, 2001. - 224 с.

80. Кузнецов, A.C. Инструментальное средство разработки трансляторов мультисинтаксических языков программирования. / A.C. Кузнецов // Вестник университетского комплекса: Сб.научн.трудов; Красноярск: ВСФ РГУИТП, НИИ СУВПТ, 2006-Вып.7(21). С.227-230.

81. Кузнецов, A.C. Автоматизация процесса генерации компиляторов мультисинтаксических языков программирования / A.C. Кузнецов, И.В. Ковалев, Е.А. Веретенников // Вестник Сиб. гос. аэрокосмич. ун-та. -2007. Вып. 3(16). - С. 73-75.

82. Кузнецов, A.C. Генерация компиляторов мультисинтаксических языков программирования мультиверсионных систем / A.C. Кузнецов, И.В. Ковалев // Международный журнал «Программные продукты и системы». -2008.-Вып. 4 (84).-С. 101-103.

83. Кузнецов, A.C. Разработка мультиверсионных программ с использованием мультисинтаксических языков и технологий Текст. / A.C. Кузнецов //

84. Вестник НИИ СУВПТ: Сб. науч. трудов. Красноярск: НИИ СУВПТ, 2008. -№26.-С. 25-42.

85. Кузнецов, A.C. Моделирование распознавателей мультисинтаксических языков программирования мультиверсионных систем Текст. / A.C. Кузнецов // Вестник Сиб. гос. аэрокосмич. ун-та. — 2009. — Вып. 3 (24). — С. 62-66.

86. Легалов, А.И. Трансляторы: методы разработки. Методическое обеспечение учебных курсов по основам разработки трансляторов электронный ресурс. — http://www.softcraft.ru/translat.shtml.

87. Липаев, В.В. Качество программного обеспечения. / В. В. Липаев. М.: Финансы и статистика, 1983. - 263 с.

88. Липаев, В.В. Проектирование программных средств: Учеб. пособие для вузов по спец. "Автом. сист. обр. информ. и упр.". / В. В. Липаев. М.: Высшая школа, 1990. - 303 с.

89. Лотт, Дж. ActionScript 3.0. Сборник рецептов. / Дж. Лотт, Д. Шалл, К. Питере. СПб.: Символ-Плюс, 2007. - 608 с.

90. Магда, Ю.С. Использование ассемблера для оптимизации программ на С++. / Ю.С. Магда. СПб.: BHV-Петербург, 2004. - 496 с.

91. Магда, Ю.С. Ассемблер для процессоров Intel Pentium. / Ю.С. Магда. -СПб.: Питер, 2006. 410 с.

92. Макконнелл, С. Совершенный код. Мастер-класс. / С. Макконнелл. М. Издательско-торговый дом «Русская редакция»; СПб.: Питер, 2005. — 896 с.

93. Мамиконов, А. Г. Проектирование АСУ. / А. Г. Мамиконов. М.: Высшая школа, 1987.-304 с.

94. Микрин, Е.А. Бортовые комплексы управления космическими аппаратами и проектирование их программного обеспечения. / Е.А. Микрин. М.: Издательство МГТУ им. Н.Э. Баумана, 2003. - 336 с.

95. Молчанов, А.Ю. Системное программное обеспечение. / А.Ю. Молчанов. СПб.: Питер, 2006. - 400 с.

96. Набор символов — Википедия электронный ресурс. — Ьйр://ги^1к1ре<11а.ог§/ш1к1/Наборсимволов

97. Осипов, Д. Delphi. Профессиональное программирование. / Д. Осипов.- СПб.: Символ-Плюс, 2006. 1056 с.

98. Понамарев, В.А. Программирование на С++/С# в Visual Studio.NET 2003. / В.А. Понамарев. СПб.: BHV-Петербург, 2004. - 352 с.

99. Популярные скрипты электронный ресурс. http://cgi.myweb.ru/.

100. Разработка скриптов электронный ресурс. http://www.script-coding.info/.

101. Рябко, В.А. Подход к реализации среды разработки для DSL / В.А. Рябко // Проблеми програмування. — 2007. — N 4. — С. 3-12.

102. Сергеев, А.П. HTML и XML. Профессиональная работа. / А.П. Сергеев,- Киев: Диалектика, 2004. 880 с.

103. Соммервилл, И. Инженерия программного обеспечения / И. Соммервилл. М.: Издательский дом «Вильяме», 2002. 624 с.

104. Тейнсли, Д. Linux и UNIX: программирование в shell. Руководство разработчика. / Д. Тейнсли. СПб.: BHV-Петербург, 2001. - 464 с.

105. Уэлш, Б. Практическое программирование на Tel и Tk (+ CD), 4-е изд. / Б. Уэлш. М.: Издательский дом «Вильяме», 2002. - 1136 с.

106. Фаулер, М. UML. Основы. / М. Фаулер, К. Скотт. СПб.: Символ-Плюс, 2002. - 192 с.

107. Хандхаузен, Р. Знакомство с Microsoft Visual Studio 2005 Team System. / P. Хандхаузен. M.: Издательство «Русская редакция»; СПб.: Питер, 2006. -416 с.

108. Хантер, Р. Основные концепции компиляторов. / Р. Хантер. М.: Издательский дом «Вильяме», 2002. — 256с.

109. Хомский, Н. «Три модели для описания языка». / Н. Хомский // Кибернетический сборник. М. ИЛ, 1961. - Вып. 2. - С. 237-266.

110. Хопкрофт, Дж.Э. Введение в теорию автоматов, языков и вычислений, 2-е изд. / Дж.Э. Хопкрофт, Р. Мотвани, Дж.Д. Ульман. М.: Издательский Jдом «Вильяме», 2002. 528 с.

111. Центральный Javascript-pecypc электронный ресурс. -http ://www. i avascript.ru.

112. Шапошников, И.В. Самоучитель HTML4. / И.В.Шапошников. -М.СПб.: БХВ-Петербург, 2001. 288 с.

113. Энгель, Е.А. Распределенные информационно-управляющие системы: кластерная архитектура и мультиверсионное программное обеспечение: Монография. / Е.А. Энгель, В.А. Морозов, Р. Ю. Царев. Красноярск: ИПЦКГТУ, 2006.- 160 с.

114. Эрли, Дж. Эффективный алгоритм анализа контекстно-свободных языков. / Дж. Эрли // Сб. «Языки и автоматы». М.: Мир, 1975. - С. 47-70.

115. Янгер, Д. Распознавание и анализ контекстно-свободных языков за время п3/ Д. Янгер // Сб. «Проблемы математической логики». М.:Мир, 1970.-С. 344-362.