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




Формальное определение грамматики


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

Определение. Грамматика - это четверка G = (N,T,P,S), где

(1) N - алфавит нетерминальных символов;

(2) T - алфавит терминальных символов,

N \cap T = {\O}

(3) P - конечное множество правил вида

\alpha \rightarrow \beta
, где
\alpha \in (N \cup T)^* N (N \cup T)^*, \beta \in (N \cup T)^*

(4)

S \in N
- начальный знак (или аксиома) грамматики.

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

T^*
и, наконец, малые греческие буквы для обозначения цепочек из
(N \cup T)^*
.

Будем использовать также сокращенную запись

A \rightarrow \alpha_1|\alpha_2|\ldots|\alpha_n
для обозначения группы правил
A\rightarrow\alpha_1,A\rightarrow\alpha_2,\ldots,A\rightarrow\alpha_n.

Определим на множестве

(N \cup T)^*
бинарное отношение выводимости
\Rightarrow
следующим образом: если
\delta \rightarrow \gamma \in P
, то
\alpha \delta \beta \Rightarrow \alpha \gamma \beta
для всех
\alpha, \beta \in (N \cup T)^*
. Если
\alpha_1 \Rightarrow \alpha_2
, то говорят, что цепочка
\alpha_2
непосредственно выводима из
\alpha_1
.

Мы будем использовать также рефлексивно-транзитивное и транзитивное замыкания отношения

\Rightarrow
, а также его степень
k \geq 0
(обозначаемые соответственно
\Rightarrow^*
,
\Rightarrow^+
и
\Rightarrow^k
). Если
\alpha_1\Rightarrow^*\alpha_2(\alpha_1\Rightarrow^+\alpha_2, \alpha_1\Rightarrow^k \alpha_2)
, то говорят, что цепочка
\alpha_2

выводима (нетривиально выводима, выводима за k шагов) из

\alpha_1
.

Если

\alpha\Rightarrow^k \beta(k \geq 0)
, то существует последовательность шагов

\gamma_0 \Rightarrow \gamma_1 \Rightarrow \gamma_2 \Rightarrow \ldots \Rightarrow \gamma_{k-1} \Rightarrow \gamma_k

где

\alpha \; = \; \gamma_0
где
\alpha \; = \; \gamma_0
и
\beta\; = \;\gamma_k
. Последовательность цепочек
\gamma_0, \gamma_1, \gamma_2, \ldots, \gamma_k
в этом случае называют выводом
\beta
из
\alpha

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

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

L(G)\;=\; \{\omega\mid\omega\in T^*, S\Rightarrow^+\omega\}

Грамматики G1 и G2 называются эквивалентными, если они порождают один и тот же язык, то есть

L(G_1) = L(G_2)

Пример 2.5. Грамматика G = ({S, B, C}, {a, b, c}, P, S), где

P = \{S \rightarrow aSBC, \; S \rightarrow aBC,\; CB \rightarrow BC, \; aB \rightarrow ab,\; bB \rightarrow bb,\; bC \rightarrow bc, \; cC \rightarrow cc\}
, порождает язык
L(G) = \{a^nb^nc^n\mid n>0\}

Действительно, применяем n - 1 раз правило 1 и получаем

a^{n-1}S(BC)^{n-1}
, затем один раз правило 2 и получаем
a^n(BC)^n
, затем n(n - 1)/2 раз правило 3 и получаем
a^nB^nC^n
.




Содержание  Назад  Вперед