Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 60
Текст из файла (страница 60)
Алфавит Хс называется входным алфавитом языка )ч (1=1,..., пт); Хс — это множество терминальных символов Ь, вместо которых производятся подстановки в В» указанные блочными правилами из Д. Алфавит В;=Л,Х; называется внешним алфавитом б; алфавит Х вЂ” внутренним алфавитом 6, алфавит В= () В; — термис=1 нальным алфавитом 6. Понятие вывода в блочной грамматике (блочного вывода) аналогично понятию вывода в обычной грамматике с той лишь разницей, что роль начального символа здесь играет начальный язык»е (т.
е. вывод может начинаться с любого слова из ь'), а применение правила х-~~, означает подстановку вместо некоторого вхождения х любого слова из 1,р Таким образом, длина блочного вывода не учитывает сложности вывода «внутри» языков Т.ь...,1, . Язык 1.(6), порождаемый блочной грамматикой 6,— это множество всех слов в терминальном алфавите б, выводимых в 6 из Ы Языки 1.;с=~' называются блоками языка Т.. При блочном подходе к описанию языков с помощью подстановок одних языков в другие понятие нетерминального символа становится относительным: символы из Х— нетерминальпые для грамматики 6, однако они же являются терминальными для языков 1.»подстановки которыхдруг в друга порождают 1.(6).
Если все 1ч — КС-языки и для каждого Л; зафиксирована порождающая его КС-грамматика 6;= ( г» йт» Р» Ус ), то обычная КС-грамматика 6= ( Р, $', Я, ! ), порождающая Т (6), определяется следующим образом: 1) $'=В; 2) в системе нетермииальных алфавитов (й» производим переименования таким образом, чтобы они не пересекались. Получаем систему алфавитов У» после чего полагаем (г'=( () йг, ()Х; 3) в правилах Р, символы из ~им %' заменяем символами из )рп полученную систему правил обозначим йь Каждому блочному правилу х-э-(ч из Р ставим в соответствие обычное правило х-+(А множество таких правил обозначим И', полагаем Я= ( Ц Р, ())с'; 4) 7 1=1 совпадает с начальным символом грамматики 6э начального языка. Доказательство того, что (.(6) =А(6), предоставляем читателю. Если же все блоки Т.~ — конечные языки, то понятие приведенной блочной грамматики определяется так же, как аналогичное понятие для обычной КС-грамматики, с той разницей, что достижимыми н производящими здесь называются не нетерминальпые символы, а языки-блоки Вь Блочная грамматика может быть представлена сетью из языков — ориентированным графом, в котором вершины соответствуют языкам-блокам, а ребра — блочным правилам.
Такие сети удобно интерпретировать как схемы (см, ниже 5 8.3), их вершины гл — как элементы, которым приписаны языки С(о;), символы входного алфавита языка т".(о~) — как входы элемента оь блочное правило х- Тч— как соединение в схеме, ведущее от выхода элемента, которому приписан язык Ьь к элементу ом язык г'.(оь) которого содержит х в своем входном алфавите. При такой ориентации ребер (от Л~ к х) начальный язык В' оказывается приписанным выходному элементу сети.
Формально сеть из языков (Л-сеть) — это пятерка объектов Л ( лФ, У', лр, у, оэ), где .Ф=(Аь ...,А ) — система конечных алфавитов; Ю= (Хь ..., Х ) — система конечных алфавитов, таких, что Х,с:-А„..., Х ыА, и для любых й / ХД(Ау Х,) Я; Ы=(г,ь...,Ь ) — конечное множество языков в алфавитах А,, ...,А соответственно; у — связный ориентированный граф с множеством вершин У=(сп ..., и,); и'епУ вЂ” выделенная вершина, называемая выходом сети.
Каждой вершние гч графа у приписан язык В(п,)евЫ, Каждое ребро, входящее в оь помечено символом из Х(п~) — входного алфавита Е(гл), причем кратные ребра имеют различные пометки. Названия алфавитов А, В, Х вЂ” те же, что и в определении блочной грамматики. Записи вида А(6), В(Л), Х(ьп) обозначают принадлежность алфавитов объектам, указанным в скобках.
19 — 750 299 Переход от блочной грамматики 6= ( Ф, Х, Ы, Д, Е' > к представляющей ее Л-сети Х(6) определяется следующим образом. Если Я=(Е~,...,Е ), то Х(6) содержит лт вершин оь ..., о; Е(о ) =Еь 1=1, ..., гп, а выходом является вершина о', для которой Е(о') =Е'. Для каждого правила х-+.Е; нз вершины го проводятся ребра с пометкой к ко всем вершинам оь таким, что терминальный алфавит Е(о~) содержит х, Обратный переход — от сети Х к блочной грамматике 6(Х)= (лГ, М, 2', )г, Еэ) столь же прост с той разницей, что для непересечения входных алфавитов может понадобиться их переименование: 2'=(Е;,...,Е ) — это множество языков Еь „Е сети Х, в которых, возможно, переименованы входные алфавиты так, чтобы они не пересекались. Ребру в Х, ведущему от вершины оу ко входу х, ставится в соответствие блочное правило х'-~-Е'(о;), где х' — либо х„ либо символ, заменивший х при переименовании входных алфавитов; д' является объединением всех блочных правил.
Л-сети Х~ и Хз называются слабо эквивалентными, если они представляют один и тот же язык: Е(6(Л~) ) =Е(6(Ля) ), и сильно эквивалентными, если блочные грамматики 6(Л,) и 6 (Хз), полученные в результате приведения 6 (Х~) и 6(Х~), совпадают с точностью до переименования внутренних алфавитов, Сети Х~ и Х(6(Х~)) могут и не совпадать, однако оии всегда сильно эквивалентны. В частности, при переходе от Х к 6(Х) из-за переименования может произойти увеличение мощности внутреннего алфавита; при обратном переходе эта мощность не меняется. Если в блочной грамматике 6 все языки-блоки конечны: Е,=(яь...,я,Д, то каждое блочное правило х-~-Е| эквивалентно множеству обычных КС-правил х-~а~ (ат~ ...
(а, и обычная КС-грамматика, эквивалентная 6, получается объединением всех таких правил. Если же все Е~ — одно- элементные языки, то блочные правила 6 — это обычные КС-правила, а сама 6 — обычная КС-грамматика. В этом случае Х(6) является графическим представлением обычной КС-грамматики. Пример 7.9. а. КС-грамматика 6з, полученная из примера 7.8 заменой а на с, представляется Л-сетью на рис. 7.4. б. Л-сетям А~ и Х~ (рис.
7.5)соответствует одна и та же блочная грамматика с начальным языком Е~ и системой правил И=(а-~Ем а-+Ем Ь-эЕо с — «Ем с — ~-Еь); следователь- 290 но, Х~ и Хз сильно эквивалентны. Поскольку входные символы 7.и и 7.4 совпадают, то вход 7,4 переименован в с. Если не делать переименования, то грамматика 0(7.1) имела бы правило Ь-и7.м тогда как соответствующее ребро из 7,4 ко входу Ь языка Е,з в Х4 отсутствует. Рис. 7.4 Рис. 7.б в. В Л-сети Хз на рис. 7.6 блоками являются языки (.з и 7.г нз примера 7.7, а также язык 4'.4 идентификаторов (например, из примера 7,3,а).
Язык, представляемый сетью ).м — это язык арифметических выражений (без вычитания и деления) над идентификаторами из 1.ь Сеть Х4 на ьг рнс.7.6 представляет тот же язык, поэтому Хз и Х4 слабо а эквивалентны; однако Х4 а имеет ребро из 7., в 1.з, ко- с, торое дает еще одно блочное правило в 6(х4), поэто- а а му Хс и Х4 не являются сильно эквивалентными. йсю ~5' Для блочных грамматик и Л-сетей также можно определить операции подстано- ли вкн и зацикливания. Для Л-сетей 7., и Ха подстановка Рис.
7.б Хс в А1 вместо входа аозначает введение ребер от выхода Хз ко всем вершинам Хь алфавиты которых содержат а; зацикливание по а означает введение ребер от выхода Х ко всем вершинам Х, алфавиты которых содержат а. 291 19* Блочные грамматики и сети из языков не порождают новых классов языков, однако являются удобным метаязыком для описания операций над языками, для описания структур сложных языков, выделения стандартных языковых компонент в новых языках н т. п.
Подробнее о блочных грамматиках и сетях из языков см. в [541. 7.3. О СЕМАНТИКЕ ФОРМАЛЬНЫХ ЯЗЫКОВ До сих пор речь шла о синтаксических свойствах языков. Однако, как указывалось в начале главы, главное назначение любого языиа— естественного илн искусственного — быть средством общения, т.е. передавать некоторое содержание, смысл. Множества смыслов, т.е. семантина языков, весьма разнообразны. Для естественных языков нх точное определение встречает значительньм трудности — н зто обстоятельство является главным препятствием на пути машинного перевода. Для искусственных языков множества смыслов определены, как правило, точно: это, например, ходы и позиции для языка шахматцой нотации, арифметические функции для языка арифметических формул, программы для языков программирования.
Формально любое множество 5 можно объявить семантикой, т.е. множеством смыслов (значений) данного языка (., если задать интерпретирующее отображение е языка Е в 5; тогда для цепочки а~7. и(сг) будет ее смыслом. Элементы 5, являющиеся значениями цепочек Е, могут иметь фиксированное символьное воплощение, например, быть цепочками некоторого другого, «понятного» языка (скажем, для человека его родной язык является семантикой любого иностранного язына); но зто необязательно: например, говоря об арифметических функциях как о семантике арифметических формул, мы не имеем в виду нх конкретное представление.
Итак, чтобы задать семантику языка 7„ необходимо определить множество смыслов 5 и интерпретирующее отображение е языка Е в 5. Важным достоинством языкон, описываемых КС-грамматикамн, является возможность задавать отображение гг с помощью деревьев выво. да.
Кратким знакомством со средствамн такого задания мы завершим изучение формальных языков, В качестве примера рассмотрим выражения, порождаемые грамма. тнкой нз примера 7.5. Их естественная интерпретация — последовательность арнфметнчесннх действяй над перемеинымн и, Ь, с (точнее, иад числамн, подставляемыми вместо зтнх переменных, например, над чнсламн, лежащими в ячейках памяти а, Ь, с). Вычисления производятся «из глубины формулы», т. е. начинаются в самых глубоких снобках (подформулах); каждая операция может быть выполнена лишь тогда, когда уже вычислены подформулы, являющиеся ее операндами. Структура формулы описывается ее деревом вывода: самым глубоким скоб- кам соответствуют элементарные поддсревья, все вершины которых концевые; вершине о, которой синтаксически соответствует нравнло рп А- а э р (о — знак арифметической операции), семантически соответствует операция, обозначаемая знаном с „ число потомкоа оь равное числу нетермннальных символов в р„ соответствует числу операндов е.
У операция в вершине о и,- жет быть выполнена только тогда, когда выполнены 1 Ьч 7 все вычисления в подда- ет ревьях, подвешенных к з. 4 + в Поэтому вычисление формулы можно представнгь Г и, е гч Я Г и, П и, ЬГ как процесс, идущий по ее дереву вывода снизу вверх )ч Рн )н — от концевых вершин н а Ь корню. Результаты вычислений передаются, наверх, Рис. 7,7 в следующую вершину; опе. рация, выполняемая в вершине, однозначно определяется правилом рн породившим эту вершину. Таким образом, процесс вычисления люба. го арифметического выражения является последовательностью опера. ций,взятых из фиксированного для данной грамматини множества; са.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
