Пред.Страница  След.Страница   Раздел   Содержание

---

1.3.8. Неоднозначные и эквивалентные грамматики

Существуют грамматики, в которых одна и та же цепочка может быть получена с помощью различных выводов. Например, в грамматике Г_{1. 10} цепочка abc может быть получена с помощью двух различных выводов, и ей соответствуют два различных синтаксических дерева.

Г_{1. 10}:

V_т = {a, b, c, d}, V_a = {<I>, <A>, <B>},

R =  { <I> ® <A><B>,

<A> ® a,
<A> ® ac,
<B> ® b,
<B> ® cb}.

Первый вывод этой цепочки имеет вид :

1) <I> Þ <A><B> Þ <A>b Þ acb,

а второй можно получить так :

2) <I> Þ <A><B> Þ <A>cb Þ acb.

Этим выводам соответствуют разные синтаксические деревья и разборы :

Следующая грамматика также допускает построение одной и той же цепочки с помощью двух выводов, имеющих разные синтаксические деревья.

Г_{1. 11}:

V_т = {0, +}, V_a = {<I>},

R = { <I> ® 0,

<I> ® <I> + 0,
<I> ® 0 +<I> }.

Два вывода этой грамматики, порождающие одинаковые цепочки, имеют вид:

1) <I> Þ <I> + 0 Þ <I> + 0 + 0 Þ 0 + 0 + 0,

2) <I> Þ 0 + <I> Þ 0 + 0 +<I> Þ 0 + 0 + 0,

а синтаксические деревья, соответствующие этим выводам, можно изобразить так:

Рассмотренное свойство грамматик называется неоднозначностью. Оно может быть определено следующим образом.

Определение.   Цепочка языка L(Г) называется неоднозначной, если для её вывода существует более чем одно синтаксическое дерево. Если грамматика Г порождает неоднозначную цепочку, то она называется неоднозначной.

Неоднозначность может существовать не только в искусственных языках. Хорошо известно, что в естественных языках могут быть предложения, допускающие неоднозначное написание. Например, "Пальто испачкало окно". В этой фразе не ясно, что является подлежащим, а что дополнением. Другим примером служит английская фраза: "They are flying planes", которая может быть понята двояко: "Они пилотируют самолет" или : Это летящие самолеты".
Свойство неоднозначности является крайне нежелательным для искусственных языков, поскольку оно не позволяет однозначным образом восстановить дерево вывода по заданной цепочке языка.
В общем случае можно сделать следующий вывод:
1) каждой цепочке, выводимой в грамматике, может соответствовать одно или несколько синтаксических деревьев,
2) каждому синтаксическому дереву могут соответствовать несколько выводов,
3) каждому синтаксическому дереву соответствует единственный правый и единственный левый выводы.
Кроме того, следует подчеркнуть, что один и тот же язык может быть получен с помощью различных грамматик.

Определение.   Две грамматики Г₁ и Г₂ называются эквивалентными, ecли они порождают один и тот же язык, т.е. 

L(Г₁) = L(Г₂).

---

Пред.Страница  След.Страница   Раздел   Содержание