Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Формальная грамматика - это четверка 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 }
Замечание. Другой вариант метаязыка
вместо::= используется стрелка ®, терминальные символы записываются маленькими (строчными) буквами, а нетерминальные – большими (прописными) буквами.
Такой вариант мета языка чаще используется в математической литературе. Первый предпочитают использовать в литературе для программистов. Так что мы будем пользоваться и тем и другим вариантами…
Дата публикования: 2014-11-03; Прочитано: 335 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!