Инструментальное средство синтеза и исполнения транслирующих программ на основе позитивно-образованных формул тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат технических наук Бутаков, Михаил Игоревич

• Бутаков, Михаил Игоревич
• кандидат технических наук
• 2011

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

Введение.

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

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

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

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

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

1.5. Выводы

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

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

2.2. Распознающие позитивно-образованные формулы для 1Х( 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. Выводы .¡

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Бутаков, Михаил Игоревич

43. Выводы

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

Постановка и схема решения задачи контроля диалога человека и объектной программы составляет одно из защищаемых положений диссертационной работы. Данный результат опубликован в [11-19]. Получен акт о применении программного средства для контроля входных воздействий в составе СТК Терминал (см. приложение 2 к настоящей работе).

Заключение

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

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

Рассмотрим некоторые варианты использования КСТП в прикладных программах: ,

1. Учебные трансляторы. КСТП согласно схеме, приведенной в [3 с. 168], можно использовать для создания несложных трансляторов. Настройка КСТП происходит в диалоге и не требует дополнительного кода по обработке входной строки, в результате программный код учебного транслятора будет небольшим. Использование КСТП позволит учащимся быстро овладеть не одной-двумя, а более широким спектром: формальных грамматик, даже не разрабатывая учебных трансляторов.

2. Обработка входных воздействий в диалоговой системе. Диалог в современных прикладных диалоговых системах, как правило, представляет собой сложные цепочки вза и мое вяза иных входных воздействий. Штатные средства программирования обработки входных воздействий в современных системах объектно-ориентированного программирования не обеспечивают анализа контекста, в котором имеет место то или иное воздействие (см. например, [5]). В диалоговых системах входные воздействия представляют собой последовательности событий. С помощью КСТП можно разбирать последовательности таких событий, представляя их в виде входной цепочки. При выявлении некорректной последовательности событий (входной цепочки) КСТП может синтезировать сообщение об ошибке или код обработки данного сообщения.

3. Обработка запросов в \¥еЬ-приложениях. По аналогии с обработкой входных воздействий в диалоговой системе, КСТП можно использовать для обработки запросов пользователя на стороне сервера в \¥еЬ-приложениях. Результатом обработки запросов, например, может быть набор ссылок или программный код, обрабатывающий запросы.

4. Генерация справочного материала, Генерация текстов на естественном языке из заданных фрагментов является актуальной задачей [50, 59, 86, 87]. С помощью КСТП можно построить систему генерации контекстно-зависимой справки. Например, справку можно генерировать во время обработки входных воздействий пользователя в диалоговой системе. При этом транслирующие подпрограммы будут представлять собой фрагменты справочного текста. Доказательство транслирующей ПОФ позволит синтезировать справку, содержание и структура которой будут зависеть от последовательности предшествующих действий пользователя.

Приведенную идею синтеза программ на основе моделей трансляции и автоматического синтеза программ предполагается развивать в двух направлениях: Разработка алгоритмов построения транслирующих позитивно-образованных формул для других типов КС-грамматик (например, ЬЕ-грамматик, недетерминированных грамматик [78] и грамматик с количеством символов предпросмотра больше 1 [100]). Модификация алгоритма синтеза транслирующей программы. Представляется возможным и полезным разработать алгоритм синтеза ветвящейся и циклической транслирующей программы. Это позволит упростить технологию работы с транслирующей ПОФ за счет вывода из ее состава входной цепочки.

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

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

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

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

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

Список литературы диссертационного исследования кандидат технических наук Бутаков, Михаил Игоревич, 2011 год

1. Агуров П.В. (Ж Сборник рецептов / П.В. Агуров. -СПб.: БХВ-Петербург, 2007-432 с.

2. Астраханцев Ф.П. Разработка приложений для мобильных устройств на основе технологий Microsoft: Компьютерные инструменты в образовании / Ф.П. Астраханцев. СПб.: Изд-во ЦПО "Информатизация образования",2005.-№7. -С. 59-65.

3. Ахо А. Компиляторы: принципы, технологии и инструменты: Пер. с англ. / А. Ахо, Р. Сети, Д. Ульман. М.: Изд.дом «Вильямс»,2001. - 768 с.

4. Ахо А. Теория синтаксического анализа, перевода и компиляции / А. Ахо, Д. Ульман. М.:Мир, 1978, - 2 т.

5. Бабаев A.A. Автоматный интерфейс. Новый метод создания логики интерфейса Электронный ресурс. / A.A. Бабаев. RSDN Magazine №5,2005. http://www.rsdn.ru/article/UI/AutoUI.xml (12 мая 2006)

6. Бейзер Б. Тестирование черного ящика. Технологии функционального тестирования программного обеспечения и систем. СПб.: Питер, 2004. -318 с.

7. Бильгаева Н.Ц. Теория алгоритмов, формальных языков, грамматик и автоматов: Учебное пособие / Н.Ц. Бильгаева. Улан-Удэ: Изд-во ВСГТУ, 2000.-51 с.

8. Бутаков М.И. Учебный стенд по методам синтаксически управляемой трансляции / М, И. Бутаков. // Вестник Иркутского университета. Специальный выпуск: Материалы научно-теоретической конференции молодых ученых, посвященной 60-летию Великой Победы. Иркутск:

9. Изд-во Иркут. гос. Ун-та, 2005. С.49-51.

10. Бутаков М.И. Решение учебных задач трансляции на основе позитивно-образованных формул / М.И. Бутаков, О.В. Курганская. Системы управления и информационные технологии, 2008, 3.1(33). - С. 124-128.

11. Бутаков М.И. О решении задачи трансляции планированием вычислений на основе позитивно-образованных формул / М.И, Бутаков, В.И. Курганский. Системы управления и информационные технологии, 2007, N3.1(29). - С. 120-123.

12. Бутаков М.И. Об одной модели трансляции на основе позитивно-образованных формул / М.И. Бутаков, В.й. Курганский. Информационные технологии моделирования и управления, 2007,N6(40). -С.663-672.

13. Васильев С.Н. Вывод теорем на основе логических уравнений и типизации переменных / С. Н. Васильев. // Функции Ляпунова и их применение. Новосибирск: Наука, Сиб.отделение, 1987.

14. Васильев С.Н. Интеллектное управление динамическими системами / С.Н. Васильев и др.. М.: Физматлит, 2000. - 352 с.

15. Васильев С.Н. Интеллектное управление телескопом / С.Н. Васильев, Е.А. Черкашин. // Сибирский журнал индустриальной математики, т. 1, N0 2, 1998.-С. 81-98

16. Васильев С.Н. О логических средствах системы планирования вычислений «ПА САД» / С.Н. Васильев и др.. // Алгоритмы. Автоматизация программирования (Сборник научных трудов). Вып.66. - Ташкент: АН Уз.ССР, 1988. - С.97-112.

17. Васильев С.Н. Об исчислении типово- кванторы ых формул/ С.Н. Васильев, А.К. Жерлов. // ДАН. Т.343, № 2. - 1995. - С. 583-585.

18. Васильев С.Н. Методы и программные средства синтеза математических теорем / С.Н. Васильев. //Инструментальные системы и моделирование. -Новосибирск: Наука.Сиб.отд-ние, 1988. -С. 4-27.

19. Васильев С.Н. Интеллектный подход к автоматизации проектных расчетов сложный управляемых систем / С.Н. Васильев, Г.А. Опарин Н Оптимизация, управление, интеллект. — 2000. — Вып 4. С. 111-126.

20. Вилле К. Представляем С# / К. Вилле. М.:ДМК Пресс, 2001. - 192 с.

21. Гросс М. Теория формальных грамматик / М. Гросс, А. Лантен. М.: ИЗДАТЕЛЬСТВО «МИР», 1972. - 294 с.

22. Ершов А.Н. Научные основы доказательного программирования: Научн. Сообщ /' А.П. Ершов. //' Вестн. АН СССР, 1984, №10,- С. 9-19.

23. Канжелев С.Ю. Автоматическая генерация автоматного кода / С.10. Канжелев, A.A. Шалыто. Информационно-управляющие с и с тем ы.2006. № 6. - С.35-42.

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

25. Карпов Ю.Г. Теория автоматов Ю.Г. Карпов. Спб.: Питер, 2003. - 208 с.

26. Компаниец Р.И. Системное программирование. Основы построения трансляторов ./ Р.И. Компаниец, Е.В. Маньков, Н.Е. Филатов. //Учебное пособие для высших и средних учебных заведений. СПб.: КОРОНА принт, 2000. - 256 с.

27. Кристиансен Т. Perl. Сборник рецептов. Для профессионалов. 2-е изд. / Т. Кристиансен, И. Торки штон. СПб.: Питер, 2004. -- 928 с.

28. Кудрявцев Е.М. AutoLISP. Программирование в AutoCAD 14 / Е.М. Кудрявцев. М: «ДМК», 1999. - 568 с.

29. Курганский В.И. Лексический анализ на основе регулярных грамматик и конечных автоматов / В.И. Курганский, М.И. Бутаков. Иркутск: Иркут. гос. ун-т, 2006. - 20 с.

30. Курганский В.И. Математические модели лексического и синтаксического анализа для студентов младших курсов / В.И. Курганский, М.И. Бутаков. Обозрение прикладной и промышленной математики. Том 13, выпуск 3. - Москва: Изд-во «ОПиМП», 2006. - С. 7778.

31. Курганский В.И. Синтаксический анализ на основе LL( 1 Ьграмматик и автоматов с магазинной памятью / В.И. Курганский, М.И. Бутаков. -Иркутск : Иркут. гос. ун-т, 2006. 32 с.

32. Логика, Автоматы, Алгоритмы / М. А. Айзерман и др.; под ред. H.A. Королева. М.: Физматгиз, 1963. - 556 с.

33. Марчук Ю.Н. Основы компьютерной лингвистики. Учебное пособие / Ю.Н. Марчук. М.:Изд~во МПУ «Народный учитель», 2000. - 226 с.

34. Минц Г.Е. Полнота правил структурного синтеза /' Г.Е. Минц, Э.Х. Тыугу. // Докл. АН СССР. 1982. Т.265, № 6. -С.41-60.

35. M итички ii С. A. Практика программирование в среде 1С ¡Предприятие 7.7 / С.А. Митичкин. М.:Издательский Дом «КомБук». 2004 - 272 с.

36. Гайдышев И.П. Решение научных и инженерных задач средствами Excel, VBA и С/С++ / И.П. Гайдышев. — СПб. ^Издательство Б X В Пете р бу р г, 2004-512 с.

37. Мозговой М.В. Классика программирования: алгоритмы, языки, автоматы, компиляторы. Практический подход / М. В. Мозговой. -СПб.:Наука и Техника,2006. 320 с,

38. Молчанов АЛО. Системное программное обеспечение: Учебник для вузов / А. Ю. Молчанов. СПб. Литер, 2006. - 395с.

39. Опарин Г.А. К теории планирования вычислительного процесса в пакетах прикладных программ /' Г.А. Опарин. В. кн.: Пакеты прикладных программ. Методы и разработки. Новосибирск: Наука, 1981. -с. 5-20.

40. Рихтер Дж, Программирование на платформе Microsoft .Net Framework : Пер. с англ. / Дж. Рихтер. 2-е изд., испр. - М.: Издательско-торговый дом "Русская Редакция", 2003 - 512 с.

41. Румянцев М.И. К вопросу о построении лингвистической модели бизнесс-процессов коммерческого банка / М.И. Румянцев.не

42. Информационные технологии моделирования и управления, 2007,N6(40).- С.663-672.

43. Смит Родерик. Полный справочник по FreeBSD : Пер. с англ / Родерик Смит. М.: Издательский дом "Вильяме", 2005. - 672 с.

44. Соколов А.П. Системы программирования: теория, методы, алгоритмы; Учеб. Пособие / А.П. Соколов. МлФинансы и статистика, 2004. - 320 с.

45. Соколова Е.Г. Автоматическая генерация текстов на ЕЯ (портрет направления) Электронный ресурс. / Е.Г. Соколова, М.В. Болдасов. -. http://www.dialog-21 .ru/Archive/2004/Sokolova.htm (декабрь 2008)

46. Стюарт Рассел. Искусственный интеллект. Современный подход, 2-е изд.: Пер. с англ. / Рассел Стюарт, Порви г Питер. М. :Издателский дом «Вильяме», 2007. - 1408 с.

47. Троелсен. Э. С# и платформа .Net. Библиотека программиста / Э. Троелсен. СПб. Литер, 2004. --796 с.

48. Тыугу Э.Х. Концептуальное программирование / Э.Х. Тыугу. М.: Наука, 1984.-256 с.

49. Тэллес М. Наука отладки: Пер. с англ. /' М. Тэллес, Ю. Хеих. М.: КУДИЦ-ОБРАЗ, 2003. - 560 с.64.-

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

51. Хантер Р. Проектирование и конструирование компиляторов: Пер. с англ. Предисл. В.М. Савинкова / Р. Хантер. М.: Финансы и статистика, 1984 -232 с.

52. Хомский Н.О некоторых формальных свойствах грамматик / Н.О. Хомский. "Кибернетический сборник", вып. 5, ИЛ, 1962. - С.121-227.

53. Хопкрофт Д. Введение в теорию автоматов, языков и вычислений, 2-е изд. : Пер. с англ. / Д. Хопкрофт, Р. Мотвани, Д. Ульман. М. : Издательский дом "Вильяме", 2002. - 528 с.

54. Чень Ч., Ли Р. Математическая логика и автоматическое доказательствотеорем: Пер. с англ /Ч. Чень, Р. Ли. Под ред. С.Ю. Маслова. МлНаука.

55. Главная редакция физико-математической литературы, 1983. 360 с.

56. Черкашин Е.А. Программная система КВАНТ/1 для автоматическогодоказательства теорем: автореф. дис. канд. техн. наук: 05.13.11 / Е.А.

57. Чернецки К. Порождающее программирование: методы, инструменты,применение. Для профессионалов / К. Чернецки, У. Айзенкер. СПб.:1. Питер, 2005.-731 с.

58. Шалыто А.А. Автоматно-ориентированное программирование / А.А.

59. Шалы то. // Материалы IX Всероссийской конференции по проблемам118науки и высшей школы "ФУНДАМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ В ТЕХНИЧЕСКИХ УНИВЕРСИТЕТАХ". СПб.:изд-во Политехнического университета. 2005. - С.44-52,

60. Шамгунов Н.Н. Разработка методов проектирования и реализация поведения программных систем на основе автоматного подхода: автореф. дис. канд. техн. наук: 05.13.13 / Н.Н. Шамгунов. Санкт-Петербург, 2004. - 18 с.

61. Rodger S.H. A collection of tools for making automata theory and formal languages come alive / S.H. Rodger и др.. ACM SIGCSE Bulletin. Volume 29 , Issue 1. 1997.-pp. 15-19.

62. Jean Berstei. A Scalable Formal Method for Design and Automatic Checking of User Interfaces / Berstei Jean и др.. // ACM Transactions on Software Engineering and Methodology, Vol. 14, No. 2, 2005. pp. 124-167.

63. Abowd Gregory. User Interface Languages: A Survey of Existing Methods / Gregory Abowd, Jonathan Bowen. Technical Report PRG-TR-5-89. Programming Research Group, Oxford University, October 1989 - p. 65.

64. A ho A.V. Deterministic parsing of ambiguous grammars / A.V. Aho, S.C. Johnson, J.D. Ullman. // Comm. ACM 18:8, 1975, pp. 441-452.

65. An Expert System for Design of Spacecraft Attitude Control System /' S.N. Vassilyev и др.. // Artificial intelligent in Engineering, Vol. 11., No 1, 1997. -pp. 49-59.

66. Anthony A. Aaby. Compiler Construction using Flex and Bison / Aaby A.

67. Anthony. Walla Walla College. Version of February 25, 2004 - p. 96.

68. Cherry L.L. Writing tools / L.L. Cherry. // IEEE Trans, on Communications COM-30:1, 1982.-pp. 100-104.

69. Cormack G.V. Data compression using dynamic Markov modeling / G.V. Gormack, R.N. Horspool. // Computer J., Vol. 30, №» 6, 1987. - P. 541-550.

70. Bruno Ginoux. DESCARTES: An Automatic Programming System for

71. Algorithmicaily Simple Programs / Ginoux Bruno. // International Workshop119on Software Specifications & Design. Proceedings of the 9th international workshop on Software specification and design, 1998, pp. 106-109

72. Free Compiler Construction Tools. Электронный ресурс. -: http://thefreecountry.com/ (1 дек. 2007)

73. Harrison M.D. A review of formalisms for describing interactive behaviour / M.D. Harrison, D.j. Duke. // in Software Engineering and Human-Computer Interaction, volume 896 of Lecture Notes in Computer Science, SpringerVerlag, 1995.-pp. 49-75.

74. Jarvis J.F. Feature recognition in line drawings using regular expressions / IF. Jarvis. // Proc. 3rd Intl. Joint Conf. on Pattern Recognition, 1976 pp. 189192.

75. Jeff Prosise. Programming Microsoft .NET/ Prosise Jeff. MS Press, 2002 - p. 816.

76. 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-163.

77. John E. Hopcroft. Introduction to automata theory, languages, and computation / Hopcroft John E., Motwani Rajeev, Uliman Jeffrey D. -2nd ed., Addison-Wesley, 2001 -p. 521.

78. Manna, Z., Fundamental of Deductive Program Synthesis / Z, Manna, R. Waldinger. // IEEE Transaction on Software Engineering, Vol. 18(8), 1992, -pp. 674-704.

79. Manna, Z, Towards automatic program synthesis / Z. Manna, R. Waldinger. // Comm. ACM, 14(3), 1971, pp. 151-164.

80. Phyllis Reisner. Formal Grammar and Human Factors Design of an Interactive Graphics Sysyrem / Reisner Phyllis . I EE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. SE-7, N0.2, MARCH 1981 - pp. 229240

81. Sami Khun. Animating Parsing Algorithms / Khuri Sami, Sugono Yanti. -ACM SIGSE Bulletin, Volume 30, Issue 1.1998: pp. 232-236.

82. Stephen A. Blythe. LLparse and LRparse: visual and interactive tools for parsing / A. Blythe Stephen, C. James Michael, H. Rodger Susan. ACM SIGCSE Bulletin, Volume 26 , Issue 1. 1994, - pp. 208-212.

83. Terence J. LL and LR translators need k>i lookahead / J. Terrence, W. Russell. ACM SIGPLAN Notices, Volume 31 , Issue 2. 1996: - pp. 27-34.

84. Terry P.D., Compilers and Compiler Generators, an introduction with С++ Электронный ресурс. / P.D. Terry. Rhodes University, 1996-2000 -http://www.scifac.ru.ac.za/compilers/ (2004, October 21).

85. Tyugu E., Algorithms and Architectures of Artificial Intelligence / E. Tyugu. IOS Press, 2007 p. 171.

86. Vassilyev S.N. Machine Synthesis of Mathematical Theorems / S.N. Vassilyev. // J. Of Logic Programming Vol. 9, No 2&3, 1990. pp.235-266.

87. Vassilyev S.N. Intelligent control via new efficient logics / S.N. Vassilyev h pp.. // Proc. of the 17th IF AC World Congress. Seoul (Korea), 2008.-pp. 13713-13718.

88. Young R.M. How would your favorite user model cope with these scenarios? / R. M. Young, P. Barnard, T. Simon. SIGCGI Bulletin, (20), 1989. - pp. 51-55.