Системы генерации трансляторов

Владею русским со словарем, французским, хинди, испанским,
банту и другими с переводчиком.
Владимир Колечицкий

С точки зрения существующих алгорифмов синтаксического анализа, все языки и порождающие их грамматики делятся на два класса LL(n) и LR(n). Этот теоретический раскол в классе грамматик, распознаваемых анализаторами, построенными по принципу снизу вверх, и анализаторами, реализующими принцип сверху вниз, естественным образом наложил свой отпечаток и на практические реализации систем. В результате существуют системы с входными языками, специфицируемыми LR(n) и LL(n) грамматиками соответственно. Исторически первой системой, реализующей синтаксически управляемую трансляцию, была система уасс, входной язык которой принадлежит к классу LR(1) или, более точно, LALR(1). Система уасс, разработанная в 1972 году в рамках проекта Unix, успешно используется до сих пор, что, конечно, не может не свидетельствовать в пользу простоты и мощности идей, положенных в ее основу.

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

• BISON - реализация уасс, написанная в рамках проекта GNU;
• PCYACC (компании Abraxas Software (http://www.abxsoft.com/pcyacc.htm)). Это коммерческая реализация уасс, включающая в себя различные утилиты, упрощающие процесс разработки трансляторов. Среди них: документатор, отладчик, библиотекарь и т. д. В поставку включены спецификации грамматик многих современных языков программирования (С, C++, SQL и т. д.);
• Yacc++ (компании Compiler Resources, Inc. (http://world.std.com/~compres/)). Это расширение, целиком и полностью построенное на идеях объектно-ориентированного программирования. На выходе этой системы пользователь получает полноценную иерархию классов, реализующих трансляцию со специфицированного языка.

Естественное желание разработчиков пользоваться давно написанными средствами, прошедшими не один год тестовых испытаний в реальных проектах, отрицательно сказалось на количестве систем, транслирующих входные языки класса LL(n), т. е. реализующих двойственный подход к проблеме. Тем не менее, в рамках некоторых учебных проектов, а также в рамках проекта "Оберон" был создан ряд таких систем. Среди них следует отметить:

• SYNTAX - технологический комплекс, созданный в Санкт-Петербургском государственном университете под руководством профессора Б. К. Мартыненко.

Является интегрированной инструментальной системой, предназначенной для проектирования, разработки, реализации и тестирования средств синтаксически управляемой обработки данных;

• DEPOT4 (авторская разработка Юргена Лампе (Jurgen Lampe)). Это система, генерирующая трансляторы, работающие по принципу рекурсивного спуска. При этом допускается возможность регулированного отката при обнаружении неоднозначностей. Таким образом, при наличии требования на отсутствие левой рекурсии в правилах грамматики сама грамматика может быть и не 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/)). Это система, позволяющая грамматике входного языка быть контекстно-зависимой.

Системы анализа корректности программного кода

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

• lint (компании Sun Microsystems, Inc. (http://www.sun.com/)) для языка программирования С;
• PC-lint и FlexeLint (компании Gimpel Software (http://www.gimpel.com/)) анализируют программный код на языках С и C++.

Интерпретаторы

Не существует фактов, есть лишь их интерпретация.
Ф. Ницше

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

Декомпиляторы

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

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

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

Теория анализа потоков управления появилась давно, т. к. анализ активно применялся в компиляторах практически с момента их появления. Однако анализ потоков управления при компиляции имеет свою специфику - он используется в основном для целей оптимизации. Большинство алгоритмов анализа потоков управления, которые ориентированы на декомпиляцию, ставят своей целью уменьшение количества goto-выражений посредством введения новых логических переменных, дублирования кода (code replication) или использования конструкций высокого уровня, недоступных в большинстве широко используемых языков, таких как Pascal, С или C++.

В работах Кристины Цифуентес (Cristina Cifuentes) представлены алгоритмы, использующие минимальный набор инструкций высокого уровня: циклы типов while и do...while, if- и case-выражения. Управление выполнением объемлющих конструкций из вложенных не допускается. Причем эти алгоритмы используют оператор goto лишь тогда, когда граф управления не может быть структурирован никаким иным способом в пределах перечисленных конструкций.

Анализ практических достижений в области декомпиляции языка Java выполнил Дэйв Дайер (Dave Dyer) (http://www.javaworld.com/). Он сравнил между собой три наиболее известных к середине 1997 года декомпилятора: DejaVu, Mocha и WingDis. Дайер предложил систему тестирования декомпиляторов, основанную на интересной классификации допускаемых ими ошибок. В соответствии с этой системой все ошибки делятся на шесть категорий. "Тяжесть" ошибки возрастает с номером категории. Ошибки, в результате которых декомпилированная программа перестает собираться, но которые могут быть легко исправлены (например, отсутствие явного приведения типов там, где оно с очевидностью должно быть), относятся к первой, самой легкой категории, тогда как генерация правильного, но нечитаемого текста на Java считается ошибкой третьей категории. Заметим, что некоторые ошибки, проявляясь у одних декомпиляторов, полностью отсутствуют у других. Это свидетельствует о жизнеспособности такой классификации - она позволяет определить области, в которых одни декомпиляторы имеют преимущество над другими.

В настоящее время наиболее известны следующие декомпиляторы:

Не нашли, что искали? Воспользуйтесь поиском по сайту: