«Инструментальное средство синтеза и исполнения транслирующих программ на основе позитивнообразованных формул ...»

РОССИЙСКАЯ АКАДЕМИЯ НАУК

СИБИРСКОЕ ОТДЕЛЕНИЕ

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

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

Бутаков Михаил Игоревич

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

и исполнения транслирующих программ на основе позитивнообразованных формул

Специальность 05.13.11 – Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей Диссертация на соискание ученой степени кандидата технических наук

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

к.ф.-м.н., доц. В.И. Курганский Иркутск – Оглавление Введение

Глава 1. Синтез транслирующих программ на основе позитивно-образованных формул

1.1. Язык и исчисление позитивно-образованных формул

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

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

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

1.5. Выводы

Глава 2. Регулярные и LL(1)-грамматики. Существование транслирующей программы

2.1. Распознающие позитивно-образованные формулы для регулярных правосторонних детерминированных грамматик

2.2. Распознающие позитивно-образованные формулы для LL(1)грамматик

2.3. Выводы

Глава 3. Компонент синтеза транслирующих программ

3.1. Условия и общая схема применения компонента

3.2. Организация данных и диалоговый интерфейс компонента................. 3.3. Выводы

Глава 4. Примеры применения компонента синтеза транслирующих программ

4.1. Технология решения учебных задач трансляции

4.1.1. Учебные трансляторы. Требования и структура

4.1.2. Пример учебного транслятора

4.2. Контроль цепочек входных воздействий в диалоговой системе таможенного контроля Терминал

4.2.1. Назначение и структура диалоговой системы

4.2.2. Логико-лингвистическая модель диалога

4.2.3. Реализация модели

4.3. Выводы

Заключение

Литература

Приложение 1. Множество направляющих символов для LL(1)-грамматик... Приложение 2. Акт об использовании результатов работы

Введение При решении прикладных задач часто приходится решать задачи трансляции. Примерами программ, где решаются задачи трансляции, являются:

AutoCad [38], Microsoft Office (VBA) [46], 1С:Предприятие [45], предметноориентированные языки и системы программирования и др [65].

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

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

Одним из подходов к решению указанных задач является представление формального языка и входной цепочки в виде логической теории первого порядка [63]. Применение логических средств для решения задач трансляции позволяет:

Адаптировать средства интеллектуализации к терминологии и свойствам предметной области;

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

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

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

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

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

Работа основана на результатах, полученных Васильевым С.Н. и его учениками в области логического вывода и приложений логического вывода в составе пакетов прикладных программ; Ершовым А.П. в области доказательного программирования; Манна З. и Уолдингером Р. в области дедуктивного синтеза программ; Тыугу Э.Х. в области структурного синтеза программ. Существенное влияние на результаты диссертации оказали работы Н. Хомского, А.Ахо и Дж.Ульмана, посвященные моделям и методам трансляции.

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

Цель работы – обеспечить разработку и применение транслирующих программ в составе прикладных программ для формальных языков 2 и классов по Хомскому [68] на основе позитивно-образованных формул.

Для достижения указанной цели были поставлены следующие задачи:

1. Разработать постановку и схему решения задачи трансляции в регулярной правосторонней детерминированной грамматике и LL(1)грамматике;

3. Разработать инструментальное средство для конструирования и применения в составе прикладных программ транслирующих ПОФ;

4. Применить разработанное инструментальное средство на практике.

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

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

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

Научную новизну диссертационного исследования составляют:

отличающиеся от известных использованием исчисления ПОФ.

2. Инструментальное средство для конструирования транслирующих программ и их применения в составе прикладных программ, распознавателя КС-языков в виде ПОФ.

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

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

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

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

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

транслирующих программ (КСТП), алгоритмы преобразования грамматик в ПОФ и представление требований к диалогу в виде ПОФ применены при решении двух практических задач – разработки учебных трансляторов и контроля диалога в диалоговой системе Терминал.

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

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

Соответствие диссертации паспорту научной специальности. В диссертации представлена новая модель и схема решения задачи трансляции в исчислении ПОФ. Результаты работы могут быть использованы при проектировании прикладных программ и систем, включающих трансляцию формальных языков. Одним из аспектов использования является контроль допустимости цепочек входных воздействий в составе диалогового интерфейса прикладной программы. Таким образом, тематика диссертации соответствует пунктам 1, 7 области исследований специальности 05.13.11.

Апробация работы. Основные результаты работы представлены на научно-теоретической конференции молодых ученых, посвященной 60-летию Великой Победы (Иркутск, 2005), на VII Всероссийском симпозиуме по прикладной и промышленной математике (Кисловодск, 2006), на VIII школесеминаре молодых ученых «Математическое моделирование и О распространении системы электронного поштучного учета. Письмо ФТС России от 11 марта 2008 №01информационные технологии: управление, искусственный интеллект, прикладное программное обеспечение, технологии программирования»

(Иркутск, 2006), на IX школе-семинаре молодых ученых «Математическое моделирование и информационные технологии» (Иркутск, 2007), на XIV математические технологии в науке и управлении» (Иркутск, 2009), на III школе-семинаре молодых ученых «Инфокоммуникационные и вычислительные мультиконференции по проблемам управления (с. Дивноморское, 2011), на объединенном семинаре Института динамики систем и теории управления СО РАН (2008), на кафедре информационных систем Института математики, экономики и информатики ГОУ ВПО ИГУ (2010).

Результаты диссертации были получены в рамках проекта СО РАН «Интеллектные методы и инструментальные средства создания и анализа интегрированных распределенных информационно-аналитических и вычислительных систем для междисциплинарных исследований с применением ГИС, GRID и Web-технологий» (№ гос. Регистрации 01.2.00708582), 2007– гг.

опубликовано 15 печатных работ, включая 3 статьи[11, 18, 19] в журналах, рекомендованных ВАК для опубликования результатов диссертационных работ, 5 публикаций [9, 12, 13, 14, 16] в трудах региональных, всероссийских, публикаций [10, 17, 20, 39, 40, 41] в научных сборниках и журналах, свидетельство [56] об официальной регистрации программ в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам.

Результаты главы 1 опубликованы в работах [19, 20, 39, 40]; результаты главы 2 опубликованы в [17, 18, 19, 20, 39, 40]; результаты главы опубликованы в [9, 10, 14, 15, 19]; результаты главы 4 опубликованы в [11, 12, 13, 16, 18, 40, 56].

Все результаты, выносимые на защиту, получены автором лично. В основных публикациях по теме диссертации научному руководителю принадлежат постановки исследуемых задач и некоторые теоретические результаты. В работах [1717] и [1818] Курганской О.В. принадлежит результаты по диаграммному представлению транслирующей ПОФ. В работе [1256] Королькову Ю.Д. принадлежат методические и технологические вопросы, связанные с организацией учебного процесса. Все результаты по разработке и реализации алгоритмов принадлежат автору лично.

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

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

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

2. Инструментальное средство – компонент синтеза транслирующих программ – для конструирования транслирующих позитивно-образованных формул, а также применения этих формул в составе прикладных программ.

3. Постановка и схема решения задачи контроля диалога человека и объектной программы на основе формальной спецификации требований к диалогу двухуровневой иерархией формальных языков, каждый из которых задается ПОФ. Задача контроля диалога решена применением КСТП.

библиографии и двух приложений. Общий объм диссертации – 123 страниц.

Библиография включает 103 наименования. Работа иллюстрирована рисунками и содержит 4 таблицы.

Глава 1 посвящена постановке и схеме решения задачи трансляции на основе логического вывода в частном случае конструктивного фрагмента исчисления позитивно-образованных формул. В пункте 1.1. приводится описания языка позитивно-образованных формул и построенного в данном языке исчисления. Язык ПОФ является языком первого порядка. Исчисление ПОФ состоит из одного правила вывода. Суть доказательства ПОФ – ее последовательное преобразование с помощью правила вывода. Пункт 1. посвящен доказательству существования транслирующих программ в исчислении ПОФ. Под транслирующей программой понимается программа, которая принимает на вход цепочку символов (исходный код), представленную на одном языке, и преобразует е в выходную цепочку символов (объектный код) на другом языке. Пункт 1.3 посвящен описанию подмножества языка ПОФ и выделению частного случая конструктивного фрагмента исчисления позитивно-образованных формул для решения задач трансляции. Основу частного случая конструктивного фрагмента составляют формулы из описанного подмножества языка ПОФ, стандартное правило вывода [22] и новая стратегия вывода, необходимая для учета особенностей задач трансляции. В п.1.4 введено понятие транслирующей позитивно-образованной формулы и представлена принципиальная схема решения задач трансляции на основе исчисления позитивно-образованных формул. Принципиальная схема решения задачи трансляции основана на идее автоматического синтеза программ [24, 27, 32, 61, 63, 70 с. 242, 93, 94, 103], когда транслирующая программа строится доказательством теоремы ее существования из заранее подготовленного комплекта транслирующих подпрограмм.

В главе 2 приведены алгоритмы построения распознающих позитивнообразованных формул по заданным грамматикам: регулярной правосторонней детерминированной грамматике и LL(1)-грамматике. Для этих грамматик доказана эквивалентность доказательства теоремы существования транслирующей программы преобразованиями распознающей позитивнообразованной формулы и грамматического вывода.

В главе 3 представлено инструментальное средство – компонент синтеза конструирования транслирующих позитивно-образованных формул на основе регулярных правосторонних детерминированных и LL(1)-грамматик, а также применения этих формул в составе прикладных программ. В п. 3.1 разработаны условия и схема применения компонента. Компонент синтеза транслирующих программ (КСТП) обеспечивает: конструирование и испытания на примерах доказательство существования транслирующей программы для заданной входной цепочки языка, синтез и исполнение транслирующей программы при исполнении прикладной программы. Компонент может быть внедрен в инструментальную среду разработки на платформе.Net и использован в прикладной программе на любом из доступных языков программирования для платформы.Net [53, 62, 90]. Пункт 3.2 посвящен организации данных и диалоговому интерфейсу КСТП. Основу КСТП составляют объектные представления транслирующей ПОФ и формальной грамматики.

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

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

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

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

В соответствии с решением коллегии ФТС России средство таможенного контроля Терминал принято к экспериментальному опробованию в составе новой технологии контроля лесоматериалов необработанных (О распространении системы электронного поштучного учета. Письмо ФТС России от 11 марта 2008 №01-11/9055) Глава 1. Синтез транслирующих программ на основе позитивно-образованных формул Поиски систематических методов программирования, обладающих свойством доказательности, имеют уже достаточно длительную историю, восходящую к первым дням электронной вычислительной техники [32]. Среди современных видов доказательного программирования широкое применение получили следующие направления:

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

Одни из первых работ в области синтеза программы были выполнены Саймоном и Грином [70 с. 227], а также Манна и программ касались формального синтеза алгоритмов и основывались на идее высказанной Саймоном [61, с. 428]. Общий замысел идеи состоит в том, что должна быть доказана теорема с утверждением, спецификации». Если удается ограничить это доказательство конструктивной формой, то появляется возможность извлечь из результатов доказательства требуемую программу.

В синтезе программ существуют различные подходы, среди которых структурный синтез [44,63].

2. Планирование вычислений. Под планированием вычислений понимается планирование вычислительного процесса при решении прикладных задач. Данное направление сформировалось на основе исследований в части поиска решений в пространстве состояний, доказательства теорем и теории управления, а также на основании практических потребностей робототехники, составления расписаний и других проблемных областей [61, с. 554].

Наиболее заметными результатами в части планирования вычислений является применение булевого моделирования [50, 96], а также конструктивного фрагмента исчисления позитивнообразованных формул (ПОФ) [22, 26, 27, 80, 104] при решении специальных задач планирования вычислений и управления.

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

Данная глава посвящена одной из частных задач, которая может быть решена методами синтеза программ и планирования вычислений, – задаче трансляции. При решении задач трансляции метод синтеза программ представлен атрибутными грамматиками. Техника атрибутных грамматик существенно развита в системе логического программирования Prolog[91] и системе автоматического синтеза программ ПРИЗ[63].

Задачи трансляции привлекательны не только тем, что являются одной из основ практически всех технологий программирования, но и возможностью их эффективного применения при решении прикладных задач. При решении прикладных задач определенную популярность получили две модели теории трансляции – регулярные выражения и конечные автоматы. Наиболее программирования Perl4 [37] и командный интерпретатор операционных Основной особенностью языка Perl считается богатый набор команд для работы с текстом, в том числе реализованных в виде регулярных выражений систем семейства Unix5 [3 с. 166, 58]. Наиболее распространенными прикладными областями для конечных автоматов являются тестирование программирование [31, 33, 74, 75]. Успешность и популярность этих разработок объясняются в первую очередь наличием механизмов относительно простого применения моделей и методов трансляции в составе прикладных программ.

Известны и другие применения методов трансляции при решении прикладных задач (например, [35 с. 125, 43, 54, 63 c. 241,82, 83, 88, 89]).

Разработанные в диссертации механизмы синтеза прикладных программ обеспечивают при решении прикладных задач синтетическое применение имеющегося базиса прикладных подпрограмм и моделей трансляции, более грамматиками и конечными автоматами. Эти механизмы по своей сути являются вариантом реализации концепции пакетов знаний [28] на основе спецификации прикладных задач позитивно-образованными формулами (ПОФ).

Ниже в п.1.1 приводится описания языка позитивно-образованных формул и построенного в данном языке исчисления. Язык ПОФ является языком первого порядка. Формулы языка ПОФ имеют древовидную структуру с вершинами в виде кванторов всеобщности или существования. Исчисление ПОФ состоит из одного правила вывода. Суть доказательства ПОФ – ее последовательное преобразование с помощью правила вывода.

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

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

В п.1.3 описано подмножество язык ПОФ и представлен частный случай конструктивного фрагмента исчисления позитивно-образованных формул для решения задач трансляции. Описанное подмножество языка ПОФ содержит формулы, пригодные для решения задачи трансляции. Основу конструктивного фрагмента составляют: стандартное правило доказательства позитивнообразованных формул [22] и новая стратегия вывода, необходимая для учета особенностей задач трансляции.

В п.1.4 введено понятие транслирующей позитивно-образованной формулы и представлена принципиальная схема решения задач трансляции на основе исчисления позитивно-образованных формул. Принципиальная схема основана на идее автоматического синтеза программ [28, 63, 93, 94, 103], когда транслирующая программа строится из заранее подготовленного комплекта транслирующих подпрограмм (шаблонов команд запуска транслирующих подпрограмм) на основе доказательства теоремы существования транслирующей программы.

1.1. Язык и исчисление позитивно-образованных формул Введем язык ПОФ L и исчисление данного языка J.

Язык L – полный язык первого порядка. Алфавит языка L – множество символов следующих видов[105]:

x, y, z, … – символы, обозначающие переменные;

+, -, f, g, … – функциональные символы различной арности;

, =, A, B … – предикатные символы различной арности;

(, ) – запятая, скобки (для уточнения строения формул);

Атомы языка L имеют вид R (t1,...,tk ), где R k – предикатный символ арности, a каждая t i, i 1...k – переменная или константа. Примерами атомов пропозициональные константы T (истина) и F (ложь) – являются конъюнктами в языке L.

Элементарные формулы языка L имеют вид:

где X – множество переменных, A – конъюнкт.

как конъюнктивное.

как дизъюнктивное.

Основными особенностями формул языка L являются [105, с. 13716]:

Любая формула, записанная на языке L, имеет крупноблочную структуру, все элементы которой позитивные кванторы;

классического исчисления предикатов первого порядка;

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

T{, X : A } [22 с. 137, 23], т.е.

-формул принадлежащих языку L.

Логический вывод ПОФ в исчислении J представляет собой цепочку она невыводима.

следующие [105, с. 13717]:

Техника вывода (опровержения) формул языка L анализирует ближайшую окрестность корня ПОФ – базу и вопросы к базе. Это позволяет сфокусировать внимание на локальном фрагменте ПОФ без потери свойства полноты вывода;

терминов формальной выводимости;

Техника вывода хорошо совместима с эвристиками конкретных приложений, а также общими эвристиками управления выводом;

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

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

Синтез программ – это научное направление, отличительная особенность которого заключается в построении программы на основе доказательства вычислений понимают разновидность синтеза программы G на основе заранее заданного комплекта базисных подпрограмм G1,, Gn [24].

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

Теорема о существовании синтезируемой программы [21, 22, 63] на узком языке исчисление предикатов имеет вид программ, а формулы R1 X 1, Y1,, Rn X n, Yn, R X, Y - их постусловий. В случае спецификациями транслирующих подпрограмм.

Если теорема (1.1.1) доказана, то из этого доказательства и шаблонов команд запуска базисных подпрограмм G1,, Gn, связанных с определенными элементами доказательства, строится транслирующая программа.

Доказательство существования синтезируемой программы эквивалентно доказательству тождественности формулы (1.1.1) или противоречивости отрицания этой формулы. Перепишем теорему о существовании синтезируемой программы (1.1.1) в виде ПОФ:

1. Построим и преобразуем отрицание формулы (1.1.1).

2. Спустим отрицание в S непосредственно до атомов.

3. Переписав полученную формулу H & S ' в символике ПОФ, имеем Формула (1.1.2) является теоремой существования транслирующей программы записанной в виде ПОФ.

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

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

Формула вида (1.1.2) должна иметь хотя бы одну переменную вывода.

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

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

В случае разбора входной цепочки слева направо по одному символу и ограничения входной строки C c1...c n справа специальным символом конца входной строки #, спецификация транслирующей программы имеет вид символизирующий разбор соответствующей языковой конструкции, P c1, u атом, символизирующий возможность разбора входного символа c1, последнем случае механизм трансляции на основе ПОФ обеспечивает диагностирование ошибки во входной строке и/или исправление ошибки. Все это осуществляется исполнением соответствующей транслирующей подпрограммы.

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

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

алфавит терминальных символов, V N – множество нетерминальных символов, P – конечное множество правил, S – аксиома грамматики. Определим G следующим образом:

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

трансляции цепочки C 80.7 в грамматике G имеет вид (1.1.3).

Поясним элементы формулы (1.1.3). Часть вопросов ПОФ построена по s : P(ц, s), Q( A) : R(ц, s), Q( A), где: атом P ц, s означает, что обобщенный терминальный символ ц VT находится в позиции s исходной цепочки C и может быть разобран, атом Q A означает, что нетерминальный символ A VN разобран, атом R ц, s означает, что обобщенный терминальный символ ц VT находится в позиции s исходной цепочки C и успешно разобран. Другая часть s : s 3, R(., s) : s 4, P(7, s), PT (# ) построены по первым трем символам входной цепочки, где атом PT #, означает что терминальный символ конца соответствует начальному состоянию разбора, она построена по аксиоме соответствует окончанию разбора и построен по символу конца входной цепочки, где атом RT #, означает что терминальный символ конца строки # разобран.

Символ ц является обобщенным терминальным символом и служит для обозначения цифр [36] Алгоритм построения формул вида (1.1.3) по заданной грамматике подробно описан в главе 2 настоящей работы.

Доказательство формулы (1.1.3) представлено ниже в п. 1.3.

1.3. Конструктивный фрагмент исчисления позитивнообразованных формул для решения задач трансляции Определим подмножество языка L . Формулы данного подмножества имеют специальный вид (1.1.4) и предназначены для решения задачи трансляции. Формула вида (1.1.4) – это уточнение формулы вида (1.1.2) для решения задачи трансляции.

Часть : T в начале формулы необходима для построения дизъюнктивного ветвления при доказательстве ПОФ.

Q Z и EOP().

Атом RT t означает, что терминальный символ t VT успешно разобран.

Атом R t, s означает, что терминальный символ t VT находится в позиции s исходной цепочки C и успешно разобран. Аналогично, атомы PT t и P t, s означают, что терминальный символ t VT находится в позиции s исходной цепочки C и может быть разобран. Атом Q Z означает, что нетерминальный символ Z V N разобран. Атом EOP() означает, что разбор цепочки C доказательством формулы F успешно завершен.

Далее формулу U B будем называть базой ПОФ, а конъюнкты, составляющие U Q, будем называть вопросами ПОФ.

Далее формулы вида (1.1.4) будем называть распознающими позитивнообразованными формулами.

Напомним, доказательство позитивно-образованной формулы представляет собой ее многократные преобразования по правилу [22].

Применение правила заключается в поиске подходящего вопроса в U Q и соответствующей обработке базы U B. В нашем случае параметрами однократного применения правила являются ответная подстановка :u s и один из вопросов Q части U Q формулы (1.1.2).

Рассмотрим один из вариантов решения задачи трансляции:

При описании структуры цепочки используются нетерминальные и терминальные символы;

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

Конец входной цепочки обозначен специальным терминальным символом;

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

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

Элемент стратегии заключается в разделении базы U B позитивнообразованной формулы F на два конъюнкта – конъюнкт синтеза и конъюнкт вывода. Конъюнкт синтеза K S составляют атомы уже использованные при пополняется новыми атомами из конъюнкта вывода, а в конъюнкт вывода копируется постусловие обрабатываемого вопроса7. Формальные параметры постусловия при этом должны быть заменены переменными вывода в составляющих конъюнкт данного вопроса. Критерием применимости правила к данному вопросу является принадлежность каждого атома предусловия вопроса, обработанного ответной подстановкой, конъюнкту вывода.

приписывания к конъюнкту вывода только слева.

заключается в следующей обработке ПОФ:

Под обрабатываемым вопросом понимается вопрос, к которому было применено правило вывода.

вопроса Q в конъюнкт вывода K D в случае принадлежности атомов, составляющих конъюнкт предусловия обрабатываемого вопроса Q предусловия обработанного вопроса Q из конъюнкта вывода K D в конъюнкт синтеза K S в случае принадлежности атомов, составляющих конъюнкт предусловия обрабатываемого вопроса Q, конъюнкту вывода будем называть выполнением вопроса Q.

недоказуемость распознающей ПОФ. Случай, когда конъюнкт вывода содержит F, означает, что распознающая позитивно-образованная формула успешно доказана. Если по правилу найден более чем один вопрос, то формула преобразуется к виду с дизъюнктивным ветвлением баз (по одной на каждый вопрос).

Вернемся к примеру (1.1.3). При доказательстве имеет место следующая последовательность значений8 конъюнкта вывода K D в составе базы U B :

Разделяющий символ - служит для обозначения шага логического вывода ПОФ.

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

где: P – имя обрабатывающей (транслирующей) подпрограммы, b – входная переменная транслирующей подпрограммы, a – выходная переменная. В качестве входных и выходных переменных используются переменные вывода позитивно-образованной формулы и текущий элемент входной цепочки. Если транслирующая подпрограмма не возвращает значение, то нелогический элемент принимает вид [P(b)].

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

Далее формулы вида (1.1.4) с нелогическими элементами будем называть транслирующими.

Рассмотрим пример. Пусть требования к входным цепочкам заданы LL(1)-грамматикой G

A CB B CB B C ED D *ED

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

Теорема существования транслирующей программы для трансляции цепочки C i i в грамматике G имеет вид (1.1.5). Алгоритм построения ПОФ по LL(1)-грамматике подробно описан в главе 2 настоящей работы.

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

: T u:u 1,P(i, u ), Q( A)[u START()], EOP()[FINISH()] s : P(*, s ), Q( D) : R(*, s ), Q( E ), Q( D)[mult()] Команда запуска транслирующей подпрограммы строится из ее шаблона, в который при необходимости подставляются переменная вывода и значение текущего символа входной цепочки.

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

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

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

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

Транслирующая программа исполняется в объектной среде, представленной на рис. 1.1. Напомним, что в состав позитивно-образованной формулы включена входная цепочка i i. В объектной среде входная цепочка из рассматриваемого примера представлена коллекцией (рис.1.1). Транслирующая программа обеспечивает исполнение распознанной входной цепочки из трех лексем со значениями 0.34, + и 7.5. Дескрипторы этих лексем i, +, i соответственно.

Описание транслирующих подпрограмм, использованных в формуле на (1.1.6), приведено в таблице 1.1.

Рис. 1.1. Основные элементы объектной среды для исполнения транслирующей программы примера. Схема работы транслирующей подпрограммы push Успешное доказательство транслирующей ПОФ означает существование Синтезированная в процессе доказательства транслирующая программа имеет вид:

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

Подпрограмма инициализации процесса трансляции.

1 u=START();

Создает стек, присваивает начальное значение переменной Подпрограмма завершения процесса трансляции. Выводит 2 FINISH();

Подпрограмма увеличения на единицу значения переменной 3 u=Plus1(u);

4 push(u);

5 add();

6 mult();

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

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

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

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

Это один из основных результатов диссертационной работы, который выносится на защиту. Результат опубликован в [17-20].

Глава 2. Регулярные и LL(1)-грамматики.

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

С помощью формальной грамматики описывают множество цепочек символов, составляющих формальный язык. Далее формальную грамматику преобразуют в распознающий автомат, а автомат – в программу трансляции. Преобразование распознающего автомата в транслятор можно автоматизировать. На этом построена индустрия так называемых компиляторов компиляторов [36, 48].

Классификация формальных грамматик и соответствующих им распознающих автоматов была выполнена Хомским [68] при изучении естественных языков. Разработчики трансляторов языков программирования для описания лексики и синтаксиса часто используют нормальную форму Бэкуса-Наура [см., например 34].

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

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

Работа с регулярными грамматиками и остальными КС-грамматиками предполагает построение распознавателей. Способы построения данных распознавателей у каждого автора свои (например, [36, 48, 59]). Кроме этого построенные распознаватели отличаются друг от друга по алгоритму работы и структуре, так, например, распознаватели для регулярной грамматики не содержит символа конца строки, а распознаватели для LL и LR грамматик ведут работу со стеком.

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

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

В п.2.2. аналогичная работа выполнена для LL(1)-грамматик. Эти грамматики были выбраны для исследования в связи с их высокой практической значимостью и хорошей изученностью.

2.1. Распознающие позитивно-образованные формулы для регулярных правосторонних детерминированных символов V N, множеством правил P и аксиомой S [36]. Язык порождаемый данной грамматикой будем обозначать L(G).

При преобразовании правил грамматики в элементы распознающей ПОФ будем использовать обозначение. Оно символизирует преобразование то. Таким образом, последовательность символов грамматики K Q( A), RT (2),Q( B), RT (3),Q(C).

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

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

Обработка элементов входной цепочки9 C Для каждого символа исходной цепочки ci, i 1,, n 2 пополним Если входная цепочка состоит из одного символа (n=1), то он учитывается в разделе алгоритма Начальная установка и дополнительной обработки не требует.

Построенную таким образом формулу10 обозначим FR G, C и назовем распознающей позитивно-образованной формулой.

Распознающая позитивно-образованная формула FR G, C для решения задачи разбора строки C 80.7 в грамматике G имеет вид:

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

регулярной (автоматной) грамматики G и входной цепочки C формула FR (G, C ) доказуема тогда и только тогда, когда C L(G).

грамматического разбора цепочки C в грамматике G и последовательность Для упрощения записи корень позитивно-образованной формулы T здесь и далее будем опускать.

Отметим ряд свойств последовательности K значений конъюнкта вывода K D, порождаемых при доказательстве формулы FR G, C :

последовательности K содержит ровно один атом вида P t, s, Порождение элементов последовательности K детерминировано по построению формулы FR G, C и в силу детерминизма анализа, Соответствие между последовательностью вывода этой строки и состояниями базы U B ПОФ при доказательстве формулы FR G, C приведено в таблице 2.1.

Соответствие между последовательностью грамматического разбора цепочки 80.7 и состояниями конъюнкта вывода ПОФ В ходе доказательства базы индукции и индуктивного перехода рассматриваются следующие возможные случаи:

a. ни один шаг грамматического вывода невозможен;

b. текущий шаг грамматического вывода возможен, он успешно c. текущий шаг грамматического вывода возможен, за ним, по меньшей Случай (a).

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

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

цепочка. Тогда формула FR (G, C ) U B U Q имеет вид:

Справедливо и обратное. Если вывод формулы прекращен в состоянии K D конъюнкта вывода K D, то по построению формулы FR (G, C ) нет правила грамматики, которое можно было бы применить для разбора символа c1.

С c1. Значит, примененное для разбора правило грамматики имеет вид s : P(c1, s), PT (# ), Q(S ) : RT (# ). Этот вопрос будет выполнен, новое выполнен вопрос RT (# ) : F, который завершит доказательство формулы, при формула F (G, C) доказана.

Проиллюстрируем данный случай примером. Пусть дана грамматика строка. Формула FR (G, C ) имеет вид:

осуществляется последовательным выполнением приведенных выше вопросов, Случай (с). Текущий шаг разбора возможен, за ним, по меньшей мере, пункту 3.1 алгоритма, среди вопросов U Q формулы FR (G, C ) имеют место вопросы будут последовательно выполнены. Новое состояние конъюнкта вывода K D примет вид при доказательстве последовательно была применена рассмотренная выше пара вопросов, то по построению формулы FR (G, C ) имеется правило Проиллюстрируем данный случай примером. Пусть дана грамматика строка. Формула FR (G, C ) имеет вид:

состояний конъюнкта вывода формулы FR (G, C ) при ее доказательстве имеет Случай (а). Справедливость случая (а) доказывается точно так же, как и для базы индукции.

Случай (b). Текущий шаг разбора возможен, он завершает разбор, то пункту 2.2 и пункту 2.3 среди вопросов U Q формулы FR (G, C ) имеют место последовательно выполнены, новое состояние конъюнкта вывода примет вид u : u n, F. Это означает, что формула FR (G, C ) доказана.

Справедливо и обратное. Завершение последовательности вывода принадлежность одному из элементов последовательности K D,, K D атома P(cn, n), а это, свою очередь, означает применение правила грамматики вида c n, которое и завершает разбор.

Проиллюстрируем случай примером. Пусть дана грамматика десятичных строка. Формула FR (G, C ) имеет вид:

последовательность состояний конъюнкта вывода формулы FR (G, C ) при ее доказательстве имеет вид Случай (с). Справедливость случая (с) доказывается точно так же, как и для базиса индукции.

исходной строки C и последовательностью состояний конъюнктов вывода при доказательстве формулы FR (G, C ) и означает справедливость утверждения 2.2. Распознающие позитивно-образованные формулы для Алгоритм построения позитивно-образованной формулы F для LL(1)грамматики похож на алгоритм из п.2.1. Он также включает начальную установку, обработку правил грамматики G и обработку элементов входной цепочки C.

Обработка правил грамматики G.

(см. приложение 1 к настоящей работе). Для каждого правила вида Обработка элементов входной цепочки C.

распознающей позитивно-образованной формулой.

A CB B CB B C ED D *ED

Обработка правил грамматики:

U Q вопросами: s : P(, s), Q( B) : R(, s), Q(C), Q( B) соответствующими вопросами: s : P(i, s), Q( A) : P(i, s), Q(C), Q( B) данный пункт пропускается.

соответствующими вопросами: s : PT (# ), Q( B) : PT (# ) Обработка элементов входной цепочки C i i:

Таким образом, распознающая ПОФ для грамматики G будет иметь следующий вид:

Рассмотрим вопрос связи доказательства распознающей ПОФ с выводом цепочки в LL(1)-грамматике, для этого докажем утверждение.

Утверждение 2. Для всякой LL(1)-грамматики G и исходной цепочки C грамматического разбора цепочки C в грамматике G и последовательность U 0,,U m состояний базы U B при доказательстве формулы FLL G, C.

соответствующих им состояний базы данных U B. Положим, что соответствие порождаемых при доказательстве формулы FLL G, C :

особенностями ее доказательства всякий элемент последовательности либо PT #. Исключения составляет последний шаг доказательства;

заданного LL(1)-грамматикой.

Вернемся к рассмотрению ПОФ 2.2.1. Покажем соответствие между вывода этой строки и состояниями базы данных ПОФ при доказательстве формулы FLL G, C приведено в таблице 2.2.

Соответствие между последовательностью вывода цепочки в LL(1)-грамматике и состояниями ПОФ Таблица 2.2.

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

успешным шагом, дальнейший разбор не возможен.

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

Случай (а).

Пусть ни один шаг грамматического разбора не возможен. Это означает, что в части U Q формулы FLL G, C по ее построению нет ни одного прекращено в состоянии U 0 базы U B, то по построению формулы применить для разбора символа c1.

Проиллюстрируем данный случай примером. Рассмотрим грамматику Очевидно, что C L(G) и нет ни одного вопроса, который мог бы быть Случай (b).

имеет вид S c1. По построению формулы FLL G, C согласно пункту обработки правил грамматики G среди вопросов U Q формулы FLL G, C Согласно пункту 2 обработки элементов исходной строки при построении формулы FLL G, C среди вопросов U Q формулы FLL G, C имеют место последовательно выполнены. Это означает, что формула FLL G, C доказана. Справедливо и обратное. Если доказательство формулы FLL G, C осуществлено выполнением указанных выше трех вопросов, то Проиллюстрируем данный случай примером. Рассмотрим грамматику последовательность состояний конъюнкта вывода при ее доказательстве Случай (c).

использованного на данном шаге грамматического разбора правила грамматики G :

согласно пункту 1 обработки правил грамматики G и пункту обработки элементов исходной строки среди вопросов U Q формулы имеет вид s : s 2, P c2, s, Q(Z ),[ ], EOP(). Справедливо и обратное, если при доказательстве формулы FLL G, C была последовательно применена указанная выше пара вопросов, то по ее построению вид:

FLL (G, C ) при ее доказательстве имеет следующий вид, согласно пункту 2 обработки правил грамматики G среди вопросов Справедливо и обратное.

доказательстве имеет вид правил грамматики G среди вопросов U Q формулы FLL G, C имеет вопрос будет выполнен. Новое состояние базы данных U B имеет вид обратное.

доказательстве имеет вид Справедливость случая (a) доказывается точно так же, как и для базиса индукции.

Случай (b).

правил грамматики G и пункту 2 обработки элементов исходной строки среди вопросов U Q формулы FLL G, C имеют место вопросы : PT (# ), EOP() : F и они будут последовательно выполнены. Это означает, что формула FLL G, C доказана.

C i i;. Тогда формула FLL (G, C ) U B U Q имеет вид:

доказательстве имеет вид правил грамматики G и пункту 2 обработки элементов исходной строки среди вопросов U Q формулы FLL G, C имеют место вопросы последовательно выполнены. Это означает, что формула FLL G, C доказана.

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

Случай (c).

FLL G, C согласно пунктам 1 и 3 обработки правил грамматики G и пункту 1 обработки элементов исходной строки среди вопросов U Q данных U B после выполнения последнего вопроса имеет вид F G, C согласно пункту 2 обработки правил грамматики G среди согласно пункту 2 обработки правил грамматики G среди вопросов вопрос будет выполнен. Новое состояние базы данных U B имеет вид s : P c j 1, s, Q( Z1 ), Q( Z 2 ),....,Q( Z h ), RT (c j 1 ),[ ], EOP(). Справедливо и обратное.

FLL G, C согласно пункту 4 обработки правил грамматики G среди вопросов U Q формулы FLL G, C имеет место вопрос обработки правил грамматики G среди вопросов U Q формулы Эти вопросы будет выполнен. Новое состояние базы данных Проиллюстрируем этот случай примером. Рассмотрим грамматику

A CB B CB B C ED D *ED

цепочку C (i) i. Тогда формула FLL (G, C ) U B U Q имеет вид:

u : u 1, P((,u ), Q( A), EOP() Вывод входной цепочки имеет вид а последовательность состояний конъюнкта вывода при ее доказательстве имеет вид Справедливо и обратное. Среди элементов последовательности состояний U r 1,U r 2, базы данных формулы FLL G, C по ее построению найдется выполнением вопросов к базе данных, построенных по правилу исходной цепочки C и состояний базы данных U при доказательстве формулы FLL G, C означает справедливость утверждения 2.

В данной главе представлены алгоритмы построения распознающих позитивно-образованных формул для формальных грамматик 2 и 3 классов по Хомскому: регулярной правосторонней детерминированной грамматике и LL(1)-грамматике.

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

Применение логического подхода к задаче разбора и преобразования входной цепочки позволяет унифицировать различные модели трансляции. Как известно [3], они различаются наличием или отсутствием символа конца входной цепочки и различной структурой распознающих автоматов: от детерминированного конечного автомата до нескольких разновидностей автоматов с магазинной памятью, имеющих разное количество стеков, различные интерпретации элементов таблиц переходов и т.п. Правило конструктивного фрагмента исчисления ПОФ является основой такой унификации. Это продемонстрировано на примере двух грамматик – регулярных грамматик и LL(1)-грамматик.

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

Этот результат опубликован в [17-20].

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

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

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

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

Данная глава посвящена инструментальному средству конструирования и применения в составе прикладных программ транслирующих позитивнообразованных формул. Инструментальное средство выполнено в виде компонента. Под компонентом понимается объект, доступный прикладной программе при ее исполнении, а системе визуального объектноориентированного программирования при проектировании прикладной программы [73 с. 24].

Глава состоит из трех пунктов:

В п. 3.1 разработаны условия и схема применения компонента.

предназначен для конструирования и испытания на примерах транслирующих ПОФ при проектировании прикладной программы, доказательства существования транслирующей программы для заданной входной цепочки языка, а также синтеза и исполнения транслирующей программы в режиме исполнения прикладной программы. Компонент может быть внедрен в инструментальную среду разработки на платформе.Net и использован в прикладной программе на любом из доступных программных языков среды разработки на платформе.Net [53, 62, 90].

представления транслирующей ПОФ и формальной грамматики.

Элементами объектного представления транслирующей ПОФ сущности: транслирующая ПОФ в целом, входная и выходная подпрограммы с командами запуска, атомы, переменные вывода и формальной грамматики составляют класс контекстно-свободных грамматик и его наследники – классы регулярных и LL(1)грамматик.

Пункт 3.3 содержит выводы по данной главе.

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

КСТП обеспечивает:

Конструирование транслирующих ПОФ. Транслирующие позитивнообразованные формулы конструируются в диалоговом режиме с помощью специального редактора. Особенностью конструирования ПОФ является возможность автоматического построения ее части на основе заранее подготовленной регулярной или LL(1)-грамматики по алгоритмам, описанным в п.2.1 и п.2.2.

Тестирование транслирующих позитивно-образованных формул.

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

Доказательство существования транслирующей программы для заданной входной цепочки языка. Доказательство транслирующей программы инициируется методами КСТП во время исполнения пользовательского приложения. Результатом доказательства является конъюнкт синтеза.

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

Исполнение транслирующей программы. Исполнение транслирующей программа может быть исполнена после завершения или по мере ее Общая схема применения КСТП в пользовательском приложении представлена на рис. 3.1. Согласно схеме, экземпляр компонента встраивается в пользовательское приложение, разрабатываемое в одной из инструментальных сред разработки платформы.NET, дополняя приложение своими свойствами и конструирования и использования транслирующей ПОФ.

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

Результат исполнения транслирующей программы КСТП записывает в выходную цепочку.

Применение компонента для выполнения синтаксически-управляемой трансляции (лексического и синтаксического анализа) в проекте учебного транслятора основана на схеме, предложенной в [3 с. 168 ]. Используемая схема приведена на рис. 3.2.

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

Среда разработки.Net

КСТП КСТП

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

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

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

Основу КСТП составляют объектные представления транслирующей ПОФ и формальной грамматики. Элементами объектного представления транслирующей ПОФ являются экземпляры классов, характеризующих следующие сущности:

Транслирующая программа;

Транслирующие подпрограммы, команды их запуска и другие данные, ассоциированные с транслирующими подпрограммами.

Атомы, переменные вывода, а также формальные параметры атомов.

Представленные выше экземпляры классов разносятся по коллекциям (см. например [1, 62]). Коллекции формируются, в частности, из атомов, составляющих конъюнкт, или из аргументов атома. Транслирующая ПОФ в целом представлена следующими коллекциями:

Переменных вывода при корневом кванторе существования ПОФ.

Атомов в составе конъюнктов вывода и синтеза в базе U B.

Каждый вопрос, в свою очередь, это совокупность коллекций:

Атомов в составе предусловия вопроса.

Атомов в составе постусловия вопроса.

Объектное представления формальной грамматики составляет класс контекстно-свободных грамматик и его наследники – классы регулярных и LL(1)-грамматик (рис. 3.3). Классы регулярных и LL(1)-грамматик отличаются друг от друга функциональными членами, предназначенными для контроля принадлежности конкретной грамматики соответствующему классу.

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

Диалоговый режим при применении КСТП обеспечивается штатными средствами инструментальной среды и собственными диалоговыми формами.

На рис. 3.4 и 3.5 приведены примеры диалога с применением штатных средств инструментальной среды.

Рис. 3.3. UML-диаграмма классов грамматик в КСТП Собственные диалоговые средства КСТП составляют четыре диалоговых формы:

1. Форма редактирования грамматик (рис.3.6). На форме вводятся множество терминальных символов, множество нетерминальных регулярной правосторонней детерминированной грамматике или подпрограмм (рис.3.7). На форме вводятся шаблоны команды запуска транслирующей подпрограммы и параметры запуска.

Также на форме вводится ссылка на подготовленный к исполнению код класса транслирующих подпрограмм. Класс наследуется от интерфейса КСТП ISubRutines, методы данного класса и являются реализацией транслирующих подпрограммами.

представления транслирующей ПОФ (рис. 3.8). На форме редактируются коллекции, составляющие транслирующую ПОФ – конъюнкт вывода, конъюнкт синтеза и вопросы ПОФ. Кроме этого 4. Форма сохранения результатов настроек транслирующей ПОФ в файл. Настройки сохраняются в виде XML-документа для последующей их загрузки в другой экземпляр КСТП.

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

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

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

Ниже представлен сравнительный анализ КСТП с другими средствами разработки трансляторов.

синтаксического анализа транслятора для задачи распознавания арифметических выражений КСТП можно применять в любой инструментальной среде визуального объектно-ориентированного программирования для платформы.Net. КСТП испытан в таких диалоговых средах как Visual Studio.Net 2005, Sharp Develop 2.2, Code Gear RAD Studio 2007.

Разработка компонента синтеза транслирующих программ составляет одно из защищаемых положений диссертационной работы. Данный результат опубликован в [17, 39-41, 56].

Севостьянова Д.В., Курганский В.И. Восходящий грамматический разбор на основе позитивно-образованных формул // Вестник Иркутского государственного университета. Материалы научной студенческой конференции, 2009 г. – С. 163- Jacques Cohen. Parsing and compiling using Prolog / Jacques Cohen, Timothy J. Hickey. – ACM Transactions on Programming Languages and Systems (TOPLAS). Volume 9 Issue 2, April 1987: –pp.125- Свойство Designer Форма Вызов диалога редактирования транслирующей Свойство Коллекция Предоставляет доступ для работы с входной InputString SynExecAfterProve Метод Synthesize Метод Execute Осуществляет исполнение синтезированной Свойство Коллекция Предоставляет доступ к вопросам ПОФ.

PCFQuery Свойство Коллекция Предоставляет доступ к конъюнкту синтеза.

Свойство Коллекция Предоставляет доступ к конъюнкту вывода.

PCFKprove GetOutputString BuildPCFbyGrm Свойство Коллекция Предоставляет интерфейс для задания RoutinesTmpl Свойство Atoms Коллекция Предоставляет интерфейс для работы с атомами.

Свойство Коллекция Предоставляет интерфейс для работы с SpecialTrSymbols Свойство Строка Предоставляет доступ для сохранения (загрузки) SettingsName Свойство Строка Предоставляет доступ для редактирования Description Свойство Строка Предоставляет доступ для редактирования Descriptor ProveStart ProveStep ProveEnd Основные функциональные члены КСТП ProveAbduk Метод Коллекция Возвращает результат исполнения Свойство Коллекция Элементы коллекции содержат пары, где указатель – значение типа delegate Colletion_SR Размещение КСТП в дизайнере формы Рис.3.4. Пример управления проектом приложения с применением экземпляров КСТП Рис.3.5. Редактирование текста учебного транслятора штатными средствами инструментальной среды Редактирование LL(1)-грамматики Нетерминалы Vn ABCDEF Правила грамматики Рис.3.7. Форма для редактирования шаблонов команд запуска транслирующих подпрограмм Редактор ПОФ Конъюнкт вывода Конъюнкт синтеза u:u=1,P(1,u),Q(A)[START()],EOP()[FINISH()] Вопрос №3. s:P(ц.1),Q(A) P(ц,s),Q(C),Q(B). Подстановка: u->s Рис.3.8. Непосредственное редактирование транслирующей ПОФ Глава 4. Примеры применения компонента синтеза транслирующих программ Большинство современных методов и нотаций программирования концентрируются на поиске и композиции функциональных компонентов, которые обычно выражаются в виде объектов, модулей, процедур [73, с. 25].

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

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

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

Данная глава посвящена применениям КСТП при решении двух практических задач.

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

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

4.1. Технология решения учебных задач трансляции Для разработки трансляторов и прикладных систем лингвистического обеспечения можно использовать обычные инструментальные средства, применяемые для создания программного обеспечения, такие как интегрированные среды разработки и программирования [например, 52]. Но создание трансляторов с использованием только этих средств очень трудоемкий процесс. Поэтому, для того чтобы сократить время, затрачиваемое на разработку и повысить качество программы, в дополнение к этим средствам могут использоваться специальные инструментальные средства разработки трансляторов.

Идея использования дополнительных инструментальных средств для разработки трансляторов, по-видимому, впервые предложена Тони Брукером в 1960 году при разработки языка Atlas Autocode [4]. Идея, предложенная Брукером, заключалась в генерации таблицы переходов автомата по формальной грамматике.

Современные средства разработки трансляторов значительно расширили идею Брукера. Выделяют следующие типы современных средств разработки трансляторов:

1. Генераторы лексических анализаторов. Данные генераторы строят лексические анализаторы, на основе правил регулярной грамматики.

Сгенерированный лексический анализатор представляет конечный автомат [66, 69]. Как правило, такие системы генерируют программный код, который может быть интегрирован в код, построенный генераторами синтаксических анализаторов. Примерами таких систем является lex, flex, JLex, YooLex [85].

2. Генераторы синтаксических анализаторов. Данные системы генерируют код синтаксических анализаторов, на основе правил формальной грамматики записанных, например, в виде БНФ [30]. В зависимости от типа формальной грамматики выделяют следующие разновидности синтаксических анализаторов:

Генераторы анализаторов восходящего разбора. Эти генераторы основаны на LR-грамматиках. Основой LR-анализатора является используется метод LALR [8]. Примерами таких генераторов являются YACC, Bison, Gold, GDK, PLY [85].

Генераторы анализаторов нисходящего разбора. Основу генератора составляет предикативный анализ. Основой предикативного анализа также является однозначная таблица переходов [67].

известному алгоритму [3]. Примерами таких генераторов являются LISA, Coco/R, ppCC, JavaCC, SLK, Tap [85, 102].

3. Средства синтаксически-управляемой трансляции. Такие системы позволяют создавать наборы программ, которые осуществляют обход дерева синтаксического разбора и генерируют промежуточный код. Код генерируется из атрибутов заложенных в грамматику [3 с. 280]. В качестве примера таких систем можно привести Kimwitu, The Memphis Tree Builder & TreeWalker Tool, ParseUnit, DESCARTES [41, 84, 85].

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

Примерами таких систем являются Twig, BEG, IBURG [3].

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

Примерами таких систем являются Berkeley ANalysis Engine, Oprimix, Pag [3, 85].

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

Примерами таких систем являются метаситема-САТУРН, COCKTAIL, ELI, GENTLE, PCCTS [49, 85].

компилятора позволяют построить редактор, ориентированный на определенный язык, отладчик, редактор структур и диалоговых интерфейсов. В качестве примера таких систем можно привести The Synthesizer Generator, Centaur, Synthesizer Generator, Eclipse [85].

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

Построить транслирующую программу человеку, имеющему опыт написания программ объемом несколько десятков команд, даже на основе хорошо проработанной математической модели представляется трудновыполнимой задачей. Вывод один — необходимы средства автоматизации решения учебных задач, не только соответствующие современному уровню в научно-техническом плане, но и обеспечивающие достижение учебных целей. Популярные средства автоматизации разработки транслирующих программ (например, [47 с.74, 76, 81, 85, 95, 98, 99, 100]) ориентированы на решение практических задач, но не обеспечивают достижения учебных целей в должном объеме. Большое количество Web-ресурсов, посвященных вопросам разработки трансляторов, и их содержание говорят о популярности вопросов математического моделирования языков и процессов трансляции в профессиональной, студенческой и аспирантской среде.

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

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

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

Все остальные действия, связанные с разработкой учебного транслятора, обеспечиваются штатными средствами среды разработки Visual Studio.Net [52].

Описание технологии решения учебных задач с использованием компонента представлено на рис. 3.2. Технология внедрена в Институте математики, экономики и информатики Иркутского государственного технологию, включает КСТП и зарегистрирован Иркутским государственным университетом в Федеральной службе по интеллектуальной собственности, патентам и товарным знакам [56].

Далее в п. 4.1.1 рассмотрим требования к учебным трансляторам и их структуру, а в п. 4.1.2 – пример учебного транслятора.

4.1.1. Учебные трансляторы. Требования и структура Рассмотрим технологию решения учебных задач трансляции более подробно. Учебная задача трансляции состоит из двух подзадач – задачи лексического анализа и задачи синтаксического анализа.

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

1. Разработка регулярной грамматики для распознавания заданного типа лексем (например, целочисленная константа, идентификатор и 2. Построение набора транслирующих подпрограмм (например, построение коллекции лексем или исправление ошибок во входной 3. Построение транслирующей ПОФ из заданной грамматики по приведенному в гл. 2 алгоритму.

4. Тестирование транслирующей ПОФ на примерах правильных и неправильных цепочек символов входной строки 5. Программная реализация лексического разбора входной строки с помощью методов, свойств и событий КСТП;

Таким образом, лексический разбор входной строки выполняется несколькими экземплярами КСТП. Результатом выполнения лексического разбора является коллекция (таблица) лексем с двумя полями – исходное представление и дескриптор лексемы. Например, в результате выполнения лексического разбора арифметического выражения вида 12.5 iVar * получится коллекция следующего вида:

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

Решение задачи синтаксического анализа заключается в настройке одного экземпляра КСТП на синтаксический разбор последовательности лексем.

Настройка состоит из следующих шагов:

1. Разработка LL(1)-грамматики для распознавания синтаксических 2. Построение набора транслирующих подпрограмм (пример комплект транслирующих подпрограмм приведен в таблице 1.1 гл. 3. Построение транслирующей ПОФ по приведенному в гл. 4. Тестирование транслирующей ПОФ на примерах правильных и неправильных цепочек символов входной строки.

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

4.1.2. Пример учебного транслятора Рассмотрим пример транслятора, вычисляющего десятично-дробные арифметические выражения. Транслятор разрабатывается в Visual Studio.Net.

Для управления транслятором используется диалоговая форма (рис.4.1), ее визуальное объектное представление на этапе проектирования приведено на рис. 4.2.

Рис. 4.2. Объектное представление диалоговой формы учебного транслятора Диалоговое окно транслятора и результат его работы представлен на рис.

4.1. Учебный транслятор обеспечивает лексический анализ входной цепочки литер из текстового элемента управления, помеченного элементом управления типа Label (Входная строка), размещение результата лексического анализа в коллекции лексем mColl, синтаксический анализ этой коллекции лексем и размещение результата трансляции в текстовом элементе управления, помеченного элементом управления типа Label (Выходная строка).

В программном проекте использовано два экземпляра КСТП tpoUnit1 и tpoUnit2. Первый компонент обеспечивает лексический анализ числовых констант с плавающей точкой на основе ПОФ приведенной в пункте 2. (формула 2.1.1) настоящей работы. Лексемы +, *, # распознаются с помощью метода Substring для строковых величин [62, c. 124].

коллекции mColl. LL(1)-грамматика, составляющая основу этого экземпляра КСТП, и соотвествующая транслирующая ПОФ приведены в пункте 2. (формула 2.2.1) настоящей работы. Класс транслирующих подпрограмм составляют шесть функций, все они реализуют операции работы со стеком.

Класс транслирующих подпрограмм имеет вид:

class SyntaxSubRutines : CTPOUnit.ISubRutines private Stack iSteck;

private int iInternalU;

public int START() iSteck = new Stack();

return iInternalU;

public void FINISH(ref ArrayList OUT_VAL) OUT_VAL.Add(m_COL.Pop().ToString());

public int Plus1() iInternalU++;

return iInternalU;

public void push(ref ArrayList IN_VAL) iSteck.Push(IN_VAL[iInternalU]);

public void add() iSteck.Push((int)iSteck.Pop() + (int)iSteck.Pop());

public void mult() iSteck.Push((int)iSteck.Pop() * (int)iSteck.Pop());

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

using System;

using System.Collections.Generic;

using System.ComponentModel;

using System.Data;

using System.Drawing;

using System.Text;

using System.Windows.Forms;

using System.Collections;

namespace WindowsApplication public partial class Form1 : Form public Form1() InitializeComponent();

TPOUnit.Lexemes mColl = new TPOUnit.Lexemes();

// обработка нажатия кнопки «Анализировать»

private void button1_Click(object sender, EventArgs e) for (int i = 0; i < textBox1.Text.Length; i++) if (iSemi.Contains(textBox1.Text.Substring(i, 1))) mColl.addLexeme(iLex, tpoUnit1.Descriptor);

mColl.addLexeme(textBox1.Text.Substring(i, 1), textBox1.Text.Substring(i, 1));

// обработка нажатия кнопки «Транслировать»

private void button2_Click(object sender, EventArgs e) SyntaxSubRutines iSRutines;

tpoUnit2. RoutinesTmpl = iSRutines; //ссылка на класс транслирующих подпрограмм tpoUnit2.InputString = mColl;

if (tpoUnit2.Prove() && tpoUnit2.Synthesize() && tpoUnit2.Execute()) textBox2.Text = tpoUnit2.GetResult().ToString();

MessageBox.Show("Входная строка отвергнута!", "Синтаксический анализ") 4.2. Контроль цепочек входных воздействий в диалоговой системе таможенного контроля Терминал Диалог в современных прикладных диалоговых системах зачастую представляет собой сложные цепочки взаимосвязанных входных воздействий, которые порождают различные виды событий. Штатные средства программирования обработки событий в современных системах объектноориентированного программирования не обеспечивают анализа контекста входного воздействия (см. например, [6]).

Первые попытки формально специфицировать входные воздействия в диалоговых системах появились в 80-х годах [86]. В работе [78] рассмотрен обзор различных моделей спецификации входных воздействий. Наибольшую популярность получила модель, основанная на формальных грамматиках и предложенная Рейснером [97]. Основная идея данной модели основана на трех тезисах [77]:

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

2. Представление последовательности входных воздействий в виде строки (например {BM_CLICK}{WM_SETFOCUS}{WM_SETTEXT});

3. Описание правильных (неправильных) последовательностей входных воздействий с помощью формальных грамматик.

В данном пункте предложена разновидность модели контроля входных воздействий с помощью регулярных и LL(1)- грамматик. Отличие заключается в использовании транслирующих ПОФ для моделирования разбора последовательности входных воздействий. Применение ПОФ позволяет решать более широкий спектр задач за счет возможности синтеза различных транслирующих программ. Использование методик искусственного интеллекта при контроле входных воздействий впервые предложена Янгом [106].

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

В соответствии с решением коллегии ФТС России средство таможенного контроля Терминал принято к экспериментальному опробованию в составе новой технологии контроля лесоматериалов необработанных13.

Далее в пункте 4.2.1 приведено назначение и структура диалоговой СТК Терминал. В пункте 4.2.2 рассмотрена логико-лингвистическая модель СТК Терминал. Пункт 4.2.3 посвящен реализации модели.

4.2.1. Назначение и структура диалоговой системы СТК Терминал предназначено для сбора учетных и контрольных данных о деятельности лесного склада. СТК представляет собой специальное вычислительно устройство – портативный терминал сбора данных (например, Minec4x или TDS Recon). Устройство базируется на специальной версии операционной системы Windows. Особенностью данных устройств является отсутствие приемлемого манипулятора курсором, поэтому управление вводом осуществляется с помощью кнопок на клавиатуре корпуса устройства.

Основная программная часть СТК Терминала разрабатывалась на платформе.Net Compact Framework в среде разработке MS Visual Studio.Net 2003 на языке C# [55], дополнительные программные библиотеки были разработаны отдельно в MS Visual eMbedded Tools 3.0 на языке C++ [2].

Диалог СТК Терминал состоит из 5 основных и 18 вспомогательных диалоговых форм. Рассмотрим основные формы подробно.

О распространении системы электронного поштучного учета. Письмо ФТС России от 11 марта 2008 №01Форма «Бревно». Данная форма предназначена для ввода характеристик бревен. Форма используется в четырех различных контекстах – для ввода данных о приемке, для ввода контрольных характеристик при контроле на складе, для ввода контрольных характеристик при контроле транспортного средства и для отображения данных об отгруженных в транспортное средство бревенах. Форму составляют 4 кнопки, 4 поля для ввода и 4 выпадающих списка (рис. 4.4).

характеристик штабеля. Форма используется в трех контекстах – для ввода данных о приемке, для ввода данных об отгрузке и для контроля транспортного средства. Форму составляют 4 кнопки, 11 полей для ввода и 1 выпадающий список (рис. 4.5).

3. Форма «Акт». Данная форма предназначена для ввода данных об актах приемки и отгрузки. Форма используется в двух контекстах – для создания акта приемки и для создания акта отгрузки. Форму составляют 5 кнопок, 2 поля для ввода и 1 список (рис. 4.6).

4. Форма «Акт контроля на складе». Данная форма предназначена для ввода данных об акте контроля бревен на лесном складе. Форму составляют 2 кнопки и 2 поля для ввода (рис. 4.7).

5. Форма «Акт контроля транспортного средства». Данная форма предназначена для ввода данных об акте контроля бревен и штабелей на транспортном средстве. Форму составляют 4 кнопки и 3 поля для ввода (рис. 4.7).

Рис. 4.4. СТК Терминал. Диалоговая форма «Бревно»

Рис. 4.5. СТК Терминал. Диалоговая форма «Штабель»

Рис. 4.7. СТК Терминал. Диалоговая форма «Акт контроля на складе»

форма «Акт контроля транспортного средства»

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

4.2.2. Логико-лингвистическая модель диалога Логико-лингвистическая модель состоит из комплекта транслирующих ПОФ. Основу каждой транслирующей ПОФ составляет регулярная или LL(1)грамматика. Особенностью применения грамматики является таблица обозначений. Таблица обозначений необходима для сопоставления входных воздействий терминальным символам грамматики.

Пример таблицы обозначений:

Как видно из таблицы входное воздействие составляют три элемента:

идентификатор объекта, идентификатор события и значение события. Под первым номером в таблице описано воздействие, которое происходит при вводе цифр в элемент управления IDC_NUMB, ему сопоставлен терминальный символ ц‘. Некоторые параметры входного воздействия для вырожденных случаем могут опускаться. Так, под вторым номером в таблице описано воздействие с двумя параметрами и ему сопоставлен терминальный символ a‘.

Таким образом, терминальные символы языка входных воздействий в диалоговой системе – это обозначения кортежей вида.

прописных символов (например, START, END и т.д.).

Суть логико-лингвистической модели диалога СТК Терминал – контроль правильных цепочек входных воздействий. Правильные цепочки входных воздействий в СТК Терминал описаны для основных диалогов и элементов управления с помощью регулярной или LL(1)- грамматик, а их контроль реализован в виде экземпляров КСТП. На рисунке 4.9. представлено два уровня логико-лингвистической модели диалога. Рассмотрим их подробно:

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

КСТП КСТП

КСТП КСТП КСТП КСТП КСТП КСТП КСТП

Рис. 4.9. СТК Терминал. Логико-лингвистическая модель Первый уровень – уровень формы. КСТП на данном уровне контролирует входные воздействия к элементам управления. Грамматики первого уровня самая сложная и включает большое число терминальных и нетерминальных символов. Например, на рис. 4.10 представлена упрощенная схема вызова формы «Бревно». Символы А, B, C, … на дугах схемы – терминальные символы. Таблица обозначений терминальных символов в данном случае имеет вид:

3 IDC_LOGTYPE WM_ SETFOCUS C