За последнее время в различных областях математики возрос интерес к использованию аппарата формальной лингвистики. В первую очередь это относится к порождающим грамматикам, которые представляют собой удобное средство для описания структуры объектов. Если при разработке и реализации языков программирования выбор грамматики возлагается на человека, то в распознавании образов и некоторых других дисциплинах возникла задача построения грамматики по известному конечному множеству порожденных ею предложений (образцу). В отечественной литературе она встречается под двумя названиями: задача восстановления грамматики и задача грамматического вывода. Уже сам факт неоднозначного именования отражает нестабильность и некоторую противоречивость взглядов на задачу. Дело в том, что алгоритмы построения грамматик уже довольно давно применяются в различного рода системах распознавания образов (речь идет о структурном подходе), но лишь недавно возник интерес к этой задаче, как к самостоятельной области исследования. В обзорах [1, 2] систематизированы существующие методы построения грамматик, однако вопрос о постановке задачи практически не затрагивался, что снижает их ценность. В настоящее время существуют и разрабатываются новые методы решения недостаточно формализованной задачи.

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

Задача грамматического вывода рассматривается в связи с функционированием модели грамматического вывода. Основными компонентами модели являются источник и анализатор. Источник - это некоторое устройство, которое располагает языком L_и (языком источника). На каждом такте своей работы источник передает одно новое слово из L_и на вход анализатора. Фактически источник формирует последовательность образцов {Ω_i | i ≥ 1}, где Ω_i состоит из слов,переданных на первом, втором, ..., i-м тактах. Анализатор - это некоторое устройство, которое на i-м такте своей работы по образцу Ω_i строит конечное множество грамматик G_i (множество решающих грамматик). При этом анализатор применяет к образцу алгоритм (метод) восстановления M.

Задача грамматического вывода называется разрешимой для языка источника L_и, последовательности образов {Ω_i | i ≥ 1} и метода восстановления M, если существует число l такое, что множество решающих грамматик G_l, полученное из образца Ω_l методом М, содержит грамматику g* такую, что L(g*) = L_и.

Рассмотрим подробнее понятия, участвующие в формулировке задачи.

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

В модели грамматического вывода не делается никаких предположений о природе и устройстве источника. Наиболее общее предположение на этот счет состоит в том, что источник располагает грамматикой источника g_и такой, что L(g_и) = L_и. Однако в постановке задачи приоритет отдан языку источника, что позволяет делать предположения о свойствах грамматики g_и. В задаче грамматического вывода сложилась четкая тенденция развития в соответствии с классификацией Хомского.

Для регулярных грамматик задача исследована в работах [5, 6]. В наиболее полном и изящном методе Фельдмана [6] предполагается, что регулярная грамматика g_и удовлетворяет следующему условию: для любой тройки нетерминалов A, B, С и любого терминала а множество правил вывода не содержит правил A → aB, А → aC. Заметим, что элементы множества решающих грамматик, в том числе и грамматики, порождающие L_и, могут не удовлетворять этому условию. Такое свойство метода Фельдмана не является фатальным; в методе восстановления LL(1)-грамматик [4, 7], который представляет собой обобщение метода Фельдмана, множество решающих грамматик образует LL(1)-грамматики.

Для контекстно-свободного языка источника, кроме метода восстановления LL(1)-грамматик, исследованы случаи, когда L_и - однозначный КС-язык [4, 8], язык, порождаемый грамматикой со свободным операторным предшествованием [9], конечно-характеризуемый язык [4, 10]. Методы восстановления контекстно-зависимых грамматик в настоящее время имеют эвристический, узкоспециализированный характер.

Последовательность образцов - ключевое понятие для понимания специфики задачи восстановления. Тип последовательности образцов и класс языка источника определяют область применимости того или иного метода восстановления.

Любая последовательность образцов { Ω_i | i ≥ 1 }, должна удовлетворять естественному необходимому условию: существует минимальное число l₀ такое, что слова образца Ω_l0 содержат все терминальные символы языка источника. Строго говоря, метод восстановления целесообразно применять только для образцов Ω_l при l ≥ l₀.

До настоящего времени задача восстановления исследовалась для трех типов последовательности образцов:
1) структурно-полной последовательности [1], относительно фиксированной грамматики источника g_и, когда для любого правила вывода из g_и на вход анализатора передается хотя бы одно слово, при выводе которого использовалось это правило;
2) полной положительной последовательности [1], когда каждое слово языка источника передается на вход анализатора;
3) фундаментальной последовательности, когда для любого l ≥ 1 существует номер m = m(l,L_и) такой, что

{ x ∈ Lи | |x| ≤ l } = Ωm.

(1)

Понятие типа последовательности существенно влияет на метод восстановления. Так, в основе метода Пао, ориентированного на структурно-полную последовательность образцов, лежит полный перебор [5]. Метод оказывается неэффективным даже для довольно простых языков источника. Методы восстановления, ориентированные на полную положительную последовательность, существенно используют тот факт, что для любого l ≥ 1 существует m = m(l,L_и) такое, что

{ x ∈ Lи | |x| ≤ l } ⊂ Ωm.

Как правило, эти методы сопровождаются неформальной рекомендацией, согласно которой слова языка источника должны подаваться на вход анализатора равномерно по длине слова. Методы восстановления, применяемые для фундаментальной последовательности образцов, предполагают, что образец каждый раз удовлетворяет равенству (1), где l - максимальная длина слов образца. Поэтому для любого слова y, |y| ≤ l, может быть проверено условие y ∈ L_и.

Анализатор. Его конкретная природа (также, как и источника) в формулировке задачи грамматического вывода не уточняется, хотя все разработчики методов восстановления согласны, что анализатор - это программа, содержащая в качестве своего основного модуля метод восстановления.

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

В некоторых задачах источник выполняет более сложную работу по одновременному формированию двух последовательностей образцов -
положительной { Ω_i | i ≥ 1 }, Ω_i ⊂ L_и, и
отрицательной { Ω^-_i | i ≥ 1 }, Ω^-_i ∩ L_и = ∅.
В предложенной модели грамматического вывода такое функционирование источника не предусмотрено, поскольку роль элементов отрицательного образца пассивна; они используются только в качестве теста проверки при описанной тактике поведения анализатора. Пока не известны методы восстановления, которые могли бы анализировать структуру отрицательного образца. С появлением таких методов для отрицательной последовательности необходимо будет ввести некоторые ограничения (аналогично положительной последовательности). Есть основания предполагать, что эти гипотетические условия будут эквивалентны требованию фундаментальности.

Итак, в реальных системах восстановления анализатор может применять различные тактики восстановления. На этом обстоятельстве необходимо остановиться и сказать несколько слов о разграничении функций между компонентами модели грамматического вывода. В формулировке задачи на каждом такте работы анализатор выполняет только одну операцию: строит множество решающих грамматик G_i, применяя метод М к образцу Ω_i. В частности, анализатор не должен разбивать образец на подобразцы и строить множество G_i, как объединение соответствующих подмножеств, полученных применением метода М к подобразцам. Аналогично метод восстановления (если рассматривать его, как программу) не должен содержать никаких объемлющих циклов, в которых происходит переформирование образцов. Право формировать образцы принадлежит только источнику.

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

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

На первом этапе по образцу строится одна или несколько нерекурсивных грамматик, порождающих все слова образца. Каждая такая грамматика представляет собой конечную структуру образца. Конкретное представление этих грамматик может быть весьма разнообразным, так в методе восстановления регулярных грамматик Фельдмана первый этап состоит в левой факторизации образца [11]. В методах восстановления однозначных КС- и LL(1)-грамматик нерекурсивные грамматики представляются в виде П-сетей с ребрами, помеченными терминальными символами. На первом этапе используются свойства грамматик тех классов, на которые ориентирован метод. Для контекстно-свободных грамматик часто используется лемма о разрастании КС-языков [11] или ее модификации [8].

На втором этапе с помощью специальных методов укрупнения структуры образца строится множество решающих грамматик. Основу каждого метода укрупнения составляет критерий отождествления пары нетерминалов. В методе Фельдмана критерий отождествления зависит от целочисленного параметра k. Для единственной нерекурсивной грамматики g₀, полученной на первом этапе, параметр k может принимать конечное число значений 0 ≤ K ≤ d, где d - максимум глубин по всем деревьям вывода в g₀. Таким образом, метод укрупнения Фельдмана по конечной структуре образца g₀ строит, вообще говоря, несколько решающих грамматик g(k), k = 0, ..., d. Другой метод, предложенный Креспи-Регицци [9] для грамматик со свободным операторным предшествованием, по конечной структуре строит одну решающую грамматику.

Ситуация, при которой построение множества решающих грамматик проходит в два этапа, типична, но не обязательна. В качестве контрпримера можно привести метод восстановления грамматик, порождающих конечно-характеризуемые языки. Однако выделение двух этапов правомерно, так как методы конечного структурирования и укрупнения структуры образца в определенной степени независимы и имеют разные области применимости. Например, метод восстановления однозначных КС-грамматик, предложенный автором [4], включает в себя метод укрупнения, который применим и для более широкого класса КС-грамматик.

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

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

Множество решающих грамматик G_i полностью определяется методом и образцом Ω_i. При этом все элементы G_i должны удовлетворять необходимому условию:

∀ g ∈ Gi : ⊂ L(g)

(2)

В зависимости от метода условие (2) либо проверяется в явном виде на последнем шаге, либо может быть доказано. Разделение методов на две группы относительно способа проверки условия (2) тесно связано с понятием устойчивости метода. Вопрос об устойчивости ставится следующим образом. Допустим, что источник по неизвестным причинам передал на вход анализатора несколько слов, не принадлежащих языку Lи. Можно ли с помощью метода восстановления обнаружить эти слова? Для метода Фельдмана, например, ответ на этот вопрос отрицателен - метод абсолютно неустойчив. По-видимому, говорить об абсолютно устойчивых методах бессмысленно, однако есть методы, позволяющие находить некоторые ошибочные слова. Так, методом восстановления однозначных КС-грамматик может быть обнаружено ошибочное слово, содержащее, например, символ, не встречающийся в других словах. На последнем шаге этого метода строится множество Ω^g' = Ω_i \ L(g'), причем решающая грамматика g = < N, Σ, P, S > получается из g'= < N', Σ', P', S' > добавлением правил вывода:

Ошибочное слово всегда принадлежит пересечению множеств Ω^g'. Устойчивость методов восстановления - совершенно неисследованная проблема грамматического вывода.

Само по себе множество решающих грамматик малоинформативно. Большой интерес для практических приложений представляет иерархия по порождающей мощности. Как известно, уже для пары произвольных КС-грамматик сравнение их порождающих мощностей представляет алгоритмически неразрешимую проблему. Однако для решающих грамматик некоторые соотношения такого рода могут быть получены непосредственно из метода восстановления. Например, для метода Фельдмана доказано, что

На этом заканчивается обсуждение задачи грамматического вывода. Большая часть аспектов задачи выявлена в процессе разного рода обсуждений. Автор выражает глубокую благодарность Н.П.Трифонову, Ю.И.Журавлеву, И.В.Задыхайло, В.Ш.Кауфману, М.Г.Мальковскому, М.Р.Шура-Буре за полезные обсуждения работы.

Цитированная литература

1. Фу К. Структурные методы в распознавании образов. -М.: Мир, 1977.
2. Хант Э. Искусственный интеллект. - М.: Мир, 1978.
3. Соловьев С.Ю. Об одной конструктивной процедуре грамматического вывода. - Вестник Московского ун-та. Сер. 15, "Вычислительная математика и кибернетика", 1980, с.44-48.
4. Соловьев С.Ю. Методы восстановления контекстно-свободных грамматик. - В кн.: Вопросы теоретического и прикладного программирования. - М.: Изд-во МГУ, 1980, с. 82-87.
5. Fu К., Booth T. Grammatical Inference: Introduction fnd Survay - Part I. - IEEE Transaction on Systems, Man and Cybernetics, 1975, SMC-5, N 1, p.95-111.
6. Biermann A., Feldmann J. On the Synthesis of finite-state machines from samples of their behavior. - IEEE Trans. Comp., 1971, C-21, P.592-597.
7. Соловьев С.Ю. Метод восстановления LL(1)-грамматик. - В кн.: Прикладная математика и математическое обеспечение ЭВМ. - М.: Изд-во МГУ, 1980, с.92-93.
8. Соловьев С.Ю. Подход к восстановлению контекстно-свободных языков. - В кн.: Автоматизация производства пакетов прикладных программ. - Таллин: Изд-во Таллинского политехнического ин-та, 1980, с.126-129.
9. Crespi-Reghizzi S., Melkanoff M., Lichten L. The use of grammatical inference for designing programming language. CACM, 1973, 16, N 2, p.83-90.
10. Гладкий А.В. Конфигурационные характеристики языков. - Проблемы кибернетики, 1963, вып.10, c.261-260.
11. Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. Т.1. - М.: Мир, 1976.