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

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

Приведенные выше неформальные доводы должны убедить нас, что G/,ai порождает только цепочки сбалансированных скобок. Нам еще нужно доказать обратное: что каж­дая цепочка сбалансированных скобок порождается этой грамматикой. Однако доказа­тельство индукцией по длине сбалансированной цепочки весьма просто и оставляется в качестве упражнения.

Мы отмечали, что множество цепочек сбалансированных скобок не является регуляр­ным языком, и теперь докажем это. Если бы        был регулярным, то для него по лемме о накачке для регулярных языков существовала бы константа п. Рассмотрим сбалансиро­ванную цепочку w = (")", т. е. п левых скобок, за которыми следуют п правых. Если разбить w = xyz в соответствии с леммой, то у состоит только из левых скобок, и цепочка xz содер­жит больше правых скобок, чем левых. Эта цепочка несбалансированна, т. е. получено про­тиворечие с предположением, что язык сбалансированных скобок регулярен. □

Языки программирования содержат, конечно же, не только скобки, но скобки состав­ляют существенную часть арифметических и условных выражений. Грамматика, изобра­женная на рис. 5.2, более типична для структуры арифметических выражений, хотя там использованы всего два оператора, сложения и умножения, и включена детальная струк­тура идентификаторов, которая, вероятней всего, обрабатывалась бы лексическим анали­затором компилятора, как мы упоминали в разделе 3.3.2. Однако язык, представленный на рис. 5.2, также нерегулярен. Например, в соответствии с этой грамматикой, (па)п явля­ется правильным выражением. Мы можем использовать лемму о накачке для того, чтобы показать, что если бы язык был регулярным, то цепочка с некоторыми удаленными ле­выми скобками, символом а и всеми нетронутыми правыми скобками также была бы правильным выражением, что неверно.

Многие объекты типичного языка программирования ведут себя подобно сбалансирован­ным скобкам. Обычно это сами скобки в выражениях всех типов, а также начала и окончания блоков кода, например, слова begin и end в языке Pascal, или фигурные скобки { и } в С. Таким образом, любое появление фигурных скобок в С-программе должно образовывать сба­лансированную последовательность с { в качестве левой скобки и } — правой.

Есть еще один способ балансирования "скобок", отличающийся тем, что левые скоб­ки могут быть несбалансированны, т. е. не иметь соответствующих правых. Примером является обработка if и else в С. Произвольная if-часть может быть как сбалансиро­вана, так и не сбалансирована некоторой else-частью. Грамматика, порождающая воз­можные последовательности слов if и else, представленных /' и е соответственно, име­ет следующие продукции.

S->e\SS\iS\iSeS

Например, ieie, iie и iei являются возможными последовательностями слов if и else, и каждая из этих цепочек порождается данной грамматикой. Примерами непра­вильных последовательностей, не порождаемых грамматикой, являются е/ и /ее/7.

Простая проверка (доказательство ее корректности оставляется в качестве упражнения) того, что последовательность символов / не порождается грамматикой, состоит в рассмот­рении каждого е по очереди слева направо. Найдем первое /' слева от рассматриваемого е. Если его нет, цепочка не проходит проверку и не принадлежит языку. Если такое /' есть, вычеркнем его и рассматриваемое е. Затем, если больше нет символов е, цепочка проходит проверку и принадлежит языку. Если символы е еще есть, то проверка продолжается.

Пример 5.20. Рассмотрим цепочку /ее. Первое е соответствует / слева от него. Оба удаляются. Оставшееся е не имеет / слева, и проверка не пройдена; слово /ее не принад­лежит языку. Отметим, что это заключение правильно, поскольку в С-программе слов else не может быть больше, чем if.

В качестве еще одного примера рассмотрим iieie. Соответствие первого е и / слева от него оставляет цепочку iie. Соответствие оставшегося е и /' слева оставляет /'. Символов е больше нет, и проверка пройдена. Это заключение также очевидно, поскольку последо­вательность iieie соответствует С-программе, структура которой подобна приведенной на рис. 5.10. В действительности, алгоритм проверки соответствия (и компилятор С) гово­рит нам также, какое именно if совпадает с каждым данным else. Это знание сущест­венно, если компилятор должен создавать логику потока управления, подразумеваемую программистом. □

if (Условие) {

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.

Exp : Id        { . ..}

| Exp ' + '        Exp {.• . }

| Exp '*'        Exp {••.}

| ' (' Exp        ') ' { . - . } t

Id : 'a'        {...}

'b'        {...}

| Id 'a'        { . . . }

| Id 'b'        {...}

| Id '0'        {•■.}

| Id '1'        {...}

r

Рис. 5.11. Пример грамматики в нотации YACC

Отметим следующие соответствия между нотацией YACC и нашими грамматиками.

Двоеточие используется в качестве символа продукции — Все продукции с данной головой группируются вместе, и их тела разделены вер­тикальной чертой. Список тел для данной головы заканчивается точкой с запятой. Завершающий символ не используется. Терминалы записываются в апострофах. Некоторые буквы могут появляться в одиночных апострофах. Хотя у нас они не показаны, YACC позволяет пользова­телю определять также и символические терминалы. Появление таких термина­лов в исходной программе обнаруживает лексический анализатор и сигнализиру­ет об этом синтаксическому анализатору через свое возвращаемое значение. Цепочки символов и цифр, не взятые в апострофы, являются именами пере­менных. Мы воспользовались этой возможностью для того, чтобы дать нашим переменным более выразительные имена— Ехр и Id, хотя можно было ис­пользовать Ew. I.

□

5.3.3. Языки описания документов

Рассмотрим семейство "языков", которые называются языками описания документов (markup languages). "Цепочками" этих языков являются документы с определенными метками, которые называются дескрипторами (tags). Дескрипторы говорят о семантике различных цепочек внутри документа.

Читатель, возможно, знаком с таким языком описания документов, как HTML (Hypertext Markup Language). Этот язык имеет две основные функции: создание связей между документами и описание формата ("вида") документа. Мы дадим лишь упрощен­ный взгляд на структуру HTML, но следующие примеры должны показать его структуру и способ использования КС-грамматики как для описания правильных HTML - документов, так и для управления обработкой документа, т. е. его отображением на мо­ниторе или принтере.

Пример 5.22. На рис. 5.12, а показан текст, содержащий список пунктов, а на рис. 5.12, б— его выражение в HTML. На рис. 5.12, б, показано что HTML состоит из обычного текста, перемежаемого дескрипторами. Соответствующие друг другу, т. е. пар­ные дескрипторы имеют вид <х> и </х> для некоторой цепочки х.15 Например, мы видим парные дескрипторы <ЕМ> и </ЕМ>, которые сигнализируют, что текст между ними должен быть выделен, т. е. напечатан курсивом или другим подходящим шрифтом. Мы

видим также парные дескрипторы <0L> и </OL>, указывающие на упорядоченный спи­сок, т. е. на нумерацию элементов списка. Вещи, которые я ненавижу.

Заплесневелый хлеб. Людей, которые ведут машину по узкой дороге слишком медленно.

а) видимый текст <Р>Вещи, которые я <ЕМ>ненавижу</ЕМ>: <OL>

<Ы>Заплесневелый хлеб.

<Ы>Людей, которые ведут машину по узкой дороге слишком медленно. </OL>

6) исходный HTML-текст Рис. 5.12. HTML-документ и его видимая версия

Мы видим также два примера непарных дескрипторов: <Р> и <LI>, которые вводят абзацы и элементы списка, соответственно. HTML допускает, а в действительности по­ощряет, чтобы эти дескрипторы сопровождались парными им </Р> и </LI> на концах абзацев и списков, однако не требует этого. Поэтому эти парные дескрипторы не рас­сматриваются, что обеспечивает некоторую сложность нашей HTML-грамматике, разви­ваемой далее. □