Стр. 10 - Информационные структуры и их преобразование

8 Содержание
ИНФОРМАЦИОННЫЕ СТРУКТУРЫ И ИХ ПРЕОБРАЗОВАНИЕ
1.2. Формальное определение языка
Алфавит и совокупность правил, формализующих построение цепочек
языка, называют его грамматикой . G{N,Σ,P,S} - грамматика, где N -
нетерминальные символы, Σ - терминальные символы, S - некоторый
начальный символ, P - правило.
Построим грамматику, которая бы генерировала произвольные целые
числа:
Σ =0…9;
S=<чис>.
Определим правила: <чис>:=<ц>|<чис><ц>; <ц>:=0|1|2|…|9.
Выведем 4-разрядное число:
<чис>=><чис><ц>=><чис><ц><ц>=<чис><ц><ц><ц>=><ц><ц><ц><ц
>=>
2<ц><ц><ц>=>23<ц><ц>=>234<ц> =>2345
Такую форму грамматики называют нормальная форма Бэкуса-Наура.
Пусть имеется вывод:W=>U0 =>U1=U2 =V. Говорят, что W порождает
цепочку V и пишут W=>+V(без λ) W=>∗V(с λ).Если в цепочке есть хотя бы 1
нетерминал, то из неё можно вывести новую цепочку.
Пусть G(z) грамматика. Сентенциальная форма – любое высказывание,
выводимое из начального символа. Цепочка X называется сентенциальной
формой, если имеет место вывод Z=>+X, Z=>∗X.
Сентенциальная форма, которая содержит только терминальные
символы, получила название предложения.
<чис>
<чис>
<чис>
<чис>
<чис>
<ц>
2
<ц>
<ц>
<ц>
<ц>
3
4
5
Синтаксическое
дерево