Основы конструирования компиляторов

          

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


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

программирования при помощи БНФ - формы Бэкуса-Наура.

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

  • N - алфавит нетерминальных символов;
  • T - алфавит терминальных символов, N
    Формальное определение грамматики
    T =
    Формальное определение грамматики
    ;
  • P - конечное множество правил вида
    Формальное определение грамматики
    Формальное определение грамматики
    Формальное определение грамматики
    , где
    Формальное определение грамматики
    Формальное определение грамматики
    (N
    Формальное определение грамматики
    T)*N(N
    Формальное определение грамматики
    T)*,
    Формальное определение грамматики
    Формальное определение грамматики

    (N

    Формальное определение грамматики
    T)*;
  • S
    Формальное определение грамматики
    N - начальный символ (или аксиома) грамматики.

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

обозначения терминальных символов, малые латинские буквы из конца алфавита для обозначения цепочек из T* и, наконец, малые греческие буквы для обозначения цепочек из (N

Формальное определение грамматики
T)*.

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

Формальное определение грамматики
Формальное определение грамматики
1|
Формальное определение грамматики
2|...|
Формальное определение грамматики
n для обозначения группы правил A
Формальное определение грамматики
Формальное определение грамматики
1, A
Формальное определение грамматики
Формальное определение грамматики
2, ..., A
Формальное определение грамматики
Формальное определение грамматики
n.

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

Формальное определение грамматики
T)* бинарное отношение выводимости
Формальное определение грамматики
следующим образом: если
Формальное определение грамматики
Формальное определение грамматики
Формальное определение грамматики
Формальное определение грамматики
P, то
Формальное определение грамматики
Формальное определение грамматики
Формальное определение грамматики
Формальное определение грамматики
Формальное определение грамматики
Формальное определение грамматики
Формальное определение грамматики

для всех

Формальное определение грамматики
,
Формальное определение грамматики
Формальное определение грамматики
(N
Формальное определение грамматики
T)*. Если
Формальное определение грамматики
1
Формальное определение грамматики
Формальное определение грамматики
2, то говорят, что цепочка
Формальное определение грамматики
2

непосредственно выводима из

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

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

отношения

Формальное определение грамматики
, а также его степень k
Формальное определение грамматики
0 (обозначаемые соответственно
Формальное определение грамматики
*,
Формальное определение грамматики
+ и
Формальное определение грамматики
k). Если
Формальное определение грамматики
1
Формальное определение грамматики
*
Формальное определение грамматики
2 (
Формальное определение грамматики
1
Формальное определение грамматики
+
Формальное определение грамматики
2,
Формальное определение грамматики
1
Формальное определение грамматики
k
Формальное определение грамматики
2), то говорят, что цепочка
Формальное определение грамматики
2 выводима (нетривиально выводима, выводима за k шагов) из
Формальное определение грамматики
1.

Если

Формальное определение грамматики
Формальное определение грамматики
k
Формальное определение грамматики
(k
Формальное определение грамматики
0), то существует последовательность шагов

Формальное определение грамматики
где
Формальное определение грамматики
=
Формальное определение грамматики
0 и
Формальное определение грамматики
=
Формальное определение грамматики
k. Последовательность цепочек
Формальное определение грамматики
0,
Формальное определение грамматики
1,
Формальное определение грамматики
2, ...,
Формальное определение грамматики
k в этом случае называют выводом
Формальное определение грамматики

из

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

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

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

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

Грамматики G1

и G2 называются эквивалентными, если они порождают один и тот же язык, т.е.
L(G1) = L(G2).

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

P = {S

Формальное определение грамматики
aSBC, S
Формальное определение грамматики
aBC, CB
Формальное определение грамматики
BC, aB
Формальное определение грамматики
ab, bB
Формальное определение грамматики
bb, bC
Формальное определение грамматики
bc, cC
Формальное определение грамматики
cc}, порождает язык L(G) = {anbncn|n > 0}.

Действительно, применяем n- 1 раз правило 1 и получаем an-1S(BC)n-1, затем один раз правило 2 и получаем an(BC)n, затем n(n- 1)/2 раз правило 3 и

получаем anBnCn.

Затем используем правило 4 и получаем anbBn-1Cn. Затем применяем n- 1 раз правило 5 и получаем anbnCn. Затем применяем правило 6 и n - 1 раз правило 7 и получаем anbncn. Можно показать, что язык L(G) состоит из цепочек только такого вида.

Пример 2.6. Рассмотрим грамматику G = ({S}, {0, 1}, {S
Формальное определение грамматики
0S1, S
Формальное определение грамматики
01}, S). Легко видеть, что цепочка 000111
Формальное определение грамматики
L(G), так как существует вывод

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


Нетрудно показать, что грамматика порождает язык L(G) = {0n1n|n > 0}.

Пример 2.7. Рассмотрим грамматику G = ({S, A}, {0, 1}, {S
Формальное определение грамматики
0S,

S
Формальное определение грамматики
0A, A
Формальное определение грамматики
1A, A
Формальное определение грамматики
1}, S). Нетрудно показать, что грамматика порождает язык L(G) = {0n1m|n, m > 0}.


Содержание раздела