5.2.4.3. Системы генерации трансляторов
Владею русским со словарем, французским, хинди, испанским, банту и другими с переводчиком. Владимир Колечицкий
С точки зрения существующих алгорифмов синтаксического анализа, все языки и порождающие их грамматики делятся на два класса LL(n) и LR(n). Этот теоретический раскол в классе грамматик, распознаваемых анализаторами, построенными по принципу снизу вверх, и анализаторами, реализующими принцип сверху вниз, естественным образом наложил свой отпечаток и на практические реализации систем. В результате существуют системы с входными языками, специфицируемыми LR(n) и LL(n) грамматиками соответственно. Исторически первой системой, реализующей синтаксически управляемую трансляцию, была система уасс, входной язык которой принадлежит к классу LR(1) или, более точно, LALR(1). Система уасс, разработанная в 1972 году в рамках проекта Unix, успешно используется до сих пор, что, конечно, не может не свидетельствовать в пользу простоты и мощности идей, положенных в ее основу.
Однако, несмотря на простоту и ортогональность архитектуры этой системы, нельзя не отметить также и некоторую многословность, появляющуюся при попытке спецификации сложной грамматики на входном языке системы, а также узкую ориентированность на язык С, как язык реализации построенного по грамматике транслятора. Эти и некоторые другие ограничения и послужили основной движущей силой, давшей жизнь целому семейству систем, имеющих своим прототипом оригинальный уасс. Перечислим некоторые из них:
BISON - реализация уасс, написанная в рамках проекта GNU (http://www.gnu.org/software/bison/bison.html);
PCYACC (компании Abraxas Software (http://www.abxsoft.com/pcyacc.htm)). Это коммерческая реализация уасс, включающая в себя различные утилиты, упрощающие процесс разработки трансляторов. Среди них: документатор, отладчик, библиотекарь и т. д. В поставку включены спецификации грамматик многих современных языков программирования (С, C++, SQL и т. д.);
Yacc++ (компании Compiler Resources, Inc. (http://world.std.com/~compres/)). Это расширение, целиком и полностью построенное на идеях объектно-ориентированного программирования. На выходе этой системы пользователь получает полноценную иерархию классов, реализующих трансляцию со специфицированного языка.
Естественное желание разработчиков пользоваться давно написанными средствами, прошедшими не один год тестовых испытаний в реальных проектах, отрицательно сказалось на количестве систем, транслирующих входные языки класса LL(n), т. е. реализующих двойственный подход к проблеме. Тем не менее, в рамках некоторых учебных проектов, а также в рамках проекта "Оберон" был создан ряд таких систем. Среди них следует отметить:
SYNTAX - технологический комплекс, созданный в Санкт-Петербургском государственном университете под руководством профессора Б. К. Мартыненко (http://www.niimm.spb.su/~mbk/syntax/syntax.html).
Является интегрированной инструментальной системой, предназначенной для проектирования, разработки, реализации и тестирования средств синтаксически управляемой обработки данных;
DEPOT4 (авторская разработка Юргена Лампе (Jurgen Lampe) (http://%20www.math.tu-dresden.de/wir/depot4/depot4.html)). Это система, генерирующая трансляторы, работающие по принципу рекурсивного спуска. При этом допускается возможность регулированного отката при обнаружении неоднозначностей. Таким образом, при наличии требования на отсутствие левой рекурсии в правилах грамматики сама грамматика может быть и не LL(1). Естественно, что чем ближе грамматика к классу LL(1), тем более быстрый транслятор можно будет с нее получить;
LLGEN (является частью большого учебно-коммерческого проекта, известного под названием Amsterdam Compiler Kit - АСК (http://www.cs.vu.nl/vakgroepen/cs/ack.html)). Она также генерирует трансляторы, работающие по принципу рекурсивного спуска.
Представленная картина оказалось бы неполной, если бы мы не рассмотрели здесь экспериментальные системы, реализующие нестандартные подходы к проблеме спецификации и реализации трансляций. Вот очень короткий список таких проектов:
ALE - Attribute-Logic Engine (авторская разработка Боба Карпентера (Bob Carpenter) и Джеральда Пенна (Gerald Penn) (http://www.cs.toronto.edu/~gpenn/ale.html)). Система, базирующаяся на принципах искусственного интеллекта;
EAG (ftp://hades.cs.kiin.nl/pub/eag/). Система, в основе которой лежат расширенные аффиксные грамматики;
PRECC (авторская разработка Питера Брюера (Peter Breuer) и Джонатана Боуена (Jonathan Bowen) (http://www.afm.sbu.ac.uk/precc/)). Это система, позволяющая грамматике входного языка быть контекстно-зависимой.
- 5. Системы программирования
- 5.1. Введение в системы программирования
- 5.1.1. Основные понятия и определения
- 5.1.2. История и эволюция
- 5.1.2.1. Некоторые важные даты
- 5.1.2.2. Основные этапы в формировании состава систем программирования
- 5.1.2.3. История развития системы программирования компании Borland Inc. На базе языка Pascal
- 5.1.3. Классификация
- 5.1.3.1. Классификация по ориентации на поддержку процессов
- 5.1.3.2. Функциональная классификация
- 5.1.3.3. Классификация по категориям
- 5.1.3.4. Классификация по предоставляемому интерфейсу
- 5.1.4. Проблемы и перспективы развития
- 5.1.5. Рекомендации по литературе
- 5.2. Процесс-ориентированный инструментарий
- 5.2.1. Возникновение и исследование идеи
- 5.2.2. Управление
- 5.2.2.1. Системы управления проектами
- 5.2.2.2. Организационные средства
- 5.2.2.3. Средства оценки качества
- 5.2.3. Анализ требований и проектирование
- 5.2.3.1. Системы на основе структурной методологии
- 5.2.3.2. Системы на основе объектно-ориентированной методологии
- 5.2.4. Программирование (реализация)
- 5.2.4.1. Трансляторы
- 5.2.4.2. Компиляторы
- 5.2.4.3. Системы генерации трансляторов
- 5.2.4.4. Системы анализа корректности программного кода
- 5.2.4.5. Интерпретаторы
- 5.2.4.6. Декомпиляторы
- 5.2.4.7. Усложнители декомпиляции (шифраторы, обфускаторы)
- 5.2.4.8. Системы управления компиляцией и построением программ
- 5.2.5. Тестирование и отладка
- 5.2.5.1. Тестовые мониторы
- 5.2.5.2. Средства отслеживания тестового покрытия
- 5.2.5.3. Средства динамического построения профиля программы
- 5.2.5.4. Системы построения срезов программы
- 5.2.5.5. Отладчики
- 5.2.5.6. Системы отслеживания проблем (ошибок)
- 5.2.6. Ввод в действие
- 5.2.7. Сопровождение
- 5.2.8. Завершение эксплуатации
- 5.3. Универсальный инструментарий
- 5.3.1. Инструменты работы с текстом
- 5.3.1.1. Средства, базирующиеся на регулярных выражениях
- 5.3.1.2. Средства поиска различий
- 5.3.1.3. Средства поиска на основе шаблонов
- 5.3.1.4. Обозреватели и базы данных программ
- 5.3.1.5. Средства обнаружения плагиата
- 5.3.1.6. Текстовые редакторы
- 5.3.1.7. Синтаксически-ориентированные редакторы
- 5.3.1.8. Гипертекстовые средства
- 5.3.2. Системы документирования
- 5.3.3. Системы разработки интерфейсов
- 5.3.4. Системы управления базами данных
- 5.3.5. Системы управления базами знаний и экспертные системы
- 5.3.5.1. Системы искусственного интеллекта
- 5.3.5.2. Механизмы выводов на знаниях
- 5.3.5.3. Неточный вывод на знаниях
- 5.3.6. Электронные библиотеки и инструментарий Интернета
- 5.3.6.1. Парадигма усиления информации
- 5.3.6.2. Профессиональный поиск информации
- 5.3.6.3. Проблемы работы с информационными ресурсами Интернета
- 5.3.6.4. Коллекции информационных ресурсов в Интернете
- 5.3.6.5. Базы данных в Интернете
- 5.3.6.6. Краткая история поисковых средств Интернета
- 5.3.6.7. Искусственный интеллект и задача поиска в Интернете
- 5.4. Инструментарий поддержки процессов некоторых технологических подходов
- 5.4.1. Системы формального преобразования и верификации программ
- 5.4.2. Средства сборочного программирования
- 5.5. Инструментальные системы
- 5.5.1. Инструментальные среды программирования
- 5.5.2. Средства автоматизации разработки программ (case-средства)
- 5.5.3. Интегрированные среды
- 5.5.4. Репозитории проекта
- 5.6. Средства поддержки коллективной разработки
- 5.6.1. Системы разделения файлов
- 5.6.1.1. Система управления версиями файлов
- 5.6.1.2. Система управления пространствами
- 5.6.1.3. Система синхронизации удаленных пространств
- 5.6.2. Системы поддержки работы виртуальных групп
- 5.7. Естественно-языковый интерфейс
- 5.7.1. Диалоговые системы
- 5.7.2. Вопросно-ответные системы
- 5.7.3. Автоматизированные обучающие системы и системы контроля знаний
- 5.7.4. Системы искусственного интеллекта