Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[0]

бесконтекстный язык

Теория формальных языков возникла во второй половине пятидесятых годов. Она использовала для целей описания языков уже существовавший в математике формальный аппарат. В работах Н. Хомского [Chomsky 56], [Chomsky 57], [Chomsky 59a] были выделены классы специальных исчислений, названных им грамматиками, играющие важную роль в современных приложениях теории формальных языков.

Особо важным среди выделенных классов является класс сравнительно про стых бесконтекстных грамматик, которые называют также контекстно свобод ными. Весьма распространено употребление аббревиатуры "КСграмматика". Но термин "бесконтекстная грамматика"кажется нам более удачным стилистически. Изучение именно бесконтекстных грамматик обусловило своеобразное врастание теории формальных языков в информатику.

Теория формальных грамматик сразу же сомкнулась с теорией автоматов. В начале шестидесятых годов было формализовано понятие магазинного автомата [Oettinger 61], [Schutzenberger 63] и установлено, что язык является бесконтекстным тогда и только тогда, когда он допускается магазинным автоматом [Chomsky 62], [Evey 63]. Отметим, что полезность магазинов была понята еще в пятидесятых годах [Burks -Warren -Wright 54], [Newell -Shaw 57], [Ершов 58].

Потребности теории и практики перевода языков программирования обусловили наибольший интерес к подклассам магазинных автоматов, обладающих свойства ми однозначности и детерминированности. Согласно [Ginsburg 66] однозначные магазинные автоматы введены в [Haines 65]. Детерминированные магазинные ав -томаты, хотя и в особой форме и под другим названием, впервые изучались в [Schutzenberger 63]. В частности, там было доказано, что детерминированный, т. е. допускаемый детерминированным магазинным автоматом, бесконтекстный язык является однозначным. Многие свойства детерминированных магазинных автоматов и детерминированных языков были исследованы в [Ginsburg Greibach 65], [Ginsburg Greibach 66].

Работа по переводу (трансляции) языков программирования вызвала интерес к формальному определению перевода, т. е. отношения, связывающего с каждой цепочкой языка другую цепочку - результат перевода. В [Feldman -Gries 68] высказывается мнение, что с развитием теории перевода программирование на чало возвращать долг теории формальных языков. С понятиями бесконтекстной грамматики и конечного и магазинного автоматов связаны соответственно два фундаментальных метода определения перевода: с помощью так называемой схе мы перевода и с помощью преобразователя. К пионерским работам о первом из методов, по другому, о синтаксически управляемой трансляции, относятся [Irons

61] и [Barnett Futrelle 62].

Первое приближение к современному понятию конечного преобразователя бы ло дано в работе [Ginsburg 62]. Затем оно последовательно обобщалось в работах [Chomsky 62] и [Elgot -Mezei 65]. Преобразователь с магазинной памятью - это магазинный автомат, который снабжен выходной лентой и, разумеется, способно стью писать на ней и о котором говорят, что преобразователь с ним согласован [Ginsburg 66] или что он лежит в основе преобразователя [Aho -Ullman 72]. Результат перевода пишется на выходной ленте слева направо по мере чтения


входной цепочки. Понятие преобразователя с магазинной памятью, используемое и в нашей работе, впервые формализовано в [Evey 63].

Отметим, что синтаксический анализ можно рассматривать как перевод, при котором порождаемые бесконтекстной грамматикой цепочки отображаются в некоторые представления их деревьев вывода. Понятие дерева вывода, издавна при менявшееся в лингвистике, можно найти во многих источниках под различными названиями. В явной форме оно содержится в [BarHillel -Pedes -Shamir 61]. Среди представлений дерева вывода популярны левый или правый выводы и разбор, определяемый, например, как обращение правого вывода. Заметим, что идея "дисциплинированного"вывода появилась в [Evey 63]. Точнее, там рассматривал -ся левый вывод. Обсуждаемые в нашей работе преобразователи с магазинной памятью сопоставляют входным цепочкам их разборы.

Очень скоро стало понятным, что класс детерминированных языков содержит довольно обширные и удовлетворительно отражающие синтаксические черты язы ков программирования подклассы, в случае которых можно строить анализаторы (т. е. алгоритмы синтаксического анализа), расходующие на обработку цепочки длины n время c\n и память c2n, где о\ и c2 - малые константы. Среди методов синтаксического анализа, рассчитанных на такого рода подклассы детермини рованных языков, большую популярность приобрели методы предшествования, публикации о которых появились в начале шестидесятых годов [Floyd 63], [Pair 64].

Методы предшествования изучались и обобщались многими исследователями. Наиболее полная, повидимому, библиография по этому вопросу имеется в [Aho -Ullman 72], [Aho -Ullman 73]. Между прочим, работы [Floyd 63] и [Wirth -Weber 66] (последняя излагает полученный независимо от [Pair 64] метод про стого предшествования) произвели на нас большое впечатление и повлияли на наше восприятие других методов синтаксического анализа. В [Гончарова 75], [Станевичене 76], [Станевичене 78], [Stanevichene 79], [Миронова -Станевичене 82] было, в частности, формализовано определение "добавки"к методу простого предшествования, необходимой для получения LR(k) метода [Knuth 65]. Полу ченная вариация LR(k) метода применима на практике. Опыт применения описан в [Изимбетов 88], [Миронова 92].

В 1965 году появилась знаменитая статья [Knuth 65], в которой было обнаруже но, что время и память, пропорциональные длине анализируемой цепочки, доста точны в случае любого детерминированного языка. Она вызвала многочисленные попытки усовершенствовать или обобщить предложенный в ней механизм синтак сического анализа детерминированных языков. Интерес к этой теме не остыл до сих пор, как свидетельствует, например, статья [Lee Choe 94]. Однако отложим обсуждение этого направления исследований, чтобы указать другие направления, намеченные основоположниками теории формальных языков.

В ранних работах по теории формальных языков [Chomsky 62], [Chomsky 63], [Chomsky Schutzenberger 63] приведено любопытное наблюдение о возможно сти характеризовать языки морфическими образами множеств, в бесконтекст ном случае определяемых с помощью языков Дика. Обзор результатов, имеющих аналогию с теоремой ХомскогоШютценберже о представлении каждого


бесконтекстного языка морфическим образом пересечения языка Дика с локальным (в [Chomsky -Schutzenberger 63] локальный язык назван стандартным регулярным событием), приводится в [Hirose -Okawa -Yoneda 85]. Некоторые результаты о представлении языков посредством морфизмов отнесены к математическим жемчужинам [Salomaa 81].

Отметим также характеризации бесконтекстных языков системами уравнений и специфическими выражениями, указывающими на стремление авторов разработать схемы исследования бесконтекстных языков, аналогичные успешно примененным в теории регулярных языков. К наиболее ранним зарубежным работам по этой теме относится [Interna 67]. Некоторые последующие работы переведены на русский язык, например, [Gruska 71], [McWhirter 71]. В тот же период тема разрабатывалась отечественными учеными; так, в [Гладкий 73] рассматривают -ся подстановочные выражения, теория которых восходит к работам [Диковский 72а], [Диковский 72б].

Система уравнений для задания бесконтекстного языка [Летичевский 69] яв -ляется результатом алгебраической трактовки агазинного автомата. Заметим, что такая система легко усматривается в нашем так называемом ядре магазинного автомата.

Теория формальных грамматик и языков рассматривает некоторые алгоритмические проблемы, что естественно для дисциплины, возникшей из потреб ностей лингвистики и информатики. Многие алгоритмические проблемы оказались неразрешимыми, что было установлено к середине шестидесятых годов. Повидимому, самая ранняя публикация в этом ряду - это работа [BarHillel -Perles Shamir 61], в которой доказана неразрешимость проблемы эквивалентно сти бесконтекстных грамматик - весьма важный факт, заставляющий применять для преобразования языковых описаний лишь процедуры, которые заведомо да дут эквивалентный результат. Еще один из впечатляющих (по крайней мере, на наш взгляд) фактов этого ряда - нераспознаваемость неоднозначности бескон текстных языков, независимо доказаннная в [Гладкий 65б] и [Ginsburg Ullian

Таким образом, в шестидесятые годы бурно шло накопление результатов теории бесконтекстных языков. Книга [Гладкий 73] и другие источники свидетельству ют, что советские ученые уже в этот период внесли большой вклад в теорию формальных языков; яркое явление - работы А.В.Гладкого и А.А.Летичевского, например. Тогда же были поставлены вопросы, и сейчас остающиеся актуальны ми. Они связаны с построением алгоритмов, которые обслуживали бы потребно сти приложений, заинтересованных в автоматическом преобразовании языковых описаний достаточно широкого класса, в проверке эквивалентности таких описа ний. Отсутствие приемлемых алгоритмов вынуждает к использованию наиболее простых формальных языковых моделей и к преодолению возникающих при этом трудностей специальными для каждого случая приемами.

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



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49]