Карпов - Основы построения трансляторов (2005), страница 6

Во всех остальных случаях этого примера языки задавались совершенно не годными для строгого формального анализа средствами. Так, для случая 5 нужно заранее знать, что такое "правильное скобочное выражение", в случае 8 определение "русский язык" ничего не говорит китайцу, а для понимания случая 9 нужно уже заранее знать язык Паскаль. Суть проблемы состоит в том, что невозможно задать новый язык, пользуясь определением 2.1. Определение "языком Паскаль называется множество программ, составляющих этот язык" будет воспринято как тавтология. Оно никак не помогает человеку, с этим языком незнакомому.

Описанная выше ситуация отражает общую трудность задания бесконечного множества объектов (в нашем случае бесконечного множества цепочек). Для задания такого множества простым перечислением требуются бесконечные Языки и грамматики ресурсы. Нужно суметь задать бесконечное множество цепочек с помощью какого-либо коцечиого механизма (алгоритма, устройства, исчисления, набора правил и т.

д.). Такие механизмы и называются грамматиками. Определение 2.2. Любой конечный механизм задания языка называется грамматикой. Существуют два пути задания языка. Первый — это конечное множество правил порождения за конечное число шагов правильных цепочек, причем эти правила не позволяют построить никакую цепочку„не принадлежащую языку. Другой подход — это задание механизма распознавания, который„получив в качестве аргумента любую конечную цепочку над словарем Г, за конечное число шагов дает ответ, принадлежит ли эта цепочка определяемому языку или нет. В соответствии с этими двумя подходами существует и два типа грамматик (рис.

2,2): порождающие и распознающие. Под порождающей грамматикой языка Е понимается конечный набор правил, позволяющий строить все "правильные" предложения языка Л, и применение которых не дает ни одного "неправильного" предложения. Распознающая грамматика задает критерий принадлежности произвольной цепочки данному языку. Это фактически некоторый алгоритм, принимающий в качестве входа символ за символом произвольную цепочку над словарем Г и дающий на выходе один из двух возможных ответов: либо "данная цепочка принадлежит языку Л", либо "данная цепочка не принадлежит языку У.".

Фактически этот алгоритм должен разделить все возможные входные цепочки на два класса: один класс — принадлежащие языку 1 цепочки, а другой — цепочки, не принадлежащие языку Л. Рис. 2.2. Порождающая и распознающая грамматики В качестве распознающей грамматики может выступать передача на радио 'Говорим по-русски". На вход программы поступает, например, вопрос: "Правильно ли говорить: Скучаю по Вас~".

Конечное число экспертов про- граммы в конечное время дает на любой такой вопрос ответ: "Да" или "Нет". Роль распознающей грамматики (распознающей процедуры) могут выполнить не только эксперты, но и абстрактные распознающие устройства, обычно называемые автоматами. Рассмотрим, например, конечный автомат без выхода. Свяжем с некоторыми состояниями автомата метку "Да" и назовем их "финальными" или "заключительными" состояниями, с остальными свяжем метку "Нет" и назовем их "незаключительными" состояниями.

Тогда все множество входных цепочек автомата разобьется на два класса. Первому классу принадлежат цепочки, приводящие автомат из начального в одно из финальных состояний (помеченных "Да"), второму — все другие цепочки, т. е. те, которые приводят автомат в какое-либо незаключительное состояние. При построении трансляторов подобные автоматы используются как модели алгоритмов распознавания цепочек языка.

В качестве порождак>щей грамматики может выступать диктатор (например, вождь племени), назначивший себя специалистом по языкознанию: все, что он говорит, и даже все, что он может сказать, считается для племени правильным м. Наше дальнейшее изучение будет связано с методом задания языков с помощью порождающих механизмов, в частности с порождающей грамматикой Хомского. Именно эта модель лежит в основе подавляющего большинства идей в области формальных грамматик.

Порождающая и распознающая грамматики играют несколько разные, но взаимодополняющие роли. Порождающая грамматика удобна и естественна для задания, спецификации языка. Порождающий механизм не является алгоритмом, он определяет правила построения предложений языка. Распознающий механизм, напротив, обычно представляется алгоритмом, он важен для анализа, трансляции цепочек языка в некоторый выход. 2.3. Граииатики Хоиского В 1956 г. американский лингвист Ноам Хомский предложил модель порождающей грамматики, которая весьма удобна для задания искусственных языков ~Х62~. Особенность этой модели состоит в том, что каждой порождаемой цепочке языка эта модель позволяет сопоставить ее структуру.

Определение 2.3. Порождающей грамматикой Хомского б называется четверка объектов: б = (Т, Х, 5, Я), где: З Т вЂ” конечное непустое множество (терминальный словарь). Элементы множества Т будем называть термипальпыми символами: 33 Языки и грамматики Ч Я вЂ” выделенный элемент нетерминального словаря, ЯеМ, так называемый начальный символ; :Э Я вЂ” конечное непустое множество правил (продукций), каждое из которых имеет вид а — +р, где и а, и Р— это цепочки над объединенным словарем Х~ >Ж, т. е. составлены как из терминальных, так и из нетерминальных си м волов. ПрИмер 2.3.

Рассмотрим следующую грамматику Хомского: 6<> = ~~а. К с~, , 'Л; А„В~, Я, А), где: Я = 1Я-+аЯ)Ас, иЛ' — +И>Ас, ОАс — «В, 1ерминальный словарь грамматики 6О содержит три терминальных символа или терминала) а, Ь и с; нетерминальный словарь содержит три нетерминальных символа (нетерминала) А„В и начальный нетерминал Я; множество А ;одер>кит пять продукций (правил). Для того чтобы различать в цепочках терминалы от нетерминалов, обычно (если не указано противное) терминалы ; оозначают строчными латинскими буквами и, К ..., а нетерминалы — прописными латинскими буквами А, В, ... Цепочки символов„как было сказано выше, обычно обозначаются греческими буквами а, Р, у, ...

При таком условии, если указать начальный нетерминал грамматики (по умолчанию будем .читать начальным нетерминал 5), то вся грамматика может быть задана пе:>ечислением конечного множества правил. Так, грамматика б~~ может быть ',адана просто набором правил: 1. Ь" — эа,ЯАС 2. аЯ вЂ” +БААС 3.

оАс-+В 4.,ЯА — >е 5. В-+Ь 'Уй = !Ьмерация правил приведена здесь только для удобства ссылок на них. По —,акому заданию всегда могут быть восстановлены как терминальный, так и :Э Ж вЂ” конечное непустое множество ~нетерминальный словарь). Элементы множества Ф будем называть лепырлипсиьпычп символами; множества Х и У не пересекаются; 34 Глава 2 нетерминальный словари. Рассмотрим теперь, каким образом можно, используя правила такой порождающей грамматики, получать цепочки языка. Вопервых, рассмотрим, как из одних цепочек с помощью правил грамматики могут быть порождены другие цепочки.

Это делается с помощью операции подстановки. Определение 2.4. Из цепочки а непосредственно выводима цепочка Р в грамматике б (операция непосредственной выводимости обозначается а ==>с; Р, или просто а ==> Р, если грамматика 6' очевидна)„если: Г3 цепочку а можно представить как конкатенацию трех цепочек, а = рт~ (некоторые из этих цепочек могут быть пустыми); Э цепочку Р также можно представить как конкатенацию трех цепочек, Р=- иЬ П в грамматике Ь есть продукция т-+", "разрешающая" вместо подцепочки т подстановку цепочки ~. Символ =-~; обозначает бинарное отношение на множестве всех цепочек над объединенным словарем У'и%. Пара цепочек а и р находится в этом отношении, если а ==>~; Р.

Расположение знака бинарного отношения между своими аргументами является стандартным обозначением бинарного отношения, например, 5 > 3. Таким образом, каждая грамматика Хомского б определяет свое бинарное отношение ==~~; на множестве (Ти Ж)* всех цепочек, составленных из терминальных и нетерминальных символов грамматики Ы две такие цепочки находятся в этом отношении, если из первой можно получить вторую, используя какое-либо из правил грамматики 6. ПРИМЕР 2.4. Из цепочки ЬАсаЯ в грамматике бо можно непосредственно вывести несколько цепочек, в зависимости от того, какое правило подстановки использовать и какую подцепочку в исходной цепочке мы будем заменять.

Например, Г3 ЬАсаЛ ==> ВаЯ, если по правилу 3 грамматики бо вхождение подцепочки БАс' мы заменим на цепочку В; П ЬАсиЯ =-> ЬАсИАс, если по правилу 2 грамматики бо вхождение подцепочки аЯ заменяется на цепочку Бас; ГЧ ЬЛсаЯ ==> ЬАсааЮЬАс, если по правилу 1 грамматики б~, заменяется вхождение подцепочки 5 на цепочку аЯАс. Таким образом, грамматика Хомского — это просто конечное число правил подстановки одних цепочек вместо других.

Правила имеют вид о — +~р, где д и ~р — это цепочки терминальных и нетерминальных символов, а символ "-+" можно интерпретировать, как "можно заменить на". С помощью этих правил Языки и грамматики можно преобразовывать цепочки символов: из одних цепочек можно получить другие цепочки — объекты той же самой природы, что и исходные объекты. 1!равила грамматики — операции непосредственной подстановки— '1о>кно выполнять многократно, используя каждую следующую полученную цепочку как исходную для дальнейшего преобразования. ОПРОДОййнй9 2.5.

Из цепочки а выводима цепочка ~3 в грамматике б (обоначается а ==~;* ~3, или просто а ==* ~3, если грамматика б очевидна), если уществует конечное множество цепочек ло, л~, ... л„, п > О„такое, что а = ло, ,".„= ~3. и чля всех ~ = 1, ... и выполняется л,. ~ -. -и,. 11ными словами„цепочка Р выводима из цепочки а в грамматике б, если Р чожно получить из а за конечное число шагов применения операции непо;редственной выводимости.

Символ "==>~;""' означает рефлексивное транзи~ивное замыкание отношения ">~;", т. е. О или любое конечное число шагов выполнения операции "~,;". Далее также будем использовать обозначение '=-. ~;+" для записи транзитивного замыкания оператора "-~,", т. е. для записи , дного или любого большего конечного числа шагов выполнения этого опе- ратора. ПРИМЕР 2.5. Из цепочки ЬАсаЯ в грамматике бо можно вывести несколько ыепочек.