автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.17, диссертация на тему:Синтаксически управляемая обработка данных

Б.К.Мартыненко

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

Санкт-Петербург

Издательство С.-Петербургского университета

¿¥9/Л

К/ V

'ЗЗО - ■/

С.-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Б. К. Мартыненко

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

Пр

ез

(решение присудил

идиум ВАК Рос

с ни

¿>5

N2

ДОКТОРА!

о . ЕЛЬСТВО С.-ПЕТЕРБУРГСКОГО О ' оЕРСИТЕТА

УЛК 519.685.3 М25

Редактор Т. В. Мызникова

Рецензенты: д-р физ.-мат. наук проф. С. Н. Баранов (Ин-т информатики и автоматизации РАН), канд. техн. наук, доц. В.П.Котляров (С.-Петербургский техн. ун-т)

Печатается по постановлению Редакционно-издателъского совета С.-Петербургского университета

Q

Мартыненко Б. К. Синтаксически управляемая обработ-

М25 ка данных. — СПб: Изд-во С.-Петербургского университета, 1997. 364 с.

КВМ 5-288-01768-9

В монографии описывается актуальная для практической информатики технология синтаксически управляемой обработки данных, использующая кусочно-регулярную аппроксимацию КС-языков. Трансляции специфицируются при помощи ЙЛЭДР-грамматик и реализуются посредством контекстно чувствительных сплайновых языковых процессоров. Технология применяется для решения синтаксических проблем, а также поддерживает об-ьектно-син-таксическую парадигму программирования, которая выражается метафорической формулой "программа = объекты + грамматика".

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

Библиогр. 19 назв. Табл. 27. Ил. 7,3.

Тем.план 1997, № 63

© Б. К. Мартыненко, 1997

© Издательство

СПетер бу ргского

ISBN 5-288-01768-9 университета, 1997

ОГЛАВЛЕНИЕ

Предисловие................................................................................................9

Введение. ОБЗОР ОСНОВНЫХ КОНЦЕПЦИЙ И ВОЗМОЖНОСТЕЙ

БУГ^ТАХ-ТЕХНОЛОГИИ..................................................................16

1. Задание управляющих структур....................................................16

2. Трансляционные ЗДВ№-грамматики.............................................17

3. Сплайновые процессоры как средство реализации трансляций..................................................................................................18

4. Регулярные сплайны......................................................................20

5. Эквивалентные преобразования трансляционных грамматик.....21

6. Трансляционные граф-схемы........................................................22

7. Челночные трансляции...................................................................23

8. Спецификация микролексики.......................................................24

9. Комплексирование процессоров.......-а...........................................25

10. Встроенные функции управляющего процессора........................26

11. Генерация диагностических сообщений.......................................26

12. Генерация тестов............................................................................27

13. Спецификация вычислений...........................................................28

14. Объектно-синтаксическое программирование.............................28

15. Структурная модульность..............................................................29

16. Среда отладки средств синтаксически управляемой обработки данных.......................................................................................30

17. Языки спецификации операционного окружения........................30

18. Перспективы развития БУЖАХ-технологии..............................30

Глава 1. СПЕЦИФИКАЦИЯ И РЕАЛИЗАЦИЯ ТРАНСЛЯЦИЙ.................32

1.1. Способы спецификации и реализации трансляций в БУИЧ-

ТАХ-технологии.............................................................................32

Анализирующие трансляционная грамматика и процессор

(33). Порождающие трансляционная грамматика и процессор (36).

1.2. Трансляционная грамматика..........................................................37

Управляющая ЮЗМ^-грамматика (37). Описание операционной среды (38). Трансляция, определяемая трансляционной грамматикой (38).

1.3. Анализирующая трансляционная грамматика калькулятора.......40

1.4. Порождающая трансляционная грамматика, определяющая вычисление функции Factorial.......................................................46

1.5. Анализирующий процессор............................................................48

1.6. Реализация калькулятора посредством анализирующего процессора............................................................................................52

1.7. Порождающий процессор..............................................................60

Вырожденные варианты порождающего процессора (63). Реализация функции Factorial посредством порождающего процессора (63).

1.8. Спецификация трансляций при помощи трансляционных граф-схем......"..................................................................................64

Трансформационный подход (64). Сборка идентификаторов (67). Постановка задачи синтаксического анализа на граф-схемах (68). Представление управляющей КВОТ-грамматики в виде управляющей граф-схемы (69).

1.9. Регулярные сплайны.......................................................................75

Глава 2. ОБЪЕКТНО-СИНТАКСИЧЕСКОЕ ПРОГРАММИРОВАНИЕ.. . 77

2.1. Основные понятия и примеры объектно-синтаксического

программирования..........................................................................77

Рекурсивное вычисление функции Factorial в объектно-синтаксичеСком стиле (80). Порождающая грамматика, определяющая вычисление функции Аккермана (88).

2.2. Объектно-синтаксическая архитектура программ........................96

2.3. Информационное взаимодействие между конструкциями...........97

2.4. Объектно-синтаксическое программирование на Турбо-паскале..........................................................................................101

2.5. Историческая справка..................................................................105

Глава 3. ЧЕЛНОЧНЫЕ ТРАНСЛЯЦИИ.........................................................107

3.1. Реализация трансляций при помощи челночных процессоров.. 107

3.2. Челночный сплайновый процессор.............................................109

Прямой просмотр (110). Обратный просмотр (110). Операционная среда (111).

3.3. Функционирование челночного сплайнового процессора..........111

Прямой просмотр (111). Обратный просмотр (112).

3.4. Построение челночных сплайновых процессоров......................116

Построение управляющего процессора прямого просмотра (116). Вспомогательные алгоритмы для построения прямого

просмотра (122). Построение управляющего процессора обратного просмотра (126). Вспомогательные алгоритмы для построения обратного просмотра (129).

3.5. Спецификация челночных трансляций при помощи трансляционных RBNF-грамматик...........................................................130

Глава 4. ОПТИМИЗАЦИЯ ЧЕЛНОЧНЫХ ПРОЦЕССОРОВ.....................133

4.1. О методе оптимизации челночных процессоров........................133

4.2. Эквивалентность состояний, магазинных и входных символов ..134

4.3. Сокращение числа входов в таблицу возвратных состояний.....136

4.4. Порядок оптимизационных преобразований...............................136

4.5. Построение лексических переходников прямого и обратного просмотров....................................................................................138

4.6. Иллюстрация метода оптимизации процессора..........................139

Оптимизация калькулятора (139)

4.7. Учет диагностических сообщений при оптимизации.................146

4.8. Оптимизация управляющих граф-схем........................................146

Глава 5. ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ

ТРАНСЛЯЦИОННЫХ ГРАММАТИК............................................147

5.1. Причины, цели "и методы преобразований..................................147

Ограничения механизма анализа (147). Методы эквивалентных преобразований (149). Исключение несамовставленных нетерминалов из управляющей КС-грамматики (150).

5.2. Некоторые полезные регулярные тождества...............................153

5.3. Иллюстрация алгоритма исключения нетерминалов..................153

Глава 6. ПРАКТИЧЕСКИЕ АСПЕКТЫ ПРИМЕНЕНИЯ SYNTAX-

ТЕХНОЛОГИИ...................................................................................160

6.1. Построение трансляционной грамматики...................................160

Конструкция сцелое без знака> (162). Синтаксически управляемый калькулятор (165). CALC — трансляционная грамматика калькулятора (первоначальный вариант) (167).

6.2. Эквивалентные преобразования трансляционной грамматики ..175 Грамматика CALC (175).

6.3. Генерация диагностических сообщений об ошибках.................182

Диагностические сообщения CALC (183).

6.4. Использование резольверов в трансляционных грамматиках ....185 Gener — генераторы Алгола 68 (модель) (187).

Глава 7. МНОГОПРОЦЕССОРНАЯ ОБРАБОТКА.......................................191

7.1. Взаимодействие между языковыми процессорами.....................191

Процессор - сканер (191). ОепегЬех — лексика генераторов Алгола 68 (193).

7.2. Динамическое управление видимостью входных лексем...........197

7.3. Анализ генераторов Алгола 68....................................................199

Управляющая граф-схема Оепег 200). Управляющая таблица прямого просмотра Оепег (202). Диагностики оптимизированного процессора Оепег (212).

7.4. Лексика генераторов....................................................................215

Управляющая граф-схема ОепегЬех (215). Управляющая таблица прямого просмотра ОепегЬех (217). Размеры компонент управляющей таблицы ОепегЬех (219). Оптимизированная управляющая таблица процессора ОепегЬех (220). Размеры компонент оптимизированной управляющей таблицы ОепегЬех (222). Диагностические сообщения оптимизированного процессора ОепегЬех (223).

7.5. Однопросмотровый анализ генераторов Алгола 68....................225

Протокол однопросмотрового анализа генератора .loc.struct([5].int х, .proc[ |.real у) (225).

7.6. Челночный анализатор генераторов Алгола 68..........................232

Расширенная управляющая таблица обратного просмотра процессора Gener (232). Протокол челночного анализа локального генератора .loc.struct([5 j.int х, .proc[].real у) (237).

7.7. Сообщения об ошибках во время процессирования..................239

Сообщения о бесконтекстных ошибках (239). Сообщения о контекстных ошибках (241).

7.8. Механизм сообщений — средство обмена информацией между процессорами........................................................................243

Процессоры, обменивающиеся сообщениями (246). Расширенный синтаксис генератора Xgen (247).

Глава 8. ОПИСАНИЕ ЯЗЫКА TSL.................................................................255

8.1. Общая структура TSL-спецификации.........................................255

8.2. Заголовок......................................................................................256

8.3. Комментарий.................................................................................256

8.4. Лексика языка TSL.......................................................................257

Буквы (257). Цифры (257). Специальные знаки (258). Ключевые слова (258). Идентификаторы (259). Терминалы (260). Синонимы (260).

8.5. Описание микролексики..............................................................261

Транслитерация (261).

8.6. Описание лексики........................................................................264

8.7. Описание синтаксиса...................................................................264

Алфавит нетерминалов (265). Алфавит вспомогательных понятий (266). Алфавит терминалов (267). Алфавиты семантических символов (267). Алфавиты резольверных символов

(268). Правила управляющей грамматики (269).

8.8. Описание операционной среды...................................................270

Глава 9. ТЕСТИРОВАНИЕ ЯЗЫКОВЫХ ПРОЦЕССОРОВ.......................273

9.1. Тестирование — способ проверки правильности спецификации.................................................................................................273

9.2. Тестирование Syntax-приложений...............................................275

Взаимодействие транслитератора и сканера (275). Взаимодействие сканера и анализатора (276). Постановка задачи тестирования конечных процессоров (276).

9.3. Тестирование конечных процессоров.........................................278

Алгоритм 9.1. Генерация теста порядка п (281). Пример генерации теста уровня 3 (282).

9.4. Метод решения задачи о китайском почтальоне........................283

Алгоритм 9.2. Нахождение максимального потока минимальной стоимости (285). Алгоритм 9.3. Окрашивание сети (286). Алгоритм 9.4. Нахождение эйлерова цикла (287). Алгоритм 9.5. Поиск цикла в сети (288). Тестирование анали-

затора генераторов Алгола 68 (288).

Заключение. ИТОГИ И ПЕРСПЕКТИВЫ.....................................................290

Приложение. ТЕХНОЛОГИЧЕСКИЙ КОМПЛЕКС SYNTAX..................295

1. Назначение и возможности технологического комплекса SYNTAX.................................................................................................295

2. Подсистема проектирования...........................................................297

Запуск подсистемы (297). Функции подсистемы (298). Редактор ТЗЬ-спецификаций (303). Генератор управляющих граф-схем (303). Генератор управляющих таблиц (305). Генератор диагностических сообщений (311). Редактор диагностических сообщений (312). Генератор тестов (прототестов) (313). Генератор листингов (314). Общий порядок использования компонент (314).

3. Подсистема процессирования.........................................................318

Система меню и режимы работы (320). Раздел About (321). Раздел General (321). Раздел Edit (323). Раздел Preparation (325). Раздел Data (330). Раздел Run (331). Раздел Debug (332). Раздел Options (333). Раздел Window (336). Общий порядок работы (336).

Указатель литературы........................................................................339

Предметный указатель.......................................................................340

ПРЕДИСЛОВИЕ

Эта книга является итогом многолетней работы "виртуального" научного коллектива по разработке и развитию технологии синтаксически управляемой обработки данных, которая проводилась в Ленинградском, а ныне — Санкт-Петербургском, университете с конца 1968 г. Средний возраст его участников — 20 лет, поскольку основу его всегда составляли и сейчас составляют студенты математико-механического факультета СПбГУ.

Мысль заняться технологией трансляции возникла у автора во время научной стажировки в A/S Regnecentralen (Копенгаген, 1967-68 г.) под впечатлением от системы программирования GIER ALGOL 4 (для версии языка Алгол 60), созданной коллективом разработчиков под руководством проф. П.Наура. Каждый из 9 просмотров компилятора GIER ALGOL 4, некоторые из которых — обратные, представляет собой программу, вся логика которой упаковывается в компактную управляющую таблицу, открывающую доступ к действиям над данными. Казалось, что такие таблицы могли быть получены посредством некоторой технологии автоматически. Но, как выяснилось из разговора с Йорном Йенсеном, одним из основных участников проекта компилятора GIER ALGOL 4, никакой автоматизации не существовало, и все управляющие таблицы строились вручную посредством естественных рассуждений, основывающихся на представлениях разработчиков о синтаксисе входного языка и промежуточных языков этого компилятора.

Другим стимулом к разработке технологии трансляции явился заказ Научно-исследовательского центра электронной вычислительной техники министерства радиопромышленности СССР на реализацию алгоритмического языка Алгол 68 для машин ЕС ЭВМ. Специфика условий работы состояла в том, что в тот период* язык Алгол 68 еще не был "заморожен". Многочисленные изменения появлялись чуть ли не в каждом очередном номере Алгол-бюллетеня и их следовало оперативно учитывать.

* 1968-1974 годы.

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

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

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

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

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

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