Транслятор — это не только просто…

Давным-давно, в прошлом тысячелетии, когда компьютеры были малоразрядными,
медленными, а дисплеи — алфавитно-цифровыми, совсем юные и умудренные опытом
программисты не боялись ничего.

Грэйс Хоппер, Алан Кей, Гари Килдэлл, Пол Аллен, Билл Гейтс, Деннис Ричи и Брайан
Керниган, Никлас Вирт — перечислять имена всех знаменитостей, во многом предопределивших
облик сегодняшнего компьютинга, слишком утомительно. Но у всех них есть одна
общая черта — они или начинали, или со временем приходили к… созданию собственного
языка программирования или транслятора. Хоппер вошла в историю не только как
женщина-адмирал, но и как создательница неувядающего Cobol. Кей — один из авторов
Smalltalk. Килдэлл, разработчик знаменитой ОС CP/M, "выдумал" и реализовал
язык PL/M. Будущие основатели Microsoft написали интерпретатор Basic. Ричи и
Керниган придумали и воплотили в код C. Вирт навсегда увековечил свое имя языком
Pascal.

В неполном перечне есть еще одна скрытая закономерность — временная, ведь
все эти события и люди фактически принадлежат одной "эпохе". Эпохе
несовершенства технологий. Возможно, этот неочевидный факт кажется парадоксальным,
но именно в те времена, когда не было никаких интегрированных средств разработки
и объектно-ориентированных парадигм проектирования, когда для использования
текстового редактора надо было изучать катастрофически сложную (по сегодняшним
меркам, естественно) систему "инопланетных" команд, программисты работали
с очень высокой производительностью. Мы не будем тратить время на изучение причин
этого явного парадокса. Вместо столь неблагодарного занятия лучше займемся чем-нибудь
более полезным…

Одиссеи не будет. Или?

Нас обделили. Или мы сами себя обделили — это уже не важно. Важно то, что
"обделенность" — факт. Ее совсем недавно с ехидством, неожиданным
для признанного мирового авторитета, "открыл" знаменитый специалист
в области искусственного интеллекта (AI) Марк Мински. "2001 год наступил.
И где же HAL?" — задал всего лишь один, но безответный вопрос Мински (для
тех, кто не знаком с творчеством Артура Кларка: HAL — это ставший знаменитым
сверхинтеллектуальный бортовой компьютер HAL-9000 космического корабля Discovery
из романа "Космическая Одиссея 2001"). Вместо HAL мы имеем "то,
что имеем" — непомерно раздувающиеся от сложности разноцветные погремушки,
становящиеся год за годом все цветастее, звонче и бесполезнее. И год за годом
производительность труда создателей этих "удовольствий" не то чтобы
совсем не изменяется, но уж точно — не растет. А ведь сегодня уровень технологических
средств несоизмеримо выше, чем в "эпоху несовершенства".

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

Транслятор — это важно

Транслятор — это обобщающее название для обширного класса программ, оперирующих…
другими программами. Обычно выполняемые трансляторами операции сводятся к трансформации
одной программы в эквивалентную другую. Заметьте, что пока ни слова не было
сказано о том, что речь идет именно об исполняемых программах — напротив, класс
трансляторов, предназначенных для программирования компьютеров, весьма узок.
Куда важнее "сторонние" применения трансляции. Стоит на секунду задуматься,
и окажется, что такая привычная программа, как броузер, — это транслятор, трансформирующий
язык HTML в команды "рисования" в экранной области памяти, и любой
текстовый процессор с возможностями форматирования — тоже транслятор скрытого
описания форматированного текста в команды "рисования" или вывода
на устройство печати, и сервер SQL СУБД, обслуживающий бухгалтерию, — также
транслятор языка SQL в последовательность низкоуровневых операций с базой данных.
Более того, электронные таблицы, калькуляторы, графические пакеты — все это,
по большому счету, трансляторы.

Когда-то вполне очевидный факт важности транслятора, как одного из основных
архитектурных элементов в проектировании программ, понимали очень хорошо. Этому
есть и свидетельство — стандартные и неотъемлемые в инструментальной ОС Unix
утилиты lex и yacc — инструменты проектирования трансляторов. Но со временем
ситуация изменилась… в худшую сторону. Новомодные "интегрированные среды"
уже не включают аналогичного инструментария, да и само его использование программистом
считается признаком "высшего пилотажа".

Своя дорога к HAL

"Утрамбовать" в объем этой статьи нечто, аналогичное "краткому
курсу проектирования трансляторов", автор даже и не пытался. Впрочем, для
подобного материала не хватило бы и объема всего журнала. Так что вместо рекомендаций
"как делать" (упаси Бог) здесь вы найдете рекомендации "как учиться
делать". Что тоже немаловажно.

Начнем с главного — теоретической подготовки. Раз уж мы завели речь о трансляторах
и языках, без основ теории не обойтись. Главный элемент этой теории — "теория
формальных языков". За страшным названием она скрывает изучение и формализацию
синтаксиса и семантики языка. Так ли это сложно изучить на уровне, достаточном
для практического применения знаний?

Когда мы используем наш естественный язык, то стремимся быть понятыми и понимать.
Для этого мы соблюдаем (даже если уже забыли их) правила, которым нас учили
в школе. Мы уже практически инстинктивно "правильно" строим предложения
и соблюдаем массу нюансов родного языка. Но все это слишком недостаточно формализовано
для того, чтобы стать основой хоть каких-то инструментов. В "теории формальных
языков" формализация правил куда более строгая и основывается на различных
"формах" описания языковых структур. Самая распространенная из них
— "форма Бэкуса-Наура" (БНФ) представления грамматической структуры
некоторого языка. Идею БНФ проще всего объяснить на коротком примере совершенно
бессмысленного языка, основанного на подмножестве русского.

Итак, в нашем "пиджин рашен" (примем такое название) грамматическая
форма ПРЕДЛОЖЕНИЕ может принимать форму упорядоченной последовательности "<ФРАЗА
СУЩ> (существительного) <ГЛАГОЛ> <ФРАЗА СУЩ>". Из предыдущего
предложения (определения) сразу можно сделать вывод — символ "=>"
является укороченной записью фразы "может принимать форму". Слова,
заключенные в скобки и использованные в правой части выражений, допускают так
называемое раскрытие. Все слова, которые находятся в правой части выражений
БНФ и не заключены в скобки, никаких раскрытий не допускают — наоборот, их
можно подставлять в качестве значения раскрываемой единицы. Такой "финальный"
характер подставляемых слов (или множеств символов в более общем случае) предопределил
их название — терминалы (окончательные значения). "Вооружившись"
столь мощной теорией и грамматикой БНФ, мы смело можем составлять предложения
на нашем синтетическом "пиджин рашен":

"ТИПА БРАТАН ГОНИШЬ КОНКРЕТНО БРАТАН",

"В НАТУРЕ СИЛА ЕСТЬ ЧИСТО СИЛА".

Замечательно! Синтетический язык оказался не таким уж синтетическим и вполне подходящим
для богатого сюжета чего-нибудь вроде "Брат-N".

Фривольный характер примера не должен отвлечь от главного — мы создали "новый"
язык с помощью грамматики, представленной БНФ. Большинство разработчиков существующих
языков программирования и представления данных тоже неизбежно проходили этот
этап. Быстро и без особых усилий углубиться в технику и теорию БНФ помогут и
многочисленные книги по соответствующей тематике (к ним можно отнести короткую
и отличающуюся простотой изложения работу В. Дж. Рейуорд-Смита "Теория
формальных языков", изданную на русском в 1988 г. издательством "Радио
и Связь", и соответствующие информационные источники в Internet). Главное
— из примера видно, что все это не так уж и страшно (хотя на самом деле намного
сложнее).

Вторая важнейшая "составляющая", знание которой необходимо на "своей
дороге к HAL", — так называемые регулярные выражения. Эта исключительно
мощная идиома, не требующая слишком больших усилий в изучении, настолько эффективна,
что стала одним из главных языковых средств, например, в ОС Unix. Регулярное
выражение (РВ) — способ лаконично, непонятно (на первый взгляд), но исключительно
удачно формализовать запись шаблона, идентифицирующего последовательности символов
с некоторыми свойствами. Определяется РВ на основе ряда понятий. Так, метасимволы
РВ — класс печатных символов, имеющих в РВ специальное значение, например метасимвол
"." (точка) в РВ определяет "один любой символ". Классы
символов РВ определяют, что очевидно, класс одного символа или диапазон его
значений. Например, запись вида [abz] является классом символов и определяет
один символ с возможным значением "a или b или z", запись вида [^abz]
определяет символ со значением "любой символ, но не a или b или z".
Диапазоны символов определяются в РВ с помощью схожих записей, например, [a-z]
определяет один символ, "любой из множества английских букв нижнего регистра".
В РВ есть еще и так называемы "якоря" — спецификаторы положения определяемого
символа в последовательности символов (в начале строки, в конце строки, первый
слева в слове и т. д.); "повторители", указывающие, сколько раз должно
быть применено то или иное правило РВ, "варианты", определяющие альтернативные
значения символа и даже… комментарии. Без последних разбираться со сложными
РВ, особенно для начинающих, — задача не из простых или приятных. Но… В умелых
руках РВ — инструмент уникальный, позволяющий, например, почти с иероглифической
эффективностью описывать очень сложные классы слов и предложений. Например,
иероглиф вида

<[A-Z][^a-zs]*>

на "человеческом" языке поясняется так: "последовательность
символов, состоящая из латинских букв верхнего регистра и, возможно, включающая
пробелы, табуляции, переводы строки, возвраты каретки". Как видите, даже
на таком простом примере РВ исключительно компактны. Но, что главное, для языка
РВ (как вы уже заметили, это — полноценный язык описания шаблонов) существуют
программы, способные очень быстро или классифицировать предъявленные строки
символов, сообщая о соответствии строки тому или иному шаблону РВ, или также
с реактивной скоростью отыскивать в строках фрагменты, соответствующие РВ-шаблону.
Естественно, что в такой ориентированной на работу со строками области, как
языки и трансляторы, РВ заняли почетное место одного из основных инструментов.

Изучить базовые возможности РВ достаточно легко, а полученные знания окупятся
сторицей даже для тех, кто не работает в насквозь пропитанной идеоматикой РВ ОС
Unix. Правда, для достижения настоящего мастерства в применении РВ надо потрудиться
на совесть — действительно хорошая книга "Mastering
regular expression" насчитывает… 366 страниц! Впрочем, руководство
по регулярным выражениям редактора VIM, написанное Олегом
Райским, при тщательном изучении также окажет неоценимую услугу, а
кросс-платформенная GUI-программа
VisualREGEXP не только на первых порах окажется очень полезной.

Итак, два главных направления уже известны. Дальше все зависит не от автора…
В обязательной части осталось одно "но" — зачем все это нужно для
"такого простого дела", как разработка транслятора. Не будем оттягивать
"момент истины" — и БНФ, и РВ используются на двух главных этапах
трансляции — лексического и грамматического разбора. Более того, современные
инструментальные средства почти полностью (или вообще полностью) автоматизируют
процесс перехода от представления вашего языка на уровне БНФ-описания и шаблонов
РВ для ключевых слов и прочих лексических элементов к программе, осуществляющей
"разбор" языка.

Транслятор — программа, которая может быть очень сложной или не очень сложной,
или даже очень простой. Все зависит от языков — исходной "программы"
и целевой. Но, безотносительно к уровню сложности, в любом современном трансляторе
присутствуют в той или иной форме определенные архитектурные элементы. Сначала
текст на исходном языке надо разбить на так называемые лексические элементы
— ключевые слова, имена, символы операций и пр. Этим занимается лексический
анализатор (ЛА), и это область, где "царствуют" РВ (что понятно, учитывая
формальный характер определения РВ, гибкость и быстродействие программ "распознавания"
по РВ-шаблонам). Данная фаза необходима из-за технологических ограничений —
лексические элементы бывают разной длины (если измерять ее в символах), сами
символы могут иметь разный размер. Использовать в большой программе такое "разнообразие"
не слишком удобно и достаточно накладно. Задача ЛА — "упростить жизнь",
выделив лексические элементы (ЛЭ) и поставив им в соответствие, например, целые
числа, уникальные для каждого уникального ЛЭ. А чтобы не "потерять"
информацию о реальных значениях ЛЭ, в составе любого транслятора присутствует
так называемая Символьная Таблица (СТ). СТ позволяет, используя целое число
(соответствующее ЛЭ) в качестве индекса, найти символьное представление ЛЭ.

Трансформированная во множество целых чисел и СТ исходная программа — результат
первого этапа трансляции. На втором этапе — грамматического разбора, транслятор
из потока чисел и СТ формирует нечто совершенно новое, а именно, иерархическое
представление "предложений" исходного языка в соответствии с БНФ-грамматикой.
Для нашего примера "пиджин-рашен" поток символов a la "герой
нашего времени" — "В НАТУРЕ СИЛА ЕСТЬ ЧИСТО СИЛА", транслятор
может трансформировать в такой результат грамматического разбора:

Раз речь идет об иерархическом представлении, то для него, естественно, наилучшим
визуальным представлением являются графы, и инструментарий graphdrawing (о котором
рассказывалось в предыдущей статье) — незаменимое подспорье в проектировании
трансляторов. А иерархия с четким соотнесением каждого лексического элемента
к определенному классу и месту в ней позволяет получить массу информации, ради
которой, собственно, и "строится" транслятор. В случае с нашим примером
можно создать дополнительную грамматику с аналогичным "пиджин инглиш"
и автоматически переводить перлы полюбившихся героев "Брата-N" на
адекватный английский язык.

Итак, в трансляторах все очень просто "с высоты птичьего полета".
Сложности начинаются в деталях. И опять наступило время для любимого автором
"но". Сегодняшнее состояние инструментальных средств позволяет о многих
сложностях забыть. А заодно и хорошенько подучиться, используя сопровождающую
эти средства документацию. Однако классикой пренебрегать не стоит — канонический
учебник А. Ахо, Дж. Ульмана "Компиляторы. Принципы, техника и инструменты"
— достойная для прочтения книга даже в том случае, если вы никогда не создадите
свой язык. А вот инструменты…

Их очень много, но к лучшим можно, без сомнения, отнести блестящую разработку
школы Н. Вирта COCO-R,
могучую систему сквозного проектирования трансляторов Gentle
и, наконец, известные системы PCCTS
и ANTLR. Общее для этих инструментов — они сопровождаются бесплатными
pdf-версиями отличных книг (для COCO-R,
для Gentle — входит в состав дистрибутива, для
PCCTS), кросс-платформенны, надежны, "честны" и не ресурсоемки.
Так что дело остается за "малым" — вашим желанием и трудолюбием.