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

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

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

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

В этом направлении проведен ряд исследований в ВЦ СО АН СССР [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. Предложена технология программирования, основывающаяся на применении грамматических формализмов как прямых средств программирования. При таком подходе, система построения трансляторов, используемая в качестве инструментального средства позволила описать систему вычисления аналитических выкладок и генератор ввода данных для сетевой базы данных.