Решение системы регулярных выражений. Лабораторная работа 3 Решение системы регулярных выражений Студент фдо тусур 19 Мая 2011 года

• Название: Лабораторная работа 3 Решение системы регулярных выражений Студент фдо тусур 19 Мая 2011 года
• Анкор: Решение системы регулярных выражений
• Дата: 15.06.2022
• Размер: 1.22 Mb.
• Имя файла: part3.rtf
• Тип: Лабораторная работа; #592405

Факультет дистанционного обучения

Томский государственный университет

систем управления и радиоэлектроники (ТУСУР)

Кафедра автоматизированных систем управления

«Теория вычислительных процессов и структур»

Лабораторная работа №3

«Решение системы регулярных выражений»

Выполнил: Студент ФДО ТУСУР

«19» Мая 2011 года

Проверил: ________________

_________________________

«____» ____________ 2011

Содержание

Содержание 2

1.Лабораторное задание 3

1.1 Входные данные 3

1.2 Выходные данные 3

2.Краткая теория 4

3.Результаты работы 8

4.Выводы 9

6.Список литературы 10

Приложение. Листинг программы 11

1. Лабораторное задание

Решение системы регулярных уравнений.

1.1 Входные данные

Во входном файле (с именем INPUT.TXT) задается размерность системы регулярных уравнений n (1 ≤ n ≤ 8) а затем — ее коэффициенты:

б₁₀ б₁₁ б₁₂ … б_1n

б₂₀ б₂₁ б₂₂ … б_2n

…………………

б_n0 б_n1 б_n2 … б_nn

Максимальная длина регулярного выражения для каждого коэффициента равна 3.

Пустое множество можно задать с помощью символа нуля. Единичное множество с помощью латинских «E» или «e»

1.2 Выходные данные

В выходной файл (с именем OUTPUT.TXT) необходимо вывести:

1) Полное решение системы регулярных уравнений.

2) Упрощенное решение.

Упрощенное решение получается, если применить к полученному решению леммы 1—12.

2. Краткая теория

Рассмотрим краткую теорию решения уравнений с регулярными коэффициентами. Более подробные данные можно получить в [1] (раздел 3.5).

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

1)  — регулярное выражение, обозначающее регулярное множество ;

2) e — регулярное выражение, обозначающее регулярное множество {e};

3) если aУ, то a — регулярное выражение, обозначающее регулярное множество {a};

4) если p и q — регулярные выражения, обозначающие регулярные множества P и Q, то

а) (p+q) — регулярное выражение, обозначающее PQ;

б) pq — регулярное выражение, обозначающее PQ;

в) p^* — регулярное выражение, обозначающее P^*;

5) ничто другое не является регулярным выражением.

Принято обозначать p⁺ для сокращенного обозначения рр^*. Расстановка приоритетов:

* (итерация) — наивысший приоритет;

конкатенация;

+ (объединение).

Например, 0 + 10^* = (0 + (1 (0^*))).

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

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

1) б + в = в + б

2) ^* = e

3) б + (в + г) = (б + в) + г

4) б(вг) = (бв)г

5) б(в + г) = бв + бг

6) (б + в)г = бг + вг

7) бe = eб = б

8) б = б = 

9) б^* = б+б^*

10) (б^*)^* = б^*

11) б+б = б

12) б+ = б

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

X = aX + b,

где a и b — регулярные выражения. Можно проверить прямой подстановкой, что решением этого уравнения будет a^*b:

aa^*b + b = (aa^* + e)b = a^*b,

т.е. получаем одно и то же множество. Таким же образом можно установить и решение системы уравнений.

Определение. Систему уравнений с регулярными коэффициентами назовем стандартной системой с множеством неизвестных Д = {X₁, X₂, …, X_n}, если она имеет вид:

X₁ = б₁₀ + б₁₁X₁ + б₁₂X₂ + … + б_1nX_n

X₂ = б₂₀ + б₂₁X₁ + б₂₂X₂ + … + б_2nX_n

………………………………………

X_n = б_n0 + б_n1X₁ + б_n2X₂ + … + б_nnX_n

где б_ij — регулярные выражения в алфавите, не пересекающемся с Д. Коэффициентами уравнения являются выражения б_ij.

Если б_ij = , то в уравнении для X_i нет числа, содержащего X_j. Аналогично, если б_ij = e, то в уравнении для X_i член, содержащий X_j, — это просто X_j. Иными словами,  играет роль коэффициента 0, а e — роль коэффициента 1 в обычных системах линейных уравнений.

Алгоритм решения.

Вход. Стандартная система Q уравнений с регулярными коэффициентами в алфавите У и множеством неизвестных Д = = {X₁, X₂, …, X_n}.

Выход. Решение системы Q.

Метод: Аналог метода решения системы линейных уравнений методом исключения Гаусса.

Шаг 1. Положить i = 1.

Шаг 2. Если i = n, перейти к шагу 4. В противном случае с помощью тождеств леммы записать уравнения для X_i в виде

X_i = бX_i + в,

где б — регулярное выражение в алфавите У, а в — регулярное выражение вида

в₀ + в_i+1X_i+1 + … + в_nX_n,

причем все в_i — регулярные выражения в алфавите У. Затем в правых частях для уравнений X_i+1, …, X_n заменим X_i регулярным выражением б^*в.

Шаг 3. Увеличить i на 1 и вернуться к шагу 2.

Шаг 4. Записать уравнение для X_n в виде X_n = бX_n + в, где б и в — регулярные выражения в алфавите У. Перейти к шагу 5 (при этом i = n).

Шаг 5. Уравнение для X_i имеет вид X_i = бX_i + в, где б и в — регулярные выражения в алфавите У. Записать на выходе X_i = = б^*в, в уравнениях для X_i–1, …, X₁ подставляя б^*в вместо X_i.

Шаг 6. Если i = 1, остановиться, в противном случае уменьшить i на 1 и вернуться к шагу 5.

3. Результаты работы

Входное выражение

2

0 E 0

E B E
Решение системы

X(1)=((0)*.(E)). ((B+(E).((0)*.(E)))*.(E+(E).((0)*.(0))))+(0)*.(0)

X(2)=(B+(E).((0)*.(E)))*.(E+(E).((0)*.(0)))

Оптимизация системы

X(1)=B*

X(2)=B*

Проверки

Для X(1)

Исходное выражение с подставленными значениями X

X(1)=0.(B*)+E.(B*)+0

Полученное решение

X(1)=B*

3 случайных варианта записи X(1)

X(1)=BBB

X(1)=BB

X(1)=

Для X(2)

Исходное выражение с подставленными значениями X

X(2)=E.()+B.(B*)+E

Полученное решение

X(2)=B*

3 случайных варианта записи X(2)

X(2)=BBBB

X(2)=BBBB

X(2)=BB

4. Выводы

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

6. Список литературы

1. Ахо А., Ульяман Дж. Теория синтаксического анализа, перевода и компиляции. — М.: Мир, 1978. — 612 с.

2. Ханкер Р. Проектирование и конструирование компиляторов. — М.: Финансы и статистика, 1984 — 230 с.

3. Райуорд-Смит В. Дж. Теория формальных языков. Вводный курс. — М.: Радио и связь, 1988. — 128 с.

4. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. — М.: Мир, 1979. — 656 с.

5. Вайнгартен Ф. Трансляция языков программирования. — М.: Мир, 1977. — 192 с.

6. Гросс М., Лантен А. Теория формальных грамматик. — М.: Мир, 1971. — 294 с.

Приложение. Листинг программы

program Project3;
{$APPTYPE CONSOLE}
uses

SysUtils, Classes;

const N=8;

type

tLexInfo = record // структура с информацией про лексесу

str:string[100]; // строка

line,ps:Integer; // позиция где она найдена

end;

pTree = ^tTree;

tTree = record // дерево в котором хранятся разобранные элементы

info: string; // содержимое

pl:pTree;

pr:pTree;

end;

tptree = (Add,mpy,itr, e,null, term); // типы вершин

var p : TStringList; //список - программа

alllex: array of tLexInfo; // динамический массив

t:Text;

param: array[1..n,1..n+1] of string; // массив параметров

m:Integer;

rasdels: set of Char; //множество разделителей
(*работа с лексемами*)
// регистрация новой лексемы

procedure addlex(var s:string; l,p:integer);

begin

if s='' then Exit;

SetLength(alllex,Length(alllex)+1); // увеличить размер

with alllex[Length(alllex)-1] do

begin//записать в последний

str:=s;

line:=l;

ps:=p;

end;

s:='';

end;
procedure LoadFromInput;// загрузка из файла

var

CurChar:Char;

str,s:string;

l,p:Integer; // текущие линия, позиция

inputFile:file of char; // файл символов

begin

Assign(inputFile,'input.txt');

Reset(inputFile);

str:='';

l:=1;

p:=0;

while not Eof(inputFile) do //пока не кончится

begin

read(inputFile,CurChar);
CurChar:=UpCase(CurChar);

write(t,CurChar);
Inc(p);

if CurChar=#13 then

begin //конец строки

Inc(l);

p:=0;

end;

if str='' then // пустой сумматор

begin

if CurChar in [#32,#9,#10,#13] then Continue; // пропуск пробельных символов

if CurChar in rasdels then // это разделител

begin

s:=CurChar;

addlex(s,l,p-1); //добавить

continue;

end;

str := str + CurChar; // иначе добавить к строке

continue;

end else

begin // не пустой

if CurChar in [#32,#9,#10,#13] then // пробелы

begin

addlex(str,l,p-Length(str)); // добавить сумматор

Continue

end;

if CurChar in rasdels then // разделители

begin

addlex(str,l,p-Length(str)); // добвить сумматор

str:=CurChar;

addlex( str,l,p-1); //добавить разделитель

continue;

end;

str := str + CurChar; // суммируем

continue;
end;

end;
if str<>'' then addlex( str,l,p-Length(str)); // если сумматор не пуст

Close(inputFile); // закрыть входящий
end;
procedure LoadFromString(reg:string);// загрузка из из строки

var

CurChar:Char;

str,s:string;

l,p:Integer; // текущие линия, позиция

inputFile:file of char; // файл символов

begin

SetLength(alllex,0);

str:='';

l:=1;

p:=0;

while reg<>'' do //пока не кончится

begin

CurChar:=reg[1];

Delete(reg,1,1);

CurChar:=UpCase(CurChar);

Inc(p);

if CurChar=#13 then

begin //конец строки

Inc(l);

p:=0;

end;

if str='' then // пустой сумматор

begin

if CurChar in [#32,#9,#10,#13] then Continue; // пропуск пробельных символов

if CurChar in rasdels then // это разделител

begin

s:=CurChar;

addlex(s,l,p-1); //добавить

continue;

end;

str := str + CurChar; // иначе добавить к строке

continue;

end else

begin // не пустой

if CurChar in [#32,#9,#10,#13] then // пробелы

begin

addlex(str,l,p-Length(str)); // добавить сумматор

Continue

end;

if CurChar in rasdels then // разделители

begin

addlex(str,l,p-Length(str)); // добвить сумматор

str:=CurChar;

addlex( str,l,p-1); //добавить разделитель

continue;

end;

str := str + CurChar; // суммируем

continue;
end;

end;
if str<>'' then addlex( str,l,p-Length(str)); // если сумматор не пуст

end;
function cur( i : Integer):string; // текущая лексема

begin

if i>Length(alllex)-1 then cur:='' else

cur:=alllex[i].str;

end;

function next(var i : Integer):string; //следующая

begin

Inc(i); // со сдвигом

next:=cur(i);

end;
(*базовые операции с деревьями*)
function createTree(s:string):ptree; // создать

var p:pTree;

begin

New(p);

p.pl:=nil;

p.pr:=nil;

p.info :=s;

createTree:=p;

end;
procedure deleteTree(p:pTree); //удалить

begin

if p=nil then Exit;

deleteTree(p.pl);

deleteTree(p.pr);

Dispose(p);

end;

(*построение дерева разбора*)
function NewAddinfTree(var ind:Integer):ptree; forward;

function NewBraketTree(var ind:Integer):ptree; // скобки и терминалы

var p,p2:pTree;

s:string;

begin

s:= cur(ind);

if s='(' then

begin

Next(ind);

p:=NewAddinfTree(ind);

Next(ind);

end else

begin

p:=createTree(s);

Next(ind);

end;

NewBraketTree:=p;

end;

function NewIterationTree(var ind:Integer):ptree; // итерация

var p,p2:pTree;

begin

p:=NewBraketTree(ind);

while cur(ind)='*' do

begin

next(ind);

p2:=p;

p := createTree('*');

p.pl :=p2;

end;

NewIterationTree := p;

end;

function NewMultiplyTree(var ind:Integer):ptree; // умножения

var p,p2:pTree;

begin

p:=NewIterationTree(ind);

while cur(ind)='.' do

begin

p2:=createTree('.');

p2.pl:=p;

p:=p2;

next(ind);

p.pr := NewIterationTree(ind);

end;

NewMultiplyTree := p;

end;

function NewAddinfTree(var ind:Integer):ptree; // +

var p,p2:pTree;

begin

p:=NewMultiplyTree(ind);

while cur(ind)='+' do

begin

p2:=createTree('+');

p2.pl:=p;

p:=p2;

next(ind);

p.pr := NewMultiplyTree(ind);

end;

NewAddinfTree := p;

end;


function CreateAllTree:ptree; // создание всего дерева

var ind:Integer;

begin

ind:=0;

CreateAllTree := NewAddinfTree(ind); // от второй и дальше - стротся дерево

end;
procedure initparam; // загрузка входных параметров

var i,j,t:integer;

begin
TryStrToInt(cur(0),m);

t:=0;

for i := 1 to m do

for j := 1 to m+1 do

param[i,j] := Next(t);
end;

procedure solvesys; //решение системы

var i,j,t:Integer;

a,b, ab:string;

begin

//Шаг 1. Положить i = 1.

i:=1;

while i
begin

{Шаг 2. Если i = n, перейти к шагу 4. В противном случае с помощью тождеств леммы записать уравнения для Xi в виде

Xi = ?Xi + ?,

где ? - регулярное выражение в алфавите ?, а ? - регу-лярное выражение вида

?0 + ?i+1Xi+1 + … + ?nXn,

причем все ?i - регулярные выражения в алфавите ?. Затем в правых частях для уравнений Xi+1, …, Xn заменим Xi регулярным выражением ?*?.

}

a := param[i,i];

b:='';

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

begin

b:=param[i,j];

for t := i+1 to m do

begin

ab := Format('(%s).((%s)*.(%s))',[param[t,i],a,b]);

param[t,j]:=param[t,j]+'+'+ab;

end;

end;
// Шаг 3. Увеличить i на 1 и вернуться к шагу 2.

Inc(i);

end;
i:=m;

while i>=1 do

begin

{

Шаг 4. Записать уравнение для Xn в виде Xn = ?Xn + ?, где ? и ? - регулярные выражения в алфавите ?. Перейти к шагу 5 (при этом i = n).

Шаг 5. Уравнение для Xi имеет вид Xi = ?Xi + ?, где ? и ? - регулярные выражения в алфавите ?. Записать на выходе Xi = = ?*?, в уравнениях для Xi-1, …, X1 подставляя ?*? вместо Xi.
}

a:=param[i,i];

b:='';

ab:='';

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

begin

b:=param[i,j];

if ab<>'' then ab:=ab+'+';

if j<=m then

ab:=ab+Format('((%s)*.(%s)). (%s)',[a,b,param[j,m+1]])

else

ab:=ab+Format('(%s)*.(%s)',[ a,b]);

end;

param[i,m+1]:=ab;

//Шаг 6. Если i = 1, остановиться, в противном случае уменьшить i на 1 и вернуться к шагу 5.

Dec(i);

end;

end;

function equal(t1,t2:pTree):Boolean; // сравнение деревьев

begin

equal:=false;

if (t1=nil) and(t2<>nil) then Exit;

if (t1<>nil) and(t2=nil) then Exit;

if (t1<>nil)and(t2<>nil) then

begin

if t1.info<>t2.info then Exit;

if not equal(t1.pl,t2.pl) then Exit;

if not equal(t1.pr,t2.pr) then Exit;

end;

equal:=True;

end;
function typeof( t:pTree): tptree; // тип вершины

begin

if t.info='+' then typeof:=Add

else if t.info='.' then typeof:=mpy

else if t.info='*' then typeof:=itr

else if t.info='E' then typeof:=e

else if t.info='0' then typeof:=null

else typeof:=term;

end;

procedure Optimize(var t:pTree); // оптимизация дерева по правилам

var old:pTree;

begin

if t=nil then Exit;

Optimize(t.pl);

Optimize(t.pr);

old:=t;

case typeof(t) of

Add: begin // суммы

if equal(t.pl,t.pr) then // а+а

begin

t:=t.pl;

old.pl:=nil;

deleteTree(old);

Exit;

end;

if (TypeOf(t.pl)=itr) and equal(t.pl.pl,t.pr) then //а*+а

begin

t:=t.pl;

old.pl:=nil;

deleteTree(old);

Exit;

end;

if (TypeOf(t.pr)=itr) and equal(t.pr.pl,t.pl) then //а+а*

begin

t:=t.pr;

old.pr:=nil;

deleteTree(old);

Exit;

end;

if (TypeOf(t.pl)=itr) and (typeof(t.pr)=e ) then //а*+e

begin

t:=t.pl;

old.pl:=nil;

deleteTree(old);

Exit;

end;

if (TypeOf(t.pr)=itr) and (typeof(t.pl)=e ) then //e+а*

begin

t:=t.pr;

old.pr:=nil;

deleteTree(old);

Exit;

end;

if (TypeOf(t.pr)=null) then //а+0

begin

t:=t.pl;

old.pl:=nil;

deleteTree(old);

Exit;

end;

if (TypeOf(t.pl)=null) then //0+а

begin

t:=t.pr;

old.pr:=nil;

deleteTree(old);

Exit;

end;
end;

mpy: begin //умножение

if (TypeOf(t.pl)=null)or(TypeOf(t.pr)=null) then //а0=0а=0

begin

deleteTree(t.pl); t.pl:=nil;

deleteTree(t.pr); t.pr:=nil;

t.info := '0';

Exit;

end;

if (TypeOf(t.pl)=e) then //еа=а

begin

t:=t.pr;

old.pr:=nil;

deleteTree(old);

Exit;

end;

if (TypeOf(t.pr)=e) then //ае

begin

t:=t.pl;

old.pl:=nil;

deleteTree(old);

Exit;

end;

if (TypeOf(t.pr)=itr) and (TypeOf(t.pl)=itr) then // a*a* =a*

begin

t:=t.pl;

old.pl:=nil;

deleteTree(old);

Exit;

end;

end;

itr: begin //итерация

if (TypeOf(t.pl)=null)or(TypeOf(t.pl)=e) then //0*=e*=e

begin

deleteTree(t.pl); t.pl:=nil;

t.info := 'E';

Exit;

end;

if (TypeOf(t.pl)=itr) then

begin

t:=t.pl;

Dispose(old);

Exit;

end;

if (TypeOf(t.pl)=add)and (TypeOf(t.pl.pr)=e) then // (a+e)*=a*

begin

old:=t;

t:=t.pl;

t.info := '*';

deleteTree(t.pr);t.pr:=nil;

Dispose(old);

end;

if (TypeOf(t.pl)=add)and (TypeOf(t.pl.pl)=e) then // (e+a)*=a*

begin

old:=t;

t:=t.pl;

t.info := '*';

deleteTree(t.pl);

t.pl:=t.pr;t.pr:=nil;

Dispose(old);
end;
end;

end;

end;

procedure OutTree(tr:pTree; prow:Boolean=false); // вывод дерева как рег выражения

var lb,rb:Boolean;

cnt,i:Integer;

begin

if tr=nil then Exit;

lb:=False;

rb:=False;

if (tr.info='.') and (tr.pl.info='+' )then lb:=True;

if (tr.info='*') and (tr.pl.info='+' )then lb:=True;

if (tr.info='*') and (tr.pl.info='.' )then lb:=True;

if (tr.info='.') and (tr.pr.info='+' )then rb:=True;
if (tr.info<>'*') or( not prow) then cnt:=1 else cnt:=Random(5);
for i := 1 to cnt do

begin

if lb then write(t,'(');

OutTree(tr.pl);

if lb then write(t,')');

write(t,tr.info);

end;

if tr.pr=nil then Exit;

if rb then write(t,'(');

OutTree(tr.pr);

if rb then write(t,')');

end;
var i,j:integer;

Top:array[1..8] of pTree; // вершина синтаксичесокго дерева
begin //главная программы

p := TStringList.Create;

rasdels := [];

Assign(t,'output.txt');

Rewrite(t);

Writeln(t,'Входное выражение');

LoadFromInput; //загрузка лексем

Writeln(t,'');

initparam; // грузить парамтеры

solvesys; // решить систему

Writeln(t,'Решение системы');

for i := 1 to m do

begin

writeln(T,'X(',i,')=', param[i,m+1]); //вывод системы

end;

Writeln(t,'Оптимизация системы');
rasdels := ['(',')','*','.','+']; //новые разделители
for i := 1 to m do // оптимизация

begin

LoadFromString(param[i,m+1]); // грузить из строки

Top[i]:=CreateAllTree; // строить дерево

Optimize(Top[i]); // оптимизаировать дерево

write(T,'X(',i,')=');

OutTree(Top[i]); //вывод дерева

Writeln(t,'');

end;
Writeln(t,'Проверки');

Randomize;

for i := 1 to m do // оптимизация

begin

writeln(T,'Для X(',i,')');

for j:=1 to 3 do

begin

OutTree(Top[i]); //вывод дерева

write(T,'=');

OutTree(Top[i], true); //вывод c подставновкой в итерации

Writeln(t,'');
end;
DeleteTree(Top[i]);

end;
Close(t);

p.Free;

SetLength(alllex,0);

end.