Кук Д., Бейз Г. - Компьютерная математика (1048841), страница 41
Текст из файла (страница 41)
Еще большее значение имеет тот факт, что мы можем включить все предложения вида ««Ье йои ЬИ («Ье зоп о1)" Маро1еоп» (их бесконечное множество), добавляя и Т и Р незначительное число элементов. » Перед тем как описать механизм порождения предложений, мы должны упомянуть нотацию, введенную Бэкусом (нормальная форма Вакуса или форма БэкусаНаура, БНФ). Она особенно полезна, когда мы хотим использовать элементы из У, которые можно спутать с элементами из Т такими, как <предложение> и «предложение». Эта нотация использует четыре символа: н (мета-присвоить), < (мета-открыть), ) (мета-закрыть), ! (мета-или).
Понятия «мета-открыть» и «мета-закрыть» используются для того, чтобы выделять строки в качестве элементов У, «мета-присвоить» заменяет символ -, и если (а, р) ы Р, (а, "() ы Р, то это может быть записано в виде а::= (1! "(, что читается как «««есть 6 или (». БНФ впервые использовалась для определения синтаксиса Алгол-60. В случае, если у читателя имеются какие-либо сомнения в том, что БНФ способна определить что-нибудь серьезное, рекомендуем прочитать сообщение про Алгол-60.
В работах по формальным языкам обычно избегают длинных строк в У и, следовательно, нотация Бзкуса не используется, за исключением символа мета-или. Обычно прописные буквы используют для обовначения элементов У, а строчные — для элементов Т. Пример 2.2. Рассмотрим С (У, Т, Р, 3), где )Ч (8,Т), Т (я, Ь,с,а, Р=(Я" аТ«1, Т- 6Т!Ь!сТ!с).
Заметим, что двойное использование Т в атом примере не вызывает никаких затруднений. Грамматика будет порождать все строки а(Ь, сЩ однако мы все еще не показали, как этого можно до- «66 стичь. Будем испольаовать продукции следующим образом. Пусть а, р ю ст»; тогда р лрямо выводится из а, если а 7ор и () =7рб, где 7, 6, рж Р», оси ст+ и о- рсиР. Этот факт будем записывать в виде а». (); ои может яеформально рассматриваться как преобразования строки а в строку 6 эамещеяием подстроки о в а иа р. (Заметим, что ке обязательно аамекять конкретное вхоясдекие о в а или использовать конкретную продукцию с левой частью о.
Возможяы любые вариации.) Пусть теперь а и б — лова пад )т и существует коиечяая последовательность аа, аи ..., а„где ае а, а, р и ас с~а, (с 1, ..., т). Тогда будем говорить, что сс порождает р (записывается а =с-Р) и что вывод р из а реалиауется следусощим образом: а~ ас *: аз~ ... + » а,-с ~ (С. Аналогично а=>.~, если вывод использует непустую последовательпость прямых выводов. Если » аю )т» такое, что о =».а, то а называют еентенциальной формой. Более того, если аж Т» и Я=с-а, то а является предложением, порожденпым 6.
Таким образом, язык Ь(0), порожденный С, есть (а: аюТ» и Я» ~ а). Там, где ст подразумевается, моксио определить Ь(Х) ° =(а: а ю Т», ХсаУ и Х~а~. Поскольку, примеияя продукции к сеитеициалькым формам, можно действовать достаточно произвольно, то возке>сспо существование кескольких допустимых выводных коследовательпостей для дапкого предлоясекия в Ь(6), где с7 — конкретная грамматика. Среди этих последовательностей мы выбираем ту, которая иа каждом этапе оперирует с самой левой из возможных подстрок, в которой элементы заменяются иа элемеиты иэ Р. Такая последовательность я зывается (левой) канонической выводной ноеледовательностью для предложения.
Пример 2.3. Пусть ст ((В), ((, )), Р, В), где Р (В- (В)!ВВ1( )). Тогда предлолсекие ( ) (( ) ( )) может быть выведеко многими способами. 267 Приведем пять из них: 1) В «ВВ~. 2) В»ВВ» «( )В-« '.( )В-» «( ) (В)=: «( ) (В)~. .«( ) (ВВ) =~..е. ( ) (ВВ) -ю. '«( )(( )В)~- «( )(В( ))= ( )(( )( ))' '( )(( )( ))' 3) В ~ВВ « 4) В «ВВ». «В(В) «В(В).» .е.( )(В)~- «( )(В) « «( )(ВВ)~ «( ) (ВВ);.
«( )(( )В)= «( )(В( ))~. -( )(( н в -( )(( )( и; 5) В":ВВ»- :. В(В) ° . «В(ВВ).: -«В(( )В).е. .«( ) (( )В)= '( )(( )( )) ° Первый из этих выводов является каноническим. 2.2. Иерархия Хамского. Обсуждавшаяся до сих пор система — сильное описательное средство, однако при соадазшемся полозкении вещей она является слишком общей. Тем не менее, если наложить ограничения, мы получим болев вптересвый, хотя все еще достаточно мощный математический объект. Начальные ограничения, которые мы будем накладывать па структуру граммати» ки, определяют элементы Р. Определение (иерархия Хомского). Пусть б (М, Т, Р, Я) является ГФС, описаппой в п. 2.1. Такую грамматику называют грамматикой Хамского типе О. Если все элементы Р получаются из формы а- р, где сс "(~к"(ь а 6 '1~6"(м ть азы У'", аезУ, 6ш У+, то говорят, что 6 является контекстно-вависимой грамматикой, или врамматикой Хомского тина 1 (КЗГ).
(В этом определение строки (~ и (з могут рассматриваться как контекст, в котором х моя~ет заменяться посредством 6.) Другим (альтернативпым) ограничением для грамматики Хомского тяпа 1 является то, что в каяздой продукции а и (1 должны быть такими, что 1 ~!а! ~ 1ф. (Эквивалентность этих двух определений неочевидна и доказывается ниже.) Если подстановки могут быть выполнены 268 беэ рассмотрении контекстов, тогда мы можем ааменить «контексты» у> и '(» пустой строкой Л и получить более слабое ограничение: если х- 6«нР, то хшЛ> и 6 >и '»т+. Этому ограничению удовлетворяют грамматики Хамского типа 2.
Наконец, если Р состоит только иа продукций вида х- 6, где х >н Л> и 6 ш Т 0 ТЛ> (так, что правая часть является или единичным терминалом, или единичным терминалом, эа которым следует единичный нетерминал), то говорят, что « ' является грамматикой Хамского типа 3. I Часто бывает полезно испольэовать более общие формы внутри множества продукций, хотя формально это и не раарешается. Хотелось бы быть в состоянии включить пустую строку Л в качестве правой части любой продукции. Однако, как увидим позднее, это вызывает трудности.
Такие Л-продукции крайне необходимы с общей точки арения, если только Л>нЬ. В этом случае мы можем добавить Я- Л к Р при условии, что Я не встречается в правой части любой продукции. Однако в некоторых случаях необходимо разрешать также и более общие Л-продукции. Чтобы рааличать грамматики Хамского и те грамматики, в которых разрешаются Л-продукции, введем расширенные версии грамматик Хамского типа 2 и 3 — контекстно-свободные и регулярные грамматики соответственно. Языки, порожденные каким-либо иэ этих типов грамматик, имеют аналогичные названия. Так, структурная грамматика порождает структурный язык, структурная грамматика Хамского типа 1 — язык Хамского типа 1, контекстно-свободная грамматика — контекстно-свободный язык, а регулярная грамматика порождает регулярный язык (или регулярное множество) .
Больп>инство примеров этой главы будет касаться контекстно-свободных языков, а в гл. 9 мы скопцентрируем внимание на регулярных языках. Однако большинство практических языков являются некоторыми расширениями контекстно-аавнсимых языков. Чтобы указать на ограничения контекстно-свободной грамматики, рассмотрим следующий важный пример. Пример 2.4. (х"у"г": пш(>() является контекстноаависнмым языком. Предположим, что С =(У, Т, Р, Я), где Л>=(Я,Х, У,2), Т=(х, у, х), Р=(Р>, ..., Р>), Р =8 хХТ2, Р =й хУ2, Р - У хр, 1'-ру О, Р-рЯ рг, Рз = ЯУ УЯ, Рг гЯ гг.
Вначале заметим, что для любого яжг( мы можем по- лучить Я=эх" 'Я(УЯ)" '=~- =э х" (УЯ)" =ь. Ф ь х" У"Я' =ь. (Рг) (Рг) (Ре) =ь х"уУ" 'Я" =~. =~ х"у"Я" =ь = х"р"гЯ -'=" (Рз) (Рг) (Р,) В Фхе'2 (Р7) поэтому (х р"г": я~аг1)яиЕ(С). Теперь мы должны показать, что никакие другие строки не могут быть порождены 6. Хотя возможны некоторые изменения в порядке применения правил (Р~), (Рг) и (Рз), любое предлоясение долншо выводиться посредством сентенциальной формы такой, как х"УЯа, где а состоит из п — 1 символов У и Я. Для того чтобы получить строку над Т, мы должны в конце концов использовать правила (Р4), (Рг) и (Рг), однако (Рг) может преобразовать Я в г только в контексте гЯ, а (Рз) осуществляет такую же вамену в контексте рЯ, Аналогично для замены У на р при помощи правил (Р4) н (Рз) требуются коптексты уУ и хУ соответственно. 11а втой стадии подстрока х" состоит только иэ терминалов, поэтому на следующем шаге строка должна иметь вид х"рЯа н получаться при помощи (Рз).
Однако мы знаем, что правильное предлоя1ение должно порождаться преобразованием из Яа в У" 'Я" посредством (Ре), Действительно, только таким образом моя"но успешно получить строку. Предположим, что мы имеем промея'уточную подстроку вида рУ"Я'Ур, где (1 состоит из оставшихся элементов У и Я. Иа рассуждений, аналогичных приведенным выше, следует, что для получения подстроки у"+'Я"Ур нуж- 270 но гп раэ применить (Р<). Однако, если сейчас мы испольауем (Рь) для получения у"+<г2'-<У!>, то никаким правилом нельзя заменить элемент У на у (или любой другой терминал). Единственный способ выйти из этого поло>кения — ато р раз применить (Рг)', чтобы переместить У влево и, следовательно, получить к"у"з".
з' Это пример коптекстно-завнсимого языка, который, как будет показано, не является контекстно-свободным. Аналогично существуют контекстно-свободные языки, которые не являются регулярными (см. гл. 9). Вернемся теперь к доказательству эквивалентности альтернативных определений контекстно-завнсимых грамматик. Определение. Грамматики 6< и Сг гквивалентньь, если л (6<) = ь (62) ° з Предло>кение. с. является контекстно-зависимым языком тогда и только тогда, когда он может быть порожден грамматикой, у которой продукции о- !ь удовлетворяют условию 1» !о! -* 1р1.
Доказательство. Если Ь вЂ” контекстно-зависимый язык, то существует грамматика С с продукциями вида аА11 ацр, где А ы <У, 7 <в )т+ и щ р <н т'в такие, что Ь=Ь(С). Однако 1иА!<1 1а! + !А!+ 1!>1 = !<э!+ 1+ 11)1> 1, 1 7~1=11+17!+!Ф 1 !+1+!И=1 Ч~1 Следовательно, 1» 1иА!)1-*1с<7р), что и требовалось доказать. Пусть 6 =(!У, Т, Р, Я)-грамматика, у которой продукции о- р удовлетворяют соотношению 1<!о! щ)р1. Мы должны создать грамматику С', эквивалентную 6, с продукциями вида иА!> - сь7р.
Продукции иэ 6 имеют вид 1) А - 7<...7 или же 2) <х<... а„- р<... !)<, где и» д и А вз <т', <ь„р<, 7< ы Р. Во всех продукциях заменим каждый встречающийся элемент а,<нТ новым нетерминальным алементом А< и включим продукции А< -~ а< в С'. Продукции типа 1) теперь имеют правильную форму и включены в С'.
Однако продукции типа 2) необходимо модифицировать. Сейчас они имеют вид >у<" >ую у< °" г«п-- т< 27> где И'» и У» являются нетерминальными символами новой грамматики. Для каждой такой продукции введем новые влементы У», ..., У„не являющиеся терминалами, и и+ д новых продукций: л продукций И»1 ° . ° ьу»» ' У»И"« ° ° ° 1У»»» 'Р„И'« ... 1~'~-~1»У«И'э ° ° ° И' » у»...У И» И» у»...У «у И г» ° ° ° 1»»-«У»» — »И»» ~ 1» ° ° ° Уп-Я»-» г»»Рп+1 ° ° ° г « и е продукций У»У«...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
