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

КС-язык называется языком некоторого класса КС-языков, если он может быть задан КС-грамматикой из данного класса КС-грамматик. Например, класс 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” (“со­ставитель”, “компоновщик”). Результирующая программа компилятора называется “объектной программой” или “объектным модулем”.

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

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

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

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

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

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

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

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