1.1. Структура транслятора

Рис. 1. Структура компилятора

Транслятором называется программа, обрабатывающая текст на некотором входном языке. Наиболее распространёнными видами трансляторов для языков программирования являются компиляторы и интерпретаторы. 

Компиляторы переводят текст программы с языка высокого уровня на язык низкого уровня – машинный код.

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

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

Анализирующая часть синтаксически управляемого транслятора состоит из лексического, синтаксического и контекстного анализаторов.

Лексический анализатор преобразует входной символьный поток в последовательность более крупных единиц –  лексем. Например, текст из 14 символов (включая пробелы)

"x1-3.5+x2 <> y" 

преобразуется в последовательность из 7 лексем

[id(x1),`-,n(3.5),`+,id(x2),'<>',id(y)].

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

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

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

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

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

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

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

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