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

• Семынина, Татьяна Валерьевна
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Семынина, Татьяна Валерьевна

Введение.

1 Анализ логических конструкций формальных языков.

1.1 Исследование алгоритмов формирования многомодульных программ.

1.2 Языки и регулярные языки.

1.2.1 Алфавиты и языки.

1.2.2 Регулярные выражения.

1.3 Автомат с конечным числом состояний.

1.3.1 Проектирование автомата с конечным числом состояний.

1.3.2 Гипотеза отождествления.

1.3.3 Префиксное замыкание.

1.4 Просто звёздные языки.

1.4.1 Ограничения размера языка.

1.4.2 Однобуквенный автомат.

1.4.3 Условия полиномиального роста.

1.5. Исчисление предикатов и регулярные языки.

1.5.1 Регулярные предикаты.

1.5.2 Языки со многими переменными.

1.5.3 Исчисление и замкнутость предикатов.

Цель и задачи исследования.

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

2.1 Группы, как языки.

2.1.1 Структура автоматов для групп.

2.1.2 Построение алгоритма для решения проблемы слов.

2.2 Графы Кэли и изометрические неравенства.

2.2.1 Граф Кэли для различных групп.

2.2.2 Превращение графа Кэли в метрическое пространство.

2.2.3 Ограничение длин.

2.3. Группы автоматов.

2.3.1 Свойство Липшица для групп автоматов.

2.3.2 Стандартные автоматы.

2.3.3 Ограничение длин.

2.4. Инвариантность при замене образующих.

2.4.1 Изменение образующих.

2.4.2 Улучшение автоматической структуры.

2.4.3 Биавтоматичность.

2.4.4 Префиксное замыкание групп автоматов.

Выводы.

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

3.1 Квазигеодезические, псевдоизометрия, поочередная комбинация.

3.2 Метрические пространства, метрики путей и геодезические.

3.3 Кратчайшие строки.

3.3.1 Множества конического типа.

3.3.2 Нахождение уровня элемента группы.

3.3.3 Применение теории Люстерника - Шнирельмана к множествам конического типа.

3.4 Псевдоизометрии.

3.4.1 Псевдоотображения.

3.4.2 Равносильность группы и действующего пространства.

3.4.3 Оценки числа стационарных точек.

Выводы.

4 Определение оценки сложности символьного текста в терминах топологических инвариантов.

Введение диссертации (часть автореферата) на тему «Разработка категорных средств анализа формальных языков на основе теории конических типов»

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическая значимость и результаты внедрения: основные теоретические и практические' результаты работы внедрены и используются в производственном процессе ФГУП ВНИИС при разработки высокоэффективных инструментальных средств программирования специального назначения, в учебный процесс Воронежского государственного технического университета для студентов специальности 230201 «Информационные системы».

Апробация работы. Результаты диссертационной работы докладывались и обсуждались на следующих конференциях и семинарах: Международном семинаре «Компьютерное моделирование электромагнитных процессов в физических, химических и технических системах» (Воронеж, 2004), Международном семинаре «Физико-математическое моделирование систем» (Воронеж, 2004), Всероссийской конференции «Интеллектуализация управления в социальных и экономических системах» (Воронеж, 2004).

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

Структура и объём работы. Диссертация состоит из введения, четырёх глав, заключения, изложенных на 140 страницах машинописного текста, списка литературы из 84 наименований, содержит 40 рисунков.

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

4.4 Выводы

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

Заключение

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

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

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

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

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

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

6. Основные теоретические и практические результаты работы внедрены и используются в производственном процессе ФГУП ВНИИС при разработки инструментальных средств программирования микропроцессоров специального назначения, в учебный процесс Воронежского государственного технического университета для студентов специальности 230201 «Информационные системы».

Список литературы диссертационного исследования кандидат технических наук Семынина, Татьяна Валерьевна, 2005 год

1. Автоматизация проектирования сложных логических структур/ В.А. Горбатов, В.Ф.Демьяник, Г.Б.Кулиев и др. Под ред В.А.Горбатова. — М.: Энергия, 1978. —

2. Агранович Ю.А. Геометрическое моделирование структуры информационного пространства // серия «Моделирование, оптимизация и компьютеризация с ложных системах», книга 13 — Воронеж: ВГТУ, 2000.

3. Александров А.Д. Внутренняя геометрия выпуклых поверхностей. — М.-Л., 1948.

4. Александров П.С. Общая теория гомологии. Уч. зап. МГУ, 1940, вып. 3-7. О гомологических свойствах расположения комплексов и замкнутых множеств. Изв. АН СССР, сер. матем., 1942, 6, № 5.

5. Батыршин И.З. Лексикографические оценки правдоподобности с универсальными границами. II Операции отрицания. Теория и системы управления. Изв. АН РАН. - 1995. - № 5. - с. 133-151.

6. Бишоп Р.Л., Криттенден Р. Дж. Геометрия многообразий. Пер. с англ. -М., 1967.

7. Блисс Г.А. Лекции по вариационному исчислению. — Пер. с англ. — М., 1950.

8. Бураго Ю.Д. Неравенства изопериметрического типа в теории поверхностей ограниченной внешней кривизны. М., 1968.

9. Вишик М. Некоторые вопросы почти-изометрических отображений. Ю.Гаврилов М.А., Девятков В.В., Пупырев Е.И. Логическоепроектирование дискретных автоматов. М.: Наука, 1977. —

10. Гекке Е. Теория алгебраических чисел. — М., 1939.

11. Генис А.Л. Метрические свойства эндоморфизмов п-мерного тора // «Доклады АН СССР», т. 138, № 5. М., 1961.

12. Гладкий A.B. Формальные грамматики и языки. -М., 1973.

13. Глушков В.М. Теория автоматов и формальные преобразования микропрограмм. -М.: Кибернетика, 1965.

14. Горбатов В.А. Оценки при выборе направления вычислений в задачах синтеза конечных автоматов. — Изв. АН СССР. Техническая кибернетика, 1970, № 4

15. Горбатов В.А. Проблемы оптимизации сложных систем логического управления. В кн.: Оптимизация дискретных систем управления. -М.: ГВЦ Госплана СССР, 1972.

16. Горбатов В.А. Семантическое эквивалентирование сложных систем. — В кн.: Семиотические методы управления в больших системах. — М.: МДНТП, 1971.

17. Горбатов В.А. Фундаментальные основы дискретной математики. Информационная математика. — М.: Наука, 1999. — 544 с.

18. Громов М. Гиперболические группы. М. - Ижевск: 2000. - 159 с.

19. Громов М. Знак и геометрический смысл кривизны. — М.- Ижевск: РХД, 2000.- 160 с.

20. Зыков A.A. Теория конечных графов. Новосибирск: Наука, 1969. —

21. Ивахненко А.Г. Моделирование сложных систем: информационный подход. — К.: «Наукова думка», 1987. 136 с.

22. Курош А.Г. Общая алгебра (лекции 1969 1970 уч. г.). -М.: Наука, 1974.- 159 с.

23. Курош А.Г. Теория групп,- М.: Наука, 1967. 648 с.

24. Курош А.Г., Лившиц А.Х., Шульгейфер Е.Г. Успехи математических наук. Т. 15.-М., 1960.

25. Лаврентьев М.А., Люстерник Л.А. Курс вариационного исчисления. 2-еизд.-М.-Л., 1950.

26. Ленг С. Введение в теорию дифференцируемых многообразий.- Пер с англ.-М., 1967.

27. Люстерник Л. Пересечения в линейных в малом функциональных пространствах. ДАН XXVII, 1940, № 8.

28. Люстерник Л.А. Замечания к некоторым вариационным задачам. Уч. зап. МГУ, 1934, вып. 2, 17-23

29. Люстерник Л.А. и Щнирельман Л.Г. Топологические методы в вариационных задачах. Труды Научно-исслед. инст. мат. и мех. М., 1930.

30. Люстерник Л.А. и Щнирельман Л.Г. Применение топологии к экстремальным задачам. Труды Второго всес. матсъезда. М., 1935, т.1

31. Люстерник Л.А. Топология функциональх пространств и вариационное исчисление в целом. М.-Ленинград: Издательство АН СССР, 1947.-100 с.

32. Люстерник Л.А., Соболев В.И. Элементы функционального анализа. -2- е изд., перераб. М.: Наука, 1965. - 522 с.

33. Майника Э. Алгоритмы оптимизации на сетях и графах. -М.: Мир, 1981. —

34. Марков A.A. Теория алгоритма. // «Труды математического института АН СССР», т. 42, М.-Л., 1952.

35. Марковский A.B. Анализ структуры знаковых ориентированных графов // Изв. АН. Теория и системы управления,- 1997. № 5. - с. 144149.

36. Мелихов А.Н., Бернщтейн Л.С., Коровин С.Л. Ситуационные советующие системы с нечетко логикой. М.: Наука, 1990. - 272 с.

37. Новиков П.С. Конструктивная математическая логика с точки зрении классической. -М.: Наука, 1977. —

38. Норенков И.П. Основы автоматизированного проектирования: Учеб. для вузов. 2-е изд., перераб. и доп. М.: Изд-во МГТУ им. Н.Э.Баумана, 2002. - 336 с.

39. Общая теория систем. М.: Мир, 1977.

40. Ope О. Теория графов. М.: Наука, 1980.

41. Поспелов Д.А. Логико-лингвистические модели в системах управления. М.: Энергия, 1981.

42. Рейуорд-Смит В.Дж. Теория формальных языков. Вводный курс: Пер. с англ. М.: Радио и связь, 1988. - 128 с.

43. Рохлин В.А. Об энтропии автоморфизма компактной коммутативной группы // «Теория вероятностей и его применения», т. 6, вып. 3 — М., 1961.

44. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.

45. Семынина Т.В. Оценка числа стационарных точек для функций, заданных на конечных автоматах // Физико-математическое моделирование систем: Мат. меж. сем. Воронеж: ВГТУ, 2004.С.34-39

46. Семынина Т.В. О возможности применения теорий категорий к множеству конического типа // Физико-математическое моделирование систем: Мат. меж. сем. Воронеж: ВГТУ, 2004.С 144-161.

47. Семынина Т.В., Юрасов В.Г., К теории регулярных языков // Компьютерное моделирование электромагнитных процессов в физических, химических и технических системах, мат. 3 межд. сем. Воронеж: ВГТУ, 2004. С.254-257.

48. Семынина Т.В., Юрасов В.Г., Проектирование обобщённых конечных автоматов // Компьютерное моделирование электромагнитных процессов в физических, химических и технических системах, мат. 3 межд. сем. Воронеж: ВГТУ, 2004. С.311 -318.

49. Семынина Т.В.Основные свойства регулярных языков // Компьютерное моделирование электромагнитных процессов в физических, химических и технических системах, мат. 3 межд. сем. Воронеж: ВГТУ, 2004. С.307-311.

50. Семынина Т.В., Агранович Ю.Я. О вероятностном смысле геометрической информации // Вестник вып. 4. Воронеж.: ВГТУ, 2001. С.92-95.

51. Семынина Т.В., Фурсова С.А., Организация самостоятельной работы студентов в соответствии с требованиями государственных общеобразовательных стандартов // Интеллектуальные информационные ситемы: Всерос. конф. Воронеж ВГТУ, 2000. С. 146147.

52. Семынина Т.В., Агранович Ю.Я. О геометрической структуре информационного пространства // Обеспечение прогрессивного развития хозяйственных структур в транзитивной экономике: Межвуз. сб. научн. тр. Воронеж: БУПК, 2002. С.205-215.

53. Семынина Т.В., Юрасов В.Г., Агранович Ю.Я. Методы метризации информационного пространства на основе конечных геометрий // Интеллектуализация управления в социальных и экономических системах: Тр. Всерос. конф. Воронеж: ВГТУ, 2004. С.266-268.

54. Семынина Т.В., Агранович Ю.Я. Определение геометрической информации и энтропии // Некоторые аспекты экономики, методики обучения, истории кооперации, права и товароведения современной России: Межвуз. сб. научн. тр. Воронеж: БУПК, 2001. С. 172-179.

55. Сигалов А. Почти-изометрические отображения и псевдодифференцируемость. ДАН, 1946, № 1.

56. Синай Я. О понятии энтропии динамической системы. ДАН, т. 124, № 4,-М., 1959.

57. Харари Ф. Теория графов. М.: Мир, 1973. - 300 с.

58. Хинчин А .Я. Понятие энтропии в теории вероятностей // «Успехи математических наук», Т.8, вып. 3. — М., 1953.

59. Цаленко М.Ш., Шульгейфер Е.Г. Основы теории категорий. М., 1974.

60. Эльсгольц Л.Э. Длина многообразия и ее свойства. Мат сб., 1939, № 3.

61. Эльсгольц Л.Э. Теория вариантов, дающих оценку числа критических точек непрерывной функции, заданной на многообразии. Мат сб., 1939, №5.

62. Alonso J.M. Combings of groups. To appear in MSRI Proceedings of the workshop on algorithms, word problems and classification in combinatorial group theory. 1989. - p.220

63. Anick D.J. On the homology of associative algebras. TAMS. 1986. -p.220.

64. Artin E. Theory of braids. Annals of mathematics, 1947. p.240.

65. Baumslag G., Gersten S.M., Shapiro M., Short H. Automatic groups and amalgams. Unpublished, p.280.

66. Birman J.S. Braids, Links and mapping Class Groups. Princeton Univ.press. - 1975. - p.245.

67. Bowditch B.H. Geometric finiteness for hyperbolic groups. Preprint, originally Warwick Ph.D. thesis, 1988 -p.266.

68. Bowditch B.H. Notes of Gromov's hyperbolicity criterion. In Group theory a geometric viewpoint. World Scientific, Singapore, to appear. Proceedings of the ISTP conference in summer, 1990. p.80.

69. Buchberger B., Loos R. Algebraic simplification. In Buchberger B., Collins G.E., Loos R., editors. Computer Algebra, Simbolic and Algebraic Computation, Second Edition. Springer-Verlag, New-York, 1982.— p. 113.

70. Epstein D.B.A., Cannon J.W., Holt D.F., Levy S.V.F., Paterson M.S, Thurston W.P., Word Processing in Groups, Jones and Bartlett, Boston MA, 1992

71. Jaco W., Shalen P. Seifert fibre spaces in 3-manifolds, 1979. p. 274.

72. Johannson K. Homotopy equivalence of 3-manifolds with boundaries. Springer-Verlag, Berlin, New-York, 1979. p. 274.

73. Kapovich M., Potiagailo L. On the absence of Ahlfors' Finiteness Theorem for Kleinian groups in dimension-3, 1991. p.270.

74. Knuth D.E., Bendix P.B. Simple word problems in universal algebra. In Leech J., editor, Computational problems in abstract algebras. Pergamon Press, 1970.-p. 300.

75. Koebe P. Allgemeine Theorie der Riemannischen Mannigfaltigkeiten, 1927. -p.460.

76. Koebe P. Riemannischen Mannigfaltigkeiten und nichteuklidische Raumformen, 1929. p.460.

77. Lundell A.T., Weingram S. The topology of CW complexes. Van Nostrand. New-York, 1969. - p.250.

78. Macdonald I.D. The theory of groups. Oxford University Press, Oxford, 1968.-200.