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

Размещено на http://allbest.ru

Введение

ФОРМАЛЬНЫЕ ГРАММАТИКИ И ЯЗЫКИ

В последние три десятилетия появилось большое количество работ по общей теории языков и грамматик. Можно выделить четыре научных направления, которые удалось объединить по методам их исследования в одну общую задачу теории языков. Первое из этих направлений связано с построением формальной, или математической, лингвистики, которая начала особенно быстро развиваться в тот период, когда были сформулированы вопросы машинного перевода. Эта проблема требовала формализации понятий словарь, грамматика, язык, их классификации и умения относить конкретные словари, грамматики, языки к определенному классу. Интерес к задачам такого рода еще более усилился с появлением искусственных языков программирования. С появлением трансляторов проблема перевода во многом определила построение общей теории вычислительных машин, а сами языки программирования стали все более приближаться к формально построенным математическим конструкциям. Независимо от указанных двух направлений развивалось построение формальных моделей динамических систем. Для создания продуктивной теории эти модели должны были быть, с одной стороны, достаточно узкими, а с другой - достаточно широкими, чтобы охватить некоторый общий класс прикладных задач. Типичным примером такого рода является модель конечного автомата. Эта модель позволяет описать многие процессы, заданные на конечных множествах и развивающиеся в счетном времени, что позволило создать для нее продуктивную теорию. Если в эту модель ввести бесконечность по какому- либо параметру, то это приводит к общему классу систем, например, к машинам Тьюринга. Независимо и параллельно развивалась общая теория алгоритмов как ветвь современной математики. Развитие вычислительной техники поставило перед математической теорией алгоритмов новую задачу: стало необходимым классифицировать алгоритмы по различным признакам. Эквивалентность понятий "алгоритм" и "машина Тьюринга" позволила предположить, что поиски классификации алгоритмов окажутся связанными с поисками промежуточных моделей между моделями конечного автомата и машиной Тьюринга. Таким образом, перечисленные четыре направления оказались тесно связанными. Теория языков, порожденная чисто лингвистическими задачами, оказалась в центре интересов математиков, занимающихся теорией алгоритмов, и ученых, разрабатывающих абстрактные модели динамических систем и теоретические основы автоматики. Теория формальных языков и грамматик является разделом математической лингвистики - специфической математической дисциплины, ориентированной на изучение структуры естественных и искусственных языков. По характеру используемого математического аппарата теория формальных грамматик и языков близка к теории алгоритмов и теории автоматов. На интуитивном уровне язык можно определить как некоторое множество предложений с заданной структурой, имеющих определенное значение. Правила, определяющие допустимые конструкции языка, составляют синтаксис языка. Значение, или смысл фразы, определяется семантикой языка. Если бы все языки состояли из конечного числа предложений, то не было бы проблемы синтаксиса. Но, так как язык содержит неограниченное (или довольно большое) число правильно построенных фраз, то возникает проблема описания бесконечных языков с помощью каких-либо конечных средств. Различают следующие виды описания языков:

1) порождающее, которое предполагает наличие алгоритма, последовательно порождающего все правильные предложения языка;

2) распознающее, которое предполагает наличие алгоритма, определяющего принадлежность любой фразы данному языку.

1. Основные понятия порождающих грамматик

грамматика граф алгоритм

Алфавит - это непустое конечное множество. Элементы алфавита называются символами.

Цепочка над алфавитом У={а1, а2, …, аn} есть конечная последовательность элементов аi. Множество всех цепочек над алфавитом У обозначается ыяяяяЬя*@_У*. Длина цепочки х равна числу ее элементов и обозначается |x|. Цепочка нулевой длины называется пустой и обозначается символом е. Соответственно, непустая цепочка определяется как цепочка ненулевой длины. Пусть имеется алфавит У={а, b}. Тогда множество всех цепочек определяется следующим образом: У*={ е, а, b, aa, ab, ba, bb, aaa, aab, aba, . . .}.

Цепочки x и y равны, если они одинаковой длины и совпадают с точностью до порядка символов, из которых они состоят. Над цепочками x и y определена операция сцепления (конкатенации, произведения), которая получается дописыванием символов цепочки y за символами цепочки x. Язык L над алфавитом У представляет собой множество цепочек над У. Необходимо различать пустой язык L=0 и язык, содержащий только пустую цепочку: L={е}?0. Формальный язык L над алфавитом У - это язык, выделенный с помощью конечного множества некоторых формальных правил. Пусть M и L - языки над алфавитами. Тогда конкатенация LM = {xy?x?L, y?M}. В частности, {е}L = L{е}=L. Используя понятие произведения, определим итерацию L* и усеченную итерацию L+ множества L:

L+ = U

?

i=1

Li ,

L* = U

?

i=1

Li ,

где i - степень языка, L определяется рекурсивно следующим образом:

L0 = {е};

L1 = L;

Ln+1 = Ln L = L Ln;

{е}L=L{е}=L.

Например, если задан язык L={a}, тогда L*={е, а, аа, ааа, …}, L+={a, aa, aaa, …}.

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

VT - конечный алфавит, определяющий множество терминальных символов;

VN - конечный алфавит, определяющий множество нетерминальных символов;

Р - конечное множество правил вывода, т.е. множество пар следующего вида:

u > v, где u, v ?(VT?VN)*;

S - начальный символ (аксиома грамматики), S?VN.

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

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

В грамматике G цепочка х непосредственно порождает цепочку у, если х = бuв, у = бvв и u>v ? Р, т.е. цепочка у непосредственно выводится из х, что обозначается х => у.

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

L(G) = {х | х ? VT*; S => *х}, где =>*- выводимость.

Пример. Дана грамматика G = (VT, VN, Р, S), в которой VT = {а, b}, VN = {S}, Р = {S > aSb, S > ab). Определить язык, порождаемый этой грамматикой.

Решение. Используя рекурсию, выведем несколько цепочек языка, порождаемого данной грамматикой:

S > ab;

S > aSb => aabb;

S > aSb =>aaSbb => aaabbb; . . .

Определим язык, порожденный данной грамматикой:

L(G) = {anbn | n > 0}.

Говоря о представлении грамматик, нужно отметить, что множество правил вывода грамматики может приводиться без специального указания множеств терминалов и нетерминалов. В таком случае обычно предполагается, что грамматика содержит в точности те терминальные и нетерминальные символы, которые встречаются в правилах вывода. Также предполагается, что правые части правил, для которых совпадают левые части, можно записать в одну строку с использованием разделителя. Так, правила вывода из приведенного примера можно записать следующим образом: S > aSb | ab.

1.2 Классификация грамматик

Правила порождающих грамматик позволяют осуществлять преобразования строк. Ограничения же на виды правил позволяют выделить классы грамматик. Рассмотрим классификацию, которую предложил Н. Хомский. Грамматики типа 0 - это грамматики, на правила вывода которых нет ограничений. Грамматики типа 1, или контекcтные грамматики -это грамматики, все правила которых имеют следующий вид: хАу > х?у, где A ? VN, x, y, ? ? (VN ? VT)+.

Грамматики типа 2 - это бесконтекстные, или контекстно-свободные грамматики (КС- грамматики). Правила вывода для этих грамматик имеют следующий вид: А > ?, где А ? VN, ? ? (VN ? VT)*.

Грамматики типа 3 - это автоматные грамматики, которые делятся на два типа:

а) леволинейные (леворекурсивные), правила вывода для которых имеют следующий вид: А > Аа | a, где А ? VN;

б) праволинейные (праворекурсивные), правила вывода для которых имеют следующий вид: А > Aа | a.

Язык L называется языком типа i, если существует грамматика типа i, порождающая язык L.

1.3 Методика решения задач

Пример 1. Дана порождающая грамматика G = (VT, VN, Р, S), в которой VT = {a, d, е}, VN = {В, С, S}, Р = {S > аВ, В > Cd | dC, С > е}. Выписать терминальные цепочки, порожденные данной грамматикой, и определить длину их вывода.

Решение. Получим следующие терминальные цепочки:

S > аВ > aCd > aed,

S > аВ > adC > ade,

длина вывода которых равна 3.

Пример 2. Дана грамматика G = (VT, VN, Р, C), в которой VT = {a, b, c, d, е}, VN = {A, В, С, D, E}, Р = {A > ed, В > Ab, С > Bc, С > dD, D > Ae, E > bc}. Определить, принадлежит ли языку L(G) цепочка eadabcb.

Решение. Выведем возможные терминальные цепочки из аксиомы с помощью заданных правил вывода:

С > Bc > Abc > edbc,

С > dD > dAe > dede.

Так как первые же терминальные символы полученных цепочек не совпадают с заданной, можно сделать вывод о том, что цепочка eadabcb не принадлежит языку L(G).

Пример 3. Построить КС-грамматику (грамматику типа 2), порождающую цепочки из 0 и 1 с одинаковым числом тех и других символов.

Решение. Определим множества, задающие грамматику:

VT = {0, 1}; VN = {S}; Р = {S > 0S1, S > 1S0, S > е, S > S01, S > S10}.

Пример 4. Описать язык, порождаемый следующими правилами: S > bSS | а.

Решение. Построим несколько терминальных цепочек, применяя заданные правила вывода:

S > a;

S > bSS > baa;

S > bSS > bbSSS > bbaaa;

S > bSS > bbSSbSS > bbaabaa;

S > bSS > bbSSbSS > bbbSSbSSbbSSbSS > ...

Из полученных цепочек видно, что:

а) цепочки всегда начинаются с терминала b, кроме аксиомы, и заканчиваются терминалом а;

б) количество терминалов а в любой цепочке всегда на 1 больше, чем b.

Исходя из этих выводов, определим язык, порождаемый заданными правилами, следующим образом:

L(G) = {б | б ? {a, b}*}, |a| = |b| + 1, причем цепочки начинаются с терминала b и заканчиваются терминалом а.

1.4 Грамматический разбор

В КС-грамматике может быть несколько выводов, эквивалентных в том смысле, что в них применяются одни и те же правила к одинаковым в промежуточном выводе цепочкам, но в различном порядке. Например, для грамматики G с правилами вывода S > ScS|b|a возможны следующие эквивалентные выводы терминальной цепочки acb:

S > ScS > Scb > acb и S > ScS > acS > acb.

Деревом вывода цепочки х в КС-грамматике G = (VT, VN, Р, S) называется упорядоченное дерево, каждая вершина которого помечена символом из множества V ? VN ? {е} так, что каждому правилу А > b1b2b3 ... bk, использующемуся при выводе цепочки х, в дереве вывода соответствует поддерево с корнем А и прямыми потомками b1, b2, b3, ..., bk, которое приведено на рисунке:

A

b1 b2 … bk

В силу того, что цепочка х ? L(G) выводится из аксиомы S, корнем вывода всегда является аксиома. Внутренние узлы вывода соответствуют нетерминальным символам. Концевые вершины дерева вывода - листья - это вершины, не имеющие потомков. Такие вершины соответствуют либо терминалам, либо пустым символам (е) при условии, что среди правил грамматики имеются правила с пустой правой частью. При чтении слева направо концевые вершины дерева вывода образуют цепочку х. Дерево вывода часто называют деревом грамматического разбора, или синтаксическим деревом, а процесс построения дерева вывода - грамматическим разбором (синтаксическим анализом). Одной цепочке языка может соответствовать больше одного дерева, так как эта цепочка может иметь разные выводы, порождающие разные деревья. КС-грамматика G == (VT, VN, Р, S) называется неоднозначной (неопределенной), если существует цепочка х ? L(G), имеющая два или более дерева вывода.

Рассмотрим пример.

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

G1 = (VT, VN, Р1, S), VN = {S},

P1={S > S+S | S | SsS | (S) | a};

G2= (VT, VN, Р2, S), VN = {S, A, B},

P2 = {S > S + A | A | A, A > AаB | A / B | B, B > a| (S)},

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

Решение: Грамматика G1 является неоднозначной, так как она имеет правила с правой частью, содержащей два вхождения нетерминала S и знак арифметической операции.

Построим два дерева вывода для простейшей цепочки а + а + а:

Грамматика G2 является однозначной, так как не содержит правил с двойным вхождением нетерминального символа. Так, для цепочки а + а + а она имеет только одно дерево вывода.

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

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

Преобразование цепочки, обратное порождению, называется редукцией.

1.4.1 Представление грамматики в виде графа

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

Рассмотрим представление грамматики G в виде графа: G = (VT, VN, Р, S), в которой VT ={a, b, с}, VN = {S}, P={S > aSa | bSb | c}.

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

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

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

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

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

Пусть имеется КС-грамматика 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 > ?, где Аj > ? ? P2. Построим эквивалентную КС-грамматику Gэ = (VT, VN, Pэ, S), в которой множества терминальных и нетерминальных символов, а также аксиома совпадают с теми же объектами исходной грамматики G, а множество правил Pэ получено объединением правил множества P2 и правил P(Аi) для всех 1? i ?n:

n

Pэ = U

i=1

P ( A i ) ? P2 .

Пример. Пусть задана грамматика G со следующими правилами вывода S > aFb | А; А > аА | В; В > aSb | S; F > bc | bFc.

Построим множества правил Р2, P(S), P(A), P(B), P(F).

Определим правила для Р2: Р2 = {S > aFb; А > аА; В > aSb; F > bc | bFc}.

Определим правила для P(S): S => A => B или S =>*А; S=>В, где =>* обозначает непосредственную выводимость. P(S) = {S > аА; S > aSb).

Определим правила для Р(А): А => В => S или А =>* В; А => S. Р(А) = {А > aSb; А > aFb}.

Определим правила для Р(В): В => S => А или В =>* S; В =>*А. Р(В) = {В > aFb; В > аА}.

Определим правила для P(F): так как непосредственно выводимых нетерминалов не существует, то P(F) = 0.

Объединив полученные правила, можно записать грамматику Gэ, эквивалентную исходной:

S > aFb | aSb | аА; А > аА | aSb | aFb;

В > аА | aSb | aFb; F > bc | bFc.

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

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

aFb aA aSb bFc bc

S A B F

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

S > aFb | aSb | аА;

А > аА | aSb | aFb;

В > аА | aSb | aFb;

F > bc | bFc.

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

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

Грамматика, не содержащая правил с пустой правой частью, называется неукорачивающей грамматикой. В грамматике с правилами вида А>е длина выводимой цепочки при переходе от 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.

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

Нетерминальный символ А называется непродуктивным (непроизводящим), если он не порождает ни одной терминальной цепочки, т.е. не существует вывода А >* х, где х?V*T. Поэтому представляет интерес удаление из грамматики всех непродуктивных нетерминальных символов. Рассмотрим, как для произвольной КС-грамматики можно построить эквивалентную КС-грамматику, все нетерминальные символы которой продуктивны. С этой целью выделяется множество W1={A | A > ? ? P, ? ? V*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 все нетерминалы продуктивны.

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

Существует еще один тип нетерминальных символов, которые можно удалять из грамматики вместе с правилами, в которые они входят. Например, в грамматике 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.

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

Пусть в грамматике 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.

Удалим правила для нетерминала В. Тогда эквивалентная грамматика G1 будет включать следующие правила:

S > aSb | bAa | ab | ba; A > Aaba | Abaa| b | е.

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

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

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

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.

3. Приведение КС-грамматики к нормальному виду

Приведенные грамматики

Приведенные грамматики - это КС-грамматики, которые не содержат недостижимых и бесплодных символов, циклов и -правил ("пустых" правил). Приведенные грамматики называют также КС-грамматиками в каноническом виде.

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

удалить все бесплодные символы;

удалить все недостижимые символы;

удалить -правила;

удалить цепные правила.

Следует подчеркнуть, что шаги преобразования должны выполняться именно в указанном порядке, и никак иначе.

3.1 Преобразования грамматик

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

Определение: символ A є VN называется бесплодным в грамматике G = (VT, VN, P, S), если множество { | є VT^*, A => } пусто.

Определение: символ x є (VT U VN) называется недостижимым в грамматике G = (VT, VN, P, S), если он не появляется ни в одной сентенциальной форме этой грамматики.

Алгоритм удаления бесплодных символов

Вход: КС-грамматика G = (VT, VN, P, S).

Выход: КС-грамматика G' = (VT, VN', P', S), не содержащая бесплодных символов, для которой L (G) = L (G').

Метод:

Рекурсивно строим множества N₀, N₁,.

1. N₀ = , i = 1.

2. N_i = {A | (A > ) є P и є (N_i-1 U VT) ^*} U N_i-1.

3. Если N_i ? N_i-1, то i = i+1 и переходим к шагу 2, иначе VN' = N_i; P' состоит из правил множества P, содержащих только символы из VN' VT; G' = (VT, VN', P', S).

3.2 Алгоритм удаления недостижимых символов

Вход: КС-грамматика G = (VT, VN, P, S)

Выход: КС-грамматика G' = (VT', VN', P', S), не содержащая недостижимых символов, для которой L (G) = L (G').

Метод:

1. V₀ = {S}; i = 1.

2. V_i = {x | x є (VT U VN), (A > x) P и A є V_i-1} U V_i-1.

3. Если V_i ? V_i-1, то i = i+1 и переходим к шагу 2, иначе VN' = V_i VN; VT' = V_i VT; P' состоит из правил множества P, содержащих только символы из Vi; G' = (VT', VN', P', S).

Удаление символов сопровождается удалением правил вывода, содержащих эти символы.

Если в этом алгоритме переставить шаги (1) и (2), то не всегда результатом будет правильным.

В качестве примера рассмотрим контекстно-свободную грамматику G с правилами

S > U, S > VZ, T > aa, T > bb, U > aUa, U > bUb, V > aTb, V > bTa, W > YZY, W > aab, X > Xa, X > Xb, X > е, Y > YY, Y > aU, Y > е, Z > W, Z > b.

Удалив четыре правила, содержащие бесплодный символ U, получим грамматику G1:

S > VZ, T > aa, T > bb, V > aTb, V > bTa, W > YZY, W > aab, X > Xa, X > Xb, X > е, Y > YY, Y > е, Z > W, Z > b.

В ней символ X является недостижимым. Удалив три правила, содержащие X, получим грамматику G2 с правилами:

S > VZ, T > aa, T > bb, V > aT b, V > bT a, W > YZY, W > aab, Y > YY, Y > е, Z > W, Z > b.

Очевидно, L (G) = L (G2) и грамматика G2 не содержит бесплодных и недостижимых символов.

Преобразование неукорачивающих грамматик

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

Определение. Правило вида A > называется "пустым" (аннулирующим) правилом.

Определение. Грамматика называется неукорачивающей или грамматикой без "пустых" правил, если либо

1) схема грамматики не содержит аннулирующих правил,

2) либо схема грамматики содержит только одно правило вида S > , где S - начальный символ грамматики, и символ S не встречается в правых частях остальных правил грамматики.

Для грамматик, содержащих аннулирующие правила, справедливо следующее утверждение.

Утверждение. Для каждой КС-грамматики G', содержащей аннулирующие правила, можно построить эквивалентную ей неукорачивающую грамматику G, такую что

L (G') =L (G).

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

Если же в грамматике есть правило вида S > , где S - начальный символ грамматики, и символ S входит в правые части других правил грамматики, то следует ввести новый начальный символ S' и заменить правило S > двумя новыми правилами: S' > и S'> S.

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

G ({a,b}, {S}, P = { S > aSbS, S > bSaS, S > }, S).

Выполняя все возможные замены символа S в первом правиле грамматики, получаем четыре правила вида:

S > aSbS, S > abS, S > aSb, S > ab.

Поступая аналогично со вторым правилом, имеем:

S > bSaS, S >baS, S > bSa, S > ba.

Учитывая, что начальный символ, образующий аннулирующее правило, входит в правые части других правил грамматики, заменим правило S > правилами вида S' > и S' > S.

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

S' > S | , S > aSbS | abS | aSb | ab | bSaS |?baS | bSa | ba

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

3.3 Исключение цепных правил

Определение. Правило грамматики вида A > B, где A, B є VN, называется цепным.

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

Идея доказательства заключается в следующем.

Если грамматика G имеет правила A > B, B > C, C > aX, то такие правила могут быть заменены одним правилом А > aX, поскольку вывод А => B => C => aX цепочки aX в грамматике G может быть получен в грамматике G' с помощью правила A >aX.

1. Для каждого А є N построить N_A={B¦A =>*B} следующим образом:

а) Положить N₀ = {A} и i=1.

б) Положить N_i ={C¦B>C принадлежит Р и В є N_i-1 } U N_i-1.

в) Если N_i ? N_i-1, положить i = i+1 и повторить шаг (б).

В противном случае положить N_A = N_i.

2. Построить Р' так: если В > б принадлежит Р и не является цепным правилом, включить в Р' правило А > б для всех таких А, что В є N_А.

3. Положить G' = (VT, VN, P', S).

В качестве примера выполним исключение цепных правил из грамматики G:

G = ({+,*, (,),a}, {E,T,F}, P={E > E+T | T, Т > T*F | F, F > (E) | a}, E).

Разобьем правила грамматики на два подмножества:

P₁ = {E > T, T > F},

P₂ = {E > E+T, T > T*F, F > (E) | a }

На шаге (1) N_Е = {E, T, F}, N_T = {T, F}, N_F = {F}. После шага (2) множество Р' станет таким

E > T+T | T*F | (E) | a

T > T*F | (E) | a

F > (E) | a

3.4 Описание процедур

1) Анализ

Входные данные: правила, введенные в Memo1.

Выходные данные: правила, выведенные в Memo2.

procedure TForm1. btn1Click (Sender: TObject);

label l;

BEGIN

mmo2. Clear;

for i: =0 to mmo1. Lines. Count do

if Length (mmo1. Lines [i]) >2 then begin

mm: = []; s: =mmo1. Lines [i];

for j: =0 to Length (s) do begin

if (s [j] in ['А'. 'Я']) or (s [j] in ['а'. 'я']) then mmo1. Lines. Delete (i);

mm: =mm+ [s [j]]; end;

if (not (s [1] in ['A'. 'Z'])) or (s [2] <>'-') or (' ' in mm) then mmo1. Lines. Delete (i);

end else mmo1. Lines. Delete (i);

for i: =0 to mmo1. Lines. Count do begin

s: =mmo1. Lines [i];

n: =Pos ('/',s); Delete (s,n,1);

m: =Pos ('/',s); Delete (s,m,1);

if (n>0) and (m>0) and (n<m) then begin

mmo2. Lines. Add (Copy (s,1,n-1));

mmo2. Lines. Add (Copy (s,1,2) +Copy (s,n,m-n));

mmo2. Lines. Add (Copy (s,1,2) +Copy (s,m,Length (s) - m+1));

goto l;

end;

IF n>0 then begin

mmo2. Lines. Add (Copy (s,1,n-1));

mmo2. Lines. Add (Copy (s,1,2) +Copy (s,n,Length (s) - n+1));

goto l;

end;

IF (n=0) and (Length (s) >2) then mmo2. Lines. Add (s);

l:

end;

for i: =0 to mmo2. Lines. Count do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

END;

Пример выполнения:

Введем в Мемо1 следующие правила и нажмем на кнопку 1

грамматика алгоритм символ правило

2) Удаление бесплодных символов

Входные данные: правила из Мемо2

Выходные данные: правила в Мемо2 (без бесплодных символов)

procedure TForm1. btn2Click (Sender: TObject);

var vn2: set of Char;

begin

v: =mmo2. Lines. Count;

for i: =0 to v do p [i]: ='';

for i: =0 to v do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do

if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

mmo2. Clear;

vn: = [];

for i: =0 to v-1 do if mn [i] = [] then vn: =vn+ [p [i,1]];

vn2: = [];

j: =0;

while vn<>vn2 do begin

vn: =vn2;

for i: =0 to V-1 do

if (mn [i] - vn= [])

then vn2: =vn2+vn+ [p [i,1]];

end;

for i: =0 to v do

for j: =1 to Length (p [i]) do

if Length (p [i]) >2 then if (not (p [i,j] in vn)) and (p [i,j] in ['A'. 'Z']) then p [i]: ='';

for i: =0 to v do begin mn [i]: = [];

for j: =3 to Length (p [i]) do if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [p [i,j]];

if Length (p [i]) >2 then mmo2. Lines. Add (p [i]);

end;

for i: =0 to v do p [i]: ='';

for i: =0 to mmo2. Lines. Count do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do

if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

end;

Пример использования:

1. Введем в Мемо1 правила

2. Нажмем на кнопку 1

3. Нажмем на кнопку 1

3) Удаление недостижимых символов

Входные данные: правила из Мемо2

Выходные данные: правила в Мемо2 (без недостижимых символов)

procedure TForm1. btn3Click (Sender: TObject);

begin

v: =mmo2. Lines. Count;

for i: =0 to v do p [i]: ='';

for i: =0 to v do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do

if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

mmo2. Clear;

vn: = [];

for i: =0 to 3 do

if Length (p [i]) >1 then begin vn: =vn+ [p [i,1]] +mn [0]; Break; end;

m: =0;

while m<4 do begin

for i: =0 to v do

if Length (p [i]) >2 then

if p [i,1] in vn then vn: =vn+mn [i];

Inc (m);

end;

for i: =0 to v do

for j: =0 to Length (p [i]) do

if Length (p [i]) >2 then if (not (p [i,j] in vn)) and (p [i,j] in ['A'. 'Z']) then p [i]: ='';

for i: =0 to v do

if Length (p [i]) >2 then mmo2. Lines. Add (p [i]);

for i: =0 to v do p [i]: ='';

for i: =0 to mmo2. Lines. Count do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do

if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

end;

Пример использования:

1. Введем правила в Мемо1

2. Нажмем на кнопку 1

3. Нажмем на кнопку 3

4) Устранение правил с пустой правой частью

Входные данные: правила из Мемо2

Выходные данные: правила в Мемо2

procedure TForm1. btn4Click (Sender: TObject);

begin

v: =mmo2. Lines. Count;

for i: =0 to v do p [i]: ='';

for i: =0 to v do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do

if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

mmo2. Clear;

j: =0;

for i: =0 to v do

if Length (p [i]) >2 then

if p [i,3] ='e' then begin

Inc (j); r [j]: =p [i,1]; p [i]: ='';

end;

n: =j; k: =0;

for i: =1 to n do

for j: =0 to v do begin

if Length (p [j]) >1 then

if r [i] in mn [j] then begin

s: =p [j];

Delete (s,1,2);

s1: =s;

m: =Pos (r [i],s);

delete (s,m,1);

l: =Pos (r [i],s);

if (m>0) and (l>0) then begin

inc (k);

p [k+v]: =Copy (p [j],1,2) +s;

Inc (k); l: =Pos (r [i],s); Delete (s1,l+1,1);

p [k+v]: =Copy (p [j],1,2) +s1;

Inc (k); l: =Pos (r [i],s1); Delete (s1,l,1);

p [k+v]: =Copy (p [j],1,2) +s1;

end;

if (m>0) and (l=0) then begin

inc (k);

p [k+v]: =Copy (p [j],1,2) +s;

end;

end; end;

for i: =0 to v+ (k-1) do

for j: =i+1 to v+k do begin

if p [i] =p [j] then p [j]: ='';

if (Length (p [i]) =3) and (p [i,1] =p [i,3]) then p [i]: ='';

end;

for i: =0 to v+k do

if Length (p [i]) >2 then mmo2. Lines. Add (p [i]);

for i: =0 to v do p [i]: ='';

for i: =0 to mmo2. Lines. Count do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do

if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

end;

Пример использования:

1. Вводим правила в Мемо1

2. Нажимаем на кнопку 1

3. Нажимаем на кнопку 4

5) Исключение цепных правил

Входные данные: правила из Мемо2

Выходные данные: правила в Мемо2

procedure TForm1. btn5Click (Sender: TObject);

begin

v: =mmo2. Lines. Count;

for i: =0 to v do p [i]: ='';

for i: =0 to v do p [i]: =mmo2. Lines [i];

mmo2. Clear;

for i: =1 to 5 do r [i]: =' '; k: =0;

for i: =0 to v do

if Length (p [i]) =3 then

if (p [i,1] in ['A'. 'Z']) and (p [i,3] in ['A'. 'Z']) and (p [i,1] <>p [i,3]) then begin

inc (k); r [k]: =p [i,1]; r [k+1]: =p [i,3]; p [i]: ='';

end;

for i: =1 to k do begin

mn [i]: = [];

for j: =i+1 to k+1 do

mn [i]: =mn [i] + [r [j]];

end;

m: =0; l: =0;

for i: =1 to k do begin

inc (m);

for j: =0 to v do

if (Length (p [j]) >2) and (p [j,1] in mn [m]) then begin

inc (l); p [v+l]: =p [j];

p [v+l,1]: =r [m]; end;

end;

for i: =0 to v+l do

if Length (p [i]) >2 then mmo2. Lines. Add (p [i]);

end;

Пример использования:

1. Ведем правила в Мемо1

2. Нажмем на кнопку 1

3. Нажмем на кнопку 5

Литература

1. "Теория и реализация языков программирования" Серебряков В. А. Издательство М3-Пресс, 1999г., 174 стр.

2. "Давайте создадим компилятор!" Джек Креншоу Издательство Самиздат, 1995г., 135 стр.

3. "Алгоритмы, языки, автоматы и компиляторы" М. Мозговой Издательство Наука и техника, 2006г., 316 стр.

4. Крючкова Е.Н. «Теория формальных языков и автоматов» - Барнаул; 1996.

Приложение

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ComCtrls, Grids, jpeg, ExtCtrls, XPMan, Menus, Buttons;

type

TForm1 = class (TForm)

btn1: TButton;

mmo1: TMemo;

mmo2: TMemo;

btn2: TButton;

btn3: TButton;

btn4: TButton;

btn5: TButton;

lbl1: TLabel;

xpmnfst1: TXPManifest;

procedure btn1Click (Sender: TObject);

procedure btn2Click (Sender: TObject);

procedure btn3Click (Sender: TObject);

procedure btn4Click (Sender: TObject);

procedure btn5Click (Sender: TObject);

procedure btn1MouseMove (Sender: TObject; Shift: TShiftState; X,

Y: Integer);

procedure btn2MouseMove (Sender: TObject; Shift: TShiftState; X,

Y: Integer);

procedure FormMouseMove (Sender: TObject; Shift: TShiftState; X,

Y: Integer);

procedure btn3MouseMove (Sender: TObject; Shift: TShiftState; X,

Y: Integer);

procedure btn4MouseMove (Sender: TObject; Shift: TShiftState; X,

Y: Integer);

procedure btn5MouseMove (Sender: TObject; Shift: TShiftState; X,

Y: Integer);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

i,m,n,j,v,k,l: Integer;

s,s1: string;

p: array [0.40] of string;

vn,vt,k1,k2,mm: set of Char;

mn: array [0.25] of set of Char;

c: Char;

r: array [1.5] of Char;

implementation

{$R *. dfm}

procedure TForm1. btn1Click (Sender: TObject);

label l;

BEGIN

mmo2. Clear;

for i: =0 to mmo1. Lines. Count do

if Length (mmo1. Lines [i]) >2 then begin

mm: = []; s: =mmo1. Lines [i];

for j: =0 to Length (s) do begin

if (s [j] in ['А'. 'Я']) or (s [j] in ['а'. 'я']) then mmo1. Lines. Delete (i);

mm: =mm+ [s [j]]; end;

if (not (s [1] in ['A'. 'Z'])) or (s [2] <>'-') or (' ' in mm) then mmo1. Lines. Delete (i);

end else mmo1. Lines. Delete (i);

for i: =0 to mmo1. Lines. Count do begin

s: =mmo1. Lines [i];

n: =Pos ('/',s); Delete (s,n,1);

m: =Pos ('/',s); Delete (s,m,1);

if (n>0) and (m>0) and (n<m) then begin

mmo2. Lines. Add (Copy (s,1,n-1));

mmo2. Lines. Add (Copy (s,1,2) +Copy (s,n,m-n));

mmo2. Lines. Add (Copy (s,1,2) +Copy (s,m,Length (s) - m+1));

goto l;

end;

IF n>0 then begin

mmo2. Lines. Add (Copy (s,1,n-1));

mmo2. Lines. Add (Copy (s,1,2) +Copy (s,n,Length (s) - n+1));

goto l;

end;

IF (n=0) and (Length (s) >2) then mmo2. Lines. Add (s);

l:

end;

for i: =0 to mmo2. Lines. Count do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

END;

procedure TForm1. btn2Click (Sender: TObject);

var vn2: set of Char;

begin

v: =mmo2. Lines. Count;

for i: =0 to v do p [i]: ='';

for i: =0 to v do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do

if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

mmo2. Clear;

vn: = [];

for i: =0 to v-1 do if mn [i] = [] then vn: =vn+ [p [i,1]];

vn2: = [];

j: =0;

while vn<>vn2 do begin

vn: =vn2;

for i: =0 to V-1 do

if (mn [i] - vn= [])

then vn2: =vn2+vn+ [p [i,1]];

end;

for i: =0 to v do

for j: =1 to Length (p [i]) do

if Length (p [i]) >2 then if (not (p [i,j] in vn)) and (p [i,j] in ['A'. 'Z']) then p [i]: ='';

for i: =0 to v do begin mn [i]: = [];

for j: =3 to Length (p [i]) do if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [p [i,j]];

if Length (p [i]) >2 then mmo2. Lines. Add (p [i]);

end;

for i: =0 to v do p [i]: ='';

for i: =0 to mmo2. Lines. Count do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do

if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

end;

procedure TForm1. btn3Click (Sender: TObject);

begin

v: =mmo2. Lines. Count;

for i: =0 to v do p [i]: ='';

for i: =0 to v do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do

if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

mmo2. Clear;

vn: = [];

for i: =0 to 3 do

if Length (p [i]) >1 then begin vn: =vn+ [p [i,1]] +mn [0]; Break; end;

m: =0;

while m<4 do begin

for i: =0 to v do

if Length (p [i]) >2 then

if p [i,1] in vn then vn: =vn+mn [i];

Inc (m);

end;

for i: =0 to v do

for j: =0 to Length (p [i]) do

if Length (p [i]) >2 then if (not (p [i,j] in vn)) and (p [i,j] in ['A'. 'Z']) then p [i]: ='';

for i: =0 to v do

if Length (p [i]) >2 then mmo2. Lines. Add (p [i]);

for i: =0 to v do p [i]: ='';

for i: =0 to mmo2. Lines. Count do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do

if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

end;

procedure TForm1. btn4Click (Sender: TObject);

begin

v: =mmo2. Lines. Count;

for i: =0 to v do p [i]: ='';

for i: =0 to v do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do

if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

mmo2. Clear;

j: =0;

for i: =0 to v do

if Length (p [i]) >2 then

if p [i,3] ='e' then begin

Inc (j); r [j]: =p [i,1]; p [i]: ='';

end;

n: =j; k: =0;

for i: =1 to n do

for j: =0 to v do begin

if Length (p [j]) >1 then

if r [i] in mn [j] then begin

s: =p [j];

Delete (s,1,2);

s1: =s;

m: =Pos (r [i],s);

delete (s,m,1);

l: =Pos (r [i],s);

if (m>0) and (l>0) then begin

inc (k);

p [k+v]: =Copy (p [j],1,2) +s;

Inc (k); l: =Pos (r [i],s); Delete (s1,l+1,1);

p [k+v]: =Copy (p [j],1,2) +s1;

Inc (k); l: =Pos (r [i],s1); Delete (s1,l,1);

p [k+v]: =Copy (p [j],1,2) +s1;

end;

if (m>0) and (l=0) then begin

inc (k);

p [k+v]: =Copy (p [j],1,2) +s;

end;

end; end;

for i: =0 to v+ (k-1) do

for j: =i+1 to v+k do begin

if p [i] =p [j] then p [j]: ='';

if (Length (p [i]) =3) and (p [i,1] =p [i,3]) then p [i]: ='';

end;

for i: =0 to v+k do

if Length (p [i]) >2 then mmo2. Lines. Add (p [i]);

for i: =0 to v do p [i]: ='';

for i: =0 to mmo2. Lines. Count do begin p [i]: =mmo2. Lines [i];

mn [i]: = [];

for j: =3 to Length (p [i]) do

if p [i,j] in ['A'. 'Z'] then mn [i]: =mn [i] + [P [i,j]];

end;

end;

procedure TForm1. btn5Click (Sender: TObject);

begin

v: =mmo2. Lines. Count;

for i: =0 to v do p [i]: ='';

for i: =0 to v do p [i]: =mmo2. Lines [i];

mmo2. Clear;

for i: =1 to 5 do r [i]: =' '; k: =0;

for i: =0 to v do

if Length (p [i]) =3 then

if (p [i,1] in ['A'. 'Z']) and (p [i,3] in ['A'. 'Z']) and (p [i,1] <>p [i,3]) then begin

inc (k); r [k]: =p [i,1]; r [k+1]: =p [i,3]; p [i]: ='';

end;

for i: =1 to k do begin

mn [i]: = [];

for j: =i+1 to k+1 do

mn [i]: =mn [i] + [r [j]];

end;

m: =0; l: =0;

for i: =1 to k do begin

inc (m);

for j: =0 to v do

if (Length (p [j]) >2) and (p [j,1] in mn [m]) then begin

inc (l); p [v+l]: =p [j];

p [v+l,1]: =r [m]; end;

end;

for i: =0 to v+l do

if Length (p [i]) >2 then mmo2. Lines. Add (p [i]);

end;

procedure TForm1. btn1MouseMove (Sender: TObject; Shift: TShiftState; X,

Y: Integer);

begin

lbl1. Caption: ='Анализ грамматики';

end;

procedure TForm1. btn2MouseMove (Sender: TObject; Shift: TShiftState; X,Y: Integer);

begin

lbl1. Caption: ='Удаление бесплодных символов';

end;

procedure TForm1. FormMouseMove (Sender: TObject; Shift: TShiftState; X,Y: Integer);

begin

lbl1. Caption: ='Приведение грамматики';

end;

procedure TForm1. btn3MouseMove (Sender: TObject; Shift: TShiftState; X,Y: Integer);

begin

lbl1. Caption: ='Удаление недостижимых символов';

end;

procedure TForm1. btn4MouseMove (Sender: TObject; Shift: TShiftState; X,Y: Integer);

begin

lbl1. Caption: ='Преобразование неукорачивающих правил';

end;

procedure TForm1. btn5MouseMove (Sender: TObject; Shift: TShiftState; X,Y: Integer);

begin

lbl1. Caption: ='Исключение цепных правил';

end;

end.

Пример работы программы:

Шаг 1: вводим правила в Мемо1

Шаг 2: нажимаем на кнопку 1

Шаг 3: нажимаем на кнопку 2

Шаг 4: нажимаем на кнопку 3

Шаг 5: нажимаем на кнопку 4

Шаг 6: нажимаем на кнопку 5

Размещено на Allbest.ru