Реализация языков программирования

Алгоритмические языки высокого уровня в отличие, скажем, от языка макроассемблера, в значительной степени потеряли непосредственную связь с машинным языком. Это дистанцирование, то есть стремление сделать язык машинно-независимым, приблизить его к предметной области и алгоритмам, потребовало создания инструментов, позволяющих выполнить программы на ЭВМ. Иными словами, мы должны выразить смысл конструкций АЯВУ в терминах машинного языка. Два основных способа сделать это реализуются соответственно интерпретаторами и трансляторами.

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

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

Формально говоря, каждый язык программирования L сопоставляет тексту программы p некоторый смысл, например, функцию L [ p ], отображающую входные данные в выходные. Интерпретатором для языка L в языке I, называется программа int, записанная в языке I, удовлетворяющая следующему свойству

I [ int ](p, d) = L [ p ](d)

Иными словами, интерпретатор на вход получает программу p в языке L и её данные d и делает то же, что и программа p над данными d. Отметим, что в данных рассуждениях одна и та же программа p присутствует как пассивно, т.е. как данное, которое можно, в частности, передать на вход интерпретатору, так и активно – как функция, которая приписывается ей языком L.

Трансляторы

Вотличие от интерпретатора транслятор можно сравнить с литературным переводчиком. Он получает текст либо сразу целиком, либо значительную его часть, имеет возможность прочитать и проанализировать текст многократно, сделать подстрочный перевод и лишь в конце составить окончательный текст. Именно то, что этот процесс в значительной степени заключается в «составлении» текста, объясняет другое название – компилятор. При этом родной язык переводчика может отличаться как от входного, так и выходного языка. Таким образом, формально транслятор (компилятор) с языка L ₁ в язык L ₂ – это программа comp на языке I, удовлетворяющая следующему свойству: если p – программа на языке L ₁, то I [ comp ](p) – есть программа obj на языке L ₂, такая что для любых данных d

L ₂[ obj ](p) = L₁[ p ](d)

Основное отличие от интерпретатора заключается в том, что компилятор не выполняет входную программу, а только переводит её на другой язык.

Т-диаграммы

Графически мы будем изображать интерпретатор прямоугольником, в верхней части которого указан реализуемый язык, а в нижней – язык, на котором интерпретатор написан:

LI

  

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

Для графического изображения транслятора используется T-блок, в основаниии которого указывается язык реализации, слева – входой язык транслятора, справа – выходной:

L1àL2 I

 

Входные данные, т.е. программы на языке L₁ подаются слева, а результат указывается справа.

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

И

К

Р

ИàР Р

РàК Р

 

 

где блоки, помеченные буквами И, Р и К означают тексты на итальянском, руском и китайском языке соответственно. Заметим, что здесь мы предполагали, что оба переводчика «думают» по-русски. Правильнее было бы полагать, что у нас есть не переводчики, а инструкции по переводу на русском языке, которые мы, как носители языка, можем «исполнять» без посторонней помощи. Если же одна из инструкций оказалась написана на другом языке, скажем на немецом (Н), то для того, чтобы её выполнить нам потребовалась бы помощь интерпретатора,

НР

Р

ЯàР Н

 

ЯàР Н

НàР Р

ЯàР Р

либо следовало предварительно перевести инструкцию с немецкого на русский,

 

и затем использовать её по старой схеме.

Типичным примером многофазной трансляции является трансляция с языка высокого уровня в язык ассемблера, который затем траслируется в машинные команды «штатным» транслятором. Пошаговая трансляция может состоять из более чем двух шагов. Так, например, одна из возможных реализаций языка C++ состоит в том, чтобы сначала перевести его в язык C, затем с языка C – в язык ассемблера, и, наконец, с языка ассемблера в машинный язык.

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

КàЭ Н

К

И

Э

Э

ИàЭ Н

Э

ЭР

Э

ЭС

 

 

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

И

ИР

РК

 

 

 

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

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

C0àA A

 

C0àA С0

После этого мы тут же переписываем этот транслятор на языке С₀:

 

 

C0àA C0

C0àA A

C0àA A

Поскольку второй транслятор является программой на языке C₀, то мы можем применить к нему первый транслятор

 

 

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

Далее мы шаг за шагом расширяем язык, добавляя в него новые конструкции. Например, на следующем шаге мы добавляем сложные выражения с возможностью использования скобок и учётом приоритета операций, получая язык C₁. Затем добавляем структурные управляющие операторы if, while, switch – язык C₂, затем – сложные структуры данных – язык C₃, и т.д. И каждый раз мы реализуем язык C_i+1 на языке C_i, поскольку, имея исполняемый транслятор с C_i в ассемблер, мы можем получить и исполняемый транслятор с C_i+1  в ассемблер:

Ci+1àA Ci

CiàA A

Ci+1àA A

 

 

В конце этого процесса, когда будут включены уже все конструкции языка C, осталось выкинуть всё лишнее, что мы вставили в C₀.

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

Сi+1Сi

Ci A

Сi+1A

 

Один из возможных подходов к реализации этого преобразования дают смешанные вычисления, которые выходят за рамки данного курса.

CàA A

CàB A

CàB C

Предположим теперь, что мы уже реализовали язык С для одной машины (A) и нам необходимо реализовать его для другой (B). Совсем не обязательно повторять весь процесс раскрутки на новой машине – можно использовать так называемую кросс-компиляцию. Всю работу по созданию нового транслятора мы выполняем на старой машине,

 

CàB C

CàB B

CàB A

используя новую лишь для проверки того, что разрабатываемый транслятор порождает правильный код для машины B. Когда же разработка закончена, мы применяем его к самому себе, получая транслятор, исполняемый на машине B и геренерирющий код для этой же машины:

 

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