dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 43
Текст из файла (страница 43)
Другие переменные представляют дополнительные классы цепочек, которые помогают определить язык, заданный стартовым символом.4.Имеется конечное множество продукций, или правил вывода, которые представляютрекурсивное определение языка. Каждая продукция состоит из следующих частей:а) переменная, (частично) определяемая продукцией. Эта переменная часто называется головой продукции;б) символ продукции →;в) конечная цепочка, состоящая из терминалов и переменных, возможно, пустая.Она называется телом продукции и представляет способ образования цепочекязыка, обозначаемого переменной в голове.
По этому способу мы оставляем терминалы неизменными и вместо каждой переменной в теле подставляем любуюцепочку, про которую известно, что она принадлежит языку этой переменной.Пример множества продукций приведен на рис. 5.1.Описанные четыре компонента образуют контекстно-свободную грамматику, илиКС-грамматику, или просто грамматику, или КСГ.
Мы будем представлять КСграмматику G ее четырьмя компонентами в виде G = (V, T, P, S), где V — множество переменных, T — терминалов, P — множество продукций, S — стартовый символ.Пример 5.2. Грамматика Gpal для палиндромов имеет видGpal = ({P}, {0, 1}, A, P),где A обозначает множество из пяти продукций (см. рис. 5.1).
Пример 5.3. Рассмотрим более сложную КС-грамматику, которая представляет выражения типичного языка программирования (в несколько упрощенном виде). Вопервых, ограничимся операторами + и *, представляющими сложение и умножение. Вовторых, допустим, что аргументы могут быть идентификаторами, однако не произвольными, т.е. буквами, за которыми следует любая последовательность букв и цифр, в томчисле пустая. Допустим только буквы a и b и цифры 0 и 1.
Каждый идентификатор должен начинаться с буквы a или b, за которой следует цепочка из {a, b, 0, 1}*.5.1. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈСтр. 187187В нашей грамматике нужны две переменные. Одна обозначается E и представляетвыражения определяемого языка. Она является стартовым символом. Другая переменная, I, представляет идентификаторы. Ее язык в действительности регулярен и задаетсярегулярным выражением(a + b)(a + b + 0 + 1)*.В грамматиках, однако, регулярные выражения непосредственно не используются.Вместо этого будем обращаться к множеству продукций, задающих в точности то же самое, что и соответствующее регулярное выражение.1.E→I2.E→E+E3.E→E*E4.E → (E)5.I→a6.I→b7.I → Ia8.I → Ib9.I → I010.
I → I1Рис. 5.2. Контекстно-свободная грамматика для простых выраженийГрамматика для выражений определяется формально как G = ({E, I}, T, P, E), где T ={+, *, (, ), a, b, 0, 1}, а P представляет собой множество продукций, показанное нарис. 5.2. Продукции интерпретируются следующим образом.Правило 1 является базисным для выражений.
Оно гласит, что выражение можетбыть одиночным идентификатором. Правила 2–4 описывают индуктивное образованиевыражений. Правила 2 и 3 говорят, что выражение может состоять из двух выражений,соединенных знаком сложения или умножения. Правило 4 — что если заключить произвольное выражение в скобки, то в результате получается также выражение.Ñîêðàùåííîå îáîçíà÷åíèå ïðîäóêöèéПродукцию удобно рассматривать как “принадлежащую” переменной в ее голове. Мы будем часто пользоваться словами “продукции для A” или “A-продукции” для обозначенияпродукций, головой которых является переменная A.
Продукции грамматики можно записать, указав каждую переменную один раз и затем перечислив все тела продукций для этойпеременной, разделяя их вертикальной чертой. Таким образом, продукции A → α1,A → α2, …, A → αn можно заменить записью A → α1 | α2 | … | αn. Например, грамматикудля палиндромов (см. рис. 5.1) можно записать в виде P → ε | 0 | 1 | 0P0 | 1P1.188Стр.
188ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈПравила 5–10 описывают идентификаторы I. Правила 5 и 6 образуют базис; они гласят, что a и b — идентификаторы. Остальные четыре правила описывают индуктивныйпереход: имея произвольный идентификатор, можно приписать к нему справа a, b, 0 или1 и получить еще один идентификатор. 5.1.3. Ïîðîæäåíèÿ ñ èñïîëüçîâàíèåì ãðàììàòèêèДля того чтобы убедиться, что данные цепочки принадлежат языку некоторой переменной, мы применяем продукции КС-грамматики. Есть два способа действий.
Простейший подход состоит в применении правил “от тела к голове”. Мы берем цепочки,про которые известно, что они принадлежат языкам каждой из переменных в теле правила, записываем их в соответствующем порядке вместе с терминалами этого тела и убеждаемся, что полученная цепочка принадлежит языку переменной в голове. Такая процедура называется рекурсивным выводом (recursive inference).Есть еще один способ определения языка грамматики, по которому продукции применяются “от головы к телу”. Мы разворачиваем стартовый символ, используя одну изего продукций, т.е. продукцию, головой которой является этот символ.
Затем разворачиваем полученную цепочку, заменяя одну из переменных телом одной из ее продукций, итак далее, пока не получим цепочку, состоящую из одних терминалов. Языкграмматики — это все цепочки из терминалов, получаемые таким способом. Такое использование грамматики называется выведением, или порождением (derivation).Начнем с примера применения первого подхода — рекурсивного вывода, хотя частоестественнее рассматривать грамматики в качестве применяемых для порождений, и далее мы разовьем систему записи таких порождений.Пример 5.4. Рассмотрим некоторые из выводов, которые можно сделать, используяграмматику для выражений (см.
рис. 5.2). Результаты этих выводов показаны на рис. 5.3.Например, строчка (i) говорит, что в соответствии с продукцией 5 цепочка a принадлежит языку переменной I. Строчки (ii)–(iv) свидетельствуют, что цепочка b00 являетсяидентификатором, полученным с помощью одного применения продукции 6 и затемдвух применений продукции 9.В строчках (v) и (vi) использована продукция 1 для того, чтобы прийти к заключению,что цепочки a и b00, которые выведены как идентификаторы в строчках (i) и (iv), принадлежат также и языку переменной E. В строчке (vii) применяется продукция 2 для вывода, что сумма этих идентификаторов является выражением, в строчке (viii) — продукция 4, и эта же сумма в скобках также представляет собой выражение.
В строчке (ix) используется продукция 3 для умножения идентификатора a на выражение, исследованноев строчке (viii). Процесс порождения цепочек путем применения продукций “от головы к телу” требует определения нового символа отношения ⇒. Пусть G = (V, T, P, S) — КС-грамматика. Пусть αAβ — цепочка из терминалов и переменных, где A — переменная.
Таким5.1. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈСтр. 189189образом, α и β — цепочки из (V U T)*, A ∈ V. Пусть A → γ — продукция из G. Тогда мыговорим, что αAβ ⇒ αγβ. Если грамматика G подразумевается, то это записываетсяGпросто как αAβ ⇒ αγβ. Заметим, что один шаг порождения заменяет любую переменнуюв цепочке телом одной из ее продукций.ВыведеннаяцепочкаДля языкапеременнойИспользованная продукцияИспользованныецепочки(i)aI5—(ii)bI6—(iii)b0I9(ii)(iv)b00I9(iii)(v)aE1(i)(vi)b00E1(iv)(vii)a + b00E2(v), (vi)(viii)(a + b00)E4(vii)a*(a + b00)E3(v), (viii)(ix)Рис.
5.3. Вывод цепочек с использованием грамматики, показанной на рис. 5.2Для представления нуля, одного или нескольких шагов порождения можно расши∧рить отношение ⇒ подобно тому, как функция переходов δ расширялась до δ . Для обозначения нуля или нескольких шагов порождения используется символ *.*Базис. Для произвольной цепочки α терминалов и переменных считаем, что α ⇒ α.GТаким образом, любая цепочка порождает саму себя.**Индукция. Если α ⇒ β и β ⇒ γ, то α ⇒ γ.
Таким образом, если α может породитьGGGβ за нуль или несколько шагов, и из β еще за один шаг порождается γ, то α может поро*дить γ. Иными словами, α ⇒ β означает, что для некоторого n ≥ 1 существует последоGвательность цепочек γ1, γ2, …, γn, удовлетворяющая следующим условиям.1.α = γ1.2.β = γn.3.Для i = 1, 2, …, n–1 имеет место отношение γi ⇒ γi+1.**Если грамматика G подразумевается, то вместо ⇒ используется обозначение ⇒ .G190Стр.
190ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈПример 5.5. Вывод о том, что a*(a + b00) принадлежит языку переменной E, можноотразить в порождении этой цепочки, начиная с E. Запишем одно из таких порождений.E⇒E*E⇒I*E⇒a*E⇒a * (E) ⇒ a * (E + E) ⇒ a * (I + E) ⇒ a * (a + E) ⇒a * (a + I) ⇒ a * (a + I0) ⇒ a * (a + I00) ⇒ a * (a + b00)На первом шаге E заменяется телом продукции 3 (см. рис. 5.2).
На втором шаге применяется продукция 1 для изменения E на I и т.д. Заметим, что мы систематически придерживались тактики замены крайней слева переменной в цепочке. На каждом шаге, однако, мыможем произвольно выбирать переменную для замены и использовать любую из продукций для этой переменной. Например, на втором шаге мы могли бы изменить второе E на(E), используя продукцию 4. В этом случае E * E ⇒ E * (E). Мы могли бы также выбратьзамену, не приводящую к той же самой цепочке терминалов. Простым примером было быиспользование продукции 2 на первом же шаге, в результате чего E ⇒ E + E, но теперь никакая замена переменных E не превратит цепочку E + E в a * (a + b00).*Мы можем использовать отношение ⇒ для сокращения порождения. На основании*базиса нам известно, что E ⇒ E.
Несколько использований индукции дают нам утвер***ждения E ⇒ E * E, E ⇒ I * E и так далее до заключительного E ⇒ a * (a + b00).Две точки зрения — рекурсивный вывод и порождение — являются эквивалентными.Таким образом, можно заключить, что цепочка терминалов w принадлежит языку неко*торой переменной A тогда и только тогда, когда A ⇒ w.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
