Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 31 стр.

UptoLike

Составители: 

В эквивалентную грамматику будут включены правила вида А w, AV
N
; w(V
T
V
N
)
*
, если из вершины с меткой А существует путь в вершину с меткой w.
S aFb | aSb | аА;
А аА | aSb |
aFb;
В аА | aSb | aFb;
F bc | bFc.
Получено то же множество правил Р, что и аналитическим методом.
4.5.2. Построение неукорачивающей грамматики
Грамматика, не содержащая правил с пустой правой частью, называется
неукорачивающей грамматикой.
В грамматике с правилами вида А→ε длина выводимой цепочки при переходе от k-го
шага к (k+1)-му уменьшается. Поэтому грамматики с правилами вида А→ε называются
укорачивающими. Восходящий синтаксический разбор в укорачивающих грамматиках
сложнее по сравнению с разбором в неукорачивающих грамматиках, т.к. при редукции
необходимо отыскать такой фрагмент входной цепочки, в которую можно вставить пустой
символ.
Покажем, что для произвольной КС-грамматики, порождающей язык без пустой
цепочки, можно построить эквивалентную неукорачивающую КС-грамматику.
Построим множество всех нетерминальных символов грамматики G=(V
T
, V
N
, P, S), из
которых выводится пустая цепочка, выделив следующие множества:
W
1
= {A | A→ε P},
W
n+1
= W
n
{B | B→ϕ P, ϕ W
*
n
}.
Затем найдем множество правил эквивалентной грамматики в два этапа:
а) удалив из множества P исходной грамматики правила с пустой правой частью P
1
'
= P\{
A→ε | A→ε P};
б) получив новые правила A→ϕ' после удаления из каждого правила исходной
грамматики A→ϕ P те нетерминалы, которые вошли в множество W
n
по правилу:
P
1
" = { A→ϕ' | A→ϕ P'; ϕ =ϕ
1
Bϕ
2
| BW
n
; ϕ'=ϕ
1
Bϕ
2
}.
Повторив п.б) для каждого нетерминала, принадлежащего множеству W
n
, получим
эквивалентную грамматику G = (V
T
, V
N
, P
э
, S).
Пример. Пусть задана грамматика G со следующими правилами вывода: S АbА | сАb |
Bb; А аАb | ε; ВАА|а. Необходимо:
1) построить множество нетерминалов, из которых выводится ε;
2) построить неукорачивающую грамматику, эквивалентную исходной.
Для того чтобы построить множество всех нетерминалов грамматики, из которых
выводится пустая цепочка, выделим следующие множества:
W
1
= {А | А ε P};
W
m+1
= W
m
{В | В ϕ Р, ϕ W
*
m
}.
Так как мы имеем правило А ε Р, то можно построить множество W
1
= {A},
включающее нетерминал А.
Построим множество W
2
. С нетерминалом А связан нетерминал В, т.е. существует
правило В АА и А W
1
. Следовательно, W
2
={A,B}.
W
3
= W
2
, т. к. множество W
3
={В|В ϕ Р, ϕ W
*
m
} является пустым.
Исключив правило, содержащее пустую цепочку в правой части, получим
неукорачивающую грамматику G1 следующего вида:
S АbА | сАb | Bb | bA | Ab | cb | b;