Расширение класса индексных языков

• Автор: Маслов, Александр Николаевич
• Шифр специальности: 01.01.10
• Научная степень: Кандидатская
• Год защиты: 1981
• Место защиты: Москва
• Количество страниц: 75 с. : ил.

Введение
Задача формального языка, будь то естественный язык, например русский, или язык программирования, например Алгол 60, состоит в построении конечного представления для потенциально бесконечного класса предложений языка. Наиболее естественным ^ ^ подходом к описанию языка является построение порождающей грамматики. Другой подход связан с построением распознающего автомата.
Классическим типом порождающих грамматик считаются бесконтекстные грамматики [Л . Однако для ряда приложений и теоретических исследований класс бесконтекстных грамматик является недостаточным. Поэтому в течении ряда лет значительное внимание уделяется изучению более широких классов рекурсивных языков [5, 12, 26, 27 ].
Целью настоящей работы является определение и исследование нового типа грамматик, называемых многоуровневыми индексными грамматиками. Показывается, что многоуровневые индексные грамматики обладают многими свойствами бесконтекстных грамматик, обеспечившими их практическую применимость, и являются существенным расширением последних. Рассматривается также соотношение многоуровневых индексных грамматик и грамматик Вейнгаардена, использованных для описания языка Алгол 68.
Актуальность темы обусловлена трудностями при формальном описании современных языков программирования и необходимостью совершенствовать методы трансляции, а также расширением сферы применения формальных грамматик в других областях (теория развивающихся организмов [36] , схемы программ, логический вывод).

Предшествующие работы.
Активное развитие теория формальных грамматик начала после работы Хомского [I] , где вводится класс бесконтекстных грамматик в качестве модели для формализации синтаксиса фрагментов естественных языков. К настлящему моменту теория бесконтекстных грамматик хорошо разработана во многих направлениях [2, 3, 4, 21, 22] в ней получено много интересных и содержательных результатов. Установление эквивалентности бесконтекстных грамматик и магазинных автоматов явилось основанием для использования бесконтекстных грамматик для описания, реализации я исследования языков программирования. При этом магазинный автомат составлял основу синтаксической части транслятора. Бесконтекстные грамматики были удачно использованы для описания синтаксиса Алгола 60. Класс бесконтекстных грамматик мы обозначим ^ £.
При дальнейшем “развито языков программирования выяснилось, что беоконтекстных грамматик недостаточно для описания ряда конструкций. Так для описания Алгола 68 были введены грамматики Вейнгаарцена (обозначаемые далее через V ), позволяющие добиться некоторой наглядности при описании языка. Примерно в то же время в работах Лого [7, 8] были введены и изучены индексные грамматики (в наших обозначениях класс а в диссертации М. Фишера [э]
были определены два класса грамматик 10 и 01, обобщающие известные типр макрогенераторов. Класс 01 грамматик оказался по порождающей способности эквивалентным классу индексных грамматик.
Ахо показал, что индексные грамматики обладает основными из тех свойств бесконтекстных грамматик, которые делают их удобными для описания фрагментов естественных языков и языков программирования, а также определил для них класс допускающих автоматов.
Дальнейшие результата, касающиеся индексных грамматик, получены в [9, 10, 18, 19] , см, также обзоры [б] и [12]
В [18] Ш. Грейбах обобщила метод построения допускающих автоматов для индексных грамматик.
СйНЦОВ [13] показал, что грамматики Вейнгаардена порождают все рекурсивно-перечислимые множества, поэтому невозможна система построения трансляторов на их основе (нет распознающего алгоритма). Этим в определенной мере обусловлена сложность реализации Алгола 68 (см. £373 7.,
Метод описания языка программирования (или фрагмента
естественного языка в системе автоматического перевода) должен удовлетворять двум противоположным требованиям. Первое, он должен позволять описывать как можно больше языков.
Второе, для описанных языков должен иметься (достаточно простой) алгоритм анализа. 1 этом отношении введение индексных грамматик [7] и автоматов, допускающих индексные языки [в] , является существенным шагом по отношению к бесконтекстным грамматикам.
Основные результаты.
В настоящей диссертации рассматривается возможность дальнейшего расширения класса индексных языков.
Определяется последовательность -8-1 классов языков, порождаемых обобщенндаи индексными грамматиками (классы которых также обозначаются Л«)» Показано, что каждому классу -Д-к ,
К < «=к> » соответствует семейство допускающих автоматов ^ (названных к-уровневымн магазинными автоматами). Изучены свойства замкнутости классов .Як . Каждый из них является полным главным абстрактным семейством языков. Показано, что при К < °о разрешимы проблема, пустоты и проблема принад-

Пусть заданаЦУ- грамматика Н(/= О }Х.0У
И Г-<2,Ме},С>, Р = рС —У} , Каждое У (см. замечание 2) делится разделителем О на подслова б; ) каждое - порождающее или основное слово.
Алфавит основных символов моделирующей грамматики -это 2и|#;0} . Алфавит вспомогательных символов гра№-матики Ср содержит следующие группы символов:
1) - двойники к алфавиту 2 .
2) Все метапонятия М грамматикиШх/и двойники метапонятий М ;
3) все упорядоченные по возрастанию индекса ^ подмножества метапонятий )(- [ Мг* Мг* , цустое под-
множество ыетапонятий отождествляется с пустым словом £ ;
4) символР, , указывающий окончание некоторого этапа вывода;
5) все пары вида (М^МЛ или (М^Р.) , где и М*

метапонятия;
6) все символы "М =м , где М - метапонятие;
7) все X”такие, что ЗГ(Х-У)€Р •
8) все , не содержащие О такие, что ЗУ(Х^У)вР
; те из них, которые не оканчиваются маркером # , совпадают с соответствующими элементами из пункта 7;
9) все<гУ> такие, что ЗХ(Х-У>?;
10) символ £ , указывающий на незавершенность некоторого этапа вывода;