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

1.1.3. Построение компилятора

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

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

1.2. Определение формальной грамматики и языка

1.2.1. Первичные понятия

Определение. Конечное множество символов, неделимых в данном рассмотрении, называется словарем или алфавитом, а символы, входящие в множество, - буквами алфа-

вита.

Например, алфавит A = {a, b, c, +, !} содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

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

Например, слово a=ab++c в алфавите A имеет длину l(a) = 5, а слово b=00110010 в алфавите B имеет длину l(b) = 4.

Если задан алфавит A, то обозначим через A* множество всевозможных цепочек, которые могут быть построены из букв алфавита A. При этом предполагается, что пустая цепочка, которую обозначим знаком $, также входит в множество A*.

Определение. Формальной порождающей грамматикой Г называется совокуп-

3

ность четырех объектов: Г = { VT, VA, <I> VA, R },

где VT - терминальный алфавит (словарь); буквы этого алфавита называются тер-

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

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

<I> - начальный символ грамматики <I> VA.

R - множество правил вывода или порождающих правил вида α → β , где α и β -

цепочки, построенные из букв алфавита VT VA, который называют полным алфавитом (словарем) грамматики Г.

В множество правил грамматики могут также входить правила с пустой правой частью вида <Е> → . Чтобы избежать неопределенности из-за отсутствия символа в правой части правила, условимся использовать символ пустой цепочки, записывая такое правило в виде <Е> → $.

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

Определение. Пусть r = τ → γ - правило грамматики Г и α = χ'τ χ" - цепочка симво-

лов, причем χ', χ" ( VT VA) *. Тогда цепочка β= χ' γ χ " может быть получена из цепочки путем применения правила r (т.е. заменой в α цепочки τ на γ). В этом случае говорят, что цепочка β непосредственно выведена из цепочки α и обозначают это

α β .

Определение. Если задана совокупность цепочек Ω = ( ϖ0, ϖ1,...,ϖn), таких что существует последовательность непосредственных выводов:

ϖ0 ϖ1, ϖ1 ϖ2, ... ,ϖ n-1 ϖ n,

то такую последовательность называют выводом ϖn из ϖ0 в грамматике Г и обозна-

4

чают

ϖ 0 * ϖn.

Определение. Множество конечных цепочек терминального алфавита VT грамматики Г, выводимых из начального символа <I>, называется языком, порождаемым грамматикой Г и обозначается L( Г).

L( Г ) = {ϖ VT* | <I> *ϖ }.

Определение. Если язык, порождаемый грамматикой Г, не содержит ни одной конечной цепочки (конечного слова), то он называется пустым.

Утверждение. Для того, чтобы язык L( Г ) не был пустым, в множестве R должно быть хотя бы одно правило вида r = χ → ψ, где ψ VT* и должен существовать вывод

<I> * χ.

1.3. Типы формальных языков и грамматик

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

1.3.1. Грамматики типа 0

Грамматики типа 0, которые называют грамматиками общего вида, не имеют ника-

ких ограничений на правила порождения. Любое правило r = η → ψ

может быть построено с использованием произвольных цепочек η, ψ ( VT VA)*.

1.3.2. Грамматики типа 1

Грамматики типа 1, которые называют также контекстно-зависимыми грамматика-

ми, не допускают использования любых правил. Правила вывода в таких грамматиках должны иметь вид: χ1<A>χ2 → χ1ω χ2, где χ1, χ2 - цепочки, возможно пустые, из множе-

ства (VT VA)*, символ <А> VA а цепочка

5