Теоретические основы информатики

   В силу того, что цепочка х ∈ L(G) выводится из аксиомы S, корнем вывода всегда

является аксиома. Внутренние узлы вывода соответствуют нетерминальным символам.

Концевые вершины дерева вывода - листья - это вершины, не имеющие потомков. Такие

вершины соответствуют либо терминалам, либо пустым символам (ε) при условии, что среди правил грамматики имеются правила с пустой правой частью. При чтении слева направо концевые вершины дерева вывода образуют цепочку х.

   Дерево вывода часто называют деревом грамматического разбора, или синтаксическим деревом, а процесс построения дерева вывода - грамматическим разбором (синтаксическим анализом). Одной цепочке языка может соответствовать больше одного

дерева, так как эта цепочка может иметь разные выводы, порождающие разные деревья.

   КС-грамматика G == (VТ, VN, Р, S) называется неоднозначной (неопределенной), если существует цепочка х ∈ L(G), имеющая два или более дерева вывода.

 

 

 

Преобразования КС-грамматик

   Часто требуется изменить грамматику таким образом, чтобы она удовлетворяла

определенным требованиям, не изменяя при этом порождаемый грамматикой язык. Для этого используются эквивалентные преобразования КС-грамматик, некоторые из которых

рассмотрены ниже.

Удаление правил вида А → В

   Преобразование первого типа состоит в удалении правил А → В, или <нетерминал> → <нетерминал>.

   Покажем, что для любой КС-грамматики можно построить эквивалентную грамматику, не содержащую правил вида: А → В, где А и В - нетерминальные символы.    Пусть имеется КС-грамматика G=(VT, VN, P, S), где множество нетерминалов VN={A1, A2, . . . , An}. Разобьем Р на два непересекающихся множества: P = P1 ∪ P2. В P1 включены все правила вида Аi → Ak, в P2 включены все остальные правила, т.е. P2 = P \ P1. Затем для каждого Аi определим множество правил P(Аi), включив в него все такие правила Аi→ϕ, что Аi →* Aj и Аj→ ϕ, где Аi → ϕ ∈ P2. Построим эквивалентную КС-грамматику Gэ = (Vт, VN, Pэ, S), в которой множества терминальных и нетерминальных символов, а также аксиома совпадают с теми же объектами исходной грамматики G, а множество правил Pэ получено объединением правил множества P2 и правил P(Аi) для всех 1≤ i ≤n:

       n

Рэ=U P ( Ai ) ∪P2

       i=1

Графическая модификация метода

 Аналитическое преобразование по рассмотренному алгоритму оказывается довольно сложным. При автоматизированном преобразовании грамматик проще применить графическую модификацию этого метода. С этой целью каждому нетерминальному символу и каждой правой части правил из множества Р2 поставлена в соответствие вершина графа. Из вершины с меткой U в вершину с меткой V направлено ребро, если в грамматике

существует правило U → V.

 

 

  В эквивалентную грамматику будут включены правила вида А → w, A∈VN; w∈(VT ∪VN)*, если из вершины с меткой А существует путь в вершину с меткой w.

S → aFb | aSb | аА;

А → аА | aSb | aFb;

В → аА | aSb | aFb;

F → bc | bFc.

Получено то же множество правил Р, что и аналитическим методом.

Построение неукорачивающей грамматики

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

неукорачивающей грамматикой.

   В грамматике с правилами вида А→ε длина выводимой цепочки при переходе от k-го шага к (k+1)-му уменьшается. Поэтому грамматики с правилами вида А→ε называются укорачивающими. Восходящий синтаксический разбор в укорачивающих грамматиках сложнее по сравнению с разбором в неукорачивающих грамматиках, т.к. при редукции

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

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

   Построим множество всех нетерминальных символов грамматики G=(VT, VN, P, S), из которых выводится пустая цепочка, выделив следующие множества:

W1= {A | A→ε ∈ P},

Wn+1 = Wn ∪{B | B→ϕ ∈ P, ϕ ∈ W* n }.

   Затем найдем множество правил эквивалентной грамматики в два этапа:

а) удалив из множества P исходной грамматики правила с пустой правой частью P1 ' = P\{A→ε | A→ε ∈ P};

б) получив новые правила A→ϕ' после удаления из каждого правила исходной грамматики A→ϕ ∈ P те нетерминалы, которые вошли в множество Wn по правилу:

P1" = { A→ϕ' | A→ϕ ∈ P'; ϕ =ϕ1Bϕ2 | B∈Wn; ϕ'=ϕ1Bϕ2}.

Повторив п.б) для каждого нетерминала, принадлежащего множеству Wn, получим эквивалентную грамматику G = (VT, VN, Pэ, S).

Пример. Пусть задана грамматика G со следующими правилами вывода: S → АbА | сАb |

Bb; А → аАb | ε; В→АА|а. Необходимо:

1) построить множество  нетерминалов, из которых выводится ε;

2) построить неукорачивающую  грамматику, эквивалентную исходной.

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

W1 = {А | А → ε ∈ P};

Wm+1 = Wm ∪ {В | В → ϕ ∈ Р, ϕ ∈ W* m}.

Так как мы имеем правило А → ε ∈ Р, то можно построить множество

W1 = {A},включающее нетерминал А.

Построим множество W2. С нетерминалом А связан нетерминал В, т.е. существует правило В → АА и А ∈ W1. Следовательно, W2={A,B}.

W3 = W2, т. к. множество W3={В|В → ϕ ∈ Р, ϕ ∈ W*m } является пустым.

Исключив правило, содержащее пустую цепочку в правой части, получим

неукорачивающую грамматику G1 следующего вида:

S → АbА | сАb | Bb | bA | Ab | cb | b;

A → aAb | ab;

В → АА | A | a.

Построение грамматики с продуктивными нетерминалами

   Нетерминальный символ А называется непродуктивным (непроизводящим), если он не порождает ни одной терминальной цепочки, т.е. не существует вывода А →* х, где х∈V*т. Поэтому представляет интерес удаление из грамматики всех непродуктивных нетерминальных символов. Рассмотрим, как для произвольной КС-грамматики можно

построить эквивалентную КС-грамматику, все нетерминальные символы которой продуктивны. С этой целью выделяется множество W1={A | A → ϕ ∈ P, ϕ ∈ V*T}.T}. Затемстроится множество W1, W2, . . . , Wn+1 по следующим правилам:

Wn+1 = Wn ∪{BB → x ∈ P, x ∈ (VT ∪ Wn)*}.

   Пусть задана грамматика G со следующими правилами вывода: S → SA | BSb | bAb; A →aSa | bb; B → bBb | BaA. Построим множество продуктивных нетерминалов:

W1 = {A}, т.к. в множестве P есть правило A → bb;

W2 = {A, S}, т.к. имеется правило S → bAb и A ∈ W1;

W3 = W2.

   Все символы множества VN\Wn являются непродуктивными, не используются в выводе никакой терминальной цепочки и их можно удалить из грамматики вместе со всеми правилами, в которые они входят. Грамматика G1, эквивалентная исходной грамматике, будет включать следующее множество правил:

S → SA | bAb; A → aSa | bb.

В грамматике G1 все нетерминалы продуктивны.

Построение грамматики, аксиома которой зависит от всех нетерминалов

   Существует еще один тип нетерминальных символов, которые можно удалять из грамматики вместе с правилами, в которые они входят. Например, в грамматике G, заданной множеством правил P: S → aSb | ba; A → aAa | bba, нетерминал А не участвует ни в каком выводе, т.к. из аксиомы нельзя вывести цепочку, содержащую этот нетерминал. Поэтому из заданной грамматики можно удалить нетерминал А. Рассмотрим, как для произвольной КС-грамматики можно построить эквивалентную КС-грамматику, аксиома которой зависит от всех нетерминальных символов.

   Для этого построим множество нетерминалов, от которых зависит аксиома. С этой целью выделим множества W1, W2, . . . , Wn+1по следующим правилам:

W1 = {S},

Wn+1 = Wn ∪{B | A → xBy ∈ P, A ∈ Wn}.

   Нетерминал B∈Wn тогда и только тогда, когда аксиома S зависит от B. Все нетерминалы, не содержащиеся в Wn, можно удалить из грамматики вместе с правилами, в которые они входят.

Пример. Пусть дана КС-грамматика G:

S → abS | ASa | ab; A → abAa | ab; B → bAab | bB.

Найдем нетерминалы, от которых зависит аксиома:

W1 = {S},

W2 = {S, A}, т.к. имеется правило S → Asa и S ∈ W1;

W3 = W2.

Эквивалентная грамматика G1, аксиома которой зависит от всех нетерминальных символов:

S → abS | ASa | ab; A → abAa | ab.

Удаление правил с терминальной правой частью

   Пусть в грамматике G имеется с терминальной правой частью A→β, где β ∈ V*T. Тогда любой вывод с использованием этого правила имеет вид: S →* xAy → xβy. Здесь нетерминал А в сентенциальной форме xAy появился на предыдущем шаге вывода B → uAv. Если в это правило вместо А подставить β, получим правило B → uβv. Тогда длина вывода некоторой цепочки сократится на один шаг. Следовательно, для того чтобы удалить

терминальное правило грамматики A→β, необходимо учесть следующие правила:

   а) если для нетерминала А больше нет правил, тогда во всех правых частях А заменяется

на β;

   б) если для нетерминала А есть другие правила, тогда добавляются новые правила, в которых А заменяется на β.

Пример. Пусть дана КС-грамматика G:

S → aSb | bAa | B; A → ABa | b | ε; B → ab | ba.

Удалим правила для нетерминала В. Тогда U_8Н_ ˜Пэ_эквивалентная грамматика G1 будет включать

следующие правила:

S → aSb | bAa | ab | ba;    A → Aaba | Abaa| b | ε.

Построение эквивалентной праворекурсивной КС-грамматики

   Некоторые специальные методы грамматического разбора неприменимы к

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

рекурсии в другой. Рассмотрим, как для любой леворекурсивной КС-грамматики построить эквивалентную праворекурсивную КС-грамматику.

   Пусть нетерминал А - леворекурсивен, т.е. для него имеются правила следующего вида:

A → Ax1 | Ax2 | . . . | Axp | w1| . . . | wk, где xi и wj - цепочки над множеством VT ∪ VN.

   Введем дополнительные нетерминалы B и D и указанные правила заменим на

эквивалентные им:

A → AB | D;

B → x1 | x2 | . . . | xp;

D → w1| w2 | . . . | wk.

В результате замены получим вывод, который имеет вид:

A → AB→ ABB → ABBB → . . . → AB* → DB*.

   Таким образом, для нетерминала А можно определить эквивалентные правила:

A → DK;

K → BK | ε.

   Выполняя подстановку D и B в эти правила, получим следующие праворекурсивные правила:

A → w1K| w2K | . . . | wkK;

K → x1K | x2K | . . . | xpK | ε.

Пример. Пусть задана грамматика G со следующими правилами вывода:

S → Sa | ba.

Требуется построить эквивалентную ей праворекурсивную грамматику.

   Для решения задачи воспользуемся рассмотренным выше алгоритмом. В исходной грамматике один леворекурсивный нетерминал S. Построим для него вывод:

S → SB | D;

B → a; D → ba. Вывод из S имеет вид: S → SB→ SBB→ . . . →DB*.

Запишем эквивалентные правила для S:

S → DK; K → BK | ε.

Подставим в эти правила B и D и получим эквивалентную праворекурсивную

грамматику G1:

S → baK; K → aK | ε.

Рассмотрим вывод цепочки baaaa в исходной леворекурсивной грамматике G:

S → Sa → Saa → Saaa → baaaa.

Эту же цепочку можно вывести в эквивалентной праворекурсивной грамматике G1:

S → baK → baaK → baaaK → baaaaK → baaaa.

 

 

 

 

 

Практическая часть

Задание 1. Расчет информационной емкости документов предметной области.

 

Р1	Р2	Р3	Р4	Р5	Р6	Р7	Р8	Р9	Р10	Р11	Р12
Код подразделения	Название подразделение	Код должности	Название должности	Должностной оклад	ФИО	Дата рождения	Домашний адрес	паспорт	Табельный номер	пол	Дата назначения
03	Отдел маркетинга	106	Завотделом	1000	СмирноваА.И.	20.01.1987	Ул. Ленина д. 10 кв. 9	4203457645	1022	Жен	20.08.2006
10	Плановый отдел	414	Маркетолог	15000	Петров Н.П.	14.02.1995	Ул. Интернациональная д. 50. Кв. 3	3908763412	1023	Муж	6.05.2008
12	бухгалтерия	302	Старший экономист	16000	Грядкина Н.В.	3.11.1991	Ул. Лесная д. 69. КВ. 10	4105478375	1024		11.07.2011
	Экономический отдел	306	Экономист	9000	Булочкин О.Г.	25.09.1994	Кл. пушкина д. 20. КВ. 4	3811347509	1025		5.05.2007
		102	Главный бухгалтер	12000	Иванов Ф.А.	31.12.1975	Ул центральная д. 56. КВ.14	4208486574	1026		10.07.2009
		211	Старший бухгалтер	12500
		212	Бухгалтер	13000
		214	кассир	5000