Карпов - Основы построения трансляторов (2005) (943926), страница 7
Текст из файла (страница 7)
Например (здесь выделены заменяемыс подцепочки): :~ ЬАсаЯ =т'"' сЬс, поскольку ЬАссй =-> ВаЯ == саЖ => сЬЬАс ==> сЬВ => сЬс; Ч ИсаЯ.==* Виск, поскольку ЬАсаЯ ==> ЬАсас~КЬАс ==. ЬАсаис ==> Ваас. Гаким образом, грамматика Хомского представляет собой механизм порождения одних символьных цепочек из других символьных цепочек„причем из .одной и той же цепочки можно породить несколько различных цепочек, час—.о бесконсчное их количество. Например, в грамматике бо цепочка ЬАсаЯ :юсле подстановки вместо Я цепочки аЯЬАс по первому правилу превращает.я в цепочку, также содержащую Я.
Из этой новой цепочки по тому же правилу мы опять можем породигь цепочку, содержащую Я и т. д., — любое конечное количество раз. ~ Иметим, что порождающая грамматика Хомского не предписывает опреде.1енный единственный вывод, т. с. не задает алгоритм порождсния. Здесь от;~тствует важнейший элемент алгоритма — его детерминированность, опре'сленность последовательности операций. Грамматика представляет только возмо>кность — это инструмент, механизм порождения цепочек, и с этой .очки зрения грамматика Хомского является исчислением, подобным, на- 36 Глава 2 Перейдем теперь к вопросу о том, как связаны между собой грамматика Хом- ского и порождаем ы й ею яз ы к. 2.3Л. Как грамматика порождает язык? Определение 2.6.
Языком, порождаемым грамматикой б, называется мно- жество терминальных цепочек, выводимых из начального символа грамма- тики. Или, формально, Л(Ст) = (о,~-=?'" ~ Я =~с;*о,~. Итак, любой вывод цепочек языка мы должны начинать только с начального нетерминального символа. Если после произвольного конечного числа подстановок, выполненных в соответствии с правилами грамматики, полученная в результате цепочка состоит только из терминалов, то это цепочка является цепочкой порождаемого данной грамматикой языка. Отсюда ясны названия терминальные/нетерминальные символы. Только терминальные, окопчаиельпьк символы могут встретиться в цепочках языка, заканчивающих вывод. Нетерминальные — это дополнительные, вспомогательные символы, необходимые для задания языка конечным набором правил. Например, цепочка ЬЬЬ принадлежит языку, порождаемому грамматикой Йо.
Действительно: Я ==> «5Ь4с =- ЬЬАсЬАс ==. "ЬВЬАс ==> ЬВВ ==> ЬЬВ ==> ЬЬЬ (здесь в промежуточных цепочках вывода выделены подцепочки, которые на сле- дующем шаге заменяются в соответствии с одним из правил грамматики). ПРИМЕР 2.6. Попробуем охарактеризовать весь язык, который порождается введенной нами грамматикой Сто. Начинаться любой вывод может только с начального нетерминала, и для его замены в Йо есть только одно, первое пра- пример, исчислению высказываний.
Действительно, в исчислении высказываний объектами. над которыми производятся операции, являются высказывания, в грамматиках Хомского — цепочки символов. Конечным множеством операций в исчислении высказываний является фиксированное множество логических операций, с помощью которых из одних высказываний получаются другие. В грамматике Хомского множеством операций являются правила грамматики, в соответствии с которыми осуществляются подстановки, и из цепочек символов получаются объекты той же природы — другие цепочки символов.
В отличие от исчисления высказываний, в грамматике Хомского множество операций — правил — свое для каждой грамматики. Но в обоих случаях — и в исчислении высказываний, и в грамматиках Хомского — конечное множество операций используется для получения одних объектов из других: высказываний из высказываний, цепочек из цепочек. В обоих случаях порядок применения операций, алгоритм получения новых объектов из старых не предписан, можно использовать разные операции, разные объекты и получать разное — обычно бесконечное — число порожденных объектов. Глава 2 Применение любого из трех правил сразу завершит вывод с получением со- ответствующей цепочки языка из начального символа.
ПРИМЕР 2»8» Г) — ~а, Ь~: Е~ — ~а Ь ~ ~~ ~ О',. Любая цепочка языка Е2, порождаемая искомой грамматикой, имеет вид АВ, где А — цепочка, состоящая только из и, а о — цепочка из Ь, причем количества символов в группах А и В равны. При порождении удобно одновременно порождать и а, и Ь, тогда это требование будет выполнено автоматически. Если одним из правил грамматики будет 5-+аЯ~, то многократным его применением можно построить: Я ==:> аЯ~ ==> иаЯ)Б ==> ... =~ аа...иКЬ...ЬЬ ==> ...
Все промежуточные цепочки вывода не являются цепочками языка, порождаемого 62, поскольку эти цепочки состоят не только из терминальных символов. Для получения терминальных цепочек требуемого вида достаточно в этих промежуточных цепочках убрать Я, что может быть сделано при наличии в грамматике правила Я вЂ” +а. Окончательно: Вывод цепочки азЬ: Я == аЯ~ ==> ааЯЬБ == ааа%БЬ ==> аааЬЬЬ. ПРИМЕР 2.9. ~'з =- (,а., Ь, с~; Лз = (а'Ьс"'~ п, т > О~.
Структура любой цепочки языка Л~ — АоС (А — цепочки из а, С вЂ” цепочки из с, средняя часть В любой цепочки порождаемого языка состоит из единственного терминального символа Ь). Поскольку количества символов а в начале цепочек языка и с в конце цепочек могут не совпадать, отдельные части структуры цепочек можно генерировать независимо.
Искомая грамматика: К-+АВС А — +аА А-+а С вЂ” С» С вЂ” +с Введем небольшое упрощение при записи правил грамматики. Все альтернативные замены одного и того же нетерминала (т. е. различные правые части правил с одинаковой левой частью) будем записывать в одну строку через знак альтернативы 1'. =зыки и грамматики Я-+АВС А — +аА !а  — >Ь С вЂ” +С'с ~ с ~1ример вывода в грамматике бз. Я -..=~ АВС.' ==: аАВС ~ ааАВС ==> аааВС => .;«а!й.." =~ аааЬС.с =- аасйсс. Здесь иа каждом шаге вывода в промежуточной ,.ег!очке заменялась самая левая подцепочка, которую можно было заменить в ;.1ответствии с правилами грамматики.
Такой вывод называется канониче;ким левым выводом. Ту же цепочку языка можно породить в этой грамматике и с помощью другого вывода — например, заменяя самый правый не»ерминал в промежуточной цепочке вывода. Такой вывод называется кано:! !! геским прзВым: Л" => .4ВС' =-> АВС'с =-. АВсс ==:> АЬсс ==> аАЬсс:.."~ ааАЬсс ==:> .;«иЬсс. Наконец. можно породить ту же цепочку ни левым, ни правым выволом, произвольно выбирая заменяемую подстроку: Я ~ АВС' ==> АВСс =- «ЛВГс =- а.4ЬСс' ==> ааАЬ! 'с =~ ааЛЬсс ==> аиаЬсс. 11осгроенные нами грамматики б!- — 6; имеют особый вид правил "А — +а"— :;епочка левой части, определяющая заменяемую подцепочку, содержит ;о,!ько один-единственный символ нетерминального словаря.
Такие грамма; пки — по сути, частный подкласс грамматик Хомского — являются наибоее ингересными в теории трансляции, они называются "контекстно-свобод!ыми (КС) грамматиками". Для таких грамматик вывод цепочки порождае'!ого языка на каждом шаге состоит в замене некоторого нетерминала ;снтенциальной формы (промежуточной цепочки вывода) некоторой цепоч~ои в соответствии с одним из правил грамматики, причем замена эта н( у'чи; ывает ко!пекста„в котором находится этот нетерминал. Отсюда и название .-ра м мати ки — контекстно-свооодная.
".1оро>кдение цепочки языка в контекстно-свободной грамматике можно более .добно графически представить деревом, показывающим, как нетерминалы, ;~оящие в узлах дерева, заменяются цепочками правых частей соответст.'уюгцих правил (продукций) грамматики. Для всех трех различных выводов :!Спочки аааЬсс, приведенных выше, дерево вывода в грамматике бз одно и . о же (рис. 2.3), т. е.
в деревьях вывода информация о порядке подстановок в выводе цепочки языка из начального символа отсутствует. Итак, для КС- рамматик вывод удобно характеризовать именно деревом, а не линейной !оследовательностью шагов подстановок. деревья вывода л!обых цепочек языка, порождаемого КС-грамматикой, име.;1г следующу!о структуру. Корень дерева всегда помечен начальным симво1ом грамматики, в каждом внутреннем узле дерева стоит какой-либо нетер.!инал, а листья дерева помечсны терминальными символами так, что читае- Глава 2 мые слева направо они представляют терминальную цепочку, выведенную из начального символа.
Из любого узла дерева, помеченного нетерминальным символом Д, идут вниз ветви к узлам, помеченным Х1Х ... Хь если Д вЂ” +Х1Х. Х~. — это одно из правил грамматики (рис. 2.4). Рис. 2.3. Дерево вывода цепочки аааосс в грамматике бз Рис. 2.4. Представление узла дерева вывода для правила Я-+Х1Х~ ... Х~ Таким образом, вывод любой цепочки языка, порождаемой КС-грамматикой из начального символа грамматики, может быть экономно представлен деревом вывода.
Очевидно, что как правый, так и левый выводы цепочки языка— единственные в КС-грамматике, они однозначно восстанавливаются по дереву вывода. Обратно дерево вывода однозначно строится по любому выводу цепочки. Поэтому правый и левый выводы называются каноническими выводами цепочки в КС-грамматике. Можно предположить, что дерево вывода цепочки языка в КС-грамматике и представляет ту искомую структуру цепочки, с которой мы связывали надежды на построение алгоритмов трансляции языков.
Это предположение и сделал Н. Хомский. Согласно Хомскому, пепгериипалы граичаиики предслгавтот собой языковые копструкции (классы), г<граинцие оггределеппые ролгг в предлолсепиях языка, а дерево вывода связываеи эпггг роли и ггх с.иысловые паерузки, что иозволяет поспгроипгь или "вычислить" слгыслы более общих копспгрукций из смыслов их соспгивляющг~х копструкггий и, в конце копцов, вы ч ислиl11ь С.1гысл всеГО и~) ед?юлсишя. Именно эти понятия и идеи будут объектом нашего дальнейшего исследова- ния и формализации. Сделаем одно важное замечание, пользуясь примером 2.9. В этом примере по заданному языку Лз = ~а Ьс ~ п, пг > О,' ставилась задача построения порож- дающей этот язык грамматики.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
