Кузнецов О.П., Адельсон-Вельский Г.М. - Дискретная математика для инженеров (1048837), страница 56
Текст из файла (страница 56)
Справедливо н обратное: для.любой неукорачивающей грамматики существует эквивалентная ей контекстная грамматика. Мы не будем здесь доказывать это утверждение; отметим лишь, что для его доказательства можно использовать метод двойников — так, как это было сделано в примере 7.1, д. Из этих двух утверждений Следует, что класс языков, порождаемых неукорачнвающимн грамматиками, совпадает с классом языков типа 1.
В некоторых вариантах классификации Хомского грамматики тяпа 1 определяются именно как неукорачнвающне. Это, как видим, не изменяет классификации языков, Таким образом, разрешимость (н даже примитивная рекурснвность) является необходнмым условием принадлежности языка типу 1, н, следовательно, любое перечнслнмое, но не примитивно-рекурсивное множество цепочек является языком типа О, но не типа 1. Контекстно-свободные грамматики. Деревья вывода, По определению КС-грамматик онн могут быть и укорачивающнми (правая часть бесконтекстного правила А-+а может быть пустой); поэтому, строго говоря, существуют языки типа 2, не являющнеся языками типа ! (таковы, например, все КС-языки, содержащие пустую цепочку е, поскольку в грамматнках типа 1 пустая цепочка невыводима).
Однако в теорнн грамматик показывается, что для любой укорачивающей КС-грамматнки может быть построена неукорачивающая КС-грамматнка 6', почтн эквивалентная 6, т. е. такая, что Б(6 ) =Е(6), если еф7,(6), и Ь(6') = Ц6) е, если еевич(6). Поэтому достаточно ограничиться изучением свойств неукорачнвающнх КС-грамматик. КС-языкн являются панболее хорошо изученным классом языков. Это объясняется тем, что с одной стороны, КС- грамматнкн оказались весьма подходящим аппаратом для описания строения естественных языков и особенно языков программирования; с другой стороны, благодаря относительной простоте и содержательности структуры„КС-языков и наличию удобных средств ее описания исследование КС- языков представляет значительный теоретический интерес. Появление понятия КС-грамматнки (введенного Хомским) практически совпало с появлением метаязыка Вакуса (нли нормальной формы Бэкуса), который впервые был использован при описании языка программирования АЛГОЛ-60 н быстро стал общепринятым средством формального описания языков программирования.
Описание языка с помощью нормальных форм Бэкуса представляет 269 собой совокупность «металингвистических формул» вЂ” выражений вида Х:: = У~ ~ ... ~ У„где Х вЂ” некоторый текст, заключенный в угловые скобки и называемый металингвистнческой переменной, а уь ..., у, — последовательности металингвистнческих переменных и основных символов языка (букв, цифр, разделителей, неделимых слов типа Ьеп!п, ецио, е!зе и т.
д.). Знак и=называется металингвистической связкой и читается как «есть» или « — это»; знак ~ — это металингвистическая связка «или»; металингвистическая переменная представляет собой имя конструкции языка; металннгвистическая формула в целом — это описание различных синтаксических вариантов строения конструкции Х, стоящей в левой части, через другие конструкции и основные символы языка, указанные в правой части. Перечисление вариантов производится с помощью связки. Пример 7.2. а. Множество идентификаторов АЛГОЛ-60— это множество цепочек из букв и цифр, начинающихся с буквы.
Этот язык может быть описан с помощью следующих нормальных форм Бэкуса (металингвистических формул), в которых цепочка из букв и цифр сокращенно называется БЦ-ценочкой: ( идентификатор ):; = ( буква ) ~ ( буква ) ( БЦ-цепочка ) ( БЦ-цепочка ):: = ( буква ) ! ( цифра ) ! ( буква ) ( БЦ-цепочка ) !( цифра ) ( БЦ-цепочка ) ( буква ) п=а!Ь!...)г ( цифра) п=0)1!...9 Основные символы языка — это 26 букв латинского алфавита и 10 цифр. б.
Язык арифметических выражений (без констант и с фиксированным множеством переменных а, Ь, с) в метаязыке Бэкуса описывается следующим образом: ( арифметическое выражение ) .: = ( терм ) ! ( арифметическое выражение ) + ( терм ) ~ ( арифметическое выражение ) — ( терм ) ( терм );: ( множитель ) ! ( терм ) ( множитель ) ~ ( терм ) /( множитель ) ( множитель );: =( ( арифметическое выражение ) ) ~ ( переменная ) ( переменная ) п=а~Ь! с Уже из этих примеров ясно, что нормальные формы Вакуса нетрудно преобразовать в КС-грамматику. Действительно, основные символы соответствуют терминальным символам грамматики, металингвистические переменные— нетерминальным символам, связка::= — знаку -+., а без связки ~ можно обойтись, если формулу Х::=У,!...~ У, заменить системой формул Х;:=Уь ..., Х::=У„. Если указанное преобразование провести для последнего примера, за.
менив ( арифметическое выражение ) на символ !, ( терм ) — на 7, ( множитель ) — на М, ( переменная ) — на Л, то получим КС-грамматику из примера 7.1, г. Ясно также, что указанное соответствие является вза. имио однозначным, и всякая КС-грамматика легко преобразуется в нормальные формы Бэкуса. В частности, для сокращения записи КС-грамматик используется связка чем и будем пользоваться в дальнейшем.
Такое простое соответствие между двумя видами описаний одного и того же класса языков, которые возникли практически одновременно из разных соображений (грамматики — из теоретических, формы Бэкуса — из прикладных), является свидетельством близости теоретических н практических целей (что бывает не так часто, как хотелось бы) исследования КС-языков и одной из причин необычайно быстрого развития теории КС-языков в течение последних 20 лет.
Другая, более глубокая причина широкого использования аппарата КС-грамматик для анализа естественных языков н языков программирования — это возможность описать грамматическую (в смысле традиционной лингвистики) структуру текста языка (т. е состав и связь языковых конструкций, образующих текст) в терминах вывода этого текста в подходящей грамматике. Изучением связи между структурой текста и его выводом мы сейчас и займемся. Вывод в формальных системах вообще и в грамматиках в частности определяется как последовательность цепочек, в которой любая пара соседних цепочек ш, а;+~ находится в отношении непосредственной выводимостн: а~=ь-а +ь В КС-грамматиках вывод может быть представлен существенно более компактно — в виде дерева вывода.
Для его описания введем необходимые определения. Будем рассматривать деревья с корнями, ориентированные в направлении от корня (см. $4.3). Вершина называется потомком вершины пь если существует путь из и, в оь и непосредственным потомком оь если существует ребро (пь о~). Дерево с корнем назовем элементарным, если все его концевые верши- ны — непосредственные потомки корня.
Для деревьев с корнями упорядочение вершин слева направо определяется следующим образом: для любого элементарного поддерева его концевые вершины полностью упорядочены (т. е. расположены на плоскости так, что для любой пары вершин ясно, какая из них левее другой в обычном смысле слова); если п~ н в~ — непосредственные потомки одной вершины и ш левее пн то любой потомок ш левее любого потомка пр Легко видеть, что любые две вершины лежат либо на одном пути, либо одна левее другой.
Есликонцевые вершины дерева помечены буквами, то цепочка, которая получится, если выписать буквы в соответствии с упорядочением помеченных имн концевых вершин, называется кроной дерева. Каждому правилу гн А- з; ег,..зг, где ег — термиз'" гкп' иальный или нетерминальный символ, поставим в соответствие элементарное дерево 1(г,) с 1(1)+1 вершиной, корень которого помечен символом А, а 1(1) концевых вершин— символами з;,, е;,, „, зйн, причем упорядочение вершин со. ответствует упорядочению помечающих их символов в правой части гь Очевидно, что крона этого дерева совпадает с правой частью гь Для любого вывода Л=1, аь ап ..
а„в грамматике 6 дерево вывода определяется индуктивно. Отрезку вывода Л~ 1, а~ соответствует правило 1-»а~ грамматики 6; этому отрезку ставится в соответствие элементарное дерево, соответствующее этому правилу; заметим, что его кроной является аь Пусть уже определено дерево вывода 1(Л;) для отрезка Л;=1, аь ..., аь и его кроной является аь Дерево 1(Льы) для отрезка Ла~=1, аь ..., аь аьм определяется так.
Если а;+, получается из а, применением правила г,:А- б к некоторому вхождению А в пь то этому вхождению А однозначно соответствует концевая вершина в кроне 1(Л,). Тогда 1(Лзп) получается отождествлением кроны элементарного дерева 1(г~) с вершиной вз, т.
е. «приклеиванием» 1(П) к вершине пю Легко видеть, что эта операция над деревьями соответствует применению правила г; к аь н кроной 1(Л.ь~) является а~~о Высотой дерева вывода (или просто высотой вывода) называется длина максимального пути от корня дерева к концевой вершине, Заметим, что одновременно с индуктивным определением дерева вывода мы доказали следующее утверждение: если Л вЂ” вывод а, то крона 1(Л) совпадает с а. Кроме того, число нетерминальных вершин (т. е. вершин, помеченных Ф Рис. 7.1 18 — 750 нетерминальными символами) дерева вывода А=1, пь ..., а„терминальной цепочки и=и равно и, т.
е. числу применений правил в выводе Л. Действительно, на каждом шаге построения дерева вывода (соответствующем применению одного правила г;) ровно одна нетерминальиая вершина (та, к которой приклеивается дерево 1(г;) ) перестает быть концевой; все эти вершины для разных шагов различны, а в окончательном дереве 1(Л) концевых нетерминальных вершин нет. Таким образом, общее число вершин (и, следовательно, символов, использованных прн описании) дерева вывода 1, аь ..., и, равно и+ ~ а,~, что гораздо мень- л ше числа '~', (а~~ символов в представлении вывода как по- им следовательности цепочек.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
