Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 47
Текст из файла (страница 47)
Е =» Е ' Е ~ Е ' Е» Е =» 1" Е + Е =»1 * 1» Е =» 1" 1»1=»а*1»1=»а* Ь+1=» а" Ь»а 5.2. ДЕРЕВЬЯ РАВВОРА 205 Рассмотрим третью выводимую цепочку, Е " Е + Е, и среднее Е в ней.' Начав с Е ' Е+ Е, можно пройти по шагам указанного выше порождения, выбрасывая позиции, порожденные из Е* слева от центрального Е и из +Е справа от него. Шагами порождения тогда становятся Е, Е, Е Е У, Ь, Ь. Таким образом, следующий шаг не меняет центральное Е, следующий за ним меняет его на /, два шага за ними сохра~иют Е следующий меняет его на Ь, и заключительный шаг не изменяет того, что порождено из центрального Е.
Если мы рассмотрим только шаги, которые изменяют то, что порождается из центрального Е, то последовательность Е, Е, /, Е Е Ь, Ь превращается в порождение Е =» (~ Ь. Оно корректно описывает, как центральное Е эволюционирует в полном порождении. ь) Теорема 5Л8. Пусть ь = (~; Т, Р, Е) — КС-грамматика, и пусть существует порожде- ние А =» н, где и б Т. Тогда процедура рекурсивного вывода, примененная к О, опредеа лает, что и принадлежит языку переменной А. Доказательство. Доказательство проведем индукцией по длине порождения А =» н.
Базис. Если порождение состоит из одного шага, то А — + н должно быть продукцией. Так как н состоит только из терминалов, то факт приналлежности тт языку А устанавливается на основе базисной части процедуры рекурсивного вывода. Индукция. Пусть порождение состоит из и+! шагов и пусть для любого порождения из н и менее шагов утверждение выполняется. Запишем порождение в виде А =» ХХь..Х» ~ н. Тогда, как обсуждалось перед теоремой, можно представить т» как н' = ж,и'ь .. т»ь где: а) еслиХ вЂ” терминал, то н, =Х; б) если Х,— переменная, то Х, =» н,.
Так как первый шаг порождения А =» и действительно не является частью порождения Х ~ н„нам известно, что это порождение состоит из л или менее шагов. Таким образом, к нему при- менимо предположение индукции, и можно сделать вывод, что н принадлежит языку Хь Теперь у нас есть продукция А -» ХХь,.Хь и нам известно, что н, или равно Х, илн принадлежит языку Х,. На следующем шаге процедуры рекурсивного вывода мы обнаружим, что нчгжь ..не принадлежит языку А. Так как н пть .. не = н, выводимость того, что н б Е(А), доказана. СЗ Наше обсуждение нахождения подпорожленнй нз больших порождений предполагало, что мы имели дело с переменными второй выводимой цепочки некоторого порождения.
Однако идея применима к переменной на любом шаге порождения. ГЛАВА б. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ 206 5.2.7. Упражнения к разделу 5.2 52.1. Приведите деревья разбора для грамматики и каждой из цепочек в упражнении 5.1.2. 5.2.2. Пусть С вЂ” КС-грамматика без продукций с е в правой части. Доказать, что если и и»'.(О), длина и равна и, и ж порождается за и» шагов, то для н существует дерево разбора с и + т узлами. 5.2.3. Пусть действуют все предположения упражнения 5.2.2, но б может иметь несколько продукций с е справа. Доказать, что дерево разбора для ж может иметь до н + 2т — 1 узлов, но не более.
52,4. В разделе 5.2.6 мы заметили, что если Х»Х,...Х» =ь а, то все позиции в а, происходящие от расширения Х, находятся слева от всех позиций, происходящих от расширения Х, если» < 1 Доказать этот факт. Указание. Провести индукцию по числу шагов в порождении. з.3. Приложения контекстно-свободных грамматик Контекстно-свободные грамматики были придуманы Н. Хомским (Н.
С(»ошзку) как способ описания естественных языков, но их оказалось недостаточно. Однако по мере того, как множились примеры использования рекурсивно определяемых понятий, возрастала и потребность в КС-грамматиках как в способе описания примеров таких понятий. Мы рассмотрим вкратце два применения КС-грамматик, одно старое н одно новое.
1. Грамматики используются для описания языков программирования. Более важно здесь то, что существует механический способ превращения описания языка, вроде КС-грамматики, в синтаксический анализатор — часть компилятора, которая изучает структуру исходной программы и представляет ее с помощью дерева разбора. Это приложение является одним из самых ранних использований КС-грамматик; в действительности, это один из первых путей, по которым теоретические идеи компьютерной науки пришли в практику. Развитие ХМ1.
(Ехгепзй»(е Матадор Ьапяцаяе) призвано облегчить электронную коммерцию тем, что ее участникам доступны соглашения о форматах ордеров, описаний товаров, и многих других видов документов. Существенной частью ХМЬ является определение и»ила документа (ОТΠ— Оосшпепг Туре Оейбпйоп), представляющее собой КС-грамматику, которая описывает допустимые дескрипторы (гааз) и способы их вложения друг в друга.
Дескрипторы являются привычными ключевыми словами в угловых скобках, которые читателю, возможно, известны по языку НТМЬ, например, <ЕМ> и <!ЕМ> для указания текста, который нужно выделить. Однако дескрипторы ХМЬ связаны не с форматированием текста, а с тем, что он означает. Например, можно было бы заключить в скобки <РНОНЕ> н </РНОНЕ> последовательности символов, интерпретируемые как телефонные номера. 207 5.3. ПРИЛОЖЕНИЯ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК 5.3.1. Синтаксические анализаторы Многие объекты языка программирования имеют структуру, которая может быть описана с помощью регулярных выражений. Например, мы обсуждали в примере 3.9, как идентификаторы можно представлять регулярными выражениями.
Вместе с тем, существует также несколько весьма важных объектов в языках программирования, которые нельзя представить с помощью только лишь регулярных выражений. Приведем два примера, Пример 5.19. Обычные языки программирования используют круглые гь'или квадратные скобки во вложенном и сбалансированном виде, т.е. так, что можно некоторой левой скобке поставить в соответствие правую, которая записана непосредственно за ней, удалить их и повторять эти действия вплоть до удаления всех скобок. Например, (0), 00, (00) и е являются сбалансированными скобками, а )( и (() — нет.
Все цепочки сбалансированных скобок (и только они) порождаются грамматикой бм, = ((В), ((, )), Р, В), где Р состоит из продукций  — + ВВ)(В) ( а Первая продукция,  — > ВВ, гласит, что конкатенация двух цепочек сбалансированных скобок сбалансирована. Это утверждение очевидно, поскольку можно сопоставить скобки в двух цепочках независимо друг от друга. Вторая продукция, В -> (В), говорит, что если поместить пару скобок вокруг сбалансированной цепочки, то новая цепочка также будет сбалансированной. Это утверждение тоже очевидно, так как если скобки внутренней цепочки соответствуют друг другу, их можно удалить, и новые скобки становятся соседними.
Третья продукция, В -+ г, является базисной, гласящей, что пустая цепочка сбалансирована. Приведенные выше неформальные доводы должны убедить нас, что О, ~ порождает только цепочки сбалансированных скобок. Нам еще нужно доказать обратное: что каждая цепочка сбалансированных скобок порождается этой грамматикой. Однако доказательство индукцией по длине сбалансированной цепочки весьма просто и оставляется в качестве упражнения.
Мы отмечали, что множество цепочек сбалансированных скобок не является регулярным языком, и теперь докажем это. Если бы ЦОь, ) был регулярным, то для него по лемме о накачке для регулярных языков существовала бы константа л. Рассмотрим сбалансированную цепочку ж = (")", т.е. л левых скобок, за которыми следуют л правых. Если разбить м =хуг в соответствии с леммой, то у состоит только из левых скобок, и цепочка хз содержит больше правых скобок, чем левых. Эта цепочка несбалансированна, т.е. получено противоречие с предположением, что язык сбалансированных скобок регулярен.
С) Языки программирования содержат, конечно же, не только скобки, но скобки составляют существенную часть арифметических и условных выражений. Грамматика, изображенная на рис. 5,2, более типична для структуры арифметических выражений, хотя там использованы всего два оператора, сложения и умножения, и включена детальная структура идентификаторов, которая, вероятней всего, обрабатывалась бы лексическим анали- 208 ГЛАВА б. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ жтором компилятора, как мы упоминали в разделе 3.3.2. Однако язык, представленный па рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
