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

ВВЕДЕНИЕ.

1. ОБЗОР МЕТОДОВ И ПРОБЛЕМ, СВЯЗАННЫХ С ФУНКЦИЯМИ ПРЕДШЕСТВОВАНИЯ.

1.1. Основные понятия .II

1.2. Понятие класса грамматик, обладающих функциями предшествования

1.3. Способы доказательства существования функции предшествования

1.4. Методы построения функции предшествования

1.4.1. Методы вычисления функции предшествования

1.4.2. Методы нахождения функции предшествования

1.5. Функции предшествования как часть синтаксического анализатора.

1.5.1. Проблемы нахождения отношения "?"

1.5.2. Проблемы редуцирования

Выводы.

2. ОПТИМИЗАЦИЯ ПАМЯТИ АНАЛИЗАТОРА ГРАММАТИКИ ПРЕДШЕСТВОВАНИЯ, РЕДУЦИРУЕМОЙ С (1,1) - ОГРАНИЧЕННЫМ КАНОНИЧЕСКИМ К0НТЕКСТ0М40 2.1. Приведение грамматики предшествования к виду, обладающему двумя функциями предшествования .£I

2.1.1. Нахождение циклов в матрице предшествования

2.1.2. Частные виды стратификации для преобразования грамматик предшествования

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

2.2. Метод проведения редуцирования с(/1/1) - ограниченн-ным каноническим контекстом при функциях предшествования

2.2.1. Определение минимального (1,1) ~ ограниченного канонического контекста

2.2.2. Определение упорядоченных векторов

2.3. Обработка ошибок при упорядоченных векторах и функциях предшествования

2.4. Модифицированный алгоритм синтаксического анализа для грамматик предшествования

Выводы.

3. ТЕХНОЛОГИЯ И СРЕДСТВА РЕАЛИЗАЦИИ

3.1. Система построения трансляторов ELMA.

3.I.I. Конструктор и анализатор системы E.LMА.

3.2. Инструментальное средство на базе системы ELMA.

3.2.1. Обработка аналитических выкладок

3.2.2. Надстройка над базой данных

3.3. Опыт минимизации транслятора, работающего при помощи модифицированного анализатора

3.3.1. Характеристика языков, реализованных в системе ELM А.

3.3.2. Эффективность нахождения функции предшествования и упорядоченных векторов

3.3.3. Пример вычисления функции предшествования и упорядоченных векторов на языке DAMAL.

Выводы.

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

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

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

В этом направлении проведен ряд исследований в ВЦ СО АН СССР [21] , в Киевском Госуниверситете [32] , в ВЦ АН СССР [б] , Кроме того интересная работа проделана в ИК УССР [10, 19] , в ИТА АН СССР [3] , а также в ИК ЭССР [22] .

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

- б тавной частью технологических средств, дающих возможность перехода от больших и средних ЭВМ к мини- и микро-ЭВМ.

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

Целью данной работы является разработка подсистемы системы построения трансляторов Е1МА [12] , которая позволит минимизировать требуемый объем памяти создаваемого транслятора. Создаваемый транслятор, полученный из описания языка пользователя при помощи системы Е1-МА и является исследуемым объектом. Предлагаемая подсистема разработана на основе методов, являющихся основными результатами диссертации.

Система построения трансляторов Е1.МА разработана в Таллинском политехническом институте. Нынешняя версия системы является уже четвертой. В начале ее разработки для проведения синтаксического анализа была выбрана так наз. техника анализа "снизу-вверх", базирующаяся на грамматиках простого предшествования Ц651 . В процессе дальнейшего развития системы был разработан уже новый класс грамматик, опирающийся на грамматики предшествования. Таким классом стали грамматики предшествования, редуцируемые с (1/1) - ограниченным каноническим контекстом, позволяющие анализировать все детерминированные языки [18Ц .

В последнее время заметно возрос интерес к мини- и микроЭВМ. В связи с этим возникла идея использования трансляторов, составленных при помощи системы Е1.МА, для вычислительных машин такого типа. На этом пути встала проблема ограничений, накладываемых на требуемый объем памяти транслятора. Таким образом необходимой задачей дальнейшего развития системы ЕША становится минимизирование транслятора, работающего на грамматиках предшествования, редуцируемых с (4,1)- ограниченным каноническим контекстом.

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

Следовательно, один из методов минимизации памяти может состоять в приведении исходной грамматики (контекстно-свободной грамматики) к виду, обладающему двумя функциями предшествования. Тем самым становится возможным сократить требуемый для (п * п)-матрицы предшествования объем памяти до 2г\'(п'4 Другой способ минимизации состоит в введении множества минимального контекста. Дело в том, что если исходная грамматика предшествования содержит правила с одинаковыми правыми частями, то для выбора правильного из них (для редуцирования) в ходе синтаксического анализа надо иметь множество (1И) - контекста (т.е. всевозможные односимвольные пары слева и справа для правых частей правил). Для средних и больших по величине грамматик таких пар может быть довольно много. Но вследствие введения множества минимального контекста можно существенно сократить количество сохраняемых контекстных пар.

Научной новизной в диссертации можно считать следующие новые результаты, полученные при решении поставленной задачи:

1) предлагается эффективный метод преобразования грамматики предшествования к виду, обладающему двумя функциями предшествования и соответствующие алгоритмы;

2) разработан метод минимизации количества контекста, необходимого для редуцирования правил грамматики с одинаковыми правыми частями и использования последнего во время синтаксического анализа вместе с функциями предшествования;

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

Практическая значимость состоит в использовании результатов, изложенных в диссертационной работе вместе с системой построения трансляторов ELMA, разработанной в Таллинском политехническом институте [12]. При помощи этой системы реализованы входные языки системы PARES[23] , языки самой системы ELMA [12].» синтаксический анализатор языка программирования ADA [93 и целый ряд других проблемно-ориентированных языков. Результаты данной работы могут быть использованы также в организациях, занимающихся теоретическими исследованиями и практическими приложениями, связанными с проблемой автоматизации построения трансляторов, а также при решении любой задачи, где применяется синтаксическое управление.

Диссертация состоит из трех глав.

В первой главе вводятся понятия, используемые в дальнейшем. Дается краткая характеристика методов и алгоритмов, связанных с так наз. "нахождением" и "вычислением" функции предшествования. Рассмотрены возможности редуцирования с (Л , Л) - ограниченным каноническим контекстом для грамматик предшествования. Приведены понятия строгой эквивалентности и простой эквивалентности анализаторов.

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

В третьей главе описывается общая структура и основные свойства системы построения трансляторов Е1-МА. Приводятся также основные результаты, полученные при работе с системой ЕЬМА и характеризующие эффективность алгоритмов, предложенных во второй главе. Кроме того приводится технология, разработанная автором для использования системы построения трансляторов в качестве инструментального средства. Для этой цели введено понятие переменной типа дерева. По предложенной технологии разработаны средства для вычисления аналитических выкладок £25] и синтаксически управляемый генератор ввода С 30] .

В заключении приводятся общие итоги и основные выводы диссертационной работы.

I. ОБЗОР МЕТОДОВ И ПРОБЛЕМ, СВЯЗАННЫХ С ФУНКЦИЯМИ ПРЕДШЕСТВОВАНИЯ

О существовании функции предшествования упоминалось уже в статье Флойда [51] , где он ввел понятие отношения предшествования. Затем появились статьи Вирта и Вебера [65], Белла [45] > Мартина [57] , Ахо и Ульмана [41] , Трахтенгерца и Щумей [.37] и других.

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

Первые методы вычисления функции предшествования базировались на итеративных алгоритмах. Они давали положительные результаты в том случае, если функции предшествования действительно вычислялись для грамматики предшествования. Однако, сущность функции предшествования еще не была вскрыта. После разработки более сложных методов была выявлена причина, по которой невозможно было найти функции предшествования для заданной грамматики. Устранению этой причины и разработке новых методов посвящены статьи Берча [46] , Белла [44] , Мартина [57] , Бабичева, Прониной и Трахтенгерца [ 4 ] .

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

Ключевые слова: контекстно-свободная грамматика; грамматика простого предшествования; функции предшествования; граф линеаризации; преобразования грамматики; грамматика предшествования, редуцируемая с (1,1) - каноническим контекстом.

1.1. Основные понятия

Определение 1.1. ([I]) . Контекстно-свободная грамматика - это упорядоченная четверка (\/М/Ут , где

Хч и Ут - непересекающиеся множества нетерминальных и терминальных символов, V» Ур и Ум алфавит грамматики, Р - множество синтаксических правил грамматики вида А , ДвУ^ , и. ^ ( Ут и У^) и и 3 — начальный нетерминальный символ.

Соглашения. Обозначим через строчные латинские буквы а , Ь , О , . терминальные символы, через а , V , X »У -цепочки произвольных символов. Символом А - пустую цепочку. Заглавными латинскими буквами А ,В, С , . обозначим нетерминальные символы, черезX,У,2 - произвольные символы грамматики. Обозначим через |х| длину словах , через % к - буквенное начало слова х и через хСк^ обозначим К - буквенное окончание слова х (К - целое число и |х(< к ). ПустьМ - некоторое множество и - бинарное отношение на этом множестве. Введем обозначения х<* = (х,у)б.<*}и

Определение 1.2. . Слово у непосредственно выводимо из слова X (обозначим через Х=>у ), еслих=2/1Аг2, и А-»2€.Р. Если г^еУ* , то слово у непосредственно канонически выводимо из слова х ( х у ).

Определение 1.3.([I]) . Будем говорить, что слово х поровдает словоу только тогда, когда существует последовательность слов х0,хП; . . ,ха такая, что (1,2,.,п)и которая является транзитивно-рефлексивным замыканием операции ( ). Транзитивное замыкание обозначим + через => .

Определение 1.4. ([I]) . Строка х называется сентенциальной формой, если

Определение 1.5. ([I]) . Если 6=>аАу=>игУ , то выделенное слово 2 , принадлежащее канонической сентенциальной форме и^у » называется основой канонической сентенциальной формы и.2У ( УеХ/^). Процесс выделения основы состоит из шагов переноса.

Определение 1.6. ([I]) . Формальный язык , порождаемый грамматикой 6=(У|Ч>У|. - это совокупность всех терминальных цепочек, выводимых из начального символа в в грамматике & [х | хе У^Б^Х У

Определение 1.7. ([II). Грамматика называется приведенной, если ни в каком правиле А ге Р, г .Л. и хАу хуг » кроме того не может иметь места А^А . Определение 1.8.([I]) . Грамматика, в которой нет двух различных правил с одинаковыми правыми частями, называется обратимой.

Определение 1.9. ([I]). Грамматика является (к) - грамматикой , если для произвольного правого вывода 5- ^ в каждой правовыводимой цепочке , читая ее слева направо, можно выделить основу и определить, каким нетерминалом надо ее заменить, дойдя при этом не более, чем до К-ого символа, расположенного справа от правого конца этой основы.

По Е591 опишем бинарные отношения для контекстно-свободной грамматики: {( Х,У) I А цХУуе р], у = [( Х,А) ) А ^ иХ в Р}х Л« [(А,Х) | А XV Лт=^(А,а) | А ^еР].

Определение 1.10. ([I]). Контекстно-свободная грамматика называется грамматикой простого предшествования, если между символами грамматики существуют попарно непересекающиеся отношения предшествования <• = ; = - у > = и грамматика является приведенной и обратимой. (Через ^ обозначим отношение являющееся источником синтаксических ошибок и не пересекающееся с отношениями предшествования).

Теорема 1.1. ([40Д). Если Э - грамматика предшествования и ф'Х1Хг.УкАТ1Т2.ТЕ-7ХлУ,.ХкГ1У1.Ут1,Т2;.Те

В 6 , ТО

I) Л(.< Х1+< V Х4 * Х.им К К);

3)

4> Ут»Тч;

5) никакие другие отношения предшествования между этими символами, кроме указанных, не существуют.

Определение 1.11. ([59"]). Конфликтом предшествования типа Рлназовем существование пары символов (X,У ) таких, что £(Х (•> П=)ЗЧ1(Х,У)£(>П<]], а конфликтом типа Я, -существование символов (Х,У ) таких, что

Определение 1.12. ([381). Пусть б=(УыХ-,Р,Б) является контекстно-свободной грамматикой, некоторым множеством правил вида иху/, (и,у е V*) . Стратификацией на множестве правил Я , определяемой словом х (обозначим через БТС*)), называется преобразование грамматики 6 в грамматику 6/=(У(Ч , где

Ч/= ч, и {О),

Р' = Р, и Рг и Р5, Р, = р\Я,

Рг = ^ А -»• ЦОУ 1 А -»ЧХУ6 Й}, Рз =

Определение 1.13. (ЕЦ) . Приведенная контекстно-свободная грамматика называется грамматикой слабого предшествования, если

1) отношения <• и = и > попарно не пересекаются в б ,

2) если А"* и ХУ^ и В-^Уу^ Р , то не имеет места Х<Е> или Х = В.

Определение 1.14{ [51]). Каждому символу X грамматики предшествования поставим в соответствие два целых числа £СХ) ид(У)» Для которых должны выполняться следующие отношения: д (V) тогда и только тогда, когда Х = У ; < 3 тогда и только тогда, когда Х<-У; (X) > д (У) тогда и только тогда, когда Х>У .

Функции ^ и д назовем функциями предшествования.

Определение 1.15. ([57]). Графом линеаризации назовем ориентированный граф, построенный по (п.*п.) - матрице предшествования М следующим образом:

1) сначала пометим а вершин буквами ^, ^; ., » а оставшиеся вершины - буквами 94/9г/-/9п.»

2) если М-^ я « , построим новую вершину N , сливая ^ и ^ , причем N представляет все те вершины, которые ранее представлялись вершинами ^ ид. ;

3) если М-^^-С , проведем дугу из ^ в ^ ;

4) если М= ■> , проведем дугу из в ^ .

По [52]] разобьем шаг анализа на два действия:

1) нахождение основы X ^. Х^ (1 ^ сентенциальной формы Х^.-./Хк (детектирование);

2) нахождение такого правила подстановки

А^Х^.Х^Р ,что Х1.Х,.,АХ>1.ХК=> к (редуцирование). Определение 1.16. (11]). Цепочка языка у свертывается в цепочку х тогда и только тогда, когда существует последовательность цепочек ./ХПтакая, что Х0= X , у= Ха , Х-^^ Х^ ( 1= Шаг свертывания называем сверткой.

Определение 1.17.( [173). Назовем каноническим контекстом для нетермилана А множество:

СГ" IС*'*»! в #к &ихАуу' м=т' М- к>^т)

Определение 1.18.(£17^). Грамматика предшествования является редуцируемой с (т,к)- каноническим контекстом тогда и только тогда, если для любых двух нетерминалов А и В лт,к л ггпк . . имеет место условие Ьд ~ у> »причем правила А-*и ,

В-?-и , А*В принадлежат множеству Р .

Из теоремы 1.1 следует, что X , А) € Сд° - Х< А V X =А,

А ,Т) е. С* з СА<Т V д«т V А ->ТЗ &Те. Ут и .

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

Ь.С(А) = <1Х1(Х,Л)е сл°1

КС [А)- ^ Т| (Л,Т)е С* ).

Определение 1.19. ([17"}). Независимым каноническим контекстом нетерминала А назовем декартово произведение его левых и правых контекстных символов (обозначим через

С,'/1 - 1.0 (А) * ЯС(А)). А

Определение 1.20. ([I]). Грамматика слабого предшествования 6 называется грамматикой простого предшествования со смешанной стратегией предшествования, если из того, что и В-* и принадлежат Р , следует, что 1С(А) Г\1С(В)=^

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

4. Разработанный модифицированный синтаксический анализатор компактнее по объему требуемой памяти в сравнении с 5и?(1)-анализатором.

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

ЗАКЛЮЧЕНИЕ

В настоящей работе рассмотрена задача минимизации транслятора, работающего на грамматиках предшествования, редуцируемых с (1,Н)- ограниченным каноническим контекстом [18] .

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

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

В третьей главе приведены результаты реализации и внедрения разработанной подсистемы совместно с системой Е|МА . Там же дана общая структура системы построения трансляторов ЕЬМА, причем указано место нахождения разработанных алгоритмов в системе. Машинный эксперимент подтверждает практическую ценность разработанных алгоритмов и возможность их применения в системе Е1МА для построения трансляторов с высокой скоростью работы и малым объемом требуемой памяти. Кроме того разработана технология, дающая возможность использовать систему построения трансляторов в качестве инструментального средства.

В итоге приведены основные результаты диссертации.

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

2. Реализована и внедрена подсистема системы построения трансляторов Е1-МА , позволяющая минимизировать требуемый объем памяти анализатора. Подсистема реализована на ЕС ЭВМ.

3. Разработан эффективный метод минимизации явно сохраняемого (4/0" ограниченного канонического контекста, метод преобразования грамматики предшествования в вид, обладающий двумя функциями предшествования и метод вычисления упорядоченных векторов.

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

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

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

3. Бабаев И.О. »Новиков Ф.А., Петрушин а Т.И. Язык Декарт входной язык системы СПОРА. - В сб. "Прикладная информатика", вып. I, 1980, с. 27-76.

4. Бабичев A.B. »Пронина В.А., Трахтен-г е р ц Э.А. Приведение порождающих грамматик к виду, обладающему функциями предшествования. Программирование, 1977, № 3,с. 43-53.

5. Берестовая С.М.; П е р е в о з ч и к о в а 0.Л., Романов В.Н., Ю щ е н к о Е.Л. Конструирование систем программирования обработки данных. М., Статистика, 1979,270 с.

6. Бирюков А.Н. ,Курочкин В.М. .Серебряков В.А. Система построения трансляторов, основанная на однородном и универсальном подходе. Тезисы докл. на I Всесоюзной конференции "Технология программирования", Киев, 1979.

7. Вадер А.Р., В о о г л а й д А.О. Описание метаязыка в системе построения трансляторов. Тр. Таллинск. политехи, ин-та, 1978, № 439, с. 83-92.- но

8. Вайнгартен Ф. Трансляция языков программирования. М., Мир, 1977, 192 с.

9. В е г н е р П. Программирование на языке АДА. М., Мир, 1983, 240 с.

10. В е л ь б и ц к и й И.В., Ходаковский В.Н., Шопмов Л.И. Технологический комплекс производства программ на машинах ЕС ЭВМ и БЭСМ-б, М., Статистика, 1980.

11. Вооглайд А.О., Л е п п М.В. Опыт внедрения классических методов синтаксического анализа. Тр. Таллинск. политехи, ин-та, 1979, № 464, с.3-20.

12. Вооглайд А.О., Л е п п М.В., Л и й б Д.Б. Входные языки системы ELMA . Тр. Таллинск. политехи, ин-та, 1982, № 524, с. 79-96.

13. Вооглайд А.О., Л и й б Д.Б. Грамматические формализмы как прямые средства программрования модульных систем. Тезисы. Всесоюзный семинар по методам синтеза типовых модульных систем обработки данных. НК СССР по автоматическому управлению. М., 1981, с. 77.

14. Вооглайд А.О., Л и й б Д.Б. Древовидная переменная в обработке данных. Тр. Таллинск. политехи, ин-та, 1980, № 482, с. 3-18.

15. Вооглайд А.О., Л и й б Д.Б. Полная оптимизация памяти анализаторов предшествования. Тр. Таллинск. политехи. ин-та, 1980, № 482, с. 15-29.

16. Вооглайд А.О., Л и й б Д.Б. Реализация и описание структурных средств для обработки данных. Тезисы. Автоматизация производства ППП. Таллинск. политехи, ин-т, Таллин, 1980, с. 41-43.

17. Вооглайд А.О., Т о м б а к М.О. О проблемах редуцирования в грамматиках предшествования. Тр. Таллинск. политехи, ин-та, 1975, № 386, с. 23-37.

18. Вооглайд А.О., Т о м б а к М.О. Система построения эффективных многопроходных трансляторов с LR(k") семантикой. Программирование, М., 1976, № 5, с. 28-38.

19. Глушков В.М. и др. Система автоматизации производства программ (АПРОП), РФАП, Киев, 1976.

20. Г р и с Д. Конструирование компиляторов для цифровых вычислительных машин. М., Мир, 1975, с. 544.

21. Ершов А.П., Ильин В.П. Пакеты программ технология решения прикладных задач. - Новосибирск, 1979. - 22 с. (Препринт/ВЦ СО АН СССР,- 121).

22. К а х р о М.И., К а л ь я А.П., Т ы у г у Э.Х. Инструментальная система программирования ЕС ЭВМ (ПРИЗ). "Финансы и статистика", 1981.

23. К р а х т В.А., Э й в а к Ю.Э. Алгоритмический язык манипулирования данными DAMAL. Таллин, Таллинск. политехи, ин-т, 1982, 120 с.

24. Л е п п М.В. Схема трансляции, реализуемая при помощи СПТ ТПИ. Тр. Таллинск. политехи, ин-та, 1980, № 482, с. 31-40.

25. Л и й б Д.Б. Инструментальное средство для аналитических выкладок. Тезисы. Всесоюзная конференция по методам трансляции. АН СССР СО ВЦ. Новосибирск, 1981, с. 162-164.

26. Л и й б Д.Б. О преобразовании матрицы предшествованияв векторы предшествования. Тр. Таллинск. политехи, ин-та, 1983, № 554, с. 95-109.

27. Л и й б Д.р. Оптимизация памяти анализатора грамматики предшествования, редуцируемой с ОКК. Тр. Таллинск. политехн. ин-та, 1984, № 568, с. 81-89.

28. Л и й б Д.Б. Оптимизация распознавателя типа "перенос-свертка". Автоматизация производства ППП и трансляторов. II всесоюзная конференция. Тезисы докладов, Таллин, 1983, с. 150—151.

29. Л и й б Д.Б. Технология программирования модульных систем. Тр. Таллинск. политехи, ин-та, 1982, № 524, с. 97-103.

30. Л и й б Д.Б., Р е н з е р A.B. Синтаксически ориентированный генератор ввода. Тр. Таллинск. политехи, ин-та, 1981, Jfo 511, с. 71-81.

31. Пронина В.А. 0 существовании функций предшествования для порождающих грамматик. Автоматика и телемеханика, 1975, № 7, с. I27-I3I.

32. Р е д ь к о В.Н. Языковые процессоры с семантико-син-таксическим управлением. Тезисы докладов Всесоюзной конференции по методам трансляции, Новосибирск, 1981.

33. Рейнгольд Э.,Нивергельт Ю., Д е о Н. Комбинаторные алгоритмы. Теория и практика. М., Мир, 1980, 476 с.

34. Р е н з е р A.B. Об автоматическом интерфейсе между базами данных типа CODASYL и системами ввода-вывода. Тр. Таллинск. политехи, ин-та, 1982, $ 524, с. 29-37.

35. Р о х т л а Х.Х. Нейтрализация синтаксических ошибокв системе построения трансляторов ТЛИ. Тр. Таллинск. политехи, ин-та, 1982, № 524, с. II9-I29.

36. Трахтенгерц Э.А. Введение в теорию анализа и распараллеливания программ ЭВМ в процессе трансляции, Наука, М., 1981, с. 256.

37. Трахтенгерц Э.А., Ш у м е й A.C. 0 сущест- из вования функций предшествования для порождающих грамматик. Ж. вычислит, матем. и матем. физ., 1974, №2, с. 520-522.

38. Т о м б а к М.О. Об устранении конфликтов предшествования. Тр. ВЦ Тартуского гос. ун-та, Тарту, 1976, № 37, с. 60-91.

39. Ф у к с м а н A.JI., К р и ц к и й С.П., Д а г а лд я н Х.А., Дженибабаев Х.П. Основы разработки трансляторов. Изд. Ростовского ун-та, 1974, 230 с.

40. A h о, A.V., Denning, P.J., U 1 1 m a n, J.D. Weak and Mixed Strategy Precedence Parsing.- J. of the ACM, 1972, vol. 19, N 2, pp. 225-243.

41. A h о, A.V., U 1 1 m a n, J.D. Error Detection in Precedence Parsers. Mathematical Systems Theory, 1973, vol. 7, N 2, pp. 97-113.

42. A note on Computing Precedence Functions. Short note. The Computer Journal, 1982, vol. 25, H 3, pp. 397-398.

43. А о e, J., Yamamoto, J., S h i m a d a, R. Practical Method for Reducing Weak Precedence Parsers. IEEE Transactions on Software Engineering, 1983, vol. 9, I 1, pp. 25-30.

44. Bell, J.R. A Compression Method for Compiler Precedence Tables. IFIP-74, 1974, pp. 359-362.

45. Bell, J.R. A New Method for Determining Linear Precedence Functions for Precedencs Grammars. Comm. of the ACM, 1969, vol. 12, IT 10, pp. 567-569.

46. В e r "t 'c' h, E. The Storage Requirement in Precedence Parsing.- Comm. of the ACM, 1977, vol. 20, N 3, pp. 192-194.

47. D a t e, C.J. An Introduction to Database System. California, IBM Laboratories, 1975, 366 p.

48. Duong -Kien, C., Hoffmann, M.-J.,

49. M u t h, D. An Improvement to Martin's Algorithm for Computation of Linear Precedence Functions. Comm. of the ACM, 1976, vol. 19, TS 10, pp. 576-577.

50. E r s h o v, A.P., G r u s h e t s k y, V.Y. An Implementation Oriented Method for Describing Algoritmic Languages. IFIP-77, 1977, p. 117.

51. Fisher, M.J. Some Properties of Precedence Languages. Proc. ACM Symp. on Theory of Computing, 1969, pp. 181190.

52. Floyd, R.W. Syntactic Analysis and Operator Precedence. J. of the ACM, 1963, vol. 10, IT 3, pp. 316-333.

53. Krishnamurthy, M.S., Rame shaChan-d r a, M.R. A Note on Precedence Functions. Inf. Proc. Letters, 1976, vol. 4. N 4, pp. 99-100.

54. Lewi, J., De V 1 a m i n c k, K., M u e n s, J., Muybrechts, M. A Programming Methodology in Compiler Constructions. Part 1. Concepts. Amsterdam- New York Oxford, North- Holland Pub. Company, 1979, 308 p.

55. Martin, D.F. A Boolean Matrix Method for the Computation of Linear Precedence Functions, Comm. of the

56. АСМ, 1972, vol. 15, П б, pp. 448-454.

57. Maurer, Н., S t и с к у, W. Ein Vorshlag für die Vervjendung Syntax-orientierter Methoden in höheren Programmiersprachen. Angewandte Informatik, 1976, IT 5, pp. 189-195.

58. McAfee, J., P r e s s e r, L. An Algorithm for the Design of Simple Precedence Grammars. J. of the ACM, 1972, vol. 19, N 3, pp. 385-395.

59. R a g s t a 1 e, W.F. Pig-FORTH Installation Manual Glossary Model. San Carlos, 1980, 60 p.

60. Shjjamasundar, R.K. A ITote on Linear Precedence Functions. Inf. Proc. Letters, 1976, vol<» 5, TT 3, p. 81.

61. Silverberg, B.A. Using a Grammatical Formalism as a Programming Language. Techn. Rep. CSRG-88, Univ. Toronto, 1978, 90 p.

62. The Forth Development Language. Berlcely, 1981, 80 p.

63. Wirt h, N. Algorithm 265. Find Precedence Functions. Comm. of the ACM, 1965, vol. 8, IT 10, pp. 604-605.

64. V/ i r t h, IT., V/ e Ъ e r, H. EULER- a Generalization of ALGOL, and Its Formal Definition: Part 1. Comm. of the ACM, 1966, vol. 9, N 1, pp. 13-25.1. D K X <D1. O »=5 SI

65. HELP 00 DSNpiGRAMR,DJSPp(MOD,PASS),UNITPSYSDA,

66. SPACE»(CYL. (<•« 1 , 1 > >1. SYSPRINT DO SYSOUTpA1. SILU 00 SYSOUTPA1. SYSIN DD «

67. EM 621 • STEP WAS EXECUTED • COND CODE 0000 EF373I STEP /TEJS / START 86300,1131

68. EFJ76I STEP /TEIS / STOP 86300 , 1 1 63 CPU 6MIN 32.06SEC MAIN 332K

69. KONSTR EXEC PGHiEELNEV1,REGIONP250K

70. STEPLIB DO DSNpELMA.LOAD,DISPiSHR

71. HELP DO DSN»*,TEIS,HELP,DISPp(MOD,PASS)1. SYSPRINT 00 SYSOUTgA1.FO OD SYSOUTpA1. SILU DD DUMMY

72. E F1 6 21 » STEP WAS EXECUTED ■ COND CODE 0000 EH7J I STEP / KONSTR / START 86300,1 163

73. E F376 I STEP /KONST R / STOP 86300,1 146 CPU OMIN 12.B6SEC MAIN 222K

74. TEST EXEC PGMbMECONTJ,REGION.250K

75. STEPLIB 00 DSNpELMA.LOA0,DISP*SHR1. SYSPRINT DD SYSOUTpA1.FO 00 SYSOUTpA1. TEMP DD DSNct&TAB,

76. DCBp (RECFM=VB,BLKSIZEP6096,LRECLS6092,DSORG*PS),

77. DISP«( HOD,PASS),UMT = SYSDA,SPACf=(TRK,(S,2)>

78. HELP DD DSNp*,TEIS,HELP,DISP*(MOD,PASS) EF162I * STEP WAS EXECUTED COND CODE 0000 EFS731 STEP /TEST / START 86300,1166

79. EFJ76I STEP /TEST / STOP 86300,1151 CPU 1MJN 33.S8SEC MAIN 236*

80. RC EXEC PGMbGRAAF20iREGIONpJOOK

81. STEPLIB DD DSNPU,ELMA,LOAD,DISP«SHR

82. HELP DD DSNp*,TEIS,HELP,DISPs(MOD,PASS)1.FO DD SYSOUTPA1. SYSPRINT OD SYSOUTPA

83. EF162I • STEP WAS EXECUTED COND CODE 0000 EF37JI STEP /LCRC / START 86300,1151

84. EFS76I STEP /LCRC / STOP 86300,1159 CPU 2MIN 57.96SEC MAIN 2S6K

85. FUNK EXEC PSMpGRAAF6,REGIONc500K

86. STEPLIB 00 DSNPU,ELMA,SUB,DISPFSHR

87. HELP DD DSNP*,TEIS,HELP,DISPP(MOD,PASS)1. SYSPRINT OD SYSOUTpA1.FO DD SYSOUTgA

88. GRAM DD DSN»OONALO,GRAM2,UNITpSYSDA,VOL?SER.SPOOL1,

89. EFH EF37 EFJ7 E F 3 7 EFS71. DISPPSHR• STEP WAS EXECUTED • COND CODE 0000

90. STEP /FUNK / START 86300,1159

91. J STEP /FUNK / STOP 86300,1262 CPU

92. JOB /GR25 / START 86300,1131

93. JOB /GR25 / STOP 86300,1262 CPU