Регулярные выражения и языки (стр. 27 )

Существует много классов цепочек, связанных с HTML-документом. Мы не будем стремиться перечислить их все, а представим только существенные для понимания тек­стов, подобных приведенному в примере 5.22. Для каждого класса мы введем перемен­ную с содержательным именем.

Text (текст) — это произвольная цепочка символов, которая может быть проинтер­претирована буквально, т. е. не имеющая дескрипторов. Примером элемента-текста служит "Заплесневелый хлеб" (см. рис. 5.12). Char (символ) — цепочка, состоящая из одиночного символа, допустимого в HTML - тексте. Заметим, что пробелы рассматриваются как символы. Doc (документ) представляет документы, которые являются последовательностями "элементов". Мы определим элементы следующими, и это определение будет вза­имно рекурсивным с определением класса Doc. Element (элемент) — это или цепочка типа Text, или пара соответствующих друг другу дескрипторов и документ между ними, или непарный дескриптор, за которым следует документ. Listltem (элемент списка) есть дескриптор <LI> со следующим за ним документом, который представляет собой одиночный элемент списка.

6. List (список) есть последовательность из нуля или нескольких элементов списка.

1.	Char	—>	a\A
2.	Text	—>	e \ Char Text
3.	Doc	—>	Ј | Element Doc
4.	Element	—>	Text I.

<ЕМ> Doc </ЕМ> | <Р> Doc | <OL> List </OL> |

Listltem        <LI> Doc List        —> e | Listltem List Рис. 5.13. Часть грамматики HTML

На рис. 5.13 представлена КС-грамматика, которая описывает часть структуры языка HTML, рассмотренную нами в примерах. В строке 1 подразумевается, что символами могут быть "а", "А" или многие другие символы из набора HTML. Строка 2 с использо­ванием двух продукций гласит, что Text может быть либо пустой цепочкой, либо любым допустимым символом с текстом, следующим за ним. Иными словами, Text есть после­довательность символов, возможно, пустая. Заметим, что символы < и > не являются до­пустимыми, хотя их можно представить последовательностями &lt; и &gt; соответст­венно. Таким образом, мы не сможем случайно вставить дескриптор в Text.

Строка 3 гласит, что документ является последовательностью из нуля или нескольких "элементов". Элемент, в свою очередь, согласно строке 4 есть либо текст, либо выделен­ный документ, либо начало абзаца с документом, либо список. Мы также предполагаем, что существуют и другие продукции для элементов, соответствующие другим видам де­скрипторов HTML. Далее, в строке 5 мы находим, что элемент списка представляет со­бой дескриптор <LI>, за которым следует произвольный документ, а строка 6 гласит, что список есть последовательность из нуля или нескольких элементов списка.

Для некоторых объектов HTML мощность КС-грамматик не нужна; достаточно регу­лярных выражений. Например, строки 1 и 2 (см. рис. 5.13) просто говорят, что Text пред­ставляет тот же язык, что и регулярное выражение (а + А + ...)*. Однако для некоторых объектов мощность КС-грамматик необходима. Например, каждая пара соответствую­щих друг другу дескрипторов, вроде <ЕМ> и </ЕМ>, подобна сбалансированным скоб­кам, которые, как мы уже знаем, нерегулярны.

5.3.4. XML и определения типа документа

Тот факт, что HTML описывается грамматикой, сам по себе не является значитель­ным. Практически все языки программирования можно описать соответствующими им КС-грамматиками, поэтому более удивительным было бы, если бы мы не смогли описать

HTML. Однако если мы обратимся к другому важному языку описания документов, XML (extensible Markup Language), то обнаружим, что КС-грамматики играют более су­щественную роль как часть процесса использования этого языка.

Цель XML состоит не в описании форматирования документа; это работа для HTML. Вместо этого XML стремится описать "семантику" текста. Например, текст наподобие "Кленовая ул., 12" выглядит как адрес, но является ли им? В XML дескрипторы окружа­ли бы фразу, представляющую адрес, например: <ADDR>KjieHOBafl ул., 12</ADDR>

Однако сразу не очевидно, что <ADDR> означает адрес дома. Например, если бы до­кумент говорил о распределении памяти, мы могли бы предполагать, что дескриптор <ADDR> ссылается на адрес в памяти. Ожидается, что стандарты описания различных типов дескрипторов и структур, которые могут находиться между парами таких дескрип­торов, будут развиваться в различных сферах деятельности в виде определений типа до­кумента (DTD — Document-Type Definition).

DTD, по существу, является КС-грамматикой с собственной нотацией для описания переменных и продукций. Приведем простое DTD и представим некоторые средства, ис­пользуемые в языке описания DTD. Язык DTD сам по себе имеет КС-грамматику, но не она интересует нас. Мы хотим увидеть, как КС-грамматики выражаются в этом языке.

DTD имеет следующий вид. <!DOCTYPE имя-DTD [

список определений элементов

]>

Определение элемента, в свою очередь, имеет вид

<! ELEMENT имя-элемента (описание элемента)>

Описания элементов являются, по существу, регулярными выражениями. Их базис обра­зуется следующими выражениями.

Имена других элементов, отражающие тот факт, что элементы одного типа могут появляться внутри элементов другого типа, как в HTML мы могли бы найти выде­ленный текст в списке. Специальное выражение \#PCDATA, обозначающее любой текст, который не включает дескрипторы XML. Это выражение играет роль переменной Text в при­мере 5.22.

Допустимы следующие знаки операций.

|, обозначающий объединение, как в записи регулярных выражений, обсуждавшихся в разделе 3.3.1. Запятая для обозначения конкатенации.

3. Три варианта знаков операции замыкания, как в разделе 3.3.1. Знак * означает "нуль или несколько появлений", + — "не менее одного появления", ? — "нуль или одно появление".

Скобки могут группировать операторы и их аргументы; в их отсутствие действуют обычные приоритеты регулярных операций.

]>

Пример 5.23. Представим себе, что продавцы компьютеров собрались, чтобы создать общедоступный стандарт DTD для описания разнообразных ПК (персональных компью­теров), которыми они торгуют. Каждое описание ПК будет иметь номер модели и спе­цификацию ее свойств, например, объем памяти, количество и размер дисков и т. д. На рис. 5.14 представлено гипотетическое, весьма упрощенное DTD для ПК.

<!DOCTYPE PcSpec [
<	ELEMENT	PCS (PC*)>
<	ELEMENT	PC (MODEL, PRICE, PROCESSOR, RAM,
<	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), в указанном порядке. Каждый из этих элементов является простым текстом.

Элемент DISK наиболее сложен. Во-первых, диск— это либо жесткий диск (HARDDISK), либо CD, либо DVD, что указано в правиле для элемента DISK операциями "логического или". Жесткие диски, в свою очередь, имеют структуру, в которой опреде­ляются производитель (MANF), модель (MODEL) и размер (SIZE), тогда как CD и DVD представлены только их скоростью.

На рис. 5.15 показан пример XML-документа, соответствующего определению на рис. 5.14. Заметим, что каждый элемент представлен в документе дескриптором с именем элемента и парным дескриптором в конце с дополнительной чертой "/", как и в HTML. Та­ким образом, на внешнем уровне (см. рис. 5.15) виден дескриптор <PCS>. . .</PCS>. Между этими дескрипторами появляется список элементов, по одному на каждый прода­ваемый ПК; только один из этих списков показан полностью.