Лекция: Понятие формальной грамматики

Формальная грамматика — это четверка G = <VN,VT, P, S >, в которой

VN — нетерминальный словарь (множество нетерминальных символов);

VT — терминальный словарь (множество терминальных символов ) ;

P — множество грамматических правил;

S Î VN — начальный нетерминальный символ.

Метаязык — язык, с помощью которого описывается язык:

::= — есть по определению;

| — “ исключающее или”;

<… > — внутри – один нетерминальный символ ;

[ ] — необязательная часть;

, — запятая – разделитель при перечислении.

Пример: Построим грамматику G1:

<прог>::=<оп> | <оп>; <прог>

<оп>::=<пер> := <выр>

<пер>::=a | b | c

<выр>::=<пер> | <пер> <зн> <выр>

<зн>::= + | — | * | /

V = VN È VT — обобщенный словарь.

V* — цепочка символов (строка, слово) из обобщенного словаря;

V*N — цепочка символов (строка, слово) из нетерминального словаря;

V*T — цепочка символов (строка, слово) из терминального словаря.

e Î V — пустой символ, входит в обобщенный словарь.

Строка a непосредственно порождает строку b и обозначается: a Þ b ,

если a = vxw b = vyw и существует некоторое правило p: x::= y,

где v,w, Î V*, х Î VN, у = V* \ {e}

Строка a порождает строку b и обозначается a Þ* b, когда от строки a можно перейти к строке b с помощью последовательности непосредственных порождений.

Продолжая пример:

<прог> Þ <оп>; <прог> Þ <оп>; <оп> Þ <пер> := <выр>; <оп> Þ*

a := b + c; c := a + b — c;

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

Строка b непосредственно свертывается встроку a и обозначается: a Ü b,

если a = vxw b = vyw и существует некоторое правило p: x::= y,

где v,w, Î V*, х Î VN, у = V* \ {e}

Строка b свертывается встроку a и обозначается a *Ü b, когда от строки b можно перейти к строке a с помощью последовательности непосредственных свертываний.

Грамматика, использующая процедуры (непосредственного) свертывания –распознающая грамматика.

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

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

L(G) = { x Î V*N | S Þ* x }

Аналогично можно определить язык L через свертывание.

L(G) = { x Î V*N | S *Ü x }

Замечание. Другой вариант метаязыка

вместо ::= используется стрелка ®, терминальные символы записываются маленькими (строчными) буквами, а нетерминальные – большими (прописными) буквами.

Такой вариант мета языка чаще используется в математической литературе. Первый предпочитают использовать в литературе для программистов. Так что мы будем пользоваться и тем и другим вариантами…