Хопкрофт, Джон, Э., Мотвани, Раджив, Ульман, Джеффри, Д. - Введение в теорию автоматов, языков и вычислений (1082271), страница 48
Текст из файла (страница 48)
5.2, также нерегулярен. Например, в соответствии с этой грамматикой, ("а)" является правильным выражением, Мы можем использовать лемму о накачке для того, чтобы показать, что если бы язык был регулярным, то цепочка с некоторыми удаленными левыын скобками, символом а и всеми нетронутыми правыми скобками также была бы правильным выражением, что неверно. Многие объекты типичного языка программирования ведут себя подобно сбалансированпыы скобкам. Обычно это сами скобки в выражениях всех типов, а также начала и окончания бкоков кода, например, слова кэед1п и епск в языке Рааса(, или фш урные скобки ( и ) в С.
Таам образом, любое появление фигурных скобок в С-программе должно образовывать сбалшсированную последовательность с ( в качестве левой скобки и ) — правой. Есть еше один способ балансирования "скобок", отличающийся тем, что левые скобки могут быть несбалансированны, т.е. не иметь соответствующих правых. Примером является обработка 1х и е1ве в С. Произвольная 1х-часть может быть как сбалансироваа, так и не сбалансирована некоторой е1ве-частью. Грамматика, порождающая возможные последовательности слов 1х и е1ве, представленных Г и е соответственно, име- ет следующие продукции. о-ь п~йй~ ко ~!Яео Например, ~еке, йе и Ге) являются возможными последовательностями слов 1х и в1ве, н каждая из этих цепочек порождается данной грамматикой, Примерами неправипьных последовательностей, не порождаемых грамматикой, являются ек и Геегй Простая проверка (показательство ее корректности оставляется в качестве упражнения) тою, что последовательность символов ( и е порождается грамматикой, состоит в рассмотрении каждого е по очереди слева направо.
НаГшем первое! слева от рассматриваемого е. Если его нет, цепочка не проходит проверку и не принадлежит языку. Если такое к есть, вычеркнем его и рассматриваемое е. Затем, если больше нет символов е, цепочка проходит проверку и принадлежит языку. Если символы е еще есть, то проверка продолжается. Пример 5.20. Рассмотрим цепочку (ее. Первое е соответствует ) слева от него. Оба удакяются.
Оставшееся е не имеет к слева, и проверка не пройдена; слово (ее не принадлежит языку. Отметим, что это заключение правильно, поскольку в С-программе слов в1ае не может быть больше, чем 1х. В качестве еще одного примера рассмотрим йе(е. Соответствие первого е и ) слева от него оставляет цепочку йе. Соответствие оставшегося е и к слева оставляет 1 Символов е больше нет, и проверка пройдена.
Это заключение также очевидно, поскольку последовательность йе(е соответствует С-программе, структура которой подобна приведенной на рнс, 5.10. В действительности, алгоритм проверки соответствия (и компилятор С) говорит нам также, какое именно 1х совпадает с каждым данным е1ве. Это знание существенно, если компилятор должен создавать логику потока управления, подразумеваемую программистом. П 5.3, ПРИЛОЖЕНИЯ КОНТЕКСТНО-СВОБОДНЫХ ГРАММАТИК 209 (Условие) ( (Условие) Инструкция; е1ее Инструкция; 11 (Условие) Инструкция; е)зе Инструкция; Рис.
5.!О. Структура (бе(ве; два свова а1пе соответствуют предыдуи(им де а первое дк'песбалансировапно 5.3.2. Генератор синтаксических анализаторов тгАСС 1с) Ехр '+ ' Ехр Ехр '*' Ехр '(' Ехр ')' ( °,) ( ..) ( ° ° ° 1 (. ) 'а' ( ° ) (.. ) ( . ) (...1 (...) ( ° ° ) 1с( 'Ъ' 1с1 'а' ) 1с( Ъ ! 1с) '0' 1с( ' 1' Рис. 5. )!. Р!ример грамматики в потаяии УАСС ГЛАВА б.
КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ И ЯЗЫКИ 210 Генерация синтаксического анализатора (функция, создающая деревья разбора по исходным программам) воплощена в программе г'АСС, реализованной во всех системах ())((Х. На вход УАСС подается КС-грамматика, запись которой отличается от используемой здесь только некоторыми деталями. С каждой продукцией связывается действие (асйоп), представляющее собой фрагмент С-кода, который выполняется всякий раз, когда создается узел дерева разбора, соответствующий (вместе со своими сыновьями) этой продукции.
Обычно действием является код для построения этого узла, хотя в некоторых приложениях УАСС дерево разбора не создается, и действие задает что-то другое, например, выдачу порции объектного кода. Пример 5.21. На рис. 5.11 показан пример КС-грамматики в нотации УАСС. Грамматика совпадает с приведенной на рис. 5.2. Мы опустили действия, показав лишь их (требуемые нотацией) фигурные скобки и расположение во входной последовательности УАСС. Отметим следующие соответствия между нотацией т'АСС и нашими грамматиками. ° Двоеточие используется в качестве символа продукции э. ° Все продукции с данной головой группируются вместе, и их тела разделены вертикальной чертой. ° Список тел для данной головы заканчивается точкой с запятой. Завершающий символ не используется ° Терминалы записываются в апострофах.
Некоторые буквы могут появляться в одиночных апострофах. Хотя у нас они не показаны, т'АСС позволяет пользователю определять также и символические терминальь Появление таких терминалов в исходной программе обнаруживает лексический анализатор и сигнализирует об этом синтаксическому анализатору через свое возвращаемое значение. ° Цепочки символов и цифр, не взятые в апострофы, являются именами переменных.
Мы воспользовались этой возможностью для того, чтобы дать нашим переменным более выразительные имена — Ехр и 1<1, хотя можно было использовать Е и Е 5.3.3. Языки описания документов Рассмотрим семейство "языков", которые называются языками описания документов (шмкцр 1апяцадев), "Цепочками" этих языков являются документы с определенными метками, которые называются дескрипторами (гааз). Дескрипторы говорят о семантике различных цепочек внутри документа.
Читатель, возможно, знаком с таким языком описания документов, как НТМ1. (НурсгТехг МагЬцр Ьапяцаяе). Этот язык имеет две основные функции: создание связей между документами и описание формата ("вида'*) документа. Мы дадим лишь упрощенный взгляд на структуру НТМЬ, но следующие примеры должны показать его структуру и способ использования КС-грамматики как для описания правильных НТМЬ- документов, так и для управления обработкой документа, т.е. его отображением на мо- ннторе или принтере. Пример5.22.На рис.5.12,а показан текст, содержащий список пунктов, а на рвс. 5.12, б — его выражение в НТМ1.. На рис. 5.12, 6, показано что НТМЬ состоит из обычного текста, перемежаемого дескрипторами.
Соответствующие друг другу, т.е. парные дескрипторы имеют вид <х> и < х> для некоторой цепочки х.з Например, мы видим парные дескрипторы <ЕМ> и <!ЕМ>, которые сигнализируют, что текст между ними должен быть выделен, т.е. напечатан курсивом или другим подходящим шрифтом.
Мы ' Иногда введение признака <х> несет в себе больше информации, чем просто нмя х для призвака. Однако мы нс рассматриваем в примерах эту возможность. 211 5.3. ПРИЛОЖЕНИЯ КОНТЕКСТНО-СВОВОДНЫХ ГРАММАТИК вИдим также парные дескрипторы <ОЬ> и </ОЬ>, указывающие на упорядоченный спи- сок, т.е. на нумерацию элементов списка. Вещи, которые я неновизсу. 1.
Заплесневелый хлеб. 2. Людей, которые ведут машину по узкой дороге слишком медленно. о) видимый текст <Р>Вещи, которые я <ЕМ>ненавижу</ЕМ>: <ОЬ> <Ь|>Заплесневелый хлеб. <Ь|>Людей, которые ведут машину по узкой дороге слишком медленно. </ОЬ> б) исходный ИТМ1-текст Рис. 5.! 2 НТМ1-документ и его видиков версия Мы видим также два примера непарных дескрипторов: <Р> и <11>, которые вводят абзацы и элементы списка, соответственно. НТМ) допускает, а в действительности поощряет, чтобы эти дескрипторы сопровождались парными им </Р> и </Ь|> на концах абзацев и списков, однако не требует этого. Поэтому эти парные дескрипторы не рассматриваются, что обеспечивает некоторую сложность нашей НТМ1,-грамматике, развиваемой далее.
П Существует много классов цепочек, связанных с НТМЬ-документом. Мы не будем стремиться перечислить их все, а представим только существенные для понимания текстов, подобных приведенному в примере 5.22. Для каждого класса мы введем переменную с содержательным именем. 1. Техт (текст) — это произвольная цепочка символов, которая может быть проинтерпретирована буквально, т.е. не имеющая дескрипторов, Примером элемента-текста служит "Заплесневелый хлеб" (см. рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
