Анализ существующих продуктов и сравнение.

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

Рассмотрим наиболее популярные из них и выделим их достоинства и недостатки.

YACC, LEX

Одним из самых ранних инструментов подобного типа стала связка YACC, LEX. Эти две утилиты появились вначале 1970-х годов для системы UNIX. YACC расшифровывается как Yet another compiler-compiler (еще один компилятор компиляторов). Он был разработан С. Джонсоном и применялся для создания многих компиляторов.

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

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

expr : expr '+' expr
     | expr '-' expr
     | expr '*' expr
     | expr '/' expr


YACC позволяет работать с грамматиками класса LALR, этот класс грамматик очень широк и конструкции многих языков программирования могут быть описаны с помощью этих грамматик. По входной грамматике YACC генерирует программу на языке C, которая является синтаксическим анализатором для исходной грамматики. Этот анализатор реализует алгоритм перенос-свертка, и является достаточно эффективным и быстродействующим. YACC имеет несколько механизмов решения конфликтов неоднозначности (СВЕРТКА-СВЕРТКА, ПЕРЕНОС-СВЕРТКА).

Для анализа входной цепочки программа, сгенерированная YACCом вызывает специальную функцию, которая поставляет набор лексем (функция лексического анализатора). Эта функция реализуется с помощью LEXа. Исходными данными для LEXа является набор регулярных выражений, представляющих различные классы лексем. LEX строит по ним детерминированный конечный автомат (ДКА), реализацию которого пользователь получает в виде готовой функции лексического анализатора для синтаксического анализатора.

Самым сложным является написание семантических процедур для YACC. Эти процедуры определяют семантику языка и реализуют проверки типов данных, контроль за необъявленными идентификаторами, построение таблиц идентификаторов, вычисление атрибутов, генерацию кода и т.д. YACC имеет возможность назначать атрибуты и вычислять их для отдельных токенов, однако вы можете для каждого токена задать лишь один атрибут.

Отсутствие графического интерфейса и удобных средств разработки усложняют работу с этой системой. Пользователь вынужден использовать самые примитивные средства для создания компилятора, такие как текстовый редактор и командный процессор. Отсутствие средств "отладки" или проверки грамматики усложняет ее написание, т.к. разработка корректной формальной грамматики является сложным процессом. Человек может не учесть некоторых конструкций языка, или "случайно" добавить новые. Для многих окажется неудобным тот факт, что существует возможность сгенерировать синтаксический анализатор лишь для языка C. На сегодняшний день программисты используют многие языки программирования и наверняка захотят использовать C++, Java, Delphi (Pascal), Visual Basic, SmallTalk и другие.

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

JavaCC

С ростом популярности языка Java появилась необходимость в создании синтаксических анализаторов и компиляторов на этом языке программирования (сам компилятор Java написан на Java). В связи с этим и появился специальный инструмент для создания компиляторов на Java- JavaCC (Java compiler-compiler). Изначально этот инструмент был разработан и поддерживался компанией Sun Microsystem, потом он перешел к компании MetaMata, а сейчас им владеет WebGain.

Этот инструмент также очень похож на YACC. Для него создаются специальные файлы с описанием грамматики и семантическими процедурами. По этой входной информации создается Java класс- синтаксический анализатор для требуемого языка.

С точки зрения интерфейса пользователя этот инструмент очень похож на YACC. JavaCC представляет собой утилиту командной строки. Пользователь должен создать специальный файл- описание языка в специальном виде, напоминающем EBNF. Затем JavaCC создаст по данному описанию набор специальных Java классов, представляющих собой парсер. Для задания семантики необходимо написать набор семантических процедур на языке Java.

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

К достоинствам данного пакета следует отнести надежность, переносимость (это достоинство наследуется от Java), наличие большого числа готовых грамматик для различных языков (в т.ч. и для Java). Нельзя оставить без внимания и тот факт, что инструмент бесплатный (его можно скачать с сайта компании WebGain (www.webgain.com))

Прочие программные системы.

Две описанные выше утилиты пользуются наибольшей популярностью и наиболее распространены, однако это не единственные инструменты подобного рода. Существует еще множество других. Многие из них являются своего рода расширением уже существующих систем(YACC++, AYACC, AFLEX) или модифицированными версиями (Bizon), существуют также визуальные надстройки (New YACC).

Приведем краткое описание некоторых принципиально отличающихся систем:

RDP компилирует атрибутные LL(1) грамматики, украшенные семантическими действиями языка C, в компиляторы на основе рекурсивного спуска.

S/SL является языком программирования для конструирования компиляторов. Он включает последовательность, повторение и выбор; ввод, сравнение и вывод токенов; вывод сообщений об ошибках; подпрограммы; вызов семантических операций.

Visual Parse++ предоставляет визуальный интерфейс, позволяющий любому программисту интерактивно изучать и применять технологии лексического и синтаксического анализа.

PRECC eXtended генератор компиляторов с бесконечным заглядыванием вперед для контекстно-зависимых грамматик. Спецификации описываются в РБНФ с наследуемыми и синтезируемыми атрибутами.

ProGrammar Developer's Toolkit - интегрированный набор инструментов и утилит для создания, тестирования и отладки синтаксических анализаторов. Он включает в себя объектно-ориентированный язык, визуальную среду разработки и интерактивный отладчик. Цена пакета 500 долларов США за одну лицензию на один компьютер.

Из представленных выше продуктов наибольший интерес с точки зрения работы с формальными грамматиками представляет продукт ProGrammar Developer's Toolkit. Однако его цена представляется серьезным препятствием для широкого внедрения. Visual Parse++ также достоин внимания, однако проект по всей видимости закрыт, т.к. сайт этой системы не отвечает на запросы.

Parser Development System

Разрабатываемый пакет содержит в себе средства визуального проектирования формальных грамматик. Он позволяет создавать свои грамматики, выполнять над ними различные преобразования (удаление левой рекурсии, удаление бесполезных символов, удаление пустых правил...). Анализ класса грамматики является очень необходимым и полезным преимуществом нашей системы. Анализ класса грамматики позволяет легко определить принадлежит ли грамматика к классам ЛЛ1, предшествования, слабого предшествования, операторного предшествования, LR0, SLR1, LALR, а также позволяет легко определить "проблемные" участки. Так, например, при анализе ЛЛ1 грамматики вам будут выданы все замечание, найденные в вашей грамматике и вы сможете легко определить, что необходимо поправить, чтобы привести ее к необходимому виду.

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

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

Для внутреннего и внешнего "общения" между частями системы и другими программами используется XML формат. С его помощью осуществляется передача структур данных от одного программного модуля к другому, сохранение исходных данных. XML позволяет создавать различные модули системы на разных языках программирования, использую для этого все имеющиеся средства. Так, например, нами были использованы Visual C++ 6.0, Java, Delphi.

Особо хочется отметить возможность быстрого преобразования XML файлов в документы HTML для публикации в Web с помощью преобразования XSL. Используя эту возможность, вы можете из полученного XML документа создать HTML страницу с его визуальным представлением. Вот небольшой пример- LL1 таблица полученная как результат работы алгоритма и преобразованная в наглядную форму в формате HTML с помощью XSL преобразования:

Для всех типов XML документов, используемых в системе, существуют соответствующие XSL фильтры, также разработана специальная программа, позволяющая осуществлять это преобразование. На основе существующих фильтров можно легко создать новые, в которых осуществить собственные варианты оформления документов.

Это достоинство становится более очевидно если обратить внимание на возможность использования программы в Internet. Для этого можно использовать консольную версию программы (CGI) или Java версию (Servlet, JSP). Таким образом, необходимо лишь получить выходной файл от программы и пропустить его через соответствующий XSL.

Проект также удачен с точки зрения управления. Основной проблемой при создании больших программных систем является контроль над созданием кода. Чаще всего с этими сложностями приходится сталкиваться при работе нескольких программистов над одним общим модулем системы. Брукс в своей книге "Мифический человеко-месяц" указывает на эту проблему и говорит о том, что при взаимодействии нескольких человек суммарная производительность растет не линейно, в зависимости от количества человек, а лишь логарифмически, так как часть ресурсов приходится тратить на взаимодействие участников команды. Таким образом, ухудшается управляемость процесса разработки, т.к. приходится контролировать не только каждого человека, но и каждую связь человек-человек. Выходом из этой ситуации является четкая декомпозиция системы и использование общих стандартов.

Декомпозиция позволяет решить большую задачу путем разбиения ее на более мелкие. Каждая маленькая задача должна решаться почти очевидным способом. Если это не так стоит разбить ее еще на несколько маленьких задач. В идеале каждая такая маленькая задача должна решаться одним человеком за два-три дня.

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

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

Для соблюдения этого требования были использованы открытые стандарты (COM, ActiveX, XML, XSL). А также разработаны свои (компонент менеджер). Это позволило определить способ написания отдельного компонента для системы, способ взаимодействия с другими компонентами, формат передаваемых данных (XML). Каждый компонент может быть написан одним человеком в течении нескольких дней, после чего компонент можно добавить в систему без полной перекомпиляции. Таким образом, третья фирма может разработать свой компонент для нашей системы и, не имея исходных кодов, расширить функциональность. Такой подход был использован многими фирмами в создании своих продуктов (MSOffice от Microsoft, Delphi от Inprise...), что определило грандиозный успех этих продуктов.

Немаловажно отметить, что продукт разрабатывается в трех версиях- консольное приложение, приложение с полноценным пользовательским интерфейсом для Win32 и Java приложение. Это определяет круг потенциальных пользователей системы. Таким образом, ее можно будет использовать как обычное приложение Win32, консольное приложение (Unix, Windows), Internet приложение. Причем стоит отметить, что все эти версии совместимы друг с другом на уровне исходных данных. Консольная версия приложения написана с учетом минимальных требований к системе. Для ее написания использовался стандарт C++, что позволяет перенести ее на любую платформу, для которой существует компилятор C++ (Win, Unix, Linux, Solaris, DOS...). Версия с полным визуальным интерфейсом обладает наибольшей привлекательностью для пользователей с современными компьютерами, т.к. позволяет наиболее эффективно использовать визуальное отображение информации. Итак, система ориентирована практически на все типы компьютеров и операционных систем. Таким образом, ее может использовать каждый, на любом компьютере и операционной системе. Это определяет круг потенциальных пользователей системы и он весьма внушителен.

С начала создания продукта был создан Internet сайт (ukman.narod.ru), на котором помещалась информация о развитии продукта. Сайт был зарегистрирован во многих поисковых системах и на нем за несколько месяцев побывало несколько сотен человек, скачано несколько десятков предварительных версий программы, это говорит о востребованности продукта на современном рынке.