Теория алгоритмов и формальных языков. Мелихов А.Н - 54 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

называется синтаксически неоднозначным. В графе неоднозначной
грамматики для цепочки со степенью неоднозначности р имеется ровно р
путей, идущих из вершины, помеченной аксиомой, в вершину, помеченную
данной цепочкой. Эта цепочка может быть выведена р способами, каждый из
которых задается своим деревом вывода.
Пример 3.4. Пусть задана грамматика
},,,{
2
RSVVG
AT
=
, где
},{ caV
T
=
,
}{SV
A
=
, S - аксиома, правила вывода имеют вид:
0,,
,
:
〉→
〉→
∗
jj
q
p
i
p
qpaSaS
apSaS
R
j
j
i
.
Эта грамматика обязательно содержит правила вывода
aSS →
,
aSaS →
,
которые вместе с правилами
cS →
порождает язык }{
2
nm
caaL = , где onm ≥≥ .
Пусть, например, мы хотим получить цепочку
nm
caa . Применим k раз
правило
aSS → и l раз правило aSaS → . Имеем mlk
=
+
и nl = . Дерево
вывода зависит от того, в каком порядке применялись правила: не различных
последовательностей применения правил существует столько, сколькими
способами можно выбрать n элементов из m элементов, т.е.
n
m
С . Итак, степень
неоднозначности цепочки
nm
caa равна
n
m
С . Для цепочки
23
caa получим 3
2
3
=C
выводов, которые показаны на рис. 3.3.
Рис. 3.3.
В некоторых случаях неоднозначность в грамматике можно устранять
путем эквивалентного преобразования грамматики, однако в общем случае
проблема устранения неоднозначности алгоритмически неразрешима. Это
затрудняет трансляцию. Практически от неоднозначности избавляются путем
S
S
S
S
S
S
S
S
S
S
S
S
a
a
a
с
a
a
a
a
с
a
a
a
a
a
a
a
с
a

Страницы