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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

V = V_N È V_T - обобщенный словарь.

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

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

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

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

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

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

где v,w, Î V^* , х Î V_N, у = 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^* , х Î V_N, у = 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 }

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

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

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