КАТЕГОРИИ:

Астрономия Биология География Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Механика Образование Охрана труда Педагогика Политика Право Психология Риторика Социология Спорт Строительство Технология Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Обобщенные КС-грамматики и приведение их к удлиняющей

⇐ ПредыдущаяСтр 16 из 71Следующая ⇒

Форме

КС-грамматика называется обобщенной, если она содержит аннулирующие правила (e - правила), то есть правила вида A® e , где e - пустая цепочка. Обобщенная грамматика зачастую более проста и наглядна. Тем не менее следует помнить, что для любой обобщенной КС-грамматики существует эквивалентная неукорачивающая КС-грамматика.

Теорема 4.6. Каждая КС-грамматика приводима к виду не более чем с одним аннулирующим правилом S® e , которого может и не быть.

Доказательство. Проведем его, как обычно, конструктивно, построением неукорачивающей грамматики.

Во-первых, нужно определить, порождает ли исходная грамматика пустую цепочку. Пусть S - начальный символ исходной грамматики G. Определим в G множество нетерминалов X_i , из которых пустую цепочку можно получить за i шагов, и множество новых нетерминалов Z_i. Таким образом мы определим аннулирующие нетерминалы.

X₀ = { A | $ A® e } , Z₀ = X₀

X₁ = { A | $ A® x , где xÎ X₀ } , Z₁ = X₁\ X₀

....................................................................

X_i= { A | $ A® x , где xÎ X_j} , Z_i = X_i\ X_i-1

На каком-то шаге Z_i станет равным Æ и процесс формирования аннулирующих нетерминалов можно закончить. Если S Ï X_j, где , то e Ï L(G) и правила S® e добавлять не надо. В противном случае, заменим в исходной грамматике во всех правилах S на S₁ , введем новый исходный нетерминал S и к правилам грамматики G добавим правила S® e ½S₁.

Все остальные правила вида A® e можно удалить. Для этого заменим каждое из правил, правые части которых содержат хотя бы по одному аннулирующему нетерминалу, множеством новых правил. Если правая часть правила содержит k вхождений аннулирующих нетерминалов, то множество, заменяющее это правило, будет состоять из 2^k правил, соответствующих всем возможным способам удаления некоторых (или всех) из этих вхождений.

Пусть имеется правило

B® j_{1 A 1}j_{2 A 2}j₃... j _kA_kj_k+1 ,

где A_i ( ) - аннулирующие нетерминалы. Добавим к этому правилу следующие правила:

B® j₁j_{2 A 2}j₃... j_kA_kj_k+1 , удалено A₁

B® j_{1 A 1}j₂j₃... j_kA_kj_k+1 , удалено A₂

..................................

B® j_{1 A 1}j_{2 A 2}j₃... j _kj_k+1 , удалено A_k

B® j₁j₂j₃... j_kA_kj_k+1 , удалены A_{1, A 2}

..................................

B® j₁j₂j₃... j_kj_k+1 , удалены A_{1, A 2}, ... A_k.

Заметим, что в случае неоднозначности, на этом шаге может получиться меньше чем 2^k правил. Так, для аннулирующего нетерминала A, правило B® aAA будет заменяться тремя правилами B® aAA½aA½a , так как в данном случае безразлично первое или второе вхождение A мы рассматриваем.

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

В результате мы получим грамматику, эквивалентную исходной, что доказывается с использованием теорем 4.1 и 4.3.

Отметим, что мы рассматривали случай, когда аннулирующие нетерминалы имеют и другие альтернативы, кроме перехода в пустую цепочку. Если A ® e единственная альтернатива нетерминала A, то правые части правил, содержащие его вхождение, можно просто исключить. ƒ

В результате применения рассмотренного алгоритма можно получить КС-грамматику, по которой вывод любой непустой цепочки характеризуется тем, что сентенциальная форма, получаемая на каждом шаге вывода, будет не короче предыдущей. Не случайно полученная грамматика носит название неукорачивающей КС-грамматики (НКС-грамматики).

Пример 4.5. Рассмотрим обобщенную КС-грамматику с аксиомой <число>.

<число> ® <знак> <цел.часть> . <др.часть>

<знак> ® +½-½e

<цел.часть> ® <цел.часть><цифра>½e

<др.часть> ® <цел.часть>

<цифра> ® 0½1½...½8½9 и приведем ее к неукорачивающей форме.

Вначале покажем, что данная грамматика не порождает пустой цепочки. Здесь

X₀= { <знак>, <цел.часть> },

X₁ = { <др.часть> },

X₂ = Æ и Z₂ = Æ.

Среди множеств X - нет нетерминала <число> и, следовательно, правила

<число> ® e добавлять не надо.

Проведем замены правил, правые части которых содержат аннулирующие нетерминалы, а затем удалим e - правила.

В результате получим грамматику

<число> ® <знак> <цел.часть> . <др.часть>½<цел.часть> . <др.часть>½

<знак>. <др.часть>½<знак> <цел.часть> . ½ . <др.часть>½

<цел.часть> . ½<знак> . ½.

<цел.часть> ® <цел.часть><цифра>½<цифра>

<др.часть> ® <цел.часть>

<цифра> ® 0½1½...½8½9

На рис. 4.2 представлены деревья вывода цепочки +.9 по исходной (рис. 4.2 (а)) и результирующей (рис. 4.2 (б)) грамматикам.

Для приведения грамматики к удлиняющей форме необходимо кроме аннулирующих правил исключить и цепные правила. Цепное правило - это правило вида A® B , где A, B Î N.

Теорема 4.7. Для любой КС-грамматики существует эквивалентная ей грамматика без цепных правил.

Доказательство. Пусть в грамматике имеется правило A ® B и A ¹ S (A - не начальный символ грамматики). Тогда все правила вида C ® aAb заменим на правила C ® aBb, а правила A ® B удалим. Если A = S и для B существуют правила B ® j₁½...½j_n , то заменим их на S ® j₁½...½j_n , после чего S ® B удалим.

Любое такое преобразование правил допустимо исходя из теорем 4.1 - 4.3 и устраняет правила вида A ® B. Повторяем такие преобразования до тех пор, пока в грамматике не останется цепных правил. š

В результате устранения аннулирующих и цепных правил получается грамматика в удлиняющей форме, где сентенциальная форма на каждом шаге вывода будет длиннее сентенциальной формы на предыдущем шаге. Напомним, что эта форма грамматики использовалась для доказательства теоремы о разрешимости контекстных языков (теорема 1.1).

Пример 4.6. Пусть дана КС-грамматика с правилами

S ® aBa

B ® A½Bc

A ® aA½bb .

Правило B ® A можно устранить, воспользовавшись результатами теоремы 4.2, и получить грамматику

S ® aBa

B ® aA½bb½Bc

A ® aA½bb š

КС-грамматика G=(N,S,P,S) называется грамматикой без циклов, если в ней нет выводов A Þ⁺ A для AÎ N. КС-грамматика G называется приведенной, если она без циклов, без аннулирующих правил и без тупиков.

Грамматики с e- правилами и циклами иногда труднее анализировать, чем грамматики без таковых. Кроме того, в любой практической ситуации тупики (бесполезные символы) без необходимости увеличивают объем анализатора. Поэтому для некоторых алгоритмов синтаксического анализа, рассматриваемых во второй части пособия, мы будем требовать, чтобы грамматики, фигурирующие в них, были приведенными. Это требование позволяет рассматривать все КС-языки.

Теорема 4.8. Если L - КС-язык, то L=L(G) для некоторой приведенной КС-грамматики G.

Доказательство. Применить к КС-грамматике, определяющей язык L, эквивалентные преобразования по теоремам 4.5 - 4.7.

Дата добавления: 2014-11-13; просмотров: 183; Мы поможем в написании вашей работы!; Нарушение авторских прав

⇐ Предыдущая 11 12 13 14 151617 18 19 20 Следующая ⇒

lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты