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

В пределах представленного входа <РС> мы видим, что модель имеет номер 4560, цена ее $2295, и она имеет процессор Intel Pentium 800MHz. Она также имеет 256Mb па­мяти, жесткий диск 30.5Gb Maxtor Diamond и читающее устройство 32х CD-ROM. Важ­но не то, что мы можем распознать все эти сведения, а то, чтобы читать и правильно ин­терпретировать числа и имена (см. рис. 5.15) этого документа могла программа под управлением DTD (см. рис. 5.14), которое должно быть ею прочитано вначале. □ <PCS> <РС>

<MODEL>4 5 6C)</MODEL> <PRICE>$22 95</PRICE> <PROCESSOR>

<MANF>Intel</MANF> <MODEL>Pentium</MODEL> <SPEED>8 00mhZ</SPEED> </PROCESSOR> <RAM>256</RAM> <DISK><HARDDISK>

<MANF>Maxtor</MANF> <MODEL>Diamond</MODEL> <SIZE>30.5Gb</SIZE> </HARDDISKX/DISK> <DISK><CD>

<SPEED>32x</SPEED> </CD></DISK> </PC> <PC>

</ PC-> </PCS>

Рис. 5.15. Часть документа, удовлетворяющая структуре DTD (см. рис. 5.14)

Возможно, читатель заметил, что правила для элементов в 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. Итак, мы получаем следующие эквивалентные продукции.

Рс —> Model Price Processor Ram Disks Disks -» Disk \ Disk Disks Существует общая техника преобразования КС-грамматики с регулярными выраже­ниями в качестве тела продукций в обычные КС-грамматики. Идею этого преобразова­ния опишем неформально; возможно, читатель захочет уточнить как смысл КС - грамматик с регулярными выражениями, так и доказательство того, что такое расшире­ние не приводит к порождению языков, не являющихся КС-языками. Мы покажем, как продукция с регулярным выражением в качестве тела преобразуется в совокупность обычных продукций. Для этого применим индукцию по размеру выражения в теле.

Базис. Если тело представляет собой конкатенацию элементов, то продукция уже имеет допустимый в КС-грамматиках вид, поэтому преобразовывать нечего. Индукция. В зависимости от старшего оператора возможны пять ситуаций.

1. При конкатенации продукция имеет вид А —> Еи Е2, где Е, и Е2 — выражения, до­пустимые в языке DTD. Введем две переменные, В и С, не используемые больше ни­где. Заменим А —> Е,, Е2:

А ВС ■ В->Е, С ->Е2

Первая продукция, А —> ВС, допустима в КС-грамматиках. Две последние могут быть как допустимыми, так и недопустимыми. Однако их тела короче, чем тело исходной продук­ции, поэтому на основании индукции их можно преобразовать в форму КС-грамматик.

Для оператора объединения продукция имеет вид А —> Е, | Е2. Заменим ее следую­щей парой продукций.

А->Е,

А-+Е2

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

Продукция имеет вид А —> ()*. Введем новую переменную В, не используемую больше нигде, и заменим продукцию следующими тремя.

А—>ВА А -> Ј В->Е,

Для продукции А —> (Е/У вводим новую переменную В, не используемую больше нигде, и заменяем продукцию следующими тремя.

А-^ВА А В В Ei

Продукция имеет вид А —> (Е,)1. Заменим ее:

А -> Ј А-+Е,

Пример 5.24. Рассмотрим преобразование DTD-правила

<!ELEMENT PC (MODEL, PRICE, PROCESSOR, RAM, DISK+)>

в обычные для КС-грамматик продукции. Тело этого правила рассмотрим как конкате­нацию двух выражений, первое из которых есть MODEL, PRICE, PROCESSOR, RAM, а второе— DISK+. Создав для этих подвыражений переменные А и В, соответственно, используем следующие продукции.

Рс —> АВ

А —> Model Price Processor Ram В Disk+

Только последняя не имеет нужного вида. Введем еще одну переменную С и сле­дующие продукции.

В С В | С С -> Disk

В данном частном случае переменные А и С в действительности не нужны, поскольку выражение, порождаемое из А, есть просто конкатенация переменных, a Disk — одиночная переменная. Вместо приведенных продукций можно было бы использовать следующие.

Рс —> Model Price Processor Ram В В -> Disk В | Disk

□

5.3.5. Упражнения к разделу 5.3

Докажите, что если цепочка скобок сбалансирована (как в примере 5.19), то она порождается грамматикой В —> ВВ | (В) | е. Указание. Проведите индукцию по длине цепочки. Рассмотрим множество всех цепочек сбалансированных скобок двух типов, круглых и квадратных. Следующий пример показывает их происхождение. Если взять выражения в языке С, которые используют круглые скобки для группиро­вания и для вызовов функций и квадратные скобки для индексов массивов, и удалить из них все, кроме скобок, то получим цепочки сбалансированных ско­бок этих двух типов. Например,

f (a[i]* (b[i] [j]+c[g(x) ] ) ,d[i] )

превращается в сбалансированную цепочку ( [ ] ( [ ] [ ] [ () ] ) [ ] ). Построить грамматику для всех сбалансированных цепочек из круглых и квадратных ско­бок, и только для них.

В разделе 5.3 рассматривалась грамматика S —> е \ SS | iS \ iSeS и утверждалось, что принадлежность цепочки w языку L этой грамматики можно проверить пу­тем повторения следующих действий, начиная с w. Если текущая цепочка начинается с е, то проверка не пройдена; w g L. Если текущая цепочка не содержит е, то проверка пройдена; we L. В противном случае удалить первое е и / непосредственно слева от него. Повторить эти три шага с полученной цепочкой.

Докажите, что этот процесс правильно распознает цепочки языка L.

Добавьте к грамматике HTML (см. рис. 5.13) следующие формы:

а)        (*) элемент списка должен заканчиваться закрывающим дескриптором </LI>;

б)        элемент может быть как неупорядоченным, так и упорядоченным списком. Не­упорядоченные списки заключаются в парные дескрипторы <UL> и </UL>;

в)        (!) элемент может быть таблицей, которая заключается в парные дескрипто­ры <TABLE> и </TABLE>. Между ними находятся одна или несколько це­почек, каждая из которых заключается в <TR> и </TR>. Первая цепочка яв­

ляется заголовком с одним или несколькими полями, каждое из которых на­чинается дескриптором <ТН> (будем предполагать, что эти дескрипторы не закрываются, хотя в действительности они парные). Поля в следующих це­почках начинаются дескриптором <TD>.

< < < < <

]>

< ! DOCTYPE CourseS^c[

ELEMENT COURSES (COURSE+)>

ELEMENT COURSE (CNAME, PROF, STUDENT*, TA?)> ELEMENT CNAME (\#PCDATA)> ELEMENT STUDENT (\#PCDATA)> ELEMENT ТА (\#PCDATA)>

Рис. 5.16. DTD для курсов 5.3.5. Преобразуйте DTD (рис. 5.16) в КС-грамматику.

5.4. Неоднозначность в грамматиках и языках

Как мы увидели, в приложениях КС-грамматики часто служат основой для обеспече­ния структуры различного рода файлов. Например, в разделе 5.3 грамматики использо­вались для придания структуры программам и документам. Там действовало неявное предположение, что грамматика однозначно определяет структуру каждой цепочки сво­его языка. Однако мы увидим, что не каждая грамматика обеспечивает уникальность структуры.

Иногда, когда грамматика не может обеспечить уникальность структуры, ее можно преобразовать, чтобы структура была единственной для каждой цепочки. К сожалению, это возможно не всегда, т. е. существуют "существенно неоднозначные" языки; каждая грамматика для такого языка налагает несколько структур на некоторые его цепочки.

5.4.1. Неоднозначные грамматики

Вернемся к грамматике выражений (см. рис. 5.2). Эта грамматика дает возможность порождать выражения с любой последовательностью операторов + и *, а продукции Ј —> Е + Е \ Е* Е позволяют порождать эти выражения в произвольно выбранном порядке.

Пример 5.25. Рассмотрим выводимую цепочку Е + Е* Е. Она имеет два порожде­ния из Е:

1. Ј=>Ј + Ј=>Ј + Ј*Ј

2. Ј=>Ј*Ј=>Ј + Ј*Ј

Заметим, что в порождении 1 второе Е заменяется на Ј * Ј, тогда как в порождении 2 — первое Е на Е + Ј. На рис. 5.17 показаны два действительно различных дерева разбора.

"        *        Е        ^        +        с.

а)        б)

Рис. 5.17. Два дерева разбора с одной и той же кроной

Разница между этими двумя порождениями значительна. Когда рассматривается структура выражений, порождение 1 говорит, что второе и третье выражения перемно­жаются, и результат складывается с первым. Вместе с тем, порождение 2 задает сложе­ние первых двух выражений и умножение результата на третье. Более конкретно, первое порождение задает, что 1+2*3 группируется как 1 + (2 * 3) = 7, а второе — что группи­рование имеет вид (I + 2) * 3 = 9. Очевидно, что первое из них (но не второе) соответст­вует нашему понятию о правильном группировании арифметических выражений.

Поскольку грамматика, представленная на рис. 5.2, дает две различные структуры любой цепочке терминалов, порождаемой заменой трех выражений в Е + Е* Е иденти­фикаторами, для обеспечения уникальности структуры она не подходит. В частности, хо­тя она может давать цепочкам как арифметическим выражениям правильное группиро­вание, она также дает им и неправильное. Для того чтобы использовать грамматику вы­ражений в компиляторе, мы должны изменить ее, обеспечив только правильное группирование. □