Отношения между классами кс-языков

КС-язык называется языком некоторого класса КС-языков, если он может быть задан КС-грамматикой из данного класса КС-грамматик. Например, класс LL-языков составляют все языки, которые могут быть заданы с помощью LL-грамматик.

Соотношение классов КС-языков представляет определенный интерес, оно не совпадает с соотношением классов КС-грамматик. Это связано с многократно уже упоминавшейся проблемой преобразования грамматик. Например, выше уже говорилось о том, что любой LL-язык является и LR(1)-языком, то есть язык, заданный LL-грамматикой, может быть задан также и LR(1)-грамматикой. Однако не всякая LL-грамматика является при этом LR(1)-грамматикой и не всегда можно найти способ, как построить LR(1)-грамматику, задающую тот же самый язык, что и исходная LL-грамматика.

На рис. 4.5 приведено соотношение между некоторыми известными классами КС-языков.

Рис. 4.5. Соотношение между различными классами КС-языков

Следует обратить внимание прежде всего на то, что интересующий разработчиков компиляторов в первую очередь класс детерминированных КС-языков полностью совпадает с классом LR-языков и, более того, совпадает с классом LR(1)-языков. То есть доказано, что для любого детерминированного КС-языка существует задающая его LR(1)-грамматика. Проблема состоит в том, что не всегда возможно найти такую грамматику, и нет формализованного алгоритма, как ее построить в общем случае. То же самое относится к упоминавшимся здесь ОПК-грамматикам и ОПК(1,1)-грамматикам.

LL-языки являются собственным подмножеством LR-языков: всякий LL-язык является одновременно LR-языком, но существуют LR-языки, которые не являются LL-языками. Поэтому LL-языки образуют более узкий класс, чем LR-языки.

Языки простого предшествования, в свою очередь, также являются собственным подмножеством LR-языков, а языки операторного предшествования – собственным подмножеством языков простого предшествования. Интересно, что языки операторного предшествования представляют собой более узкий класс, чем языки простого предшествования.

В то же время языки простого предшествования и LL-языки несопоставимы между собой: существуют языки простого предшествования, которые не являются LL-языками, и в то же время существуют LL-языки, которые не являются языками простого предшествования. Однако существуют языки, которые одновременно являются и языками простого предшествования, и LL-языками. Аналогичное замечание относится также к соотношению между собой языков операторного предшествования и LL-языков.

Таким образом, соотношение классов КС-языков не совпадает с соотношением задающих их классов КС-грамматик. Это связано с неразрешимостью проблем преобразования и эквивалентности грамматик, которые не имеют строго формализованного решения.

Основные принципы построения трансляторов

Определение и назначение транслятора, компилятора, интерпретатора

Транслятор

Транслятор – это программа, которая переводит входную программу на исходном (входном) языке в эквивалентную ей выходную программу на результирующем (выходном) языке.

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

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

Чтобы создать транслятор, необходимо прежде всего выбрать входной и выходной языки. С точки зрения преобразования предложений входного языка в эквивалентные им предложения выходного языка транслятор выступает как переводчик. Поэтому и само слово “транслятор” (translator) означает “переводчик”.

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

Компилятор

Кроме понятия “транслятор” широко употребляется также близкое ему по смыслу понятие “компилятор”.

Компилятор – это транслятор, который осуществляет перевод исходной программы в эквивалентную ей объектную программу на языке машинных команд или на языке ассемблера.

Таким образом, компилятор является видом транслятора. Его результирующая программа всегда должна быть написана на языке машинных кодов или на языке ассемблера. Результирующая программа транслятора, в общем случае, может быть написана на любом языке – возможен, например, транслятор программ с языка Pascal на язык С. Соответственно всякий компилятор является транслятором, но не наоборот – не всякий транслятор будет компилятором.

Само слово “компилятор” происходит от английского термина “compiler” (“составитель”, “компоновщик”). Результирующая программа компилятора называется “объектной программой” или “объектным модулем”.

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

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

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

Другим видом транслятора является интерпретатор.

Интерпретатор – это программа, которая воспринимает входную программу на исходном языке и выполняет ее.

В отличие от компиляторов интерпретаторы не порождают результирующую программу (и вообще какого-либо результирующего кода) – и в этом принципиальная разница между ними. Интерпретатор, так же как и компилятор, анализирует текст исходной программы. Однако он не порождает результирующей программы, а сразу же выполняет исходную в соответствии с ее смыслом, заданным семантикой входного языка. Таким образом, результатом работы интерпретатора будет результат, заданный смыслом исходной программы, в том случае, если эта программа правильная, или сообщение об ошибке, если исходная программа неверна.

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

Этапы трансляции.

Статьи к прочтению:

Отношения между классами и объектами

Похожие статьи: