Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 49
Текст из файла (страница 49)
5,12). 2. С/гаг (символ) — цепочка, состоящая из одиночного символа, допустимого в НТМ1= тексте, Заметим, что пробелы рассматриваются как символы. 3. |гас (документ) представляет документы, которые являются последовательностями "элементов". Мы определим элементы следующими, и это определение будет взаимно рекурсивным с определением класса |гас. 4. Е(етелг (элемент) — это или цепочка типа Техг, или пара соответствующих друг другу дескрипторов и документ между ними, или непарный дескриптор, за которым следует документ. 5. 1|хШет (элемент списка) есть дескриптор <11> со следующим за ним документом, который представляет собой одиночный элемент списка. 212 ГЛАВА б. КОНТККСТНО-СВОБОДНЫК ГРАММАТИКИ И ЯЗЫКИ 4. Евн(список) есть последовательность из нуля или нескольких элементов списка.
1. Сааг — з а~А~... -+ я ) Сааг Тех1 2, Тех! 3. Рос -з я ~ Е1етет.Рос 4. Е1етет тех1 'Ь <ЕМ> Рас <1ЕМ> ) <Р> Рос ) <ОЬ> Е151 <101.> ~ 5. Е)зг11ет — > <1.!> Рос — з К)Еоьйет Есп б.
ЕИ1 Рис 5.13. Части грамматики НТМЕ На рис. 5.13 представлена КС-грамматика, которая описывает часть структуры языка НТМЬ, рассмотренную нами в примерах. В строке 1 подразумевается, что символами когут быть "а", "А" или многие другие символы из набора НТМЬ. Строка 2 с использомяием двух продукций гласит, что Тех1 может быть либо пустой цепочкой, либо любым допустимым символом с текстом, следующим за ним. Иными словами, Тгхг есть последовательность символов, возможно, пустая. Заметим, что символы < и > не являются допустимыми, хотя их можно представить последовательностями ь1с; и ьдс; соответственно. Таким образом, мы не сможем случайно вставить дескриптор в Тех1.
Строка 3 гласит, что документ является последовательностью из нуля или нескольких "элементов". Элемент, в свою очередь, согласно строке 4 есть либо текст, либо выделеняый документ, либо начало абзаца с документом, либо список. Мы также предполагаем, что существуют и другие продукции для элементов, соответствующие другим видам дескрипторов НТМЬ. Далее, в строке 5 мы находим, что элемент списка представляет собой дескриптор <Е1>, за которым следует произвольный документ, а строка 6 гласит, что список есть последовательность из нуля или нескольких элементов списка.
Для некоторых объектов НТМЬ мощность КС-грамматик не нужна; достаточно регулярных выражений. Например, строки 1 и 2 (см. рис. 5.13) просто говорят, что Техг представляет тот же язык, что и регулярное выражение 1а + А + ...) . Однако для некоторых объектов мощность КС-грамматик необходима. Например, каждая пара соответствующих друг другу дескрипторов, вроде <Е1ч> и <Ин>, подобна сбалансированным скобкам, которые, как мы уже знаем, нерегулярны. 5.3.4. Хл4Ь и определения типа документа Тот факт, что НТМ1. описывается грамматикой, сам по себе не является значительным. Практически все языки программирования можно описать соответствующими им КС-грамматиками, поэтому более удивительным было бы, если бы мы ие смогли описать 213 5.3.
ПРИЛОЖЕНИЯ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК НТМЬ. Однако если мы обратимся к другому важному языку описания документов, ХМ1. (еХгепз[йе Магкцр Ьапйцаае), то обнаружим, что КС-грамматики играют более сушественную роль как часть процесса использования этого языка. Цель ХМЬ состоит не в описании форматирования документа; это работа для НТМ1.. Вместо этого ХМ1. сзремится описать "семантику" текста. Например, текст наподобие "Кленовая ул., 12" выглядит как адрес, но является ли иму В ХМЬ дескрипторы окружали бы фразу, представляюшую адрес, например: <АРРЕ>Кленовая ул., 12</АРРА> Однако сразу не очевидно, что <АРРА> означает адрес дома.
Например„если бы документ говорил о распределении памяти, мы могли бы предполагать, что дескриптор <АРРА> ссылается на адрес в памяти. Ожидается, что стандарты описания различных типов дескрипторов и структур, которые могут находиться между парами таких дескрипторов, будут развиваться в различных сферах деятельности в виде определений типа документа (РТР— Росшпеп1-Туре Ребпй[оп).
РТР, по сушеству, является КС-грамматикой с собственной нотацией для описания переменных и продукций. Приведем простое РТР и представим некоторые средства, используемые в языке описания РТР. Язык РТР сам по себе имеет КС-грамматику, но не она интересует нас. Мы хотим увидеть, как КС-грамматики выражаются в этом языке. РТР имеет следующий вид. <!РОСТУРЕ имя-РТР [ список определений элементов 1> Определение элемента, в свою очередь, имеет вид <!ЕЬЕМЕНТ имя-элемента [описание эпемента1> Описания элементов являются, по существу, регулярными выражениями. Их базис образуется следующими выражениями. 1. Имена других элементов, отражающие тот факт, что элементы одного типа могут появляться внутри элементов другого типа, как в НТМЬ мы могли бы найти выделенный текст в списке.
2. Специальное выражение 1()рсРАтА, обозначаюшее любой текст, который не включает дескрипторы ХМЬ. Это выражение играет роль переменной Тех( в примере 5.22. Допустимы следующие знаки операций, 1. ~, обозначающий объединение, как в записи регулярных выражений, обсуждавшихся в разделе 3.3.1. 2. Запятая для обозначения конкатенации. 214 ГЛАВА б. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ 3. Три варианта знаков операции замыкания, как в разделе 3.3.1.
Знак * означает "нуль или несколько появлений", ь — "не менее одного появления", 2 — "нуль или одно появление Скобки могут группировать операторы и их аргументы; в их отсутствие действуют обычные приоритеты регулярных операций. Пример 5.23. Представим себе, что продавцы компьютеров собрались, чтобы создать общедоступный стандарт РТР для описания разнообразных ПК (персональных компьютеров), которыми они торгуют. Каждое описание ПК будет иметь номер модели и спецяфякацию ее свойств, например, обьем памяти, количество и размер дисков и т.д. На рвс. 5.14 представлено гипотетическое, весьма упрощенное РТР для ПК.
<)ООСТТРЕ Рсярес ( <! ЕЬЕМЕ))Т РСБ (РС*) > <!ЕЬЕМЕ))Т РС (МООЕЬ, РВ1СЕ, РВОСЕЯЯОВ, ВАМ, О1ЯК+)> <!ЕЬЕМЕМТ МОРЕЬ (~йРСОАТА)> <!Е),ЕМЕМТ РВ1СЕ (~()РСРАТА)> <!ЕЬЕМЕМТ РВОСЕББОВ (МА))Р, МООЕЬ, БРЕЕО)> <!ЕЬЕМЕМТ МАВР (ТФРСОАТА)> <!ЕЬЕМЕМТ МООЕЬ (~()РСОАТА)> <!ЕЬЕМЕ))Т ЯРЕЕО (~()РСОАТА)> <!ЕЬЕМЕ))Т ВАМ (ТФРСРАТА)> <!ЕЬЕМЕМТ О1БК (НАВОО1БК ) СО ) ОЧО)> <!ЕЬЕМЕМТ НАВООТЯК (МА))Р, МООЕЬ, Б12Е)> <!ЕЬЕМЕНТ Я12Е (~()РСОАТА)> <!ЕЬЕМЕ))Т СО ('ЯРЕЕО)> <! ЕЬЕМЕ))Т ОЧО (БРЕЕР) > Рис.
5. ) 4. РТР дяя персональны компьютеров Именем РТР является РсЯрес. РСБ (список спецификаций) является первым эленентом, аналогичным стартовому символу КС-грамматики. Его определение, РС*, гласят, что РСЯ вЂ” это нуль или несколько элементов РС (ПК). Далее мы видим определение элемента РС. Оно состоит из конкатенации пяти комцонентов. Первые четыре — это другие элементы, соответствующие модели (МООЕЬ), цене (РВ1СЕ), типу процессора (РВОСЕБЯОВ) и памяти (ВАМ). Каждый из них должен появляться один раз в указанном порядке, поскольку запятая обозначает конкатенацию.
Последний компонент, ОТБКь, говорит, что у ПК будет один или несколько дисководов. Многие компоненты представляют собой просто текст; к этому типу относятся НО))ЕЬ, РВ1СЕ Н ВАМ. Однако РВОСЕЯЯОВ имеет структуру. Из его определения видно, что он состоит из названия производителя (щапцГасшгег, мАМР), модели и скорости (БРЕЯ))), в указанном порядке. Каждый из этих элементов является простым текстом.
5.д. ПРИЛОЖЕНИЯ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК 215 Элемент 01ЯК наиболее сложен. Во-первых, диск — это либо жесткий диск (МАЕРР1як), либо сР, либо Рз/Р, что указано в правиле для элемента 01як операциями "логического или". Жесткие диски, в свою очередь, имеют структуру, в которой определяются производитель (мАьгР), модель (мОРеР) и размер (Я12е), тогда как сР и Рт/Р представлены только их скоростью. На рис.5.15 показан пример ХМ1.-документа, соответствующего определению на рис. 5.14. Заметим, что каждый элемент представлен в документе дескриптором с именем элемента и парным дескриптором в конце с дополнительной чертой Т', как и в НТМ1..
Таким образом, на внешнем уровне (см. рис. 5.15) виден дескригпор <РСБ>...</РСЯ>. Между этими дескрипторами появляется список элементов, по одному на каждый продаваемый ПК; только один из этих списков показан полностью. В пределах представленного входа <РС> мы видим, что модель имеет номер 4560, цена ее 52295, и она имеет процессор !и!е! Реп!таю 800МНж Она также имеет 256МЬ памяти, жесткий диск 30.5ОЬ Мах!ог !)!ашопб и читающее устройство 32х СР-КОМ. Важно не то, что мы можем распознать все эти сведения, а то, чтобы читать и правильно интерпретировать числа и имена (см.
рис. 5.!5) этого документа могла программа под управлением !ЗТВ (см. рис. 5.14), которое должно быть ею прочитано вначале. П <РСЯ> <РС> <МОРЕЕ>4560</МОРЕН> <РК1СЕ>Б2295</РИ1СЕ> <РКОСЕЯЯОК> <МАЕР>1пСе1</МАЕР> <МОРЕЕ>Репг1пт</МОРЕЕ> <БРЕЕР>800жЬЕ</ЯРЕЕР> </РКОСЕЯЯОК> <НАМ>256</НАМ> <01БК><НАКРР1ЯК> <МАВР>Махсог</МАЕР> <МОРЕЕ>РЕатопс)</МОРЕЕ> <Я12Е>30.5ОЬ</Я12Е> </НАКРР1ЯК></01ЯК> <01ЯК><СР> <ЯРЕЕР>32х</ЯРЕЕР> </СР></Р1БК> </РС> <РС> </РС> </РСЯ> Рос. 5)5 Часть докучента, удовеетворяюо1ая структуре РТР (ст.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
