Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 43
Текст из файла (страница 43)
5.1). С) Пример 5.3. Рассмотрим более сложную КС-грамматику, которая представляет выражения типичного языка программирования (в несколько упрощенном виде). Вопервых, ограничимся опера~орами + и '„представляющими сложение и умножение.
Вовторых, допустим, что аргументы могут быть идентификаторами, однако не произвольными, т.е. буквами, за которыми следует любая последовательность букв и цифр, в том числе пустая. Допустим только буквы а и Ь и цифры О и 1. Каждый идентификатор должен начинаться с буквы а или Ь, за которой следует цепочка из (а, Ь, О, 1) . 5.1. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ 187 В нашей грамматике нужны две переменные. Одна обозначается Е и представляет выражения определяемого языка. Она является стартовым символом.
Другая переменная, (, представляет идентификаторы. Ее язык в действительности регулярен и задается регулярным выражением гя в 1«)га в Ь в О -'; 1)*. В грамматиках, однако, регулярные выражения непосредственно не используются. Вместо этого будем обращаться к множеству продукций, задаюгцих в точности то же са- мое, что и соответствующее регулярное выражение. 1. Š— «1 2.
Š— + Е «Е 3. Š— «ЕвЕ 4. Š— «1'Е) 5. 1 — «а б. 1«Ь 7. 1 — «(а 8. 1 — «(Ь 9. 1 — «РО 10. 1 — «П Рис. 5.2 Контекстно-своооднан граитатика длн нростых выражений Грамматика для выражений определяется формально как О = 11Е, 1), Т, Р, Е), где Т= 1-«, *, 1, ), а, Ь, О, 1), а Р представляет собой множество продукций, показанное на рис.
5.2. Продукции интерпретируются следующим образом. Правило 1 является базисным для выражений. Оно гласит, что выражение может быть одиночным идентификатором. Правила 2 — 4 описывают индуктивное образование выражений. Правила 2 и 3 говорят, что выражение может состоять из двух выражений, соединенных знаком сложения или умножения. Правило 4 — что если заключить произвольное выражение в скобки, то в результате получается также выражение. Сокращенное обозначение продукций Продукцию удобно рассматривать как "принадлежащую" переменной в ее голове.
Мы будем часто пользоваться словами "продукции для А" или "А-продукции" для обозначения продукций, головой которых является переменная А. Продукции грамматики можно записать, указав каждую переменную один раз и затем перечислив все тела продукций для этой переменной, разделяя их вертикальной чертой. Таким образом, продукции А — «аь А — «ал ..., А — «а;, можно заменить записью А -+ а, ! а, ) ... ~ а„.
Например, грамматику для палиндромов 1см. рис. 5.1) можно записать в виде Р -+ в ! 0 ( 1 ( ОРО ! 1Р1. 188 ГЛАВА б. КОНТЕКСТНО-СВОВОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ Правила 5-10 описывают идентификаторы Ь Правила 5 и б образуют базис; они гласят, что а и Ь вЂ” идентификаторы. Остальные четыре правила описывают индуктивный переход: имея произвольный идентификатор, можно приписать к нему справа а, Ь, 0 или 1 я получить еше один идентификатор. ЕЗ 5.1.3.
Порождения с использованием грамматики юь Для того чтобы убедиться, что данные цепочки принадлежат языку некоторой переиениой, мы применяем продукции КС-грамматики. Есть два способа действий. Простейший подход состоит в применении правил "от тела к голове".
Мы берем цепочки, про которые извес~но, что они принадлежат языкам каждан из переменных в теле правила, записываем их в соответствующем порядке вместе с терминалами этого тела и убеждаемся, что полученная цепочка принадлежит язык> переменной в голове. Такая процедура называется релурсивным выводом (гесигзгке 1п(егепсе).
Есть еше один способ определения языка грамматики, по которому продукции применяются "от головы к телу". Мы разворачиваем стартовый символ, используя одну из его продукций, т.е. продукцию, головой которой является этот символ. Затем разворачиваем полученную цепочку, заменяя одну из переменных телом одной из ее продукций, и так далее, пока не получим цепочку, состоящую из одних терминалов. Язык грамматики — это все цепочки из терминалов, получаемые таким способом.
Такое использование грамматики называется выведенная, или порождением (деичаПоп). Начнем с примера применения первого подхода — рекурсивного вывода, хотя часто естественнее рассматривать грамматики в качестве применяемых лля порождений, н далее чы разовьем систему записи таких порождений. Пример 5.4. Рассмотрим некоторые из выводов, которые можно сделать, используя грамматику лля выражений (см.
рис. 5.2). Результаты этих выводов показаны на рис. 5.3. Например, строчка (1) говорит, что в соответствии с продукцией 5 цепочка а принадлежит языку переменной Ь Строчки (Н)-(1г) свидетельствуют, что цепочка ЬОО является идентификатором, полученным с помошью одного применения продукции 6 и затем двух применений продукции 9.
В строчках (г) и (и) использована продукция 1 для того, чтобы прийти к заключению, что цепочки а и ЬОО, ко~орые выведены как идентификаторы в строчках (1) и (1в), принаалежат также и языку переменной Е. В строчке (ит) применяешься продукция 2 для вывода, что сумма этих идентификаторов являешься выражением, в строчке (ий) — продукция 4, и эта же сумма в скобках также представляет собой выражение. В строчке (1х) используется продукция 3 для умножения идентификатора а на выражение, исследованное в строчке (ип). П Процесс порождения цепочек путем применения продукций "от головы к телу" требует определения нового символа отношения ~.
Пусть О= (1; Т, Р,5) — КС-грамматика. Пусть а413 — цепочка из терминалов и переменных, где А — переменная. Таким 5.1. КОНТЕКСТНО-СВОБОДНЬГЕ ГРАММАТИКИ образом, а и 1З вЂ” цепочки из 1РО Т), А н И Пусть А -+ у — продукция из О. Тогда мы говорим, что аАр ~ ау1э. Если грамматика 0 подразумевается, то это записывается просто как аАД ~ ауД Заметим, что один шаг порождения заменяет любую переменную в цепочке телом одной нз ее продукций. Рис. 5.3.
Вывод цепочек с использованием грачсиатики, показанной на рис. 5.2 Для представления нуля, одного или нескольких шагов порождения можно расши- рить отношение =е подобно тому, как функция переходов 6 расширялась до б . Для обозначения нуля или нескольких шагов порождения используется символ . Базис. Для произвольной цепочки а терминалов и переменных считаем, что а =ь а. о Таким образом, любая цепочка порождает саму себя. Индукция.
Если а =в 1З и Д =в у, то а =» у Таким образом, если а может породить о о ' о 1з за нуль или несколько шагов, и из 13 еще за один шаг порождается у, то а может поро- дить у. Иными словами, а ~ Д означает, что для некоторого и > 1 существует последо- в вательность цепочек у„уз, ..., у„, удовлетворяюшая следующим условиям. 1. а= уь 2. р= ус 3. Для! = 1,2, ..., и — 1 имеет местоотношение у =ау, Если грамматика 0 подразумевается, то вместо ~ используется обозначение =в .
ГЛАВА б. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ 190 ! Пример 5.5. Вывод о том, что а»(а+ ЬОО) принадлежит языку переменной Е, можно отразить в порождении этой цепочки, начиная с Е. Запишем одно из таких порождений. Е =» Е " Е ~ 1 * Е ~ а * Е =» а ' (Е) =» а» (Е ж Е) =-» а * (1 ж Е) =» а» (а ь Е) ~ а * (а + 1) ~ а * (а + 10) =» а * (а + 100) ~ а " (а + ЬОО) На первом шаге Е заменяется телом продукции 3 (см. рис. 5.2). На втором шаге применяется продукция 1 для изменения Е на 1 и т.д. Заметим, что мы систематически придерживались тактики замены крайней слева переменной в цепочке. На каждом шаге, однако, мы можем произвольно выбирать переменную для замены и использова~ь любую из продукций для этой переменной. Например, на вт.ором шаге мы могли бы изменить второе Е на (Е), используя продукцию 4.
В этом случае Е * Е » Е * (Е). Мы могли бы также выбрать имену, не приводящую к той же самой цепочке терминалов. Простым примером было бы использование продукции 2 на первом же шаге, в результате чего Е.=» Е+ Е, но теперь ника»ля замена переменных Е не превратит цепочку Е » Е в а * (а + ЬОО). Мы можем использовать отношение ~ для сокрашения порождения. На основании базиса нам известно, что Е =» Е. Несколько использований индукции дают нам утвер- ждения Е =» Е * Е, Е =» 1" Е и так далее до заключительного Е ~ а» (а + ЬОО).
Две точки зрения — рекурсивный вывод и порождение — являются эквивалентными. Таким образом, можно заключить, гто цепочка терминалов»» принадлежит языку неко- торой переменной А тогда и только тогда, когда А =» в. Доказательство этого факта, однако, требует некоторых усилий, и мы отложим его до раздела 5.2.
П 5.1.4. Левые и правые порождения Для ограничения числа выборов в процессе порождения цепочки полезно потребовать, чтобы на каждом шаге мы заменяли крайнюю слева переменную одним из тел ее продукций. Такое порождение называешься левым ()ейглозг), и лля его указания использу- ются отношения ~ и =». Если используемая грамматика С не очевидна из контекста, то / ее имя С также добавляется внизу.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
