Специальная математика. Соловьев А.Е. - 73 стр.

 если  = vxw  = vyw и существует некоторое правило p: x::= y,
где v,w,  V* , х  VN, у = V* \ {}
Строка  порождает строку  и обозначается  *  , когда от строки  можно перейти к
строке  с помощью последовательности непосредственных порождений.
Продолжая пример:
<прог>  <оп> ; <прог>  <оп> ; <оп>  <пер> := <выр> ; <оп> *
 a := b + c; c := a + b - c;
Грамматика, использующая процедуры (непосредственного) порождения – порождающая
грамматика.
Строка  непосредственно свертывается в строку  и обозначается:   ,
 если  = vxw  = vyw и существует некоторое правило p: x::= y,
где v,w,  V* , х  VN, у = V* \ {}
Строка  свертывается в строку  и обозначается  * , когда от строки  можно перейти
к строке  с помощью последовательности непосредственных свертываний.
Грамматика, использующая процедуры (непосредственного) свертывания –распознающая
грамматика.
Строки символов из обобщенного словаря, получающиеся в процессе порождения или
свертывания, называются сентенциальными формами.
Язык L, порождаемый данной грамматикой G - множество нетерминальных цепочек,
порождаемых из начального нетерминального символа. Такие терминальные цепочки
называются предложениями данного языка.

L(G) = { x  V*N | S * x }
Аналогично можно определить язык L через свертывание.
L(G) = { x  V*N | S * x }

Замечание. Другой вариант метаязыка
вместо ::= используется стрелка  , терминальные символы записываются маленькими
(строчными) буквами, а нетерминальные – большими (прописными) буквами.
Такой вариант мета языка чаще используется в математической литературе. Первый
предпочитают использовать в литературе для программистов. Так что мы будем
пользоваться и тем и другим вариантами…


                                7.2. Деревья вывода

Порождение и свертывание можно также представлять с помощью деревьев вывода.
Пусть дана грамматика.
IT
II+T
I I - T
TM
T  T*M
T  T/M
M  (I)
MK
Ka
Kb

                                       — 73 —