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

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ Филиал ФГБОУ «ДГТУ» в г. Каспийск Кафедра ПОВТ и АС

Курсовая работа

По дисциплине:

" Теория языков программирования"

на тему:

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

Выполнила:

студент 4 курса гр. М831

Магомедов К.К.

Приняла: Сулейманова О.Ш.

Каспийск 2011 г.

Аннотация

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

1. Удалить бесплодные символы

2. Удалить недостижимые символы

3. Устранить правила с пустой правой частью

4. Исключить цепные правила Работа содержит:

_____ страниц машинописного текста

12 рисунков

3 библиографических источника

• Введение
• Задание
• Приведение КС-грамматики к нормальному виду
• Преобразования грамматик
• Алгоритм удаления недостижимых символов
• Исключение цепных правил
• Описание процедур
• Литература
• Приложение

Формальные грамматики и языки

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

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

1. Описание синтаксиса языка дается исключительно средствами формальных грамматик.

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

3. Правила, множества различных символов и отношения представляются табличными данными, на основе которых функционирует распознаватель.

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

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

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

Описание синтаксиса в виде формальных грамматик является ее исходным текстом.

Взаимосвязь синтаксиса и формальных грамматик

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

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

Из всех классов формальных грамматик только КС грамматики продуктивно используются в синтаксическом анализе. Они дают дополнительный смысл понятию нетерминальный смысл.

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

Основные понятия и определения.

Алфавит — это конечное множество символов.

Например, алфавит A = {a, b, c, +,! } содержит 5 букв, а алфавит B = {00, 01, 10, 11} содержит 4 буквы, каждая из которых состоит из двух символов.

Цепочкой символов в алфавите V называется любая конечная последовательность символов этого алфавита.

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

Более формально цепочка символов в алфавите V определяется следующим образом:

1) — цепочка в алфавите V;

2) если б — цепочка в алфавите V и a — символ этого алфавита, то бa или, а — цепочка в алфавите V;

3) в — цепочка в алфавите V тогда и только тогда, когда она является таковой в силу (1) и (2).

Если б и в — цепочки, то цепочка бв называется конкатенацией (или сцеплением) цепочек б и в.

Например, если б = ab и в = cd, то бв = abcd.

Для любой цепочки б всегда б = б = б.

Обращением (или реверсом) цепочки б называется цепочка, символы которой записаны в обратном порядке.

Обращение цепочки б будем обозначать б^R.

Например, если б = abcdef, то б^R = fedcba.

Для пустой цепочки: = ^R.

n-ой степенью цепочки б (будем обозначать бⁿ) называется конкатенация n цепочек б

б⁰ =; бⁿ = бб^n-1 = б^n-1б.

Длина цепочки - это число составляющих ее символов.

Например, если б = abcdefg, то длина б равна 7.

Длину цепочки б будем обозначать |б|. Длина равна 0.

Язык в алфавите V — это подмножество цепочек конечной длины в этом алфавите.

Обозначим через V^* множество, содержащее все цепочки в алфавите V, включая пустую цепочку .

Например, если V={0,1}, то V^* = {, 0, 1, 00, 11, 01, 10, 000, 001, 011,. }.

Обозначим через V⁺ множество, содержащее все цепочки в алфавите V, исключая пустую цепочку .

Следовательно, V^* = V⁺ U {}.

Ясно, что каждый язык в алфавите V является подмножеством множества V^*.

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

Задание

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

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

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

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

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

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

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

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

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

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

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

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

Определение: символ 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 >) є 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).

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

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

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

Метод:

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

2. V_i = 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

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

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

Определение. Правило грамматики вида 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= F, F > (E), E).

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

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

P₂ = E > E+T, T > T*F, F > (E)

На шаге (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

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

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 in ['A'. 'Z'])) or (s <>'-') 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

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 стр.

Приложение

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 in ['A'. 'Z'])) or (s <>'-') 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

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