Расширение класса индексных языков Маслов, Александр Николаевич

Короткий опис

Маслов, Александр Николаевич.
Расширение класса индексных языков : диссертация ... кандидата физико-математических наук : 01.01.10. - Москва, 1981. - 75 с. : ил.
Введение диссертации (часть автореферата)на тему «Расширение класса индексных языков»
Задача формального языка, будь то естественный язык, например русский, или язык программирования, например Алгол 60, состоит в построении конечного представления для потенциально бесконечного класса предложений языка* Наиболее естественным подходом к описанию языка является построение порождающей грамматики, Другой подход связан с построением распознающего автомата.
Классическим типом порождающих грамматик считаются бесконтекстные грамматики [1] . Однако для ряда приложений и теоретик ческих исследований класс бесконтекстных грамматик является недостаточным* Поэтому в течении ряда лет значительное внимание уделяется изучению более широких классов рекурсивных языков [5, 12, 26, 27 ].
Целью настоящей работы является определение и исследование нового типа грамматик, называемых многоуровневыми индексными грамматиками. Показывается, что многоуровневые индексные грамматики обладают многими свойствами бесконтекстных грамматик, обеспечившими их практическую применимость, и являются существенным расширением последних. Рассматривается также соотношение многоуровневых индексных грамматик и грамматик Вейнгаардена, использованных для описания языка Алгол 68.
Актуальность темы обусловлена трудностями при формальном описании современных языков программирования и необходимостью совершенствовать методы трансляции, а также расширением сферы применения формальных грамматик в других областях (теория развивающихся организмов [36] , схемы программ, логический вывод).
Предшествующее работы.
Активное развитие теория формальных грамматик начала после работы Хомского [I] , где вводится класс бесконтекстных грамматик в качестве модели для формализации синтаксиса фрашентов естественных языков. К настоящему моменту теория бесконтекстных грамматик хорошо разработана во многих направлениях [2, 3, 4, 21» 22] ; в ней получено много интересных и содержательных результатов. Установление эквивалентности бесконтекстных грамматик и магазинных автоматов явилось основанием для использования бесконтекстных грамматик для описания, реализации и исследования языков программирования* При этом магазинный автомат составлял основу синтаксической части транслятора* Бесконтекстные грамматики были удачно использованы для описания синтаксиса Алгола 60« Класс бесконтекстных грамматик мы обозначим
При дальнейшем развитии языков программирования выяснилось, что беоконтекстиых грамматик недостаточно для описания ряда конструкций* Так для описания Алгола 68 были введены грамматики Вейнгаардена (обозначаемые далее через V/" ), позволяющие добиться некоторой наглядности при описании языка. Примерно в то же время в работах А.х©[7, 3] были введены и изучены индексные грамматики (в наших обозначениях класс а в диссертации М* Фишера [э] были определены два класса грамматик 10 и 01, обобщающие известные тищ! макрогенераторов* Класс 01 грамматик оказался по порождающей способности эквивалентным классу индексных грамматик» Ахо показал, что индексные грамматики обладает основными из тех свойств бесконтекстных грамматик, которые делают их удобными для описания фрагментов естественных языков и языков программирования, а также определил для них класс допускающих автоматов.
Дальнейшие результаты, касающиеся индексных грамматик, получены в [9, 10, 18, 19] , см. также обзоры [б] и [12^ В [18] Ш. Грейбах обобщила метод построения допускающих автоматов для индексных грамматик.
Синцов [13] показал, что грамматики Вейнгаардена по-роадают все рекурсивно-перечислимые множества, поэтому невозможна система построения трансляторов на их основе (нет распознающего алгоритма). Этим в определенной мере обусловлена сложность реализации Алгола 68 (см. £371 ). у

Метод описания языка программирования (или фрагмента естественного языка в системе автоматического перевода) должен удовлетворять двум противоположным требованиям, первое, он должен позволять описывать как можно больше языков. Второе, для описанных языков должен иметься (достаточно простой) алгоритм анализа. 1 этом отношении введение индексных грамматик [?] и автоматов, допускающих индексные яжыки [в] , является существенным шагом по отношению к бесконтекстный грамматикам.