dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 47
Текст из файла (страница 47)
204ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈE ⇒ E*E ⇒ I*E ⇒ a*E ⇒lmlmlmlma * (E) ⇒ a * (E + E) ⇒ a * (I + E) ⇒ a * (a + E) ⇒lmlmlmlma * (a + I) ⇒ a * (a + I0) ⇒ a * (a + I00) ⇒ a * (a + b00)lmlmlmАналогичная теорема позволяет нам преобразовать дерево в правое порождение. Построение правого порождения по дереву почти такое же, как и построение левого.
Здесь,однако, после первого шага A ⇒ X1X2…Xk мы заменяем сначала Xk, используя правоеrmпорождение, затем Xk–1 и так далее до X1. Таким образом, примем без доказательстваследующее утверждение.Теорема 5.16. Пусть G = (V, T, P, S) — КС-грамматика. Предположим, что существует дерево разбора с корнем, отмеченным A, и кроной w, где w ∈ T*.
Тогда в грамматике G*существует правое порождение A ⇒ w.rm5.2.6. Îò ïîðîæäåíèé ê ðåêóðñèâíûì âûâîäàìТеперь завершим цикл, представленный на рис. 5.7, доказав, что если существует по*рождение A ⇒ w для некоторой КС-грамматики, то факт принадлежности w языку A доказывается путем процедуры рекурсивного вывода.
Перед тем как приводить теорему иее доказательство, сделаем важные замечания о порождениях.*Предположим, у нас есть порождение A ⇒ X1X2…Xk ⇒ w. Тогда w можно разбить на*подцепочки w = w1w2…wk, где Xi ⇒ wi. Заметим, что если Xi является терминалом, тоwi = Xi, и порождение имеет 0 шагов.
Доказать это замечание несложно. Вы можете дока*зать индукцией по числу шагов порождения, что если X1X2…Xk ⇒ α, то все позиции в α,происходящие от расширения Xi, находятся слева от всех позиций, происходящих отрасширения Xj, если i < j.*Если Xi является переменной, то можно получить порождение Xi ⇒ wi, начав с поро*ждения A ⇒ w и отбрасывая следующее:а) все шаги, не относящиеся к порождению wi из Xi;б) все позиции выводимой цепочки, которые находятся либо справа, либо слеваот позиций, порождаемых из Xi.Этот процесс поясняется примером.Пример 5.17. Используем грамматику выражений и рассмотрим следующее порождение.E⇒E*E⇒E*E+E⇒I*E+E⇒I*I+E⇒I*I+I⇒a*I+I⇒a*b+I⇒a*b+a5.2.
ÄÅÐÅÂÜß ÐÀÇÁÎÐÀСтр. 205205Рассмотрим третью выводимую цепочку, E * E + E, и среднее E в ней.2Начав с E * E + E, можно пройти по шагам указанного выше порождения, выбрасывая позиции, порожденные из E* слева от центрального E и из +E справа от него. Шагами порождения тогда становятся E, E, I, I, I, b, b. Таким образом, следующий шаг не меняет центральное E, следующий за ним меняет его на I, два шага за ними сохраняют I,следующий меняет его на b, и заключительный шаг не изменяет того, что порождено изцентрального E.Если мы рассмотрим только шаги, которые изменяют то, что порождается из центрального E, то последовательность E, E, I, I, I, b, b превращается в порождениеE ⇒ I ⇒ b. Оно корректно описывает, как центральное E эволюционирует в полном порождении.
Теорема 5.18. Пусть G = (V, T, P, S) — КС-грамматика, и пусть существует порожде*ние A ⇒ w, где w ∈ T. Тогда процедура рекурсивного вывода, примененная к G, опредеGляет, что w принадлежит языку переменной A.*Доказательство. Доказательство проведем индукцией по длине порождения A ⇒ w.Базис. Если порождение состоит из одного шага, то A → w должно быть продукцией.Так как w состоит только из терминалов, то факт принадлежности w языку A устанавливается на основе базисной части процедуры рекурсивного вывода.Индукция. Пусть порождение состоит из n + 1 шагов и пусть для любого порождения из n и менее шагов утверждение выполняется.
Запишем порождение в виде A ⇒*X1X2…Xk ⇒ w. Тогда, как обсуждалось перед теоремой, можно представить w какw = w1w2…wk, где:а) если Xi — терминал, то wi = Xi;**б) если Xi — переменная, то Xi ⇒ wi. Так как первый шаг порождения A ⇒ w*действительно не является частью порождения Xi ⇒ wi, нам известно, чтоэто порождение состоит из n или менее шагов. Таким образом, к нему применимо предположение индукции, и можно сделать вывод, что w принадлежит языку Xi.Теперь у нас есть продукция A → X1X2…Xk, и нам известно, что wi или равно Xi, илипринадлежит языку Xi. На следующем шаге процедуры рекурсивного вывода мы обнаружим, что w1w2…wk принадлежит языку A. Так как w1w2…wk = w, выводимость того, чтоw ∈ L(A), доказана.
2Наше обсуждение нахождения подпорождений из больших порождений предполагало, чтомы имели дело с переменными второй выводимой цепочки некоторого порождения. Однако идеяприменима к переменной на любом шаге порождения.206Стр. 206ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈ5.2.7. Óïðàæíåíèÿ ê ðàçäåëó 5.25.2.1.Приведите деревья разбора для грамматики и каждой из цепочек в упражнении 5.1.2.5.2.2.Пусть G — КС-грамматика без продукций с ε в правой части. Доказать, что еслиw ∈ L(G), длина w равна n, и w порождается за m шагов, то для w существует дерево разбора с n + m узлами.5.2.3.Пусть действуют все предположения упражнения 5.2.2, но G может иметь несколько продукций с ε справа.
Доказать, что дерево разбора для w может иметьдо n + 2m – 1 узлов, но не более.5.2.4.В разделе 5.2.6 мы заметили, что если X1X2…Xk ⇒ α, то все позиции в α, происходящие от расширения Xi, находятся слева от всех позиций, происходящих отрасширения Xj, если i < j. Доказать этот факт. Указание. Провести индукцию почислу шагов в порождении.*5.3. Ïðèëîæåíèÿ êîíòåêñòíî-ñâîáîäíûõ ãðàììàòèêКонтекстно-свободные грамматики были придуманы Н. Хомским (N.
Chomsky) какспособ описания естественных языков, но их оказалось недостаточно. Однако по меретого, как множились примеры использования рекурсивно определяемых понятий, возрастала и потребность в КС-грамматиках как в способе описания примеров таких понятий. Мы рассмотрим вкратце два применения КС-грамматик, одно старое и одно новое.1.Грамматики используются для описания языков программирования. Более важноздесь то, что существует механический способ превращения описания языка, вродеКС-грамматики, в синтаксический анализатор — часть компилятора, которая изучает структуру исходной программы и представляет ее с помощью дерева разбора. Этоприложение является одним из самых ранних использований КС-грамматик; в действительности, это один из первых путей, по которым теоретические идеи компьютерной науки пришли в практику.2.Развитие XML (Extensible Markup Language) призвано облегчить электронную коммерцию тем, что ее участникам доступны соглашения о форматах ордеров, описанийтоваров, и многих других видов документов.
Существенной частью XML являетсяопределение типа документа (DTD — Document Type Defifnition), представляющеесобой КС-грамматику, которая описывает допустимые дескрипторы (tags) и способыих вложения друг в друга. Дескрипторы являются привычными ключевыми словамив угловых скобках, которые читателю, возможно, известны по языку HTML, например, <EM> и </EM> для указания текста, который нужно выделить. Однако дескрипторы XML связаны не с форматированием текста, а с тем, что он означает. Например, можно было бы заключить в скобки <PHONE> и </PHONE> последовательности символов, интерпретируемые как телефонные номера.5.3.
ÏÐÈËÎÆÅÍÈß ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр. 2072075.3.1. Ñèíòàêñè÷åñêèå àíàëèçàòîðûМногие объекты языка программирования имеют структуру, которая может быть описана с помощью регулярных выражений. Например, мы обсуждали в примере 3.9, какидентификаторы можно представлять регулярными выражениями. Вместе с тем, существует также несколько весьма важных объектов в языках программирования, которые нельзяпредставить с помощью только лишь регулярных выражений. Приведем два примера.Пример 5.19. Обычные языки программирования используют круглые и/или квадратные скобки во вложенном и сбалансированном виде, т.е.
так, что можно некоторойлевой скобке поставить в соответствие правую, которая записана непосредственно заней, удалить их и повторять эти действия вплоть до удаления всех скобок. Например,(()), ()(), (()()) и ε являются сбалансированными скобками, а )( и (() — нет.Все цепочки сбалансированных скобок (и только они) порождаются грамматикойGbal = ({B}, {(, )}, P, B), где P состоит из продукцийB → BB | (B) | ε.Первая продукция, B → BB, гласит, что конкатенация двух цепочек сбалансированных скобок сбалансирована.
Это утверждение очевидно, поскольку можно сопоставить скобки вдвух цепочках независимо друг от друга. Вторая продукция, B → (B), говорит, что если поместить пару скобок вокруг сбалансированной цепочки, то новая цепочка также будет сбалансированной. Это утверждение тоже очевидно, так как если скобки внутренней цепочкисоответствуют друг другу, их можно удалить, и новые скобки становятся соседними.
Третья продукция, B → ε, является базисной, гласящей, что пустая цепочка сбалансирована.Приведенные выше неформальные доводы должны убедить нас, что Gbal порождаеттолько цепочки сбалансированных скобок. Нам еще нужно доказать обратное: что каждая цепочка сбалансированных скобок порождается этой грамматикой. Однако доказательство индукцией по длине сбалансированной цепочки весьма просто и оставляется вкачестве упражнения.Мы отмечали, что множество цепочек сбалансированных скобок не является регулярным языком, и теперь докажем это.
Если бы L(Gbal) был регулярным, то для него по леммео накачке для регулярных языков существовала бы константа n. Рассмотрим сбалансированную цепочку w = (n)n, т.е. n левых скобок, за которыми следуют n правых. Если разбитьw = xyz в соответствии с леммой, то y состоит только из левых скобок, и цепочка xz содержит больше правых скобок, чем левых. Эта цепочка несбалансированна, т.е. получено противоречие с предположением, что язык сбалансированных скобок регулярен. Языки программирования содержат, конечно же, не только скобки, но скобки составляют существенную часть арифметических и условных выражений. Грамматика, изображенная на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
