В правилах НС-грамматик по определению заменяется только один символ, левая же часть правила не обязательно состоит из одного символа w
( А®w).
В правилах могут присутствовать и другие символы, то есть контекст:
jАy®jwy.
Разрешается заменять А на w только в контексте j и y. Сам контекст при этой записи просто переписывается.
Правила, использующие контекст, называются контекстно-связанными, а правила, не имеющие контекста – контекстно-свободными(КС-правилами).
НС-грамматики, содержащие только КС-правила вида А®w, называется контекстно-свободными грамматиками (КС-грамматиками).
Языки, порожденные КС-грамматиками, называются КС-языками.
КС-грамматики представляют собой важный частный случай НС-грамматик. Их ценность обусловлена двумя обстоятельствами:
-отказ от контекста делает грамматику более простой;
-хотя в естественных языках запись одних единиц другими часто допустима только в определенных контекстах, целесообразно исследовать возможность описывать языки, отвлекаясь от этого факта, то есть в терминах КС-грамматик, хотя описание может усложниться.
Например, могут потребоваться новые категории, правила.
В самых общих чертах такая замена делается следующим образом :
пусть элементы класса Х ведут себя по-разному в соседстве с элементами класса Y и класса Z, то есть имеют место правила:
YX®YAB;
ZX®ZCD.
Введем новые символы Х1 и Х2.
Элемент Х в позиции после Y обозначим Х1, а Х после Z – через Х2, тогда приходим к КС-правилам:
X1®AB,
X2®CD.
Однако не всякая контекстно-связанная НС-грамматика может быть заменена эквивалентной ей КС-грамматикой.
Существует НС-языки, не являющиеся КС- языками, например, язык, состоящий из всевозможных цепочек вида:
(aba,aabbaa,…) или цепочек вида 
.
От контекста нельзя отказаться, если правило должно обеспечивать перестановку символов, так как по существу - это многомерная операция. Следовательно, КС-грамматики не могут порождать язык, содержащий цепочки, которые не могут быть построены без применения перестановок.
До сих пор мы занимались введением ограничений на левые части правил грамматик.
Сначала потребовали, чтобы число символов в правой части было бы не меньше, чем в левой и получили неукорачивающие грамматики, затем потребовали, чтобы замене подвергался только один символ, и получили НС-грамматики. Наконец, мы потребовали, чтобы в левой части правила вообще был один символ, и получили КС-грамматики.
Ясно, что никаких дальнейших ограничений на левую часть наложить нельзя. Поэтому, если мы хотим выделить еще более узкие классы грамматик, то придется накладывать ограничения на правые части.
Начнем с части символов в правой части. В зависимости от числа символов в правой части КС-грамматики можно разделить на два класса:
-бинарные и
-небинарные.
КС-грамматики будем называть бинарными, если правая часть любого правила КС-грамматики содержит не более двух символов.
Например:
A®BC,
A®bB,
A®B,
где A,B,C Î VH , b Î VT .
КС-грамматики будем называть небинарными, если правая часть любого правила содержит более двух символов.
Например:
A®Aab,
В®ABC,
A®w,
где A,B,C Î VH, a,b Î VT, w – непустая цепочка из более чем двух символов.
В С-маркерах, соответствующих бинарным КС-грамматикам из каждой вершины исходит не более двух ветвей. Это значит, что любая сложная составляющая всегда состоит ровно из двух непосредственно вложенных в нее составляющих.
В зависимости от числа входящих в правую часть нетерминальных символов КС-грамматики подразделяются на линейные и нелинейные.
Линейные грамматики – такие КС-грамматики, правые части которых содержат не более чем по одному вхождению нетерминального символа.
Таким образом, для бинарных КС-грамматик это правило вида :
А®aB, A,BÎVH, aÎ VT,
для небинарных КС-грамматик:
A®aBab, A®acB,
A,BÎ VT , a, b, c Î VT.
Соответственно языки, порождаемые этими грамматиками, будем называть линейными и нелинейными.
КС-грамматика называется металинейной , если правая часть ее правил не содержит цели грамматики и все правила, левые части которых отличны от цели , имеют такой же вид, как правила линейной грамматики.
Примером металинейной грамматики может служить следующая грамматика:
G=( {a,b,c}, {S,T}, {SàTT, TàaTa, TàbTb, Tàc},S).
Язык называется металинейным, если существует порождающая его металинейная грамматика.
Накладывая ограничения на состав символов правой части привил КС- грамматик, Флойд выделил следующие подклассы небинарных нелинейных грамматик:
Операционные грамматики – это грамматики, правые части правил, которых не могут содержать двух рядом стоящих нетерминальных символов.
Напрмер, AàBbC,
Aà BbcC, где A,B,C- нетерминальные символы, а b,c- терминальные символы.
Грамматики предшествий – это грамматики, правые части которых могут содержать два рядом стоящих терминальных символа.
При этом имеется возможность указать, какой из этих терминальных символов возникает в словообразовании первым, имеющим больший приоритет.
Например, Aà BaaB, где А,В – нетерминальные символы, а – терминальный символ.
Односторонние линейные грамматики – это грамматики, правые части правил которых содержат терминальные символы, только с одной стороны от нетерминального символа.
Односторонние линейные грамматики подразделяются также на левосторонние и правосторонние.
Левосторонние грамматики имеют правила следующего вида: Aà xB, Aà x, а правосторонние, соответственно, правила вида: А-->Bx, A-->x. Здесь A,B – нетерминальные символы, а x – непустая цепочка терминальных символов.
Односторонние линейные грамматики, у которых в каждом правиле цепочка x состоит только из одного символа, называются автоматными или А – грамматиками, а языки, порождаемые этими грамматиками – автоматными языками.
Взаимосвязь рассмотренных классов порождающих грамматик можно представить в виде следующей схемы:
Таким образом, КС – грамматики представляют собой наиболее важный подкласс НС – грамматик. Это объясняется четырьмя основными причинами:
-КС- грамматики является основой определения почти всех известных языков программирования;
-Все действия системы синтаксического анализа для естественных языков основаны на КС- грамматиках;
-Это единственный тип грамматик, теория которых изучена и практически проверена;
-Все трансформационные грамматики построены на основе КС- грамматик.
Рассмотренные типы грамматик порождают НС – язык, КС – язык, линейный язык, А – язык, не считая языка, порождаемого самым общим типом грамматики неограниченными правилами вывода – грамматикой типа 0 .
Взаимосвязь между языками, порождаемыми рассмотренными типами грамматик будет следующей:
.
0 коммент.:
Отправить комментарий