Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 50
Текст из файла (страница 50)
рис. 5 /4) ГЛАВА 6. КОНТЕКСТНО-СВОВОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ Возможно, читатель заметил, что правила для элементов в РТР (см. рис. 5.!4) не полностью совпадают с продукциями в КС-грамматиках. Многие правила имеют корректный вид, например, правило <!ЕЕЕМЕНТ РНОСЕББОН (МАНЕ, МОРЕР, БРЕЕР) > аналогично продукции Ргасекзаг — э МалРМаг7е! Креес!. Однако в правиле <!еьемент Р1Бк (нАЕРР1Бк 1 сР 1 РчР) > олределение для Р1БК не похоже на тело продукции. Расширение в этом случае является простым; это правило можно интерпретировать как три продукции, у которых вертикальная черта играет ту же роль, что и в продукциях обычного вида.
Таким образом, это правило эквивалентно следуюшнм трем продукциям. 0)к)г -> НаггЫгй ) Сс( ! Ргс) Труднее всего следуюшее правило. <)ЕРЕМЕНТ НС (МОРЕР, ННТСЕ, ЕНОСЕББОН, ЕДМ, Р1БК+) > Здесь "тело' содержит оператор замыкания. Решение состоит в замене Р1БК+ новой переменной, скажем, Рй)м, которая порождает с помошью пары продукций один или несколько нпемпляров переменной РМ. Итак, мы получаем следующие эквивалентные продукции.
Рс г Маг!с! Расе Ргосезяаг Ват РЬ)сз РИЬ вЂ” э Р!эй ) РВИ Р!как Сушествует общая техника преобразования КС-грамматики с регулярными выражевиями в качестве тела продукций в обычные КС-грамматикн. Идею этого преобразования опишем неформально; возможно, читатель захочет уточнить как смысл КС- грамматик с регулярными выражениями, так и доказательство того, что такое расширение не приводит к порождению языков, не являющихся КС-языками. Мы покажем, как продукция с регулярным выражением в качестве тела преобразуется в совокупность обычных продукций. Для этого применим индукцию по размеру выражения в теле. Базис.
Если тело представляет собой конкатенацию элементов, то продукция уже имеет допустимый в КС-грамматиках вид, поэтому преобразовывать нечего. Индукция. В зависимости от старшего оператора возможны пять ситуаций. 1. При конкатенации продукция имеет вид А — э Еь Е„где Е, и Е, — выражения, допустимые в языке РТР. Введем две переменные, В и С, не используемые больше нигде.
Заменим А -э Е„Е~.' А — г ВС В вЂ” >Е~ С вЂ” г Ез 5.3. ПРИЛОЖЕНИЯ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК 217 Первая продукция, А -з ВС, допустима в КС-грамматиках. Две последние могут быть как допустимыми, так и недопустимыми. Однако их тела короче, чем тело исходной продукции, поэтому на основании индукции их можно преобразовать в форму КСчрамматик. 2. Для оператора объединения продукция имеет вид А — ьЕ, ~Е,.
Заменим ее следующей парой продукций. А -э Е~ А -э Ее Аналогично, этн продукции могут иметь недопустимый вид, но их тела короче, чем тело исходной. Применяем эти же правила рекурсивно и преобразуем их к виду КС-грамматик. 3. Продукция имеет вид А — ь(Е,)*. Введем новую переменную В, не используемую больше нигде, и заменим продукцию следующими тремя. А — э ВА А — ье  — з Еу 4. Для продукции А -ь(Е,)' вводим новую переменную В, не используемую больше нигде, и заменяем продукцию следующими тремя. А — э ВА А — +  — >Е, 5, Продукция имеет видА — ь (Е,)?.
Заменим ее: А — +е А — эЕ, Пример 5.24. Рассмотрим преобразование РТР-правила <!ЕЕЕМЕНТ РС (МООЕЬ, Р81СЕ, РЕОСЕЯЯОЕ, РДМ, О1ЯК+)> в обычные для КС-грамматик продукции. Тело этого правила рассмотрим как конкатенацию двух выражений, первое из которых есть МОРЕЕ, РР1СЕ, РРОСЕЯЯОР, ЕАМ, а второе — О1ЯК+. Создав ддя этих подвыражений переменные А и В, соответственно, используем следующие продукции.
Рс — > АВ А -э Ь(оде( Расе Ргосееког Волг  — э 1эих.ь Только последняя не имеет нужного вида. Введем еще одну переменную С и следующие продукции.  — э СВ ~ С С вЂ” э Вих 218 ГЛАВА б. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ В данном частном случае переменные А и С в действительности не нужны, поскольку яыражение, порождаемое из А, есть просто конкатенация переменных, а ]ойх — одиночная переменная. Вместо приведенных продукций можно было бы использовать следующие. Рс -г )г(ог!е! Ргке Ргосеззог Ваш   — з Вий В ( Вц3 5.3,5. Чпражнения к разделу 5.3 53.1.
Докажите, что если цепочка скобок сбалансирована (как в примере 5.19), то она порождается грамматикой В-+ ВВ((В) (н Указание. Проведите индукцию по длине цепочки. 53.2. Рассмотрим множество всех цепочек сбалансированных скобок двух типов, круглых и квадратных. Следуюший пример показывает нх происхождение. Если взять выражения в языке С, которые используют круглые скобки для группирования и для вызовов функций и квадратные 'скобки для индексов массивов, и удалить из них все, кроме скобок, то получим цепочки сбалансированных скобок этих двух типов. Например, Т(а[2]*(Ь[2] [3] ~гс[д(х) ] ),с([2) ) преврашается в сбалансированную цепочку ( [] ( [] [] [ () ] ) [] ) .
Построить грамматику для всех сбалансированных цепочек из круглых и квадратных скобок, и только для них. 5.3.3. В разделе 5.3 рассматривалась грамматика В-г в(ВВ(Б(БеВ и утверждалось, что принадлежность цепочки и языку В этой грамматики можно проверить путем повторения следующих действий, начиная с и . !. Если текушая цепочка начинается с е, то проверка не пройдена; ж е 1.. Если текущая цепочка не содержит е, то проверка пройдена; и и ь. 3.
В противном случае удалить первое е и ( непосредственно слева от него. Повторить зтн трн шага с полученной цепочкой. Докажите, что этот процесс правильно распознает цепочки языка Ь. 5.3.4. Добавьте к грамматике НТМ1. (см. рис, 5.13) следуюшие формы: а) (*) элемент списка должен заканчиваться закрываюшим дескриптором </(,Т>; б) элемент может быть как неупорядоченным, так и упорядоченным списком. Неупорядоченные списки заключаются в парные дескрипторы <()' > и </()Ь>; в) (!) элемент может быть таблицей, которая заключается в парные дескрипторы <тАВ(.Е> и <г'тАВТ,Е>.
Между ними находятся одна или несколько цепочек, каждая из которых заключается в <тй> и < /тй>. Первая цепочка яв- 3.3. ПРИЛОЖЕНИЯ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК 219 ляется заголовком с одним или несколькими полями, каждое из которых начинается дескриптором <тн> (будем предполагать, что эти дескрипторы не закрываются, хотя в действительности они парные).
Поля в следуюшнх цепочках начинаются дескриптором <тО>. <! ООСТУРЕ Соо сзеБрес ( <!ЕЬЕМЕМТ СООЕЯЕБ !СООАЯЕ+)> <!ЕЕЕМЕНТ СО!)ПЯЕ )СМАМЕ, РЕОР, ЯТООЕНТ", ТА?)> <!ЕЬЕМЕМТ СИАМЕ (~АКРОБАТА)> <!ЕЕЕМЕМТ БТООЕМТ )~АКРОБАТА)> <!ЕРЕМЕ)!Т ТА (~АКРОБАТА)> ) > Рис. 5 )б.
ОТО для курсов 5.3.5. Преобразуйте Е)ТО (рис, 5.16) в КС-грамматику. 5.4. Неоднозначность в грамматиках и языках Как мы увидели, в приложениях КС-грамматики часто служат основой для обеспечения структуры различного рода файлов. Например, в разделе 5.3 грамматики использовались для придания структуры программам и документам. Там действовало неявное предположение, что грамматика однозначно определяет структуру каждой цепочки своего языка. Однако мы увидим, что не каждая грамматика обеспечивает уникальность структуры. Иногда, когда грамматика не может обеспечить уникальность структуры, ее можно преобразовать, чтобы структура была единственной для каждой цепочки.
К сожалению, это возможно не всегда, т.е. суШествуют "сушественно неоднозначные" языки; каждая грамматика для такого языка налагает несколько структур на некоторые его цепочки. 5.4,1. Неоднозначные грамматики Вернемся к грамматике выражений (см. рис. 5.2). Эта грамматика дает возможность порождать выражения с любой последовательностью операторов + и ", а продукции Š— э Е+ Е ) Е * Е позволяют порождать эти выражения в произвольно выбранном порядке. Прцмер 5.25. Рассмотрим выводимую цепочку Е+ Е * Е.
Она имеет два порождения из Е: 1. Е=~Е+Е>ЕжЕ*Е 2. Е>ЕвЕ=оЕьЕвЕ Заметим, что в порождении 1 второе Е заменяется на Е * Е, тогда как в порождении 2— первое Е на Е + Е, На рис. 5.17 показаны два действительно различных дерева разбора. 220 ГЛАВА б. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ Л~, А' Е е Е б) в) Рис 517 Дво дерева разбора с одной и озой осе кроной Разница между этими двумя порождениями значительна. Когда рассматривается структура выражений, порождение 1 говорит, что второе и третье выражения перемножаются, и результат складывается с первым.
Вместе с тем, порождение 2 задает сложение первых двух выражений и умножение результата на третье. Более конкретно, первое порождение задает, что 1 + 2 * 3 группируется как 1 + (2 * 3) = 7, а второе — что группирование имеет вид (1 + 2) " 3 = 9. Очевидно, что первое из них (но не второе) соответствует нашему понятию о правильном группировании арифметических выражений.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
