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