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

• Автор: Чеботарь, Константин Степанович
• Шифр специальности: 01.01.10
• Научная степень: Кандидатская
• Год защиты: 1984
• Место защиты: Кишинев
• Количество страниц: 151 c. : ил

С ОДЕРЖАНИЕ

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

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

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

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

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

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

цикличности атрибутных грамматик

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

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

грамматики
§ 2.4. Экономия памяти при проверке цикличности атрибутных грамматик
§ 2.5. Реализация алгоритма проверки цикличности
Глава III. ВЫЧИСЛЕНИЕ СЕМАНТИЧЕСКИХ АТРИБУТОВ
§ 3.1. Основные алгоритмы вычисления семантических атрибутов
§ 3.2. Алгоритм преобразования семантических функций
§ 3.3. Вычисление семантических атрибутов методом сортировки
Глава IV. НЕКОТОРЫЕ ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ, ПРИМЕНЯЕМЫЕ
ПРИ РЕАЛИЗАЦИИ АТРИБУТНЫХ ГРАММАТИК
§ 4.1. Задача оптимизации на множестве перестановок

§ 4.2. Генерация оптимального кода для арифметических
выражений
§ 4.3. Реализация алгоритма генерации объектного кода
с помощью атрибутной грамматики
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА
ПРИЛОЖЕНИЕ
ПРИЛОЖЕНИЕ

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

процессе проверки цикличности.
Трудоемкость алгоритма М2А связана, в основном, с большим числом всевозможных комбинаций графов, рассмотренных на шаге М2А6. Это число увеличивается еще и в результате того, что алгоритм не учитывает повторение одинаковых комбинаций. Например, если некоторое правило р: X0-*-XjXz... Хл_ рассматривается повторно, то среди всевозможных комбинаций pi (fj /^)
возможно будут и такие, которые были рассмотрены раньше.
Предлагается следующий метод удаления повторяющихся комбинаций. Под итерацией алгоритма М2А будем понимать одно последовательное выполнение шагов М2А6 - М2А9, при котором рассматриваются всевозможные комбинации тех графов /7, /}_, -.. у Гп, » которые включены в соответствующие множества И до рассмотрения этого правила. Первая итерация - это выполнение шага М2А4, т.е. присвоение начальных значений множествам Z
Итерация будет последней, если во время ее выполнения ни одно из множеств не изменяется.
Обозначим через <£(Г) номер итерации, во время которой
граф Г включается в соответствующее множество Z. , а через у1 - номер текущей итерации. Имеет место
Лемма 2.3.3. Если •) ^ 2. , то для правила^:
комбинации уО:(7/, /I,У^), Ij£ для всех
j = 1,2 /ъ рассматривать не следует.
Доказательство. Согласно определению итерации, если существует хотя бы один граф fj
, то эта итерация не последняя и рассматриваемая комбинация возможно будет рассматриваться на следующей итерации. Если же для всех Q
рассмотрена на одной из предыдущих итераций. Лемма доказана.
■?.- і , то эта комбинация уже была
, / ^j ^ /і , для которого сС(^)~