Если регулярное выражение начинается с ", то текст должен начинаться с символов, соответствующих остальной части выражения. При другом начале мы проходим по тексту, используя matchhere для выяснения, соответствует ли текст каждой позиции выражения. Как только мы находим соответствие, миссия наша завершена. Обратите внимание на использование do-while: выражениям может соответствовать пустая строка (например, шаблону $ соответствует пустая строка, а шаблону . * — любое количество символов, включая и ноль), поэтому вызвать matchhere мы должны даже в том случае, если строка текста пуста.
Большая часть работы выполняется в рекурсивной функции matchhere:

g rep абсолютно неважно, какое

Для g rep абсолютно неважно, какое именно совпадение будет обнаруже-ю, поскольку эта программа проверяет лишь наличие соответствий во-эбще и выводит всю строку, содержащую соответствие. Таким образом, поиск крайне левого максимального совпадения, жизненно необходимый для оператора замещения, хоть и делает некоторую ненужную для g rep работу, все же может быть применен без изменений и для этой программы.
Наша версия g rep вполне сравнима с версиями, поставляемыми с различными системами (неважно, что синтаксис наших регулярных выражений несколько скуднее). Существуют некоторые патологические выражения, которые приводят к экспоненциальному возрастанию трудоемкости поиска, — например, выражение а*а*а*а*а*Ь при введенном тексте ааааааааас, однако экспоненциальный поиск присутствует и в некоторых коммерческих реализациях. Вариант g rep, применяемый в Unix (он называется eg rep), использует более сложный алгоритм поиска соответствий; этот алгоритм гарантирует линейный поиск, избегая отката, когда не подходит частичное соответствие.
А как насчет того, чтобы match умела обрабатывать полноценные регулярные выражения? Для этого надо добавить возможность сопоставления классов символов типа [a-zA-Z] конкретному символу алфавита, возможность исключать значение метасимволов (например, для поиска точки нужно обозначить этот символ как литеральный), предусмотреть скобки для группировки, а также ввести альтернативы (аос или clef). Первый шаг здесь — облегчить match работу, скомпилировав шаблон в некое новое представление, которое было бы проще сканировать: слишком накладно производить разбор класса символов для каждого нового сравнения его с одним символом; предварительно вычисленное представление, основанное на битовых массивах, сделает классы символов гораздо более эффективными. Полная реализация регулярных выражений, со скобками и альтернативами, получится гораздо более сложной; облегчить написание помогут некоторые средства, о которых мы поговорим далее в этой главе.

f mt для того, чтобы

Мы часто используем f mt для того, чтобы заново разбить на абзацы почтовые сообщения и другие короткие документы; ее же мы использовали главе 3 для форматирования вывода программы markov.
Программируемые инструменты часто берут свое начало от малых ыков программирования, созданных для более простого выражения шений проблем в какой-то узкой предметной области. Прелестным шмером является инструмент Unix под названием eqn, который обра-тывает математические формулы. Язык, применяемый в нем для вво-., очень похож на обычный: например, выражение f мы прочитали бы лух как "пи на два" (pi over two), и в этом языке оно так и записывается - pi over 2. Тот же подход применяется и в ТЕХ, в нем это выраже-ie было бы записано как \pi \over 2. Если для проблемы, которую вы пытаетесь разрешить, уже существует естественный или привычный :особ записи, используйте его или, на худой конец, попробуйте его дотировать: не пытайтесь писать с нуля.
Awk развился из программы, которая использовала регулярные выражения для выявления аномалий в записях телефонного трафика; теперь же] ffk содержит в себе переменные, выражения, циклы и т. п., — и это делает о полноценным языком программирования. Perl и Tel первоначально проектировались с целью совместить удобство и выразительность малых ыков с мощью полноценных языков программирования. В результате получились действительно удобные языки программирования общего назначения, хотя, конечно, чаще всего их используют для обработки текста.
Для подобных инструментов применяют общий термин — языки скрип-~>в (scripting languages). Такое название объясняется их происхождением
ранних командных интерпретаторов, вся "программируемость" ко-рых ограничивалась исполнением заранее записанных "сценариев" cript) программ. Языки скриптов позволяют использовать регулярные выражения более творчески: не только для поиска соответствий шаблону — простого обнаружения соответствия, но и для определения участ-iB текста, которые должны быть изменены. Именно это осуществляется в двух командах regsub (от regular expression substitution — замена с помощью регулярных выражений), реализованных в приводимой ниже программе на языке Tel. Программа эта является несколько более общей фор-)й программы из главы 4, получающей биржевые котировки; новая версия выполняет это, получая данные из URL, передаваемого ей в качестве первого аргумента. Первая замена удаляет строку http://, если она присутствует; вторая — удаляет символ / и заменяет его пробелом, разбивая, таким образом, аргумент на два поля. Команда lindex получает поля из строки (начиная с индекса 0). Текст, заключенный в квадратные скобки, выполняется как команда Tel и заменяется результирующим текстом; последовательность $х заменяется значением переменной х.

Этот скрипт, как правило, производит

Этот скрипт, как правило, производит весьма объемистый вывод, большую часть которого составляют тэги HTML, заключенные между < и >. Perl удобен для текстовых подстановок, так что нашим следующим инструментом станет скрипт на Perl, который использует регулярные выражения и подстановки для удаления тэгов:

Для тех, кто не знаком

Для тех, кто не знаком с Perl, этот код будет загадкой. Конструкция
$str =" s/regexp/repl/g
строке str подставляет строку repl вместо текста, соответствующего регулярному выражению readexp (берется крайне левое максимальное соответствие); завершающий символу (от "global") означает, что действия надо произвести глобально, для всех найденных соответствий, и не только для первого. Последовательность метасимволов \s является сокращенным обозначением символа пустого места (пробел, знак табуляции, символ перевода строки и т. п.); Это означает перевод строки. Строка "&nbsp;" — это символ HTML, как и те, о которых мы упоминали I главе 2, он означает non-breakable space — неразрывный пробел.
Собрав все написанное воедино, мы получим совершенно идиотский, но функционирующий web-браузер, реализованный как скрипт командного интерпретатора, состоящий из одной строки:

и отформатирует текст по своим

Такой вызов получит web-страницу, отбросит все управление и форма-гирование и отформатирует текст по своим собственным правилам. Получился быстрый способ достать страницу текста из web.
Отметьте, что мы неспроста использовали сразу несколько Жыков (Tel, Perl, Awk) и в каждом из них — регулярные выражения. Собственно говоря, мощь различных нотаций и состоит как раз в подборе наилучшего варианта для каждой проблемы. Teм особенно хорош для получения текста из сети, Perl и Awk прекрасно редактируют и форматируют текст, а регулярные выражения — отличный способ определения фрагментов текста, которые должны быть найдены и изменены. Объединение всех этих языков получается гораздо более мощным, чем любой из них в отдельности. Целесообразно разбить задачу на части, если можнс выиграть за счет составления правильной нотации в каждой из них. <

в главе 2, вполне] огут

Многие из алгоритмов работы с деревьями, описанных в главе 2, вполне] огут быть применимы для создания и обработки синтаксических деревьев.
После того как дерево построено, обрабатывать его можно множе- j гвом способов. Наиболее прямолинейный метод, применяемый, кста-1 я, в Awk, — это прямой обход дерева с попутным вычислением узлов. | 'прощенная версия алгоритма такого вычисления для языка, основанного на целочисленных выражениях, может включать в себя восходя-] щи обход типа такого:

Первые несколько выражений case вычисляют

Первые несколько выражений case вычисляют простые выражения вроде констант или значений; следующие вычисляют арифметические выражения, а дальше может идти обработка специальных случаев, условных выражений и циклов. Для реализации управляющих структур нашему дереву потребуется не показанная здесь дополнительная информация, которая представляет собой поток управления.
Подобно тому, как мы делали в pack и unpack, здесь можно заменить явный переключатель таблицей указателей на функции. Отдельные операции при этом будут выглядеть практически так же, как и в варианте с переключателем:

Таблица указателей сопоставляет операции

Таблица указателей сопоставляет операции и функции, выполняющие операции:

Вычисление использует операции для индексирования

Вычисление использует операции для индексирования в таблице указа-1бй на функции для вызова этих функций; в этой версии другие функ-и вызываются рекурсивно.

Обе наши версии eval применяют

Обе наши версии eval применяют рекурсию. Существуют способы уст-нить ее — в частности, весьма хитрый способ, называемый шитым кодом ireaded code), который практически не использует стек вызовов. Самым ящным способом избавления от рекурсии будет сохранение функций в 1ссиве, с последующим выполнением этих функций в записанном поряд-:. Таким образом, этот массив становится просто последовательностью гструкций, исполняемых некоторой специальной машиной.
Для представления частично вычисленных значений из нашего выра-ения мы, так же как и раньше, будем использовать стек, так что, не-ютря на изменение формы функций, преобразования отследить будет трудно. Фактически мы изобретаем некую стековую машину, в которой инструкции представлены небольшими функциями, а операнды хранятся в отдельном стеке операндов. Естественно, это не настоящая машина, но мы можем писать программу так, как будто подобная машина все же существует: в конце концов, мы можем без труда реализовать ее в виде интерпретатора.
При обходе дерева вместо подсчета его значения мы будем генерировать массив функций, исполняющих программу. Массив будет также содержать значения данных, используемых командами, такие как константы и переменные (символы), так что тип элементов массива должен быть объединением:

Ниже приведен блок кода, генерирующий

Ниже приведен блок кода, генерирующий указатели на функции и помещающий их в специальный массив code. Возвращаемым значением функции generate является не значение выражения — оно будет подсчитано только после выполнения сгенерированного кода, — а индекс следующей операции в массиве code, которая должна быть сгенерирована:

сгенерированный код будет выглядеть

Для выражения а - max( b , с/2 ) сгенерированный код будет выглядеть так:

операции управляют стеком, извлекая из

Функции- операции управляют стеком, извлекая из него операнды и за-ружая результаты.
Код интерпретатора организован в виде цикла, в котором командный :четчик рс обходит массив указателей на фрикции:

в программном виде на изобретенной

Этот цикл моделирует в программном виде на изобретенной нами стековой машине то, что происходит на самом деле в настоящем компьютере:

Обратите внимание на то, что

Обратите внимание на то, что проверка делимого на ноль осуществляется в divop, а не в generate.
Условное исполнение, ветвление и циклы модифицируют счетчик программы внутри функции-операции, осуществляя тем самым доступ к массиву функций с какой-то новой точки. Например, операция goto всегда переустанавливает значение переменной рс, а операция условного ветвления — только в том случае, если условие есть истина.
Массив code является, естественно, внутренним для интерпретатора, однако представим себе, что нам захотелось сохранить сгенерированную программу в файл. Если бы мы записывали адреса функций, то результат получился бы абсолютно непереносимым, да и вообще ненадежным. Однако мы могли бы записывать константы, представляющие функции, например 1000 для addop, 1001 для pushop и т. д., и переводить их обратно в указатели на функции при чтении программы для интерпретации.
Если внимательно посмотреть на файл, который создает эта процеду-, можно понять, что он выглядит как поток команд виртуальной машины. Эти команды реализуют базовые операции нашего рабочего языка, рункция generate — это компилятор, транслирующий язык на вирту-. ьную машину. Виртуальные машины — стародавняя идея, обретшая госледнее время новую популярность благодаря Java и виртуальной шгане Java (Java Virtual Machine, JVM); виртуальные машины предо-авляют простой способ создавать переносимые и эффективные реали-, ции программ, написанных на языках высокого уровня. <

Имея такой фрагмент на входе,

Имея такой фрагмент на входе, несложная программа сможет произнес* и следующий набор деклараций для сообщений об ошибках:

У такого подхода есть несколько

У такого подхода есть несколько достоинств. Во-первых, соотношение лежду значениями enum и строками, которые они представляют, получается самодокументированным, и его нетрудно сделать независимым от роднoro языка пользователя. Во-вторых, информация хранится только в однтом месте, в одном "истинном месте", из которого генерируется весь эстальной код, так что и всё обновление информации выполняется лишь в одном месте. В случае, когда таких мест несколько, после ряда обновлений они неизбежно начнут друг другу противоречить. И наконец, нетрудно сделать так, чтобы файлы программ на С создавались заново и перекомпилировались при каждом изменении заголовочного файла. Когда потребуется изменить сообщение об ошибке, все, что надо будет сделать, — это изменить заголовочный файл и компилировать таким способом операционную систему, и тогда сообщения автоматически обновятся.
Программа-генератор может быть написана на любом языке. Особенно просто это сделать на языке, специально предназначенном для обработки строк, таком как Perl:

в дело пошли регулярные выражения.

Опять в дело пошли регулярные выражения. Выбираются строки, у которых первое поле выглядит как идентификатор, после которого стоит запятая. Первая замена удаляет все символы до первого непустого символа строки комментария, а вторая — символы конца комментария и все предшествующие им пробелы.
Среди прочих способов для тестирования компилятора Энди Кёниг (Andy Koenig) разработал метод написания кода C++, позволяющий проверить, нашел ли компилятор ошибки в программе. Фрагменты кода, которые должны вызвать реакцию компилятора, снабжаются специальными комментариями, в которых описываются ожидаемые сообщения. Каждая строка такого комментария начинается с /// (чтобы их можно было отличить от обычных комментариев) и регулярного выражения, которое должно соответствовать диагностике компилятора, выдаваемой для этой строки. Таким образом, например, следующие два фрагмента кода должны вызвать реакцию компилятора:

Если мы пропустим второй тест

Если мы пропустим второй тест через компилятор C++, то он напечатает ожидаемое сообщение, вполне соответствующее регулярному выражению:
% СС х.с
"х.с", line 1: error(321): void function may
not return a value
Каждый такой фрагмент кода пропускается через компилятор, и вывод сравнивается с прогнозируемой диагностикой, этим процессом управляет схемная оболочка и программа на Awk. Сбоем считается ситуация, гда вывод компилятора не совпадает с ожидаемым. Поскольку комментарии представлены регулярными выражениями, у них получается которая свобода в оценке вывода: ее можно делать более или менее эогой к отклонениям в зависимости от надобности.
Идея использования семантических комментариев не нова. Такие комментарии используются в языке PostScript, где они начинаются с символа %. Комментарии, начинающиеся с %%, могут содержать дополнительную информацию о номерах страниц, окаймляющем прямоугольнике ounding Box), именах шрифтов и т. п.:

В языке Java комментарии, которые

В языке Java комментарии, которые начинаются с /** и заканчиваются */, пользуются для создания документации для следующего за ними опи-НЕИЯ класса. Глобальным вариантом самодокументации кода является к называемое грамотное программирование (literate programming), и котором программа и ее документация интегрируются в один доку-нт, и при одной обработке документ готовится для чтения, а при дру-й программа готовится к компиляции.
Во всех рассмотренных выше примерах важно отметить роль нотации, смерения языков и использования инструментов. Их комбиниро-ние усиливает и подчеркивает мощь отдельных компонентов.
Упражнение 9-15
В программировании давно известна забавная задачка: написать про-шму, которая при выполнении точно воспроизводила бы саму себя — в виде исходного кода. Это такой гипертрофированный случай программы, пишущей программу. Попробуйте выполнить это — на своем любимом языке. <

в нескольких строках. Этот макрос

Обратная косая черта (\) позволяет записывать тело макроса в нескольких строках. Этот макрос используется в "операторах", которые имеют такой вид:

и другие операторы, но основная

Для инициализации иногда применяются и другие операторы, но основная часть, производящая замеры, представлена в этих одноаргументных фрагментах, которые преобразуются в значительный объем кода.
Иногда макросы могут использоваться и для генерации нормального коммерческого кода. Барт Локанти (Bart Locanthi) однажды написал эффективную версию оператора двумерной графики. Этот оператор, называемый bitblt, или rasterop, трудно было сделать быстрым, поскольку он использовал большое количество аргументов, которые могли комбинироваться самыми хитрыми способами. Проведя тщательный разбор вариантов, Локанти уменьшил комбинации до независимых циклов, которые можно было оптимизировать по отдельности. Затем каждый случай был воссоздан с помощью макроподстановки, аналогичной той, что показана в примере на тестирование производительности, и все варианты были перебраны в одном большом выражении switch. Оригинальный исходный код представлял две-три сотни строк, после выполнения макроподстановок он разрастался до многих тысяч строк. Этот конечный код был не самым оптимальным, но, учитывая сложность задачи, весьма
эактйчным и простым в написании. И кстати, как и весь код самого вы-iKoro уровня, неплохо переносимым.

когда мы генерируем код для

Однако, когда мы генерируем код для конкретного шаблона, значение этого literal фиксировано, например ' х ' , так что мы можем вместо показанного выше сравнения использовать оператор вроде следующего:

И затем, вместо того чтобы

И затем, вместо того чтобы предварительно определять специальный оператор для значения каждого символа-литеры, мы можем поступить проще: генерировать код для операторов, которые нам будут действительно нужны для данного выражения. Применив эту идею для полного набора операторов, мы можем написать JlT-компилятор, который будет анслировать заданное регулярное выражение в специальный код, оп-мизированный именно под это выражение.
Кен Томпсон (Ken Thompson) именно это и сделал в 1967 году для реализации регулярных выражений на машине IBM 7094. Его версия генерировала в двоичном коде небольшие блоки команд этой машины для разных операторов выражения, сшивала их вместе и затем запускала шучившуюся программу, просто вызвав ее, совсем как обычную функцию. Схожие технологии можно применить для создания специфических юледовательностей команд для обновлений экрана в графических системах, где может быть так много различных случаев, что гораздо более эффективно создавать динамический код для каждого из них, чем расписать с все заранее или включить сложные проверки в более общем коде.
Демонстрация того, что же включает в себя создание полноценного Т-компилятора, неизбежно вынудит нас обратиться к деталям конкретных наборов команд, однако все же стоит потратить некоторое время, гобы на деле понять, как работает такая система. В оставшейся части :ого параграфа для нас важно будет понимание сути, идеи происходя-,его, а не деталей конкретных реализаций.
Итак, вспомним, в каком виде мы оставили нашу виртуальную маши-у, — структура ее выглядела примерно так:

Для того чтобы адаптировать этот

Для того чтобы адаптировать этот код для JIT-компиляции, в него [адо внести некоторые изменения. Во-первых, массив code будет теперь» re массивом указателей на функции, а массивом исполняемых команд.
Будут ли эти команды иметь тип char, int или long — зависит только от того процессора, под который мы компилируем; предположим, что это будет int. После того как код будет сгенерирован, мы вызываем его как функцию. Никакого виртуального счетчика команд программы в новом коде не будет, поскольку обход кода за нас теперь будет выполнять собственно исполнительный цикл процессора; по окончании вычисления результат будет возвращаться — совсем как в обычной функции. Далее, мы можем выбрать — поддерживать ли нам отдельный стек операндов для нашей машины или воспользоваться стеком самого процессора. У каждого из этих вариантов есть свои преимущества; мы решили остаться верными отдельному стеку и сконцентрироваться на деталях самого кода. Теперь реализация выглядит таким образом:

После того как generate завершит

После того как generate завершит работу, gen return вставит команды, которые обусловят передачу управления от сгенерированного кода к eval.
Функция f lushcaches отвечает за шаги, необходимые для подготовки процессора к запуску свежесозданного кода. Современные машины работают быстро, в частности благодаря наличию кэшей для команд и данных, а также конвейеров (pipeline), которые отвечают за выполнение сразу нескольких подряд идущих команд. Эти кэши и конвейеры исходят из предположения, что код не изменяется; если же мы генерируем этот код непосредственно перед запкуском, топроцессор может оказаться в затруднении: ему нужно обязательно очистить свой конвейер и кэши для исполнения новых команд. Эти операции очень сильно зависят от энкретного компьютера, и, соответственно, реализация f lushcaches будет в каждом случае совершенно уникальной.
Замечательное выражение (void (*)(void)) code преобразует адрес :ассива, содержащего сгенерированные команды, в указатель на функцию, который можно было бы использовать для вызова нашего кода.
Технически не так трудно сгенерировать сам код, однако, конечно, для ого чтобы сделать это эффективно, придется позаниматься инженерной .еятельностью. Начнем с некоторых строительных блоков. Как и раньше, [ассив code и индекс внутри него заполняются во время компиляции. Для [ростоты мы повторим свой старый прием — сделаем их оба глобальными. Затем мы можем написать функцию для записи команд:

Сами команды могут определяться макросами,

Сами команды могут определяться макросами, зависящими от процессора, или небольшими функциями, которые собирали бы код, заполняя поля в командном слове инструкции. Гипотетически мы могли бы завести функцию pop reg, которая бы генерировала код для выталкивания значения из стека и сохраняла его в регистре процессора, и функцию push reg, которая бы генерировала код для получения значения, хранящегося в регистре процессора, и заталкивания его в стек. Наша обновленная функция addop будет использовать некие их аналоги, применяя некоторые предопределенные константы, описывающие команды (вроде ADDINST) и их расположение (различные позиции сдвигов SHIFT, которые определяют формат командного слова):

только самое начало. Если бы

Это, однако, только самое начало. Если бы мы писали настоящий JIT-ком-пилятор, нам бы пришлось заняться оптимизацией. При прибавлении константы нам нет нужды грузить ее в стек, вынимать оттуда и после этого прибавлять: мы можем прибавить ее сразу. Должное внимание к подобным случаям помогает избавиться от множества излишеств. Однако даже в теперешнем своем виде функция addop будет выполняться гораздо быстрее, чем в наших более ранних версиях, поскольку различные операторы уже не сшиты воедино вызовами функций. Вместо этого код, исполняющий их, располагается теперь в памяти в виде единого блока команд, и для нас все сшивается непосредственно счетчиком команд процессора.
Теперешняя реализация функции generate выглядит весьма похоже на реализацию виртуальной машины, но на этот раз она задает реальные машинные команды вместо указателей на предопределенные функции. Чтобы генерировать более эффективный код, следовало бы потратить усилия на избавление от лишних констант и другие виды оптимизации.
В нашем ураганном экскурсе в генерацию кода мы бросили лишь самый поверхностный взгляд на некоторые из технологий, применяемых в настоящих компиляторах, некоторые же вообще обошли молчанием. При этом мы лишь попутно затронули ряд аспектов, связанных со сложностью организации современных процессоров. Но мы показали, как программа может анализировать описание проблемы, чтобы создать специальный код, который наиболее эффективен для конкретной задачи. Изложенные выше идеи вы можете использовать для создания быстрой версии grep, для реализации небольшого языка программирования имени себя, для проектирования и создания виртуальной машины,' оптимизированной для решения специфических задач, или даже для создания компилятора для какого-нибудь интересного языка.
Между регулярным выражением и программой на C++ есть, конечно, немалая разница, но суть у них одна — это всего лишь нотации для решения проблем. При правильной нотации многие проблемы становятся гораздо более простыми. А проектирование и реализация выбранной нотации может дать массу удовольствия.

Программируемые инструменты

Множество инструментов группируется вокруг языков специального.'! назначения. Программа g rep — всего лишь одна из целого семейства инструментов, которые используют регулярные выражения или другие языки для разрешения программистских проблем.

Одним из первых подобных инструментов стал командный интерпретатор, или язык управления заданиями. Достаточно быстро стало понятно, что последовательность команд можно поместить в отдельный файл, а потом запустить экземпляр интерпретатора команд, или оболочки /(shell), указав этот файл в качестве источника ввода. Следующим шагомстало уже добавление параметров, условных выражений, циклов, переменных и т. п., то есть всего того, из чего в нашем представлении состоит нормальный язык программирования. Единственное отличие заключалось в том, что существовал только один тип данных — строки, а операторами в программах-оболочках являлись различные программы, осуществлявшие порой достаточно интересные вычисления. Несмотря на то что программирование под конкретные оболочки сейчас уже уходит в прошлое, уступая место работе с инструментами типа Perl в командных средах или щелканью по кнопкам в графических средах, этот "старинный" подход по-прежнему остается простым и достаточно эффективным способом создания каких-то сложных операций из простых частей.

Еще один программируемый инструмент, Awk, представляет собой небольшой специализированный язык, который предназначен для отбора и преобразования элементов входного потока; он ищет в этом потоке соответствия заданным шаблонам, а когда находит, то выполняет связанные с шаблонами действия. Как мы уже видели в главе 3, Awk автоматически читает входные файлы и разделяет каждую прочитанную строку на поля, обозначаемые от $1 до $NF, где NF есть количество полей в строке. Его поведение "по умолчанию" удобно для выполнения большого числа типовых действий, поэтому многие полезные программы пишутся на Awk в одну строчку. Так, например, программа

# split.awk: расщепляет текст на отдельные слова { for (i = 1; i <= NF; i+3-) print $i }

выводит "слова" по одному в строке. И напротив, вот программа f mt, которая заполняет каждую выводимую строку словами (до 60 символов); пустая строка означает конец параграфа:

Программы, которые пишут программы

Возможно, самым примечательным в функции generate является то, о она представляет собой программу, которая пишет другую програм-г. ее вывод есть поток исполнимых команд для другой (виртуальной) шшны. Собственно, подобная идея нам привычна, именно это делают е компиляторы, только команды они генерируют для реальных ма-ин. На самом деле формы, в которых появляются программы, пишу- \ ие программы, очень разнообразны.

Один обычный пример дает динамическая генерация HTML для web-раниц. HTML — это язык, хоть и достаточно ограниченный; кроме то, в себе он может содержать и код JavaScript. Web-страницы часто нерируются "на лету" программами на Perl или С, содержание таких раниц (например, результаты поиска или реклама, нацеленная на определенную аудиторию) зависит от приходящих запросов. Мы использовали специализированные языки для графиков, картинок, таблиц, математических выражений и индекса этой книги. Еще одним примером эжет служить PostScript — язык программирования, тексты на котором создаются текстовыми процессорами, программами рисования и множеством других источников; на финальном этапе обработки книга, которую вы держите в руках, представлена как программа на PostScript, держащая 57 000 строк.

Документ — это статическая программа, однако идея использования языка программирования как способа записи любой проблемы является весьма многообещающей. Много лет назад программисты мечтали о том, что компьютеры когда-нибудь смогут сами писать для себя программы, энечно же, эта мечта никогда не осуществится в полной мере, однако годня можно сказать, что машины нередко пишут программы за нас и иногда в таких областях, где совсем недавно это трудно было себе представить.

Наиболее распространенные программы, создающие программы, — это компиляторы, которые переводят программу с языка высокого уровня в машинный код. Однако нередко оказывается удобным переводить код программы сначала на один из широко известных языков высокого уровня. В предыдущем параграфе мы упоминали о том, что генератор синтаксического анализатора преобразует определение грамматики языка в программу на С, которая и занимается синтаксическим разбором языка.

С достаточно часто используется подобным

Язык С достаточно часто используется подобным образом -в качестве "языка ассемблера высокого уровня". Modula-З и C++ относятся к тем языкам общего назначения, для которых первые компиляторы создавали код на С, обрабатывавшийся затем уже стандартным компилятором. У такого подхода есть ряд преимуществ — одним из главных является эффективность, поскольку получается, что в принципе программа может выполняться так же быстро, как и программы на С. Еще один плюс — переносимость: такие компиляторы могут быть перенесены на любую систему, имеющую компилятор С. Подобный подход сильно помог этим языкам на ранних стадиях их внедрения.

В качестве еще одного примера возьмем графический интерфейс Visual Basic. Он генерирует набор операторов присваивания Visual Basic для инициализации объектов. Этот набор пользователь выбирает из меню и располагает на экране с по'мощью мыши. Во множестве других языков есть "визуальная" среда разработки и "мастера" (wizard), которые синтезируют код пользовательского интерфейса по щелчку мыши.

Несмотря на мощь программ-генераторов и на большое количество примеров их удачного применения, этот подход еще не признан так широко, как он того заслуживает, и нечасто используется программистами. Однако существует уйма простых возможностей программного создания кода, и вы вполне можете использовать их преимущества. Ниже приведены несколько примеров генерации кода на С или C++.

Операционная система Plan 9 генерирует сообщения об ошибках по заголовочному файлу, содержащему программные имена ошибок и комментарии к ним; эти комментарии механически конвертируются в строки, заключенные в кавычки, они помещаются в массив, который может быть индексирован перечислимым значением. В приведенном ниже фрагменте показана структура такого заголовочного файла:

Регулярные выражения

Спецификаторы формата для pack и unpack — достаточно простой юсоб записи, описывающий компоновку пакетов. Следующая тема iniero обсуждения — несколько более сложный, но гораздо более фазительный способ записи -- регулярные выражения (regular pressions), определяющие шаблоны текста (patterns of text). В этой [иге мы время от времени использовали регулярные выражения, не вая им точного описания; они достаточно знакомы, чтобы понять их без особых пояснений. Хотя регулярные выражения широко распространены в средах программирования под Unix, в других системах они применяются гораздо реже, поэтому в данном разделе мы решили показать некоторые их преимущества. На случай, если у вас нет под рукой библиотеки с регулярными выражениями, мы приведем ее простейшую реализацию.

Существует несколько разновидностей регулярных выражений, но суть у них у всех одинакова — это способ описания шаблона буквенных символов, включающего в себя повторения, альтернативы и сокращения для отдельных классов символов вроде цифр или букв. Примером такого шаблона могут служить всем знакомые символы замещения (wildcards), используемые в процессорах командной строки или оболочках для задания образцов поиска имен файлов. Как правило, символ * используется для обозначения "любой строки символов", так что команда

С:\> del *.exe

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

Причуды отдельных программ могут навести на мысль, что регулярные выражения являются механизмом? создаваемым ad hoc, для каждого случая отдельно, но на самом деле регулярные выражения — это язык с формальной грамматикой и точным значением каждого выражения. Более того, при должной реализации конструкция работает очень быстро: благодаря соединению теории и практического опыта; вот пример в пользу специализированных алгоритмов, упоминавшихся нами в главе 2.

Регулярное выражение есть последовательность символов, которая определяет множество образцов поиска.

напросто соответствуют сами себе, так

Большинство символов просто- напросто соответствуют сами себе, так что регулярное выражение abc будет соответствовать именно этой строке символов, где бы она ни появлялась. Но, кроме того, существует несколько метасимволов, которые обозначают повторение, группировку или местоположение. В принятых в Unix регулярных выражениях символ ~ обозначает начало строки, а $ — конец строки, так что шаблон ~х соответствует только символу х в начале строки, х$ — только х в конце строки. Шаблону ~х$ соответствует только строка, содержащая единственный символ х, и, наконец, ~$ соответствует пустая строка.

Символ . (точка) обозначает любой символ, так что выражению х. у будут соответствовать хау, х2у и т. п., но не ху или xaby; выражению ~. $ соответствует строка из одного произвольного символа.

Набору символов внутри квадратных скобок соответствует любой ия этих символов. Таким образом, [0123456789] соответствует одной цифре, это выражение можно записать и в сокращенном виде: [0-9]1.

Эти строительные блоки комбинируются с помощью круглых скобок' для группировки, символа | — для обозначения альтернатив, * — для обозначения нуля или более совпадений, + — для обозначения одного или более совпадений и ? — для обозначения нуля или одного совпадения. Наконец, символ \ применяется в качестве префикса перед метасимволом для исключения его специального использования, то есть \* обозначает просто символ *, а \\ — собственно символ обратной косой черты \.

Наиболее известным инструментом работы с регулярными выраже-йийми является программа g rep, о которой мы уже несколько раз упоминали. Эта программа — чудесный пример, показывающий важность нотации. В ней регулярное выражение применяется к каждой строке вводимого файла и выводятся строки, которые содержат образцы поиска, описываемые этим выражением. Эта простая спецификация с помощью регулярных выражений позволяет справиться с большим количеством ежедневной рутинной работы. В приведенных ниже примерах обратите внимание на то, что синтаксис регулярных выражений, используемых в качестве аргументов g rep, отличается от шаблонов поиска, применяемых для задания набора имен файлов; различие обусловлено разным назначением выражений.

Какой исходный файл использует класс

Какой исходный файл использует класс Regexp?

% grep Regexp *.java

В каком файле этот класс реализован?

% grep 'class.*Regexp' *.java

Куда я подевал это письмо от Боба?

% grep '"From:.* bob@' mail/*

Сколько непустых строк кода в этой программе?

grep *. с++ 1 we

Благодаря наличию флагов, позволяющих выводить номера соответствующих выражению строк, подсчитывать количество соответствий, осуществлять сравнение без учета регистра, инвертировать смысл выражения (то есть отбирать строки, не соответствующие шаблону) и т. п., программа grep используется сейчас настолько широко, что стала уже классическим примером программирования с помощью специальных инструментов.

К сожалению, не во всех системах имеется grep или ее аналог. Некоторые системы включают в себя библиотеку регулярных выражений, которая называется, как правило, regex или regexp, и ее можно использовать для создания собственной версии g rep. Если же нет ни того, ни другого, то на самом деле не так трудно реализовать какое-то скромное подмножество языка регулярных выражений. Здесь мы представляем реализацию регулярных выражений и grep, чтобы работать с ними; для простоты мы ограничимся метасимволами $ . и * , причем * обозначает повторение предыдущей точки или обычного символа. Выбор этого подмножества обеспечивает почти все возможности регулярных выражений, тогда как его программировать значительно проще, чем в исходном общем случае.

Начнем с самой функции, осуществляющей проверку на соответствие. Ее задача — определить, соответствует ли строка текста регулярному выражению:

и unpack так, чтобы можно

Измените pack и unpack так, чтобы можно было передавать и значения со знаком, причем даже между машинами, имеющими разные размеры short и long. Как вы измените форматную строку для обозначения элемента данных со знаком? Как можно протестировать код, чтобы убедиться, что он корректно передает, например, число -1 с компьютера с 32-битовым long на компьютер с 64-битовым long?

и unpack возможности обработки строк.

Добавьте в pack и unpack возможности обработки строк. (Есть вариант включать длину строки в форматную строку.) Добавьте возможность обработки повторяющихся значений с помощью счетчика. Как это соотносится с кодировкой строк?

Вспомните таблицу указателей на функции,

Вспомните таблицу указателей на функции, которую мы применили олько что в программе на С. Такой же принцип лежит в основе механиз-ia виртуальных функций C++. Перепишите pack, unpack и receive на ;++, чтобы прочувствовать все удобство этого способа.

Напишите версию printf для командной

Напишите версию printf для командной строки: пусть эта функция ечатает свой второй и последующие аргументы в формате, заданном первом аргументе. Надо отметить, что во многих оболочках имеется строенный аналог такой функции.

классе Decimal Format, где числа

Напишите функцию, реализующую спецификации.формата, .исполь-/емого в какой-нибудь программе работы с электронными таблицами ли в Java- классе Decimal Format, где числа отображаются в соответствии некоторым заданным шаблоном, указывающим количество обязатель-ых и возможных символов, положение десятичной точки и тысячных шятых и т. п. Для иллюстрации рассмотрим строку
##,##0.00
Эта строка задает число с двумя знаками после десятичной точки, э крайней мере одним знаком перед десятичной точкой, запятой в качестве разделителя тысяч и заполняющими пробелами до позиции 10 000. аким образом, число 12345.67 будет представлено как 12, 345. 67, а .4 — ж **,**0.40 (для наглядности вместо пробелов мы вставили звездоч-i). Для получения полной спецификации можете обратиться к описа-«о DecimalFormat или программам работы с электронными таблицами. <

и strstr при поиске простого

Как соотносится быстродействие match и strstr при поиске простого текста (без метасимволов)?

Напишите версию matchhere без рекурсии

Напишите версию matchhere без рекурсии и сравните ее быстродействие с рекурсивной версией.

g rep несколько ключей командной

Добавьте в g rep несколько ключей командной строки. К наиболее популярным ключам относятся -у для инвертирования смысла шаблона, -i для поиска без учета регистра и ~п для вывода номеров строк. Как должны выводиться номера строк? Должны ли они печататься на той же строке, что и совпавший текст?

соответствует строка из одного или

Добавьте в match операторы + (один или более) и ? (ноль или один). Шаблону a+bb? соответствует строка из одного или более а, за которыми следует одно или два b.

В нашей реализации match специальное

В нашей реализации match специальное значение символов " и $ отключается, если они не стоят, соответственно, в начале или конце выражения, а звездочка * рассматривается как обычный символ, если она не стоит непосредственно после литерального символа или точки. Однако более стандартным поведением является~отключение значения метасимвола постановкой перед ним символа обратной косой черты (\). Измените match так, чтобы она обрабатывала этот символ именно таким образом.

в match классы символов. Класс

Добавьте в match классы символов. Класс символов определяет соответствие любому из символов, заключенных в квадратные скобки. Для Удобства лучше ввести диапазоны, например [a-z] соответствует любой строчной букве (английского алфавита!), а также определить способ инвертирования смысла, — например, [~0-9] соответствует любому символу, кроме цифры.

Упражнение 9-12
Измените match так, чтобы в ней использовалась версия matchstar, ( которой ищется крайне левое максимальное соответствие. Кроме того, :ледует добиться возвращения позиции символов начала и конца текста, ;оответствующего шаблону. Теперь создайте новую версию дгер, кото- j рая вела бы себя как старая, но выполняла замену текста, соответству-. ющего шаблону, заданным новым текстом и выводила полученные стро-1 ки. Пример вызова:
grep 'homoiousian' 'homoousian' mission.stmt

Упражнение 9-13
Измените match и дгер так, чтобы они-работали со строками символов Unicode формата UTF-8. Поскольку UTF-8 и Unicode являются расширением набора 7-битового ASCII, такое изменение будет совместимо с предыдущей версией. Регулярные выражения, так же как и текст, в котором происходит поиск, должны корректно работать с UTF-8. Как в этом случае должны быть реализованы классы символов?

Напишите программу для автоматического тестирования

Напишите программу для автоматического тестирования регулярных выражений: она должна генерировать тестовые выражения и строки, в которых будет происходить поиск. Если можете, используйте уже существующую библиотеку как прототип для ответов, — возможно, вы найдете какие-то ошибки и в ней. <

вам предлагалось написать программу,

В упражнении 7- 7 вам предлагалось написать программу, оценивающую траты на различные операции в C++. Используя идеи, изложенные в последнем параграфе, попробуйте написать новую версию этой программы.

надо было построить модель

В упражнении 7- 8 надо было построить модель оценки затрат для tva, а в этом языке нет макросов. Попробуйте решить эту проблему, написав другую программу — на любом другом языке (или языках), которая создавала бы Java-версию и автоматизировала бы запуск тестов на эоизводительность. <

компилятор сгенерирует более быстрый код,

JIT- компилятор сгенерирует более быстрый код, если сможет заменить выражения, содержащие только константы, такие как тах(3*3, 4/2), их значением. Опознав такое выражение, как он должен вычислять его значение?

Упражнение 9-19
Как бы вы тестировали JIT-компилятор? <

---

---