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

ВВЕДЕНИЕ.

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

§ I.I. Методы формального описания языков программирования и их классификация.

§ 1.2. Описание и реализация языков программирования атрибутными грамматиками.

§ 1.3. Основные определения и обозначения.

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

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

§ 2.2. Исключение лишних графов.

§ 2.3. Определение оптимального порядка выбора правил грамматики.

§ 2.4. Экономия памяти при проверке цикличности атрибутных грамматик.

§ 2.5. Реализация алгоритма проверки цикличности.

ГЛАВА Ш. ВЫЧИСЛЕНИЕ СЕМАНТИЧЕСКИХ АТРИБУТОВ.

§ 3.1. Основные алгоритмы вычисления семантических атрибутов.

§ 3.2. Алгоритм преобразования семантических функций.

§ 3.3. Вычисление семантических атрибутов методом сортировки.

ГЛАВА 1У. НЕКОТОРЫЕ ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ, ПРИМЕНЯЕМЫЕ

ПРИ РЕАЛИЗАЦИИ АТРИБУТНЫХ ГРАММАТИК.

§ 4.1. Задача оптимизации на множестве перестановок.

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

§ 4.3. Реализация алгоритма генерации объектного кода с помощью атрибутной грамматики.

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

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

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

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

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

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

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

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

- предложены новые алгоритмы вычисления семантических атрибутов и исследована их эффективность;

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

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

Более подробно описан метод атрибутных грамматик как наиболее полно отвечающий интересам системных программистов. Рассматриваются различные классы АГ. Доказывается, что класс упорядоченных атрибутных грамматик [63] строго включает в себя класс одновизитных АГ [56 ] , а последний несравним с классом АГ, допускающих вычисление всех атрибутов произвольного дерева за несколько его обходов [54,62] . Приводится полная схема иерархии рассмотренных классов.

Показывается, что АГ успешно применяются при описании алгоритмов трансляции, языков программирования, а также в системах построения трансляторов.

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

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

Разработан эффективный метод определения оптимального порядка выбора правил грамматики в процессе проверки ее цикличности. Метод основан на применении известной задачи о выделении компонент сильной связности ориентированного графа и построении топологически упорядоченного фактор-графа [16,34] к граф/ исходной контекстно-свободной грамматики.

Предлагается также алгоритм эффективного использования памяти ЭВМ в процессе проверки цикличности. Показывается, что эта задача сводится к известной, рассматриваемой на ациклическом графе задаче Беллмана-Джонсона для двух машин [18,33] . Для таких задач в §4.1 предложен эффективный метод решения.

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

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

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

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

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

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

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

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

В основном все разработанные в диссертации алгоритмы реализованы в системе ПЛ/I ОС ЕС ЭВМ и могут быть включены в качестве компонент любой атрибутной СГГГ. Комплекс программ, реализующий окончательный вариант алгоритма проверки цикличности, сдан во Всесоюзный фонд алгоритмов и программ.

Основные результаты диссертации обсуждались на семинарах "Системы математического обеспечения ЭВМ" Вычислительного центра АН СССР и "Автоматизация программирования" Института математики с ВЦ АН Молдавской ССР, докладывались на Второй всесоюзной школе молодых ученых и специалистов по проблемах теории систем и ее приложениям (Каунас, 1978), на Всесоюзном научно-техническом совещании "Проблемы создания и использования высокопроизводительных информационно-вычислительных машин" (Кишинев, 1979), на Всесоюзном симпозиуме "Автоматизация производства пакетов прикладных программ (Автоматизация производства трансляторов)" (Таллин, 1980), на 1У Всесоюзном симпозиуме "Системное и теоретическое программирование" (Кишинев, 1983) и опубликованы в работах 40-51 .

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

1. Алгоритмический язык Алгол-60. Пересмотренное сообщение. Под ред. Ершова А.П., Лаврова С.С., %ра-Бура М.Р. - М.: Мир, 1965 - 79 с.

2. Альфа система автоматизации программирования / Бабецкий Г.И., Бежанова М.М., Волошин Ю.М. и др. - Новосибирск : Наука, 1967 - 308 с.

3. Арлазаров В.Л., Диниц Е.А., Кронрод М.А., Фараджев И.А. Об экономном построении транзитивного замыкания графа. Докл. АН СССР, 1962, т.194, №3, с. 487-488.

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

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

6. Бауэр Ф., Гооз Г. Информатика. М.: Мир, 1976 - 355 с.

7. Бирюков А.Н., Курочкин В.М., Серебряков В.А. Глобальные атрибуты и их использование при определении языков программирования.- Ж. выч. мат. и мат. физ.,1980,№5,с.1284-1293.

8. Бирюков А.Н. Магазинная организация памяти при вычислении семантических атрибутов. Тез. докл. Всесоюзн. симпоз. "Автоматизация производства пакетов прикладных программ (Автоматизация производства трансляторов)", Таллин, 1980, с. 57-60.

9. Бирюков А.Н., Курочкин В.М., Серебряков В.А. Структурные атрибуты и их реализация в СЛТ СУПЕР. Программирование, 1981, №2, с. 52-55.

10. Боревич З.И. К вопросу перечисления конечных топологий.

11. Зал. научн. семинаров Ленингр. отд. Матем. инст. АН СССР, 1977, т.71, с.47-65.

12. Боревич З.И., Бумагин В.В., Родионов В.И. Число помеченных топологий на десяти точках. Зал. научн. семинаров Ленингр. отд. Матем. инст. АН СССР, 1979, т.86, с.5-10.

13. Бранкар Р., Кардинал Д.Р., Леви Д. Простой транслирующий автомат, позволяющий генерировать оптимальный код. Труды Всесоюзн. симпоз. по методам реализ. новых алгоритм, языков. Часть П. Новосибирск, ВЦ СО АН СССР, 1975, С.З&-49.

14. Бурдюк В.Я., Рева В.Н. Об одном методе оптимизации функционалов от перестановок при наличии ограничений. Кибернетика, 1980, №1, с.99-103.

15. Вооглайд А.О., Меристе М.Б. Абстрактные атрибутные грамматики. Программирование, 1982, №5, с. 17-26.

16. Донаху Д. Взаимодополняющие определения семантики языков программирования. В кн.: Семантика языков программирования. М.: Мир, 1980, с. 222-394.

17. Зыков А.А. Теория конечных графов. Новосибирск: Наука, 1969. - 543 с.

18. Кнут Д.Е. Исскуство программирования. М.: Мир, 1976, т.1. - 736 с.

19. Конвей Р.В., Максвелл В.Л., Миллер Л.В. Теория расписаний.-М.: Наука, 1975. 360 с.

20. Курочкин В.М. Алгоритм вычисления семантических атрибутов.-Тезисы докл. Всесоюзн. симпоз. "Автоматизация производства пакетов прикладных программ (Автоматизация производства трансляторов)". Таллин, 1980, с. 64-66.

21. Лавров С.С. Методы задания семантики языков программирования. Программирование, 1978, №6, с. 3-10.- из

22. Левин Г.М., Танаев B.C. Об одном классе комбинаторных задач оптимизации. Известия АН БССР, сер. физ.-мат. наук, 1968, №5, с. 30-35.

23. Левин М.Ш., Левнер Е.В. Об эффективном решении задачи Беллмана-Джонсона на сети, имеющей вид дерева. Автоматика и телемеханика, 1978, №10, с.ПО-118.

24. Лекарм 0. Практичность и переносимость системы построения трансляторов. Труды Всесоюзн. симпоз. по методам реализ. новых алгоритм, языков. Часть I. Новосибирск, ВЦ СО АН СССР, 1975, с. 47-72.

25. Лоро Б. Метод семантических атрибутов в системе delta . -Труды Всесоюзн. симпоз. по методам реализ. новых алгоритм, языков. Часть I. Новосибирск, ВЦ СО АН СССР, 1975, С.29-46.

26. Маркотти М., Ледгард X., Бохман Г. Формальные описания языков программирования. В кн.: Семантика языков программирования. М.: Мир, 1980, с. 9-136.

27. Меристе М.Б. Методы реализации атрибутных схем в системах построения трансляторов. (Обзор). Программирование, 1980, №5, с. 40-50.

28. Пеньям Я.Э. Реализация семантики языков программирования в системе ПРИЗ. Тезисы докл. Всесоюзн. симпоз. "Автоматизация производства пакетов прикладных программ (Автоматизация производства трансляторов)". Таллин, 1980, с. 78-80.

29. Пересмотренное сообщение об алгоритмическом языке Алгол 68. М.: Мир, 1979. - 534 с.

30. Редько В.Н. Интерпретированные языки и интерпретаторы. -Кибернетика, 1969, №5, с. 81-89.

31. Редько В.Н. Композиции программ и композиционное программирование. Программирование, 1978, №5, с. 3-24.

32. Редько В.Н. Основания композиционного программирования. -Программирование, 1979, Ш, с. 3-13.

33. Серебряков В.А. Основные особенности реализации СПТ СУПЕР.-Тезисы докл. Всесоюзн. симпоз. "Автоматизация производства пакетов прикладных программ (Автоматизация производства трансляторов)". Таллин, 1980, с. 194-199.

34. Танаев B.C., Шкурба В.В. Введение в теорию расписаний. -М.: Наука, 1975. 256 с.

35. Фараджев И.А. Эффективные алгоритмы решения некоторых задач для ориентированных графов. Ж. вычисл. матем. и мат. физики, 1970, т.10, №4, с. 1049-1054.

36. Харрари Ф., Палмер Э. Перечисление графов. М.: Мир, 1977. - 326 с.

37. Хендерсон П. Функциональное программирование. Применение и реализация : Пер. с англ. М.: Мир, 1983, - 349 с.

38. Хоор Ч.Э.Р. Аксиоматическое определение языка программирования Паскаль. Труды симпоз. "Теория программирования". -Новосибирск, 1972, с. 11-36.

39. Хоор Ч.Э.Р., Лауэр П.Е. Непротиворечивые взаимодополняющие теории семантики языков программирования. В кн.: Семантика языков программирования. М.: Мир, 1980, с. 196-221.

40. Хомский Н. Формальные свойства грамматик. Кибернетический сборник, новая серия. М.: Мир, 1966, вып.2, с. 121-230.

41. Чеботарь К.С. Порядок вычисления семантических атрибутов.-Программирование, 1979, №2, с. 50-55.

42. Чеботарь К.С. Об экономии памяти при проверке цикличности атрибутных грамматик. В кн.: Проблемы создания и использования высокопроизводительных информационно-вычислительных машин : Тезисы докл. Всесоюзн. научно-техн. совещ., Кишинев,1979, с. Ill—112.

43. Чеботарь К.С. Алгоритм упорядочивания семантических атрибутов. В кн.: Проектирование транслирующих процессоров. Кишинев : Штиинца, 1980, с. 23-35.

44. Чеботарь К. С. Некоторые модификации алгоритма Кнута для проверки цикличности атрибутных грамматик. Программирование, 1981, №1, с. 74-77.

45. Чеботарь К.С. Об одной задаче оптимального использования общей памяти. В кн.: Графы, гиперграфы и дискретные оптимизационные задачи. Кишинев : Штиинца, 1982, с. 185-189,

46. Чеботарь К.С. Некоторые алгоритмы реализации систем трансляции методом атрибутных грамматик. В кн.: Системное и теоретическое программирование. Кишинев: Штиинца, 1982, с. 91-100.

47. Чеботарь К.С. Оптимальное использование рабочих ячеек в алгоритме Сети-Ульмана. Программирование, 1983, №3, с.40-45.

48. Чеботарь К.С. Модифицированный алгоритм Сети-Ульмана и его реализация семантическими атрибутами. В кн.: Системное и теоретическое программирование: Тезисы докл. Всесоюзн. симпоз., Кишинев, 1983, с. 391-392.

49. Чеботарь К.С. Эффективное использование памяти при проверке цикличности атрибутных грамматик. В кн.: Системное и теоретическое программирование: Тезисы докл Всесоюзн. симпоз., Кишинев, 1983, с. 392-394.- 116

50. Чеботарь К.С. Проверка цикличности атрибутных грамматик. -Алгоритмы и программы, (Информ. бюллетень ВНТИЦентр), Москва, №5(56), 1983, с.З (ГосФАП СССР, Ш006385).

51. Чеботарь К.С. Об одной задаче оптимизации на множестве перестановок. Известия АН Молдавской ССР, сер. физ.-техн. и мат. наук, 1984, И, с. 51-53.

52. Bochmann G.V. Semantic evaluation from left to right. -Comm. ACM, 1976, v.19, n.2, p.55-62.55» Deransart P. Proof by semantic attributes of a LISP compiler. Computer journal, 1979, v.22, n.3, p.240-245,

53. Engelfriet J., File G. The formal power of one-vizit attribute grammars. Acta informatica, 1981, v.16, n.3» P»275-302.

54. Evans J.V/., Harrary P., Lynn M.S. On the computer enumeration of finite topologies. Comm. ACM, 1967, v.10, n.5, p.295-297.

55. Jazayeri M., Ogden W.F., Rounds W.S. The intrinsically ex- 117 ponential complexity of the circularity problem for attribute grammars. Comm. ACM, v.18, n.12, p.697-706.

56. Jazayeri M. A simpler construction for showing the intrinsically exponential complexity of the circularity problem for attribute grammars. Journal ACM, 1980, v.28, n.4,p.715-720.

57. Jazayeri M., Walter E.G. Alternating semantic evaluator. -In : Proc. of ACM 1975 Ann. Conf., 1975, p.230-234.

58. Kastens U. Ordered attributed grammars. Acta informatica,1980, v.13, n.3, p.229-256.

59. Kennedy K., Warren S.E. Automatic generation of efficient evaluators for attribute grammars. Conf. Record Third Symp. on Principles Programm. Lahg., 1976, p.32-4-9.

60. Knuth D.E. Semantics of context-free languages. Math, systems theory, 1968, v.2, n.2, p.127-146.

61. Knuth D.E. Semantics of context-free languages: corrections. Math, systems theory, 1971, v.5, n.1, p.179.67» Knuth D.E. Examples of formal semantics. Lecture notes in mathematics, 1971, n.188, p.1-34.

62. Koster C.H.A. Affix grammars. In: Algol 68 implementation, J.E.L.Peck (ed.). - North-Holland PC, Amsterdam, 1971, p.95-109.

63. Lecarme 0., Bochmann G.Y. A (trully) usable and portable compiler writing systems. Information processing 74, Proc. IFIP Congress, North-Holland, 1974, p. 218-221.

64. Lev/is P.M., Rosenkrantz D.J., Steaxns R.E. Attributed translations. Journal of computer and systems sciences, 1974, v.9, n.3, p.279-307.

65. Lorho B. De la definition a la traduction des languagesde programmation: methode des attribute semantiques. -These d'Etat Univ. Paul Sabatier, Toulouse, 1974. 166 p.

66. Lucas P., Walk K. On the formal description of PL/1.

67. Annual review in automatic programming, v.6, no, p. 105-182.73» McCarthy J. A formal definition of a subset of Algol. In: Formal language description languages for computer programming, Proc. IFIP Conf., North-Holland, 1966, p.1-12.

68. PL/1 Basis/1-11. ECMA.TC10/MSI .ХЗЛ, 1974. - 346 p.75» Raiha K.-J. On attribute grammars and their use in a compiler writing system. Rep. A-1977-4. Dep. Сотр. Sci., Univ. Helsinki, 1977. - 90 p.

69. Raiha K.-J., Saarinen M. An optimization of the alternating semantic evaluator. Inform, proc. letters, 1977* v.6, n.3, p. 97-100.77* Redziejowski R.R. On arithmetic expressions and trees. -Comm. ACM, 1969, v.12, n.2, p.81-84.

70. Sethi R., Ullman J.D. The generation of optimal code for arithmetic expressions. Journal ACM, 1970, v. 17» n.4-, p.715-728.

71. Sintzoff M. Existence of a van Wijgaarden syntax for every recursively enumerable set. Ann. Soc. Sci., 1967} n.81, Bruxelles, p.115-118.

72. Tennet R.D. The denotational semantics of programming lan- 119 guages. Comm. ACM, 1976, v.19, n.8, p.4-37-4-53.

73. Tusera D. Example of transformation of a derivation tree for an expression by semantic attributes. Information processing 74-, North-Holland PC, 1977, p.381-385.

74. Uhl J., Drossopoulou S., Persch C. An attribute grammar for the semantic analisis of Ada. Lecture notes in computer science, 1982, v.139. - 511 p.

75. Wegner P. The Vienna definition language. Computing surveys, 1972, v.1, n.1, p.5-63.

76. Wirth N., Weber H. Euler: a generalisation of Algol and its formal definition. Pt.1. Comm. ACM, 1966, v.9, n.1, p.13-25.

77. Wirth N., Weber H. Euler: a generalisation of Algol and its formal definition. Pt.2. Comm. ACM, 1966, v.9, n.2, p.89-99.