Регулярные выражения и языки (стр. 25 )

Wixv2...WiXi4X^2...Xk

*

Результатом является порождение A => wlw2...wX^iX^2...Xk.

Im

Когда i = к, результат представляет собой левое порождение w из А. □

Пример 5.15. Рассмотрим левое порождение для дерева, изображенного на рис. 5.6. Продемонстрируем лишь заключительный шаг, на котором строится порождение по целому дереву из порождений, соответствующих поддеревьям корня. Итак, предполо­жим, что с помощью рекурсивного применения техники из теоремы 5.14 мы убеди­лись, что поддерево, корнем которого является левый сын корня дерева, имеет левое порождение Ј=>/=> а, а поддерево с корнем в третьем сыне корня имеет следующее

1т 1т

левое порождение.

Ј=>(Ј)=>(Ј + Ј)=>(/ + Ј)=> (а + Е) =>

Im        im        Im        Im        Im

(a +1) => (a + /0) => (a + /00) => (a + 600)

lm        lm        Im

Чтобы построить левое порождение для целого дерева, начинаем с шага в корне: А => Е * Е. Затем заменяем первую переменную Ј и в соответствии с ее порождением

1т

приписываем на каждом шаге *Ј, чтобы учесть контекст, в котором это порождение ис­пользуется. Левое порождение на текущий момент представляет собой следующее.

Ј=» Ј*Ј=> / *Ј=> а * Е

lm        Im        1т

Символ * в продукции, использованной в корне, не требует порождения, поэтому ука­занное левое порождение также учитывает первые два сына корня. Дополним левое по­рождение, используя порождение Ј => (а + 600), левый контекст которого образован це­ли

почкой а*, а правый пуст. Это порождение в действительности появлялось в примере 5.6 и имело следующий вид.

Ј* Ј /* Ј а * Ј

/m        lm        lm        lm

a * (Ј) a * (Ј+Ј)=> a *(/+Ј) a * (a + Ј)

/я?        /m        lm        lm

a * (a +1) a * (a +10) => a * (a + /00) => a * (a + 600)

lm        lm        lm

Аналогичная теорема позволяет нам преобразовать дерево в правое порождение. По­строение правого порождения по дереву почти такое же, как и построение левого. Здесь, однако, после первого шага А => Х, Х2...Хк мы заменяем сначала Хк, используя правое

гт

порождение, затем Хки так далее до X,. Таким образом, примем без доказательства следующее утверждение.

Теорема 5.16. Пусть G = (V, Т, P, S) — КС-грамматика. Предположим, что существу­ет дерево разбора с корнем, отмеченным А, и кроной w, где we f. Тогда в грамматике G

»

существует правое порождение А => w.

rm

5.2.6. От порождений к рекурсивным выводам

Теперь завершим цикл, представленный на рис. 5.7, доказав, что если существует по - *

рождение А => w для некоторой КС-грамматики, то факт принадлежности w языку А до­казывается путем процедуры рекурсивного вывода. Перед тем как приводить теорему и ее доказательство, сделаем важные замечания о порождениях.

Предположим, у нас есть порождение А =>XiX2...Xk => w. Тогда w можно разбить на

подцепочки w = w;w2...wk, где X, => w,. Заметим, что если X, является терминалом, то w, = Х„ и порождение имеет 0 шагов. Доказать это замечание несложно. Вы можете дока­зать индукцией по числу шагов порождения, что еслиXjX2...Xk => а, то все позиции в а, происходящие от расширения X,, находятся слева от всех позиций, происходящих от расширения Xj, если i < j.

*

Если Xj является переменной, то можно получить порождение X, => w„ начав с поро - *

жденияЛ => w и отбрасывая следующее:

а)        все шаги, не относящиеся к порождению w, из X,;

б)        все позиции выводимой цепочки, которые находятся либо справа, либо слева от позиций, порождаемых из X,.

Этот процесс поясняется примером.

Пример 5.17. Используем грамматику выражений и рассмотрим следующее поро­ждение.

Е=$Е*Е=>Е*Е + Е=э1*Е+Е=>1*1+Е=* l*l+l=$a*I + I=>a*b + I=$a*b + a

Рассмотрим третью выводимую цепочку, Ј*Ј + Ј, и среднее Ј в ней.2

Начав с Ј*Ј + Ј, можно пройти по шагам указанного выше порождения, выбрасы­вая позиции, порожденные из Ј* слева от центрального Ј и из +Ј справа от него. Шага­ми порождения тогда становятся Ј, Ј, /, /, /, Ь, Ь. Таким образом, следующий шаг не ме­няет центральное Ј, следующий за ним меняет его на /, два шага за ними сохраняют /, следующий меняет его на Ь, и заключительный шаг не изменяет того, что порождено из центрального Ј.

Если мы рассмотрим только шаги, которые изменяют то, что порождается из цен­трального Ј, то последовательность Ј, Ј, /, /, /, b, Ь превращается в порождение Ј => / => Ь. Оно корректно описывает, как центральное Ј эволюционирует в полном по­рождении. □

Теорема 5.18. Пусть G = (V, Т, Р, S) — КС-грамматика, и пусть существует порожде - ниеА =* w, где we Т. Тогда процедура рекурсивного вывода, примененная к G, опреде-

g

ляет, что w принадлежит языку переменной А.

*

Доказательство. Доказательство проведем индукцией по длине порождения А => w.

Базис. Если порождение состоит из одного шага, то А —» w должно быть продукцией. Так как w состоит только из терминалов, то факт принадлежности w языку А устанавли­вается на основе базисной части процедуры рекурсивного вывода.

Индукция. Пусть порождение состоит из п + 1 шагов и пусть для любого порожде­ния из и и менее шагов утверждение выполняется. Запишем порождение в виде А => *

Х, Х2...Хк => w. Тогда, как обсуждалось перед теоремой, можно представить w как w = w, w2...wk, где:

а)        если X, — терминал, то w, = Хп

* *

б)        если X, — переменная, то X, => w,. Так как первый шаг порождения А => w

действительно не является частью порождения X/ => w„ нам известно, что это порождение состоит из п или менее шагов. Таким образом, к нему при­менимо предположение индукции, и можно сделать вывод, что w принадле­жит языку Х:.

Теперь у нас есть продукция А —> Х/Х2. ■ .Хк, и нам известно, что w, или равно Х„ или принадлежит языку Хг На следующем шаге процедуры рекурсивного вывода мы обна­ружим, что w/w2...wk принадлежит языку/!. Так как w/w2...wk = w, выводимость того, что w е ЦА), доказана. □

5.2.7. Упражнения к разделу 5.2

Приведите деревья разбора для грамматики и каждой из цепочек в упражнении 5.1.2. Пусть G — КС-грамматика без продукций сев правой части. Доказать, что если w е L(G), длина w равна п, и w порождается за т шагов, то для w существует де­рево разбора с п + т узлами. Пусть действуют все предположения упражнения 5.2.2, но G может иметь не­сколько продукций с е справа. Доказать, что дерево разбора для w может иметь до п + 2т - 1 узлов, но не более. В разделе 5.2.6 мы заметили, что если Х, Х2. . - Хк => а, то все позиции в а, проис­ходящие от расширения Xt, находятся слева от всех позиций, происходящих от расширения Xj, если / < j. Доказать этот факт. Указание. Провести индукцию по числу шагов в порождении.

5.3. Приложения контекстно-свободных грамматик

Контекстно-свободные грамматики были придуманы Н. Хомским (N. Chomsky) как способ описания естественных языков, но их оказалось недостаточно. Однако по мере того, как множились примеры использования рекурсивно определяемых понятий, воз­растала и потребность в КС-грамматиках как в способе описания примеров таких поня­тий. Мы рассмотрим вкратце два применения КС-грамматик, одно старое и одно новое.

Грамматики используются для описания языков программирования. Более важно здесь то, что существует механический способ превращения описания языка, вроде КС-грамматики, в синтаксический анализатор — часть компилятора, которая изуча­ет структуру исходной программы и представляет ее с помощью дерева разбора. Это приложение является одним из самых ранних использований КС-грамматик; в дей­ствительности, это один из первых путей, по которым теоретические идеи компью­терной науки пришли в практику. Развитие XML (Extensible Markup Language) призвано облегчить электронную ком­мерцию тем, что ее участникам доступны соглашения о форматах ордеров, описаний товаров, и многих других видов документов. Существенной частью XML является определение типа документа (DTD — Document Type Definition), представляющее собой КС-грамматику, которая описывает допустимые дескрипторы (tags) и способы их вложения друг в друга. Дескрипторы являются привычными ключевыми словами в угловых скобках, которые читателю, возможно, известны по языку HTML, напри­мер, <ЕМ> и </ЕМ> для указания текста, который нужно выделить. Однако деск­рипторы XML связаны не с форматированием текста, а с тем, что он означает. На­пример, можно было бы заключить в скобки <PHONE> и </PHONE> последователь­ности символов, интерпретируемые как телефонные номера.

5.3.1. Синтаксические анализаторы

Многие объекты языка программирования имеют структуру, которая может быть опи­сана с помощью регулярных выражений. Например, мы обсуждали в примере 3.9, как идентификаторы можно представлять регулярными выражениями. Вместе с тем, существу­ет также несколько весьма важных объектов в языках программирования, которые нельзя представить с помощью только лишь регулярных выражений. Приведем два примера.

Пример 5.19. Обычные языки программирования используют круглые и/или квад­ратные скобки во вложенном и сбалансированном виде, т. е. так, что можно некоторой левой скобке поставить в соответствие правую, которая записана непосредственно за ней, удалить их и повторять эти действия вплоть до удаления всех скобок. Например, (())> (XX (00) и е являются сбалансированными скобками, а )( и (() — нет.

Все цепочки сбалансированных скобок (и только они) порождаются грамматикой Gbai = ({В}, {(> Ж Л Ј)> где Р состоит из продукций В -> ВВ\ (В) | е.