В.Ш. Кауфман - Языки программирования - концепции и принципы (1990) (1160787), страница 80

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 80)

[Данное определение проекции выглядит совершенно симметричным

относительно языков LL1 и LL2, хотя они содержательно играют различные роли.

Чтобы подчеркнуть эти роли, иногда говорят, что проекция - частичное

многозначное отображение из L1 в L2

p : L1 -> L2 ].

20.1.3. Три принципа создания компиляторов

Небольшой опыт по созданию компилятора у нас уже есть. В модели МТ мы

практиковались в создании компилятора с языка обычных (инфиксных) выражений

в польскую инверсную запись (в язык постфиксных выражений).

Наш компилятор представлял собой программу из четырех предложений:

{ e1 + e2 } R -> { e1 } { e2 } + .

{ e1 * e2 } R -> { e1 } { e2 } * .

{ ( e ) } -> { e } .

{ e } -> e .

Проекция р, соответствующая этому компилятору, должна удовлетворять

определяющему соотношению

p(F1 op F2) = p(F1) p(F2) op

где F1, F2 - правильные инфиксные формулы, ор - операция.

Уже на примере такого простого компилятора можно продемонстрировать три

важные положения.

Во-первых, созданию компилятора должна предшествовать разработка

связанной с ним проекции. Это не обязательно означает, что проекция

полностью фиксируется до начала программирования компилятора. Но, во всяком

случае, ее замысел предшествует разработке соответствующего алгоритма

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

Например, четыре предложения нашего компилятора не могли быть написаны, если

бы мы фактически не "держали в голове" приведенное определяющее соотношение

для проекции.

а) Проекционный принцип. Указанные выше соображения можно оформить в

виде проекционного принципа [41]: создание компилятора можно разбить на два

технологически независимых этапа - П-этап или этап разработки проекции и А-

этап или этап алгоритмизации проекции. Полученное на П-этапе описание

проекции (например, в виде системы определяющих соотношений) может служить

техническим заданием (спецификацией) для работы на А-этапе. Опыт показывает,

что в некоторых практически важных случаях А-этап удается полностью

автоматизировать. Делаются попытки частично автоматизировать и П-этап. Это

удается за счет предварительного формального описания как исходного, так и

целевого языка сходным образом на одном и том же метаязыке. В отличие от БНФ

такой метаязык должен позволять описывать не только синтаксис, но и

семантику ЯП. В сущности, при этом приходится создавать проекцию

описываемого ЯП на метаязык. Так что П-этап всегда носит творческий

характер. К реальным языкам индустриального программирования автоматизация

П-этапа пока неприменима из-за непрактичности метаязыков и соответствующих

систем построения трансляторов (СПТ).

б) Принцип вспомогательных переводов. Когда проекция достаточно

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

фазы компиляции - фазу анализа и фазу синтеза. В нашем примере мы воплощали

первую фазу левой частью МТ-предложения, вторую - правой.

При этом результаты первой фазы представляются на некотором

промежуточном языке, так что и анализ, и синтез иногда оказывается полезным

в свою очередь считать трансляцией (соответственно с исходного языка на

промежуточный и с промежуточного на целевой). С другой стороны, в отличие от

исходного и целевого ЯП язык МТ выступает в нашем компиляторе в роли еще

одного вспомогательного ЯП (инструментального ЯП, т.е. языка, на котором

написан компилятор).

Сказанное подчеркивает рекурсивную природу трансляции и может быть

выделено как принцип вспомогательных переводов: транслятор можно построить

из трансляторов для вспомогательных языков. Это наблюдение широко

исполььзуется в различных методах и приемах создания трансляторов.

Тройственную связь исходного, целевого и инструментального ЯП удобно

изображать Т-образной диаграммой

____________________

| |

| L1 --> L2 |

|_____ _____|

| |

| I |

|______|

С ее помощью легко описываются довольно сложные процессы, связанные с

жизненным циклом компилятора (в частности, так называемая раскрутка, активно

использующая вспомогательные переводы и применяемая при переносе

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

в) Принцип синтаксического управления (структурной индукции).

Анализ и синтез далеко не всегда удается столь четко сопоставить

некоторому определенному конструкту инструментального ЯП, как это сделано в

нашем простом примере.

Дело в том, что в языке МТ непосредственными составляющими при анализе

выражения могут быть только выражения, термы и символы. При компиляции с

более сложных исходных ЯП приходится переводить операторы, объявления,

области действия и т.п. Анализ исходного текста и синтез соответствующего

целевого не удается представить в этих случаях одним предложением. И для

анализа, и для синтеза приходится писать специальные подпрограммы.

В первых компиляторах взаимодействие таких подпрограмм было довольно

запутанным. Но уже в начале 60-х годов Айронсом был предложен принцип

упорядочивания этого взаимодействия на основе иерархической структуры

исходных текстов. Структура эта задается синтаксисом исходного языка,

поэтому сам принцип получил название принципа синтаксического управления

трансляцией (компиляцией в частности).

В синтаксически-управляемых компиляторах синтаксическим категориям

исходного языка ставятся в соответствие так называемые семантические

действия. Они то и синтезируют целевой текст в процессе так называемой

структурной индукции.

В этом процессе семантические действия, соответствующие определенным

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

соответствующих непосредственным компонентам этих категорий. Структура, по

которой ведется индукция, строится в процессе анализа (декомпозиции)

исходного текста в соответствии с определением исходного ЯП.

Принцип синтаксического управления и структурную индукцию можно в

первом приближении понять на примере нашего компилятора для перевода

выражений.

При этом левые части МТ-предложений выполняют декомпозицию (выделяя

сумму, произведение, скобочную первичную формулу), а правые части -

структурную индукцию, пользуясь уже готовыми переводами компонент

соответствующих синтаксических категорий.

В нашем компиляторе анализ и синтез чередуются (компилятор

однопроходный). Но можно сначала полностью проанализировать исходный текст,

получив в результате его структуру (обычно в виде синтаксического дерева -

это вариант промежуточного языка), а затем (на втором проходе) выполнить

структурную индукцию. Иногда применяют и большее число проходов (обычно при

ограничениях на память для размещения компилятора или при необходимости

оптимизировать программу).

Итак, мы выделили один из принципов, позволяющий структурировать

процесс создания транслятора - проекционный принцип; один из принципов,

позволяющих структурировать сам компилятор - принцип вспомогательных

переводов, и один из принципов, позволяющих структурировать синтез - принцип

синтаксического управления (несколько упрощая, можно отождествить его с

принципом структурной индукции).

[Отметим, что термин "структурная индукция" обозначает также один из

способов доказательства свойств структурированных объектов.]

Подчеркнем, что сам ЯП несравненно стабильнее (консервативнее), чем

аппаратура и методика реализации. С другой стороны, последняя авторская

реализация Модулы-2 выполнена оправдавшими себя методами двадцатилетней

давности - еще одно подтверждение принципа чайника. В сущности, лишь вопрос

о принципиальной возможности или невозможности реализации в современных

условиях кардинально влиет на грамотно проектируемый ЯП. В остальном влияние

реализаторской позиции обычно преувеличивают.

20.2. Классификация языков программирования

20.2.1. Традиционная классификация

Изучение ЯП часто начинают с их их классификации. Различают ЯП низкого,

высокого и сверхвысокого уровней; процедурные и непроцедурные, диалоговые и

пакетные; вычислительной, коммерческой, символьной ориентации; выделяют ЯП

системного программирования, реального времени, "параллельные" ЯП; даже

классические, новые и новейшие.

Определяющие факторы классификации обычно жестко не фиксируются. Чтобы

создать у читателя представление о характере типичной классификации, опишем

наиболее часто применяемые факторы, дадим им условные названия и приведем

примеры соответствующих ЯП.

Обычно выделяют следующие факторы:

1. Уровень ЯП - обычно характеризует степень близости ЯП к архитектуре

компьютера. Так, автокод (ассемблер) относят к ЯП низкого уровня; Фортран,

Паскаль, Аду называют ЯП высокого уровня; Язык Сетл [42], созданный

известным математиком Дж.Щварцем, обычно служит примером ЯП "очень высокого

уровня" (иногда говорят сверхвысокого уровня) - его базис составляют

теоретико-множественные операции, далекие от традиционной архитектуры

компьютеров. Встречаются и другие толкования уровня ЯП - это довольно

расплывчатое, однако часто используемое понятие.

В "науке о программах" Холстеда [43] сделана интересная попытка

придать этому понятию точный смысл. Уровень ЯП по Холстеду определяется

отличием программ на этом ЯП от простого вызова процедуры, решающей

поставленную задачу. Выводится формула, численно выражающая уровень ЯП.

Ясно, что в такой трактовке уровень ЯП непосредственно связан с классом

решаемых задач - один и тот же ЯП для разных классов задач имеет разный

уровень (что в целом согласуется с интуитивным понятием об уровне ЯП).

2. Специализация ЯП - характеризует потенциальную или реальную область

его применения. Различают ЯП общего назначения (или универсальные) и ЯП с

более определенной специализацией. Классическими примерами универсального ЯП

могут служить язык ассемблера ЕС или ПЛ/1. В свое время на эту роль

претендовали Алгол-60, Симула-67, Алгол-68. Реально ее играют также Фортран,

в частности, его стандарты - Фортран-66 (ГОСТ) и Фортран-77 (стандарт ИСО),

Бейсик (в особенности его развитые модификации), Паскаль (в особенности

диалекты, допускающие раздельную трансляцию), менее известные у нас ЯП, как

Корал (стандарт МО Великобритании), Джовиал (стандарт ВВС США), а также

отечественный Эль 76.

Более выраженную специализацию обычно приписывают таким ЯП, как Кобол

(коммерческая); Рефал, Снобол, Лисп (символьная); Модула, Ада (реальное

время). В Алголе-60 и Фортране также можно усмотреть специализацию (научные

и инженерные расчеты).

Все названные ЯП в той или иной степени можно отнести к базовым ЯП

широкого назначения. Обычно на их основе (или без них) строят более

специализированные ПОЯ.

3. Алгоритмичность (процедурность) - характеризует возможность

абстрагироваться от деталей (алгоритма) решения задачи. Другими словами,

алгоритмичность тем выше, чем точнее приходится планировать выполняемые

действия и их порядок (или синхронизацию); она тем ниже, чем более язык

позволяет формулировать соотношения и цели, характеризующие ПО и решаемую

задачу, оставляя поиск конкретного способа решения (способа достижения

целей) за исполнителем.

Типичные примеры алгоритмического (процедурного) языка - ассемблер,

Фортран, Ада; неалгоритмического (непроцедурного) языка - Пролог. Рефал

занимает промежуточное положение - хотя мы рассмотрим его как естественное

развитие марковских алгоритмов, многие воспринимают Рефал-предложения

(особенно с мощными спецификаторами) как соотношения, удобные для

непосредственного представления знаний о предметных областях, а поиск

подходящего Рефал-предложения - как автоматический выбор подходящего способа

решения задачи.

4. Динамизм (диалоговость, интерактивность) - характеризует степень

изменчивости программных объектов в процессе выполнения программы. Частично

мы обсуждали этот вопрос, когда занимались статическими, квазистатическими и

динамическими характеристиками объектов. С этой точки зрения различаются

статические, квазистатические и динамические ЯП.

Разделяют языки также по степени изменчивости текста программы. Один

крайний случай - текст программы в процессе ее работы менять нельзя. Этот

случай представлен "пакетными" языками (Фортран, Паскаль, Ада, Модула-2 и

т.д.). Другой крайний случай - программист волен изменить программу на любом

этапе ее исполнения. Этот случай представлен "диалоговыми" языками (Бейсик,

Характеристики

Список файлов книги