Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 57

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 57)

Пример 7.3. Арифметическое выражение а 8+с в грамматике из примера 7.1, г имеет вывод 1, 1+Т, Т+Т, Т«М+ +Т, М ° М+Т, К М+Т, а.М+Т, п»К+Т, а ° 8+К, а.8+с. Дерево этого вывода приведено на рис. 7.1. Оно содержит )б вершин, тогда как вывод— 52 символа Правда, для столь простого выражения и вывод и его дерево выглядят слишком Х Т сложными. Причинами этого + являются некоторые особенно- Т сти данной грамматики, которые будут обсуждены ниже (пример 7.5), зь Компактность — не единственное достоинство дерева вы- с вода. Не менее важно то, что дерево вывода сохраняется прн Ъ некоторых изменениях вывода„ что позволяет их считать несущественными.

Таким несущественным изменением вывода является изменение порядка применения правил к различным вхождениям нетерминальных символов цепочки. Более точно, если в выводе А=1, иь.. аь а~+ь аць ...,а,цепочки ам~ и аы, получены применением правил гь и гй грамматики к двум различным вхождениям нетерминальных символов Л;, и Ал в пь то перестановка этих цепочек в выводе допустима в том смысле, что она не изменит результата, т. е. Л'=1, аь ..., аь и~+я а~+о а;+з, ..., и„— также вывод цепочки а,, В терминах дерева вывода это очевидно: приклеивание элементарного дерева 1(гд) к вершине Ак и элементарного дерева 1(г;,) к другой вершние Ад одного н того же дерева дадут одно и то же дерево независимо от порядка этих двух операций. Множество выводов, получаемых указанными допустимыми перестановками и имеющих одно и то же дерево вывода, образует класс эквивалентности.

Среди эквивалентных выводов существует левосгоронний вывод, в котором на любом шаге правило применяется всегда к самому левому нетерминальному символу. Например, вывод, описанный в примере 7.3, — левосторонний, Между левосторонними выводами существует взаимно однозначное соответствие. Очевидно, что если левосторонние выводы равны, то равны и деревья. Пусть Л=1, аь аь.. н Ь'=1, йь рг...

различные левосторонние выводы, и пусть а; и р; — первые несовпадающие цепочки в них. Поскольку еи ~=()~ ь то и; и (), могут быть различны только за счет того, что к самому левому нетерминальному символу и;, будут применены различные правила; поэтому при построении деревьев 1(Л) и 1(Л') на этом шаге к самой левой вершине дерева с кроной а; ~ будут приклеены различные элементарные деревья, и, следовательно, 1(Л) и 1(Л') будут различны. Таким образом, для данного дерева левосторонний вывод— единственный.

Взаимно однозначного соответствия между цепочками данного языка 1. и деревьями вывода в грамматике 6, порождающей 1. (6), может и не быть. КС-грамматика 6 называется неоднозначной, если существует хотя бы одна цепочка в Е(6), имеющая в 6 более одного дерева вывода (или более одного левостороннего вывода). КС-язык, все порождающие грамматики которого неоднозначны, называется существенно неоднозначным. Пример 7.4. а. Грамматика 6 нз примера 7А, а, порождающая язык 1.

(6) =(а'"-'), однозначна. Действительно, в этой грамматике любой вывод имеет вид 1, аа1, ..., а'"1..., т. е. в нем и — 1 раз применяется второе правило; первое правило может быть применено только на последнем шаге, поскольку оно дает терминальную цепочку. Поэтому различные выводы в 6 обязательно отличаются длиной, а поскольку на каждом шаге добавляется ровно один нетерминальный символ, то выводы разной длины дают различные цепочки языка 1.(6).

Следовательно, в этой грамматике любая цепочка имеет ровно один вывод (в ней нет даже эк274 вивалентных выводов, т. е. различных выводов, имеющих одинаковое дерево). Однако этот же язык можно задать неоднозначной грамматикой 1-»-а, 1 — »-!а1, в которой, например, цепочка ат имеет несколько различных деревьев (например, рис. 7.2, а и б) и соответственно несколько левосторонних ,выводов.

а а а а б Рис. 7.2 б, Рассмотрим грамматику, полученную из грамматики примера 7.1, г отождествлением всех нетерминальных символов и удалением всех получившихся тривиальных правил 1-»-1: 1 — ! + 1( 1 — 1! ! ° 1 ~ 1(1( (1) ( а ! Ь! с. Эта грамматика эквивалентна исходной; кроме того, выводы и деревья в ией существенно короче. Однако она неоднозначна.

Выражение а Ь+с имеет в ней два дерева вывода (рис. 7.3, а и б). в. Язык (а™Ь си()а Ь "с") существеннв неоднозначен. Доказательство этого имеется, например, в (32]. Неоднозначность языка представляет собой неудобство при его использовании. Дело в том, что дерево вывода является основным средством для интерпретации цепочки; поэтому синтаксическая неоднозначность (т. е. наличие нескольких деревьев вывода) цепочки влечет за собой ее семантическую неоднозначность — наличие различных интерпретаций.

Например, для цепочки а ° Ь+с из примера 7.4,б разные деревья вывода интерпретируются как разные способы расстановки скобок (в первом случае (а ° Ь)+с, во втором — а ° (Ь+с) ), что ведет к разной последовательности операций и соответственно к разным результатам вычисле- 18» 275 иий, Отметим, что явное введение скобок после каждой неодноместной операции в языках формул (логических, арифметических, алгебраических и т, д.) является достаточным средством для обеспечения однозначности.

Грамматики со скобками (см. пример 7.1, в) хотя и приводят к избыточным скобкам' в формулах, однако пбзнолйют умень- Ь а) Риа 7.3 шить число нетерминальных символов и тем самым упростить синтаксическую структуру формулы, определяемую ее деревом. Именно поэтому языки формул исчисления высказываний и исчисления предикатов Я 6.1 и 6.2) определены в стиле примера 7.1, в. Приведение КС-грамматик. Поскольку для одного и того же КС-языка могут существовать различные грамматики (в том числе и разных типов), то возникает проблема выбора грамматики, наиболее подходящей по тем или иным свойствам, или проблема эквивалентного преобразования грамматики к нужному виду.

Желаемые свойства могут быть различными — однозначность, минимальное число правил или нетерминальных символов, простота вывода и т. д. Универсальных методов эквивалентных преобразований КС-грамматик не существует из-за неразрешимости алгоритмических проблем распознавания эквивалентности КС- грамматик и существенной неоднозначности КС-языков (см. ниже теоремы 7.6 и 7.7), Однако можно предложить эквивалентные преобразования, которые с некоторой точки зрения улучшают грамматику. Назовем нетерминальный символ А выводимым, или достижимым, если !=ь-'аА6, и производящим, если Л=~-су, где а, р — произвольные цепочки, а уеи)7"' (у — терминальная цепочка).

Нетермииальный символ называется существенным, если он дости- 276 жимый и производящий; в противном случае он называется несущественным, илн бесполезным, Грамматика называется прпееденноць если она — неукор ачивающая и не содержит бесполезных символов. Покажем„что для любой КС-грамматики можно построить эквивалентную ей приведенную КС-грамматику, Для этого сначала покажем, как выделять достижимые н производящие символы. Алгоритм выделения достижимых символов определим индуктивно.

Обозначим через М, множество всех петермннальнь'.х символов, содержащихся в правых частях правил вида 1- и. Очевидно, что все символы М, достижимы, Пусть уже определено множество не- терминальных символов М; и показано, что все символы М; достижимы, Определим М;+1 — — МДМ~, где М вЂ” множество всех нетерминальных символов из правых частей пра. вил вида А-+а, где АенМь Алгоритм останавливается на шаге й, если М~=Мь,, множество достижимых символов совпадает с М„, причем й(~ В'~. Алгоритм выделения производящих символов аналогичен предыдущему, но работает «с конца вывода», Обозначим через Я, множество всех не- терминальных символов А, для которых в 6 имеются правила вида А-~.и, где иен)г". Все символы я1 — производящие.

Пусть уже определено множество О, и показано, что все символы О~ — производящие. Определим 9~+1 Я;Щ„ где Я,.' содержит все нетерминальные символы А, для которых в 6 имеются правила вида А — ~-а, где а~я (ЩЯ,)'. Алгоритм останавливается на шаге 1, если Я~=Я~ ь Множество производящих символов совпадает с Яь причем (() )р). Теперь приведенная грамматика 6'= (Ь", %", )с', 1 ), эквивалентная предыдущей, определяется так: В" — это множество существенных символов 6'.Ж"=МДЯп Я' содержит только те правила нз Я, в которых нет бесполезных символов; Г содержит только такие терминальные символы, которые встречаются в правых частях правил из Я, Равенство Е (6) =Е (6') доказать нетрудно; зто мы предоставляем читателю.

Следующее полезное преобразование грамматики— это устранение правил вида А-э-В, которые называются цепными. Алгоритм, который по произвольной неукорачивающей КС-грамматике 6= ( г', йг, )г, 1) строит эквивалентную ей грамматику 6' без цепнгях правил, состоит из двух этапов. На первом этапе для каждого Аснар' находит- 277 ся множество )»» всех нетерминальиых символов Е, таких, что А=~-»Е; ясно, что Ее=.Ю», если имеется последовательность правил А — »В, В-»С, ..., -«-Е, т.е.

отношение А=«-»В является транзитивным замыканием (см, 5 1.3) отношения А — »Е, На втором этапе определяется множество правил В': если В- а содержится в Й и не является цепным, то для любого А, такого, что Вен)««», включаем в 17' правило А-«-а. Полагаем 6'= ( У, %', К', 1) . Пример 7.5.

Характеристики

Список файлов книги