dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 49
Текст из файла (страница 49)
ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈ6.List (список) есть последовательность из нуля или нескольких элементов списка.1.Char→a|A|…2.Text→ε | Char Text3.Doc→ε | Element Doc4.Element→Text |<EM> Doc </EM> |<P> Doc |<OL> List </OL> |…5.ListItem→<LI> Doc6.List→ε | ListItem ListРис. 5.13. Часть грамматики HTMLНа рис. 5.13 представлена КС-грамматика, которая описывает часть структуры языкаHTML, рассмотренную нами в примерах. В строке 1 подразумевается, что символамимогут быть “a”, “A” или многие другие символы из набора HTML. Строка 2 с использованием двух продукций гласит, что Text может быть либо пустой цепочкой, либо любымдопустимым символом с текстом, следующим за ним.
Иными словами, Text есть последовательность символов, возможно, пустая. Заметим, что символы < и > не являются допустимыми, хотя их можно представить последовательностями < и > соответственно. Таким образом, мы не сможем случайно вставить дескриптор в Text.Строка 3 гласит, что документ является последовательностью из нуля или нескольких“элементов”. Элемент, в свою очередь, согласно строке 4 есть либо текст, либо выделенный документ, либо начало абзаца с документом, либо список. Мы также предполагаем,что существуют и другие продукции для элементов, соответствующие другим видам дескрипторов HTML. Далее, в строке 5 мы находим, что элемент списка представляет собой дескриптор <LI>, за которым следует произвольный документ, а строка 6 гласит,что список есть последовательность из нуля или нескольких элементов списка.Для некоторых объектов HTML мощность КС-грамматик не нужна; достаточно регулярных выражений.
Например, строки 1 и 2 (см. рис. 5.13) просто говорят, что Text представляет тот же язык, что и регулярное выражение (a + A + …)*. Однако для некоторыхобъектов мощность КС-грамматик необходима. Например, каждая пара соответствующих друг другу дескрипторов, вроде <EM> и </EM>, подобна сбалансированным скобкам, которые, как мы уже знаем, нерегулярны.5.3.4.
XML è îïðåäåëåíèÿ òèïà äîêóìåíòàТот факт, что HTML описывается грамматикой, сам по себе не является значительным. Практически все языки программирования можно описать соответствующими имКС-грамматиками, поэтому более удивительным было бы, если бы мы не смогли описать5.3. ÏÐÈËÎÆÅÍÈß ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр. 213213HTML. Однако если мы обратимся к другому важному языку описания документов,XML (eXtensible Markup Language), то обнаружим, что КС-грамматики играют более существенную роль как часть процесса использования этого языка.Цель XML состоит не в описании форматирования документа; это работа для HTML.Вместо этого XML стремится описать “семантику” текста.
Например, текст наподобие“Кленовая ул., 12” выглядит как адрес, но является ли им? В XML дескрипторы окружали бы фразу, представляющую адрес, например:<ADDR>Кленовая ул., 12</ADDR>Однако сразу не очевидно, что <ADDR> означает адрес дома. Например, если бы документ говорил о распределении памяти, мы могли бы предполагать, что дескриптор<ADDR> ссылается на адрес в памяти. Ожидается, что стандарты описания различныхтипов дескрипторов и структур, которые могут находиться между парами таких дескрипторов, будут развиваться в различных сферах деятельности в виде определений типа документа (DTD — Document-Type Definition).DTD, по существу, является КС-грамматикой с собственной нотацией для описанияпеременных и продукций.
Приведем простое DTD и представим некоторые средства, используемые в языке описания DTD. Язык DTD сам по себе имеет КС-грамматику, но неона интересует нас. Мы хотим увидеть, как КС-грамматики выражаются в этом языке.DTD имеет следующий вид.<!DOCTYPE имя-DTD [список определений элементов]>Определение элемента, в свою очередь, имеет вид<!ELEMENT имя-элемента (описание элемента)>Описания элементов являются, по существу, регулярными выражениями.
Их базис образуется следующими выражениями.1.Имена других элементов, отражающие тот факт, что элементы одного типа могутпоявляться внутри элементов другого типа, как в HTML мы могли бы найти выделенный текст в списке.2.Специальное выражение \#PCDATA, обозначающее любой текст, который невключает дескрипторы XML. Это выражение играет роль переменной Text в примере 5.22.Допустимы следующие знаки операций.1.|, обозначающий объединение, как в записи регулярных выражений, обсуждавшихсяв разделе 3.3.1.2.Запятая для обозначения конкатенации.214Стр. 214ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈ3.Три варианта знаков операции замыкания, как в разделе 3.3.1.
Знак * означает “нульили несколько появлений”, + — “не менее одного появления”, ? — “нуль или однопоявление”.Скобки могут группировать операторы и их аргументы; в их отсутствие действуютобычные приоритеты регулярных операций.Пример 5.23. Представим себе, что продавцы компьютеров собрались, чтобы создатьобщедоступный стандарт DTD для описания разнообразных ПК (персональных компьютеров), которыми они торгуют.
Каждое описание ПК будет иметь номер модели и спецификацию ее свойств, например, объем памяти, количество и размер дисков и т.д. Нарис. 5.14 представлено гипотетическое, весьма упрощенное DTD для ПК.<!DOCTYPE PcSpec [<!ELEMENT PCS (PC*)><!ELEMENT PC (MODEL, PRICE, PROCESSOR, RAM, DISK+)><!ELEMENT MODEL (\#PCDATA)><!ELEMENT PRICE (\#PCDATA)><!ELEMENT PROCESSOR (MANF, MODEL, SPEED)><!ELEMENT MANF (\#PCDATA)><!ELEMENT MODEL (\#PCDATA)><!ELEMENT SPEED (\#PCDATA)><!ELEMENT RAM (\#PCDATA)><!ELEMENT DISK (HARDDISK | CD | DVD)><!ELEMENT HARDDISK (MANF, MODEL, SIZE)><!ELEMENT SIZE (\#PCDATA)><!ELEMENT CD (SPEED)><!ELEMENT DVD (SPEED)>]>Рис.
5.14. DTD для персональных компьютеровИменем DTD является PcSpec. PCS (список спецификаций) является первым элементом, аналогичным стартовому символу КС-грамматики. Его определение, PC*, гласит, что PCS — это нуль или несколько элементов PC (ПК).Далее мы видим определение элемента PC. Оно состоит из конкатенации пяти компонентов.
Первые четыре — это другие элементы, соответствующие модели (MODEL),цене (PRICE), типу процессора (PROCESSOR) и памяти (RAM). Каждый из них долженпоявляться один раз в указанном порядке, поскольку запятая обозначает конкатенацию.Последний компонент, DISK+, говорит, что у ПК будет один или несколько дисководов.Многие компоненты представляют собой просто текст; к этому типу относятсяMODEL, PRICE и RAM. Однако PROCESSOR имеет структуру. Из его определения видно,что он состоит из названия производителя (manufacturer, MANF), модели и скорости(SPEED), в указанном порядке.
Каждый из этих элементов является простым текстом.5.3. ÏÐÈËÎÆÅÍÈß ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр. 215215Элемент DISK наиболее сложен. Во-первых, диск — это либо жесткий диск(HARDDISK), либо CD, либо DVD, что указано в правиле для элемента DISK операциями“логического или”. Жесткие диски, в свою очередь, имеют структуру, в которой определяются производитель (MANF), модель (MODEL) и размер (SIZE), тогда как CD и DVDпредставлены только их скоростью.На рис. 5.15 показан пример XML-документа, соответствующего определению нарис. 5.14.
Заметим, что каждый элемент представлен в документе дескриптором с именемэлемента и парным дескриптором в конце с дополнительной чертой “/”, как и в HTML. Таким образом, на внешнем уровне (см. рис. 5.15) виден дескриптор <PCS>...</PCS>.Между этими дескрипторами появляется список элементов, по одному на каждый продаваемый ПК; только один из этих списков показан полностью.В пределах представленного входа <PC> мы видим, что модель имеет номер 4560,цена ее $2295, и она имеет процессор Intel Pentium 800MHz. Она также имеет 256Mb памяти, жесткий диск 30.5Gb Maxtor Diamond и читающее устройство 32x CD-ROM.
Важно не то, что мы можем распознать все эти сведения, а то, чтобы читать и правильно интерпретировать числа и имена (см. рис. 5.15) этого документа могла программа подуправлением DTD (см. рис. 5.14), которое должно быть ею прочитано вначале.
<PCS><PC><MODEL>4560</MODEL><PRICE>$2295</PRICE><PROCESSOR><MANF>Intel</MANF><MODEL>Pentium</MODEL><SPEED>800mhZ</SPEED></PROCESSOR><RAM>256</RAM><DISK><HARDDISK><MANF>Maxtor</MANF><MODEL>Diamond</MODEL><SIZE>30.5Gb</SIZE></HARDDISK></DISK><DISK><CD><SPEED>32x</SPEED></CD></DISK></PC><PC>...</PC></PCS>Рис.
5.15. Часть документа, удовлетворяющая структуре DTD (см. рис. 5.14)216Стр. 216ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈВозможно, читатель заметил, что правила для элементов в DTD (см. рис. 5.14) неполностью совпадают с продукциями в КС-грамматиках. Многие правила имеют корректный вид, например, правило<!ELEMENT PROCESSOR (MANF, MODEL, SPEED)>аналогично продукцииProcessor → Manf Model Speed.Однако в правиле<!ELEMENT DISK (HARDDISK | CD | DVD)>определение для DISK не похоже на тело продукции. Расширение в этом случае являетсяпростым: это правило можно интерпретировать как три продукции, у которых вертикальная черта играет ту же роль, что и в продукциях обычного вида.
Таким образом, этоправило эквивалентно следующим трем продукциям.Disk → Harddisk | Cd | DvdТруднее всего следующее правило.<!ELEMENT PC (MODEL, PRICE, PROCESSOR, RAM, DISK+)>Здесь “тело” содержит оператор замыкания. Решение состоит в замене DISK+ новой переменной, скажем, Disks, которая порождает с помощью пары продукций один или несколькоэкземпляров переменной Disk. Итак, мы получаем следующие эквивалентные продукции.Pc → Model Price Processor Ram DisksDisks → Disk | Disk DisksСуществует общая техника преобразования КС-грамматики с регулярными выражениями в качестве тела продукций в обычные КС-грамматики. Идею этого преобразования опишем неформально; возможно, читатель захочет уточнить как смысл КСграмматик с регулярными выражениями, так и доказательство того, что такое расширение не приводит к порождению языков, не являющихся КС-языками. Мы покажем, какпродукция с регулярным выражением в качестве тела преобразуется в совокупностьобычных продукций.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
