7.1.3. Конструктивные процедуры грамматического вывода

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

Метод Соломонова

В одном из первых обсуждений этой проблемы Соломонов (1964а, б) предложил метод вывода контекстно-свободных грамматик по конечной выборке. Его метод основан на теореме для контекстно-свободных языков (Хопкрофт и Ульман, 1969).

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

В теореме утверждается, что если — выборка из языка и порождается контекстно-свободной грамматикой, то достаточно длинная цепочка (если она существует), состоит из ядра окруженного двумя повторяющимися цепочками и х, из которых только одна может быть пустой, а также головной и и хвостовой у цепочками, которые обе могут быть пустыми. Грамматика языка должна содержать продукции для порождения таких предложений. В частности, она должна содержать продукции, с помощью которых можно вывести бесконечное множество подцепочек вида из некоторого нетерминального символа Один из способов — включить в грамматику продукции

Задача сводится к поиску подходящих цепочек и х.

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

Для иллюстрации этого метода выведем грамматику из выборки

Все цепочки в имеют вид Включим в продукции

Грамматика уже слишком обобщена, поскольку допускает цепочки вида которых нет в рассматриваемом языке. Это конкретная иллюстрация уже сделанного замечания об ограничениях при текстуальном представлении.

Затем алгоритм рекурсивно применяется к множеству

Все его цепочки имеют вид Заменим последние четыре продукции в (33) на и добавим продукции

Теперь рассмотрим множество Цепочки в нем имеют вид где X — пустая цепочка. Заменим последние три продукции в (34) на и добавим к грамматике

Разумеется, пустую цепочку можно отбросить. Множество далее нельзя уменьшить. Получается грамматика

Она порождает язык, содержащий выборку но не только ее одну.

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

пронумеруем цепочки из

Если определять цепочки так, чтобы они были единичной длины, как подразумевалось в предыдущем примере, то все они (кроме (1)) имеют вид , а начальное множество продукций таково:

Это множество продукций ведет к нежелательным последствиям: в дальнейшем получается слишком сложное множество продукций для этого простого случая. Кроме того, грамматика (38) допускает такие цепочки, как нежелательные в рассматриваемом языке. Другой способ исходит из того, что продукция должна быть в грамматике для вывода цепочки (1), а цепочка (3) имеет вид . Тогда начальным множеством продукций должно быть

Уже эти продукции создадут требуемый язык, но они обладают эстетическим недостатком, так как первые две определяют два различных типа основных арифметических выражений. Эту трудность можно обойти, если наш алгоритм подойдет к анализу предложений (37) с иных позиций. Напомним, что теорема позволяет, чтобы одна из цепочек или х была пустой. Предположим, что (37) — это множество предложений, в которых есть пустая цепочка К. Тогда последние три предложения имеют вид Опуская получаем грамматику

Эти две продукции порождают требуемые арифметические выражения так, что уровни вложения в полученной грамматике соответствуют разумной последовательности вычислений.

Итак, алгоритм создает основу для разработки нескольких алгоритмов грамматического вывода. Как показывает второй

пример, полезность обсуждаемого метода в каждом отдельном случае сильно зависит от выбранного способа выделения цепочек и х. Таким образом, упрощенный метод Соломонова сам по себе не приводит к разработке эквивалентных алгоритмов грамматического вывода. Полная процедура, которую применял Соломонов, несколько изящнее и ограничивается более узким классом порождаемых ею грамматик. Однако многие из проблем, упомянутых при обсуждении иллюстраций, остаются нерешенными. Интересующийся читатель может ознакомиться со статьями Соломонова (1964а, б) и их обсуждением в работе Бирмана (1971).

GRIN 1

Фельдман (1967; Фельдман и др. 1969) разработал программу осуществляющую грамматический вывод. Она ориентирована на вывод (регулярных) грамматик с конечным числом состояний, т. е. грамматик, продукции которых имеют вид или Регулярную грамматику, порождающую каждое из предложений некоторой фиксированной выборки, всегда можно найти, поскольку конечные языки могут определяться регулярными грамматиками.

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

Для иллюстрации метбда выведем грамматику из выборки

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

Сначала должна анализироваться цепочка формирует продукции

будет начальным символом нашей грамматики, так что с него должен начинаться каждый вывод. Затем анализируется еще одна длинная Новые продукции таковы:

Далее идет цепочка частично ее можно вывести с помощью уже имеющихся продукций. Применяя продукции в указанном порядке, получаем Осталось добавить только продукцию

Для вывода цепочки применяем получая в результате и добавляем

Для остальных цепочек добавляем

Вся грамматика состоит из продукций

Далее остаточные продукции сливаются. Например, продукция лишняя, так как есть продукция . Для вывода последовательности пишем вместо Это позволяет отбросить остаточную продукцию и лишнюю продукцию Аналогично отбрасывается Новая грамматика состоит из продукций

Заметим, что новая грамматика содержит рекурсивные конструкции и, таким образом, способна породить бесконечный язык.

Наконец, грамматика упрощается еще больше, но так, чтобы порождаемый ею язык не изменился. Для этого сливаются продукции, которые отличаются только обозначением переменной. В (49) можно подставить вместо во второй и третьей строках, и тогда получатся две одинаковые строки. Подобным же образом сливаются и А 5. Отметим, что при этом необходимо сделать соответствующую замену во всем множестве продукций. В результате получается упрощенная грамматика

Для построения из цепочек стержневых грамматик была написана похожая, но более сложная программа GRIN 2. Эти грамматики могут порождать языки, обладающие многими свойствами простых языков программирования.

Вывод с использованием семантики

Практически применяемые грамматики образованы не абстрактными продукциями, а командами построения предложений, имеющих смысл. Рассмотрим, в частности, языки программирования. Оператор на Фортране

— это команда „выбрать из памяти значение С, поместить его в рабочий регистр, выбрать из памяти значение В, сложить со значением С, хранящимся в рабочем регистре, и поместить результат в регистр для Семантическая структура формулы (51) с учетом порядка выполнения операций имеет вид

где каждый уровень вложения соответствует элементарной операции на Фортране. В работах Креспи-Регицци (1971) и Креспи-Регицци, Мелканов и Лихтен (1973) излагается процедура грамматического вывода, в которой для вывода грамматики, лежащей в основе рассматриваемого языка, используется знание семантики предложений в выборке. Креспи-Регицци с соавторами высказали мысль о том, что эта процедура могла бы помочь разработчикам языков программирования, позволив им описывать примерами язык, который они хотят получить, вместо того, чтобы давать его формальное определение. Соответствующая грамматика была бы построена тогда при помощи вывода по примерам.

Вывод осуществляется в три этапа. (1) Для каждой цепочки из формируется пробная грамматика. („Не предложения" не рассматриваются.) Грамматика, построенная для одной цепочки, достаточна для порождения именно этой цепочки. (2) Каждая пробная грамматика затем обобщается описанным ниже способом. (3) Наконец, различные пробные грамматики сливаются, и окончательная грамматика представляет собой объединение обобщенных пробных грамматик. Детали метода можно проиллюстрировать на примере одного предложения. Пусть

где а — это неформально „имя переменной". Предложение (63) служит примером цепочки сложений. Ее семантическая структура указывает на то, что сложения выполняются в порядке справа налево.

Для построения пробной грамматики предположим, что — цепочка в на самом нижнем уровне вложения. Она целиком состоит из терминальных символов. Продукция очевидно, должна принадлежать этой грамматике. Подстановка вместо убирает один уровень вложения. Пусть у — цепочка (нового) самого нижнего уровня вложения. Отметим, что у может содержать нетерминальные символы. Добавляем к грамматике продукцию и действуем, как раньше. Продолжаем добавлять продукции до тех пор, пока не будет убран самый верхний уровень вложения. Для примера (53) последовательность результатов такова:

Грамматика (54) порождает в точности цепочку (53). Для обобщения грамматики нетерминальные символы объединяются в классы, определяемые цепочками терминальных символов, выводимыми из нетерминалов одного класса. Из двух предложенных Креспи-Регицци и др. алгоритмов мы опишем более простой. В этом алгоритме два нетерминала сливаются, если множества терминалов, которые могут появиться в качестве первого или последнего символа цепочек, выводимых из каждого нетерминала, совпадают. Точнее, пусть продукция принадлежит пробной грамматике. Определим левое терминальное множество цепочки как множество терминальных символов, которые могут появиться в качестве самого

левого терминального (не обязательно самого левого) символа в цепочке, выводимой из . Аналогично определим правое терминальное множество . Терминальным сечением для назовем упорядоченную пару Два нетерминала и сливаются, если их терминальные сечения совпадают.

Применим этот метод обобщения к грамматике (54), чтобы лучше разобраться в работе алгоритма. Но сначала надо задать правило вычисления терминального сечения.

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

Обобщим теперь грамматику (54). Первый шаг — нахождение

Подставляя вместо символа его терминальное сечение, подсчитываем

Делаем подстановку опять, на этот раз для подсчета

Поскольку имеют одинаковые терминальные сечения, то может везде заменить . В результате получаем грамматику

Грамматика (58) порождает такие цепочки, как

представляющие собой разумное обобщение цепочки (53). Действительно, для формирования грамматики, описывающей арифметические выражения, достаточно 10 продуманно выбранных предложений. Ясно, что этот алгоритм обладает рядом интересных свойств. Вместе с тем он имеет и недостатки. Креспи-Регицци и др. отмечают, что алгоритм формирует ограниченное множество грамматик операторного предшествования (Айронс, 1961). Чтобы поправить дело, они предлагают метод обобщений, в котором нетерминалы сливаются только в том случае, когда их терминальные сечения совпадают (если рассматривать не более выводов). Полученная процедура формирует более широкий класс грамматик. Другая важная характеристика их метода (не ясно, что это — достоинство или недостаток) состоит в том, что он сильно зависит от качества выборки. Это заставляет разработчика языка быть особенно тщательным в своих исследованиях, что, возможно, и хорошо.