Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

тельного предложения, вопросительного или отрицательного, или из активной конструкции, пассивной).

2. НС-грамматика строит предложения с точно определенным порядком слов. В синтаксической структуре, определяемой НСграмматиками, не расчленены два совершенно различных по своей природе, хотя и связанных между собой отношения: синтаксическое подчинение и линейное взаиморасположение.

Порождаемому предложению сопоставляется синтаксическая структура в форме упорядоченного дерева, т. е. дерева, где между узлами, кроме отношения подчинения, задаваемого самим деревом, имеется еще и отношение линейного порядка (правее — левее).

Таким образом, порождающие грамматики имеют дело только с синтаксисом языка, т. е. с законами построения правильных сло­ воформ и предложений.

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

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

Рассмотрим класс грамматик, состоящих из двух компонент:

1. Из НС-компоненты, представляющей собой НС-грамматику с

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

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

Цепочка, полученная в результате применения всех обязатель­ ных и в случае необходимости некоторых факультативных транс­ формаций, называется Т-терминальной цепочкой.

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

116

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

Трансформации, применимые к одному С-маркеру, будем назы­

Сингулярные трансформации часто сводятся к простым пере­ становкам элементов исходной цепочик (С-маркера), к добавлению константных цепочек в заданное место или к устранению некото­ рых элементов исходной цепочки. Сингулярные трансформации яв­ ляются элементарными трансформациями.

Обобщенные трансформации основываются на элементарных

торого структурного дерева оч на структурное дерево сг2, то С-мар- кер результирующей цепочки есть' С-маркер cri, где а заменен С-маркером tf2.

Другим видом обобщенной трансформации может быть транс­ формация присоединения к одному С г маркеру другого С2 -маркера.

Таким образом, Т-грамматика основана на правилах НС-грам­ матики, к которым добавлены конечное число трансформаций оп­ ределенного типа, а также ограничений относительно порядка при­ менения трансформаций. Структура, полученная в результате при­ менения некоторой трансформации, в общем случае может быть подвергнута новым трансформациям, так что путем повторного при­ менения трансформаций можно получить бесконечное множество С-маркеров самых различных типов.

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

применимая к элементам из С т множества;

117

формации Т, если t может быть проанализирована относительно Ct

анализа. Действие трансформации при этом заключается в пере­ становке или выбрасывании некоторых элементов собственного анализа t, в замене их на некоторые другие, в постановке на задан­ ное место некоторых постоянных цепочек.

Структурный индекс (ф1, ц>п) определяет возможность / — цепочки, т. е. разложения Т-терминальных цепочек на элементы соб­ ственного анализа, которые конкретно задают область применения трансформации.

Значение Т-грамматики состоит в том, что она позволяет ре­ шить проблему анализа структур различной сложности и выступает как объяснительная теория грамматик вообще.

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

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

Сущность К-грамматик состоит в том, что для реализации син-

118

таксического кода все синтаксические классы делятся на два типа: элементарные синтаксические классы и операторы.

Например, имеются элементарные синтаксические классы 5И м (существительное в именит, падеже) и ПРЕДЛ — (предложение) . Тогда синтаксический класс, присоединяемый к 5И м справа и даю­ щий предложение, есть оператор, действующий на 5 И М справа и пе­

где Т — конечное множество символов, называемое терминальным или основным словарем (словарь словоформ);

Я— конечный набор элементарных категорий (ЭК), из кото­ рых строятся категории в Я следующим образом:

9

{?/<!>} <|>.

119