dzhon_khopkroft_radzhiv_motvani_dzheffri _ulman_vvedenie_v_teoriyu_avtomatov_yazy kov_i_vychisleniy_2008 (852747), страница 48
Текст из файла (страница 48)
5.2, более типична для структуры арифметических выражений, хотя тамиспользованы всего два оператора, сложения и умножения, и включена детальная структура идентификаторов, которая, вероятней всего, обрабатывалась бы лексическим анали208Стр. 208ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈзатором компилятора, как мы упоминали в разделе 3.3.2. Однако язык, представленныйна рис. 5.2, также нерегулярен.
Например, в соответствии с этой грамматикой, (na)n является правильным выражением. Мы можем использовать лемму о накачке для того, чтобыпоказать, что если бы язык был регулярным, то цепочка с некоторыми удаленными левыми скобками, символом a и всеми нетронутыми правыми скобками также была быправильным выражением, что неверно.Многие объекты типичного языка программирования ведут себя подобно сбалансированным скобкам. Обычно это сами скобки в выражениях всех типов, а также начала и окончанияблоков кода, например, слова begin и end в языке Pascal, или фигурные скобки { и } в C.Таким образом, любое появление фигурных скобок в C-программе должно образовывать сбалансированную последовательность с { в качестве левой скобки и } — правой.Есть еще один способ балансирования “скобок”, отличающийся тем, что левые скобки могут быть несбалансированны, т.е. не иметь соответствующих правых.
Примеромявляется обработка if и else в C. Произвольная if-часть может быть как сбалансирована, так и не сбалансирована некоторой else-частью. Грамматика, порождающая возможные последовательности слов if и else, представленных i и e соответственно, имеет следующие продукции.S → ε | SS | iS | iSeSНапример, ieie, iie и iei являются возможными последовательностями слов if иelse, и каждая из этих цепочек порождается данной грамматикой. Примерами неправильных последовательностей, не порождаемых грамматикой, являются ei и ieeii.Простая проверка (доказательство ее корректности оставляется в качестве упражнения)того, что последовательность символов i и e порождается грамматикой, состоит в рассмотрении каждого e по очереди слева направо.
Найдем первое i слева от рассматриваемого e.Если его нет, цепочка не проходит проверку и не принадлежит языку. Если такое i есть,вычеркнем его и рассматриваемое e. Затем, если больше нет символов e, цепочка проходитпроверку и принадлежит языку. Если символы e еще есть, то проверка продолжается.Пример 5.20. Рассмотрим цепочку iee. Первое e соответствует i слева от него. Обаудаляются. Оставшееся e не имеет i слева, и проверка не пройдена; слово iee не принадлежит языку. Отметим, что это заключение правильно, поскольку в C-программе словelse не может быть больше, чем if.В качестве еще одного примера рассмотрим iieie.
Соответствие первого e и i слева отнего оставляет цепочку iie. Соответствие оставшегося e и i слева оставляет i. Символов eбольше нет, и проверка пройдена. Это заключение также очевидно, поскольку последовательность iieie соответствует C-программе, структура которой подобна приведенной нарис. 5.10.
В действительности, алгоритм проверки соответствия (и компилятор C) говорит нам также, какое именно if совпадает с каждым данным else. Это знание существенно, если компилятор должен создавать логику потока управления, подразумеваемуюпрограммистом. 5.3. ÏÐÈËÎÆÅÍÈß ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр. 209209if (Условие) {...if (Условие) Инструкция;else Инструкция;...if (Условие) Инструкция;else Инструкция;...}Рис. 5.10.
Структура if-else; два слова else соответствуют предыдущим if,а первое if несбалансированно5.3.2. Ãåíåðàòîð ñèíòàêñè÷åñêèõ àíàëèçàòîðîâ YACCГенерация синтаксического анализатора (функция, создающая деревья разбора по исходным программам) воплощена в программе YACC, реализованной во всех системахUNIX. На вход YACC подается КС-грамматика, запись которой отличается от используемой здесь только некоторыми деталями. С каждой продукцией связывается действие(action), представляющее собой фрагмент С-кода, который выполняется всякий раз, когда создается узел дерева разбора, соответствующий (вместе со своими сыновьями) этойпродукции.
Обычно действием является код для построения этого узла, хотя в некоторыхприложениях YACC дерево разбора не создается, и действие задает что-то другое, например, выдачу порции объектного кода.Пример 5.21. На рис. 5.11 показан пример КС-грамматики в нотации YACC. Грамматикасовпадает с приведенной на рис. 5.2. Мы опустили действия, показав лишь их (требуемые нотацией) фигурные скобки и расположение во входной последовательности YACC.ExpId: Id| Exp ’+’ Exp{...}{...}| Exp ’*’ Exp{...}| ’(’ Exp ’)’;: ’a’’b’{...}| Id ’a’{...}{...}{...}| Id ’b’{...}| Id ’0’{...}| Id ’1’;{...}Рис.
5.11. Пример грамматики в нотации YACC210Стр. 210ÃËÀÂÀ 5. ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÅ ÃÐÀÌÌÀÒÈÊÈ È ßÇÛÊÈОтметим следующие соответствия между нотацией YACC и нашими грамматиками.• Двоеточие используется в качестве символа продукции →.• Все продукции с данной головой группируются вместе, и их тела разделены вертикальной чертой.• Список тел для данной головы заканчивается точкой с запятой. Завершающийсимвол не используется.• Терминалы записываются в апострофах. Некоторые буквы могут появляться водиночных апострофах. Хотя у нас они не показаны, YACC позволяет пользователю определять также и символические терминалы. Появление таких терминалов в исходной программе обнаруживает лексический анализатор и сигнализирует об этом синтаксическому анализатору через свое возвращаемое значение.• Цепочки символов и цифр, не взятые в апострофы, являются именами переменных. Мы воспользовались этой возможностью для того, чтобы дать нашимпеременным более выразительные имена — Exp и Id, хотя можно было использовать E и I.5.3.3.
ßçûêè îïèñàíèÿ äîêóìåíòîâРассмотрим семейство “языков”, которые называются языками описания документов(markup languages). “Цепочками” этих языков являются документы с определеннымиметками, которые называются дескрипторами (tags). Дескрипторы говорят о семантикеразличных цепочек внутри документа.Читатель, возможно, знаком с таким языком описания документов, как HTML(HyperText Markup Language). Этот язык имеет две основные функции: создание связеймежду документами и описание формата (“вида”) документа. Мы дадим лишь упрощенный взгляд на структуру HTML, но следующие примеры должны показать его структуруи способ использования КС-грамматики как для описания правильных HTMLдокументов, так и для управления обработкой документа, т.е.
его отображением на мониторе или принтере.Пример 5.22. На рис. 5.12, а показан текст, содержащий список пунктов, а нарис. 5.12, б — его выражение в HTML. На рис. 5.12, б, показано что HTML состоит изобычного текста, перемежаемого дескрипторами. Соответствующие друг другу, т.е. парные дескрипторы имеют вид <x> и </x> для некоторой цепочки x.3 Например, мы видимпарные дескрипторы <EM> и </EM>, которые сигнализируют, что текст между нимидолжен быть выделен, т.е.
напечатан курсивом или другим подходящим шрифтом. Мы3Иногда введение признака <x> несет в себе больше информации, чем просто имя x для признака. Однако мы не рассматриваем в примерах эту возможность.5.3. ÏÐÈËÎÆÅÍÈß ÊÎÍÒÅÊÑÒÍÎ-ÑÂÎÁÎÄÍÛÕ ÃÐÀÌÌÀÒÈÊСтр.
211211видим также парные дескрипторы <OL> и </OL>, указывающие на упорядоченный список, т.е. на нумерацию элементов списка.Вещи, которые я ненавижу.1.Заплесневелый хлеб.2.Людей, которые ведут машину по узкой дороге слишком медленно.а) видимый текст<P>Вещи, которые я <EM>ненавижу</EM>:<OL><LI>Заплесневелый хлеб.<LI>Людей, которые ведут машину по узкой дороге слишком медленно.</OL>б) исходный HTML-текстРис.
5.12. HTML-документ и его видимая версияМы видим также два примера непарных дескрипторов: <P> и <LI>, которые вводятабзацы и элементы списка, соответственно. HTML допускает, а в действительности поощряет, чтобы эти дескрипторы сопровождались парными им </P> и </LI> на концахабзацев и списков, однако не требует этого.
Поэтому эти парные дескрипторы не рассматриваются, что обеспечивает некоторую сложность нашей HTML-грамматике, развиваемой далее. Существует много классов цепочек, связанных с HTML-документом. Мы не будемстремиться перечислить их все, а представим только существенные для понимания текстов, подобных приведенному в примере 5.22. Для каждого класса мы введем переменную с содержательным именем.1.Text (текст) — это произвольная цепочка символов, которая может быть проинтерпретирована буквально, т.е. не имеющая дескрипторов. Примером элемента-текстаслужит “Заплесневелый хлеб” (см.
рис. 5.12).2.Char (символ) — цепочка, состоящая из одиночного символа, допустимого в HTMLтексте. Заметим, что пробелы рассматриваются как символы.3.Doc (документ) представляет документы, которые являются последовательностями“элементов”. Мы определим элементы следующими, и это определение будет взаимно рекурсивным с определением класса Doc.4.Element (элемент) — это или цепочка типа Text, или пара соответствующих другдругу дескрипторов и документ между ними, или непарный дескриптор, за которымследует документ.5.ListItem (элемент списка) есть дескриптор <LI> со следующим за ним документом,который представляет собой одиночный элемент списка.212Стр. 212ÃËÀÂÀ 5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
