СТРУКТУРА ЯЗЫКОВ .ТРАНСЛЯТОРЫ

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

1. определение и структура языка

В основе каждого языка лежит словарь. Его элементы бьшно называют словами, но в теории формальных языков X называют символами. Языки характеризуются тем, что которые последовательности слов считаются правильными Редложениями языка, а другие - неправильными, или не Ринадлежащими данному языку. Чем же определяется, яв-яется ли некоторая последовательность слов правильным Р^Дложением? Обычно это определяется грамматикой, син-Зксисом (можно сказать - структурой) языка. Синтаксис

определяется как множество правил или формул, кото задают множество (формально правильных) предложен'- Такое множество синтаксических правил не только позвол установить, принадлежит ли некоторая заданная последо^ тельность слов множеству предложений языка, но при эт* определяет структуру предложения, которая устанавлива' его смысл. Поэтому ясно, что синтаксис и семанти^ (=смысл) тесно связаны между собой. Следовательно, оппр* деления, связанные со структурой, всегда следует рассмаг' ривать как средство распознавания смысла. Но это не поме шает нам изучить вначале исключительно структурные аспек ты языка, отвлекаясь от их связи со смыслом, т. е. от их интерпретации.

Рассмотрим, например, предложение Кошки спят . Слово кошки - под.пежашее, а спят - сказуемое. Это предложение принадлежит языку, который можно описать, например, при помоши следуюших синтаксических правил:

(предложение) ;:--= (подлежащее) (сказуемое) (подлежащее) ::= кошки собаки (сказуемое) ::= спят \ едят

Смысл этих трех строчек таков:

1. Предложение состоит из подлежащего, за которым следует сказуемое.

2. Подлежащее состоит либо из одного слова кошки , либо из одного слова собаки .

3. Сказуемое состоит либо из слова спят , либо из слова едят .

Идея заключается в том, что любое предложение можно получить из начального символа (предложение) последовательным применением правил подстановки.

Формализм, или нотация, использованный при написании этих правил, называется бэкус-науровой формой (БНФ)-Впервые она была использована для описания Алгола-бС [5.7]. Синтаксические единицы (предложение), (подлежащее) и (сказуемое) называются нетерминальными символами, слова кошки, собаки, спят и едят - терминальными символами, а правила - порождающими правилами. Символы ::= и I это метасимволы*) языка БНФ. Если для краткости мы будем использовать отдельные заглавные буквы для нетерминальных символов, то данный пример можно переписать следующим образом:

*) Метасимволы не принадлежат описываемому языку, а относятся * языку описания. Метасимволами являются также ( ). - скобки нетерМ нальных символов. - Прим. перев.

6.1. Определение и структура языка 321

5::=ЛВ

А::х\у (5.1)

B::=z\w

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

j Пусть язык L = L(T, N, Р, S) задан: (а) словарем Т терминальных символов;

t(b) множеством N нетерминальных символов (грамматических категорий);

(с) множеством Р порождающих правил (синтаксисом); (d) символом S (из N), называемым начальным символом. 2. Язык L{T,N,P,S) есть множество последовательностей терминальных символов , которые могут порождаться из S по правилу 3 (приведенному ниже):

h L = U\S-l и gen (5.2)

для обозначения последовательностей символов мы ис-пользуем греческие буквы), Т* означает множество всех последовательностей символов из Т.

3. Последовательность ог может порождаться последователь-

ностью Оо в том и только в том случае, если имеются последовательности oi,02, -. ., а„ 1, такие, что каждое о, может непосредственно порождаться а, ] по правилу 4 (приведенному ниже): (оо а„) (o, , - Oi) для г = 1 ... /г. (5.3)

4. Последовательность т) может непосредственно порождаться последовательностью g в том и только в том случае, если

существуют последовательности а, р, g, tj, такие, что:

i (а) l = al; I (b) п = ariP;

(с) Р содержит порождающее правило g ::= tj.

Примечание. Правило вида а::= PiP2.-.Pn используется *ак сокращенная запись для множества порождающих правил: . . а::=р1, а::== рг.....а::=Р„.

Например, последовательность хг из примера 1 можно полупить с помощью следующих шагов непосредственного порож-Аения: SАВхВ хг; следовательно, хг, и по-