dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 50
Текст из файла (страница 50)
Для этого применим индукцию по размеру выражения в теле.Базис. Если тело представляет собой конкатенацию элементов, то продукция ужеимеет допустимый в КС-грамматиках вид, поэтому преобразовывать нечего.Индукция. В зависимости от старшего оператора возможны пять ситуаций.1.При конкатенации продукция имеет вид A → E1, E2, где E1 и E2 — выражения, допустимые в языке DTD. Введем две переменные, B и C, не используемые больше нигде. Заменим A → E1, E2:A → BCB → E1C → E25.3.
ÏÐÈËÎÆÅÍÈß ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр. 217217Первая продукция, A → BC, допустима в КС-грамматиках. Две последние могут быть какдопустимыми, так и недопустимыми. Однако их тела короче, чем тело исходной продукции, поэтому на основании индукции их можно преобразовать в форму КС-грамматик.Для оператора объединения продукция имеет вид A → E1 | E2.
Заменим ее следующей парой продукций.2.A → E1A → E2Аналогично, эти продукции могут иметь недопустимый вид, но их тела короче,чем тело исходной. Применяем эти же правила рекурсивно и преобразуем их к виду КС-грамматик.Продукция имеет вид A → (E1)*. Введем новую переменную B, не используемуюбольше нигде, и заменим продукцию следующими тремя.3.A → BAA→εB → E1Для продукции A → (E1)+ вводим новую переменную B, не используемую большенигде, и заменяем продукцию следующими тремя.4.A → BAA→BB → E1Продукция имеет вид A → (E1)?. Заменим ее:5.A→εA → E1Пример 5.24. Рассмотрим преобразование DTD-правила<!ELEMENT PC (MODEL, PRICE, PROCESSOR, RAM, DISK+)>в обычные для КС-грамматик продукции.
Тело этого правила рассмотрим как конкатенацию двух выражений, первое из которых есть MODEL, PRICE, PROCESSOR, RAM,а второе — DISK+. Создав для этих подвыражений переменные A и B, соответственно,используем следующие продукции.Pc → ABA → Model Price Processor RamB → Disk+Только последняя не имеет нужного вида. Введем еще одну переменную C и следующие продукции.B → CB | CC → Disk218Стр. 218ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈВ данном частном случае переменные A и C в действительности не нужны, посколькувыражение, порождаемое из A, есть просто конкатенация переменных, а Disk — одиночнаяпеременная.
Вместо приведенных продукций можно было бы использовать следующие.Pc → Model Price Processor Ram BB → Disk B | Disk5.3.5. Óïðàæíåíèÿ ê ðàçäåëó 5.35.3.1.Докажите, что если цепочка скобок сбалансирована (как в примере 5.19), то онапорождается грамматикой B → BB | (B) | ε. Указание.
Проведите индукцию подлине цепочки.5.3.2.Рассмотрим множество всех цепочек сбалансированных скобок двух типов,круглых и квадратных. Следующий пример показывает их происхождение. Есливзять выражения в языке C, которые используют круглые скобки для группирования и для вызовов функций и квадратные скобки для индексов массивов, иудалить из них все, кроме скобок, то получим цепочки сбалансированных скобок этих двух типов. Например,f(a[i]*(b[i][j]+c[g(x)]),d[i])превращается в сбалансированную цепочку ([]([][][()])[]).
Построитьграмматику для всех сбалансированных цепочек из круглых и квадратных скобок, и только для них.5.3.3.В разделе 5.3 рассматривалась грамматика S → ε | SS | iS | iSeS и утверждалось,что принадлежность цепочки w языку L этой грамматики можно проверить путем повторения следующих действий, начиная с w.1.Если текущая цепочка начинается с e, то проверка не пройдена; w ∉ L.2.Если текущая цепочка не содержит e, то проверка пройдена; w ∈ L.3.В противном случае удалить первое e и i непосредственно слева от него. Повторитьэти три шага с полученной цепочкой.Докажите, что этот процесс правильно распознает цепочки языка L.5.3.4.
Добавьте к грамматике HTML (см. рис. 5.13) следующие формы:а) (∗) элемент списка должен заканчиваться закрывающим дескриптором </LI>;б) элемент может быть как неупорядоченным, так и упорядоченным списком. Неупорядоченные списки заключаются в парные дескрипторы <UL> и </UL>;в) (!) элемент может быть таблицей, которая заключается в парные дескрипторы <TABLE> и </TABLE>. Между ними находятся одна или несколько цепочек, каждая из которых заключается в <TR> и </TR>. Первая цепочка яв5.3.
ÏÐÈËÎÆÅÍÈß ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр. 219219ляется заголовком с одним или несколькими полями, каждое из которых начинается дескриптором <TH> (будем предполагать, что эти дескрипторы незакрываются, хотя в действительности они парные). Поля в следующих цепочках начинаются дескриптором <TD>.<!DOCTYPE CourseSpec[<!ELEMENT COURSES (COURSE+)><!ELEMENT COURSE (CNAME, PROF, STUDENT*, TA?)><!ELEMENT CNAME (\#PCDATA)><!ELEMENT STUDENT (\#PCDATA)><!ELEMENT TA (\#PCDATA)>]>Рис. 5.16.
DTD для курсов5.3.5.Преобразуйте DTD (рис. 5.16) в КС-грамматику.5.4. Íåîäíîçíà÷íîñòü â ãðàììàòèêàõ è ÿçûêàõКак мы увидели, в приложениях КС-грамматики часто служат основой для обеспечения структуры различного рода файлов. Например, в разделе 5.3 грамматики использовались для придания структуры программам и документам. Там действовало неявноепредположение, что грамматика однозначно определяет структуру каждой цепочки своего языка. Однако мы увидим, что не каждая грамматика обеспечивает уникальностьструктуры.Иногда, когда грамматика не может обеспечить уникальность структуры, ее можнопреобразовать, чтобы структура была единственной для каждой цепочки. К сожалению,это возможно не всегда, т.е.
существуют “существенно неоднозначные” языки; каждаяграмматика для такого языка налагает несколько структур на некоторые его цепочки.5.4.1. Íåîäíîçíà÷íûå ãðàììàòèêèВернемся к грамматике выражений (см. рис. 5.2). Эта грамматика дает возможностьпорождать выражения с любой последовательностью операторов + и *, а продукцииE → E + E | E * E позволяют порождать эти выражения в произвольно выбранном порядке.Пример 5.25. Рассмотрим выводимую цепочку E + E * E. Она имеет два порождения из E:1.E⇒E+E⇒E+E*E2.E⇒E*E⇒E+E*EЗаметим, что в порождении 1 второе E заменяется на E * E, тогда как в порождении 2 —первое E на E + E.
На рис. 5.17 показаны два действительно различных дерева разбора.220Стр. 220ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈ∗+∗+a)б)Рис. 5.17. Два дерева разбора с одной и той же кронойРазница между этими двумя порождениями значительна. Когда рассматриваетсяструктура выражений, порождение 1 говорит, что второе и третье выражения перемножаются, и результат складывается с первым. Вместе с тем, порождение 2 задает сложение первых двух выражений и умножение результата на третье.
Более конкретно, первоепорождение задает, что 1 + 2 * 3 группируется как 1 + (2 * 3) = 7, а второе — что группирование имеет вид (1 + 2) * 3 = 9. Очевидно, что первое из них (но не второе) соответствует нашему понятию о правильном группировании арифметических выражений.Поскольку грамматика, представленная на рис. 5.2, дает две различные структурылюбой цепочке терминалов, порождаемой заменой трех выражений в E + E * E идентификаторами, для обеспечения уникальности структуры она не подходит. В частности, хотя она может давать цепочкам как арифметическим выражениям правильное группирование, она также дает им и неправильное. Для того чтобы использовать грамматику выражений в компиляторе, мы должны изменить ее, обеспечив только правильноегруппирование.
С другой стороны, само по себе существование различных порождений цепочки (чтоне равносильно различным деревьям разбора) еще не означает порочности грамматики.Рассмотрим пример.Пример 5.26. Используя ту же грамматику выражений, мы находим, что цепочкаa + b имеет много разных порождений. Вот два из них.1.E⇒E+E⇒I+E⇒a+E⇒a+I⇒a+b2.E⇒E+E⇒E+I⇒I+I⇒I+b⇒a+bЗаметим, что настоящей разницы между структурами, заданными этими двумя порождениями, нет.
Каждая из них говорит, что a и b — идентификаторы, и что их значениянужно сложить. В действительности, оба эти порождения приводят к одному и тому жедереву разбора, если применяются конструкции теорем 5.18 и 5.12. Два примера, приведенные выше, показывают, что неоднозначность происходит не отмножественности порождений, а от существования двух и более деревьев разбора. Итак,мы говорим, что КС-грамматика G = (V, T, P, S) является неоднозначной, если найдетсяхотя бы одна цепочка w в T*, для которой существуют два разных дерева разбора, каждое5.4. ÍÅÎÄÍÎÇÍÀ×ÍÎÑÒÜ Â ÃÐÀÌÌÀÒÈÊÀÕ È ßÇÛÊÀÕСтр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
