* !!! Модуль на рефале-5
$ENTRY Go {
= <Prout <RE5
(ALT (CAT 'a')
(CAT 'aa')
(CAT 'aaaa')
(CAT 'aaaaaaa')
(CAT (ITER 'aaa') (ITER 'aaaaa') )
) '1'>>
<Card >;
}
$EXTRN CARD, PROUT;
$EXTRN BR, CP, SYMB;
$EXTRN OPEN, PUT, PUTOUT;
$ENTRY RE5 { e.1 = <RegeMin e.1>; }
$ENTRY DI5 {
e.1 = <Open 'w' 7 'DI5.TXT'>
<DI51 e.1>;
}
DI51 {
* ???
((e.1)) = <DI51 (e.1)>;
((s.a e.1) e.2) = <PUTOUT 7 ' '> <PUTOUT 7 s.a>
((s.a) <RegeMin e.1>) <DI51 (e.2)>;
(s.a e.1) = <PUTOUT 7 ' '> <PUTOUT 7 s.a>
((s.a) <RegeMin e.1>);
( ) = ;
}
* Подпрограмма интерпретатора рег. выр. RE.REF
* Рег.выр. будем обозначать через r.1 , r.2 , ...
* Обращение <Re5 r.1>
* Результат замены - минимальный коненый автомат в виде
* (('1') 'a' ('2')) (('12') (Empty) (F)) ...
* Пример автомата можно посмотреть в результате
* тестового пуска этой программы
* В файле RE5.TXT будет
* - исходное рег.выр.,
* - конечный автомат,
* - минимальный конечный автомат.
Rege1 {
e.1 = <Begin2 <Begin1 ( () (e.1) () ) e.1 <One_S e.1>>>;
}
Begin2 {
(e.Rez) (e.Yes) ( ) = e.Rez;
(e.Rez) (e.5 (e.1) e.6) ((e.1) e.2) = <Begin2
(e.Rez) (e.5 (e.1) e.6) (e.2)>;
(e.Rez) (e.Yes) ((e.1) e.2) = <Begin2 <Begin1
((e.Rez) (e.Yes (e.1)) (e.2)) (e.1)
<One_S (e.1)> >>;
}
Begin1 {
((e.Rez) (e.Yes) (e.No)) (e.S) e.1 =
(e.Rez ((e.S) '=' e.1)) <Plus (e.Yes) (e.No) e.1>;
}
* один шаг
One_S {
=;
( ) =;
e.Exp = <Srch () e.Exp (S)>
<Srch () e.Exp ( )>;
}
Plus {
(e.1 (e.2) e.3) (e.No) ((s.a) (e.2)) e.7 =
<Plus (e.1 (e.2) e.3) (e.No) e.7>;
(e.Yes) (e.1 (e.2) e.3) ((s.a) (e.2)) e.7 =
<Plus (e.Yes) (e.1 (e.2) e.3) e.7>;
(e.Yes) (e.No) ((s.a) (e.2)) e.7 =
<Plus (e.Yes) (e.No (e.2)) e.7>;
(e.Yes) (e.No) (( ) (e.2)) e.7 = <Plus (e.Yes) (e.No) e.7>;
(e.Yes) (e.No) = (e.Yes) (e.No);
}
* --------------------------------------------
* Модифицированный вариант программы
* Regexp2.ref (Srch)
* Обращение
* <Srch () (r.Exp) ( S )>
* результат замены ((s.1) r.1) ((s.2) r.2) ...
* где s.i - обозреваемые символы,
* r.i - рег.выр.
* или <Srch () (r.Exp) ()>
* результат замены - (() (T)) или (() (F))
Srch {
(e.n) (ALT (CAT (ALT s.1 e.2) e.c) e.a) (e.s) =
<Srch (e.n) (ALT (CAT s.1 e.c) (CAT (ALT e.2) e.c) e.a) (e.s) >;
(e.n) (ALT (CAT (ALT (e.1) e.2) e.c) e.a) (e.s) =
<Srch (e.n) (ALT (CAT (e.1) e.c) (CAT (ALT e.2) e.c) e.a) (e.s) >;
(e.n) (ALT (CAT (ALT ) e.c) e.a) (e.s) =
<Srch (e.n) (ALT e.a) (e.s) >;
(e.n) (ALT (CAT (CAT e.1) e.c) e.a) (e.s) =
<Srch (e.n) (ALT (CAT e.1 e.c) e.a) (e.s) >;
() (ALT (CAT (ITER e.i) e.c) e.a) () =
<Srch () (ALT (CAT e.c) e.a) ()>;
(e.n) (ALT (CAT (ITER e.i) e.c) e.a) (e.s) =
<Srch (e.n) (ALT (CAT e.c) (CAT e.i (NITER e.i) e.c) e.a) (e.s)>;
(e.n) (ALT (CAT (NITER e.i) e.c) e.a) (e.s) =
<Srch (e.n) (ALT e.a) (e.s)>;
() (ALT (CAT ) e.a) () = (() (T));
(e.n) (ALT (CAT s.x e.c) e.a) (s.y) =
<Srch ( <Add_en ( (s.x) (CAT <ReNITER e.c>)) e.n > )
(ALT e.a) (s.y) >;
(e.n) (ALT (CAT e.c) e.a) (e.s) = <Srch (e.n) (ALT e.a) (e.s) >;
() (ALT) () = (() (F));
* () (ALT) (e.s) = (() (F));
(e.n) (ALT) (s.x) = e.n ;
}
* ---------------------------------------------
Add_en {
((s.x) (e.Exp1)) e.1 ((s.x) (ALT e.2)) e.3 =
e.1 ((s.x) (ALT <Add_en1 (e.Exp1) e.2> )) e.3;
((s.x) (e.Exp1)) e.1 = ((s.x) (ALT (e.Exp1)) ) e.1;
}
Add_en1 {
(e.1) e.2 (e.1) e.3 = e.2 (e.1) e.3 ;
(e.1) e.2 = e.2 (e.1) ;
}
ReNITER {
(NITER e.i) e.x = (ITER e.i) <ReNITER e.x>;
s.a e.x = s.a <ReNITER e.x>;
(e.a) e.x = (e.a) <ReNITER e.x>;
= ;
}
* ------------------------------------------
RegeMin {
e.1 =
* <Open 'w' 7 'RE5.TXT'>
<ReMin ( <Pre <Pre1
<Putout 7 ' Regular expression'>
<Put 7 e.1> >> ) > ;
}
Pre1 {
(ALT (CAT e.1)) = (ALT (CAT e.1));
(CAT e.1) = (ALT (CAT e.1));
e.1 = (ALT (CAT e.1));
}
Pre {
e.1 = <Br 'zam=' 1 >
<Putout 7 ' Finite Automat '>
<Out <Cod <REGE1 e.1>>>;
}
Out {
(e.1) e.2 = (<Put 7 e.1>) <Out e.2>;
= ;
e.1 = <Put 7 e.1>;
}
Cod {
((e.1) '=' e.2) e5 = ( <Zam (e.1)> '=' <Cod1 e.2> ) <Cod e.5>;
= ;
}
Cod1 {
((s.a) (e.1)) e.5 = (s.a <Zam (e.1)>) <Cod1 e.5>;
(() (e.1)) e.5 = (Empty e.1) <Cod1 e.5>;
= ;
}
Zam {
e.1 = <Zam1 e.1 <Dg 'zam' >>;
}
Zam1 {
(e.1) s.n e.5 ((e.1) s.k) e6 = s.k
<Br 'zam=' s.n e.5 ((e.1) s.k) e.6 >;
(e.1) s.n e.5 = s.n
<Br 'zam=' <Add (s.n) 1> e.5 ( (e.1) s.n) >;
}
* Равенство двух автоматов
* Обращение
* <ReEq ( ) ((s.a s.b)) (Автомат 1) (Автомат 2) >
* где s.a , s.b - номера начальных вершин автоматов
* Результат замены T , F
ReEq {
F e.1 = F ;
(e.1) ( ) (e.3) (e.4) = T ;
(e.1) ((s.a s.b) e.0) (e.3 (s.a '=' e.4) e.5)
(e.6 (s.b '=' e.7) e.8) =
<ReEq <ReEq1 (e.1 (s.a s.b)) (e.0) (e.4) (e.7) >
(e.3 (s.a '=' e.4) e.5)
(e.6 (s.b '=' e.7) e.8) >;
}
ReEq1 {
(e.1) (e.2) ( ) ( ) = (e.1) (e.2) ;
(e.1) (e.2) ((s.a s.b) e.3) (e.4 (s.a s.c) e.5) =
<ReEq1 <Dob (s.b s.c) (e.1) (e.2)> (e.3) (e.4 e.5) >;
F e1 = F e.1 ;
e1 = F e.1 ;
}
Dob {
(F F) (e.1) (e.2) = (e.1) (e.2);
(T T) (e.1) (e.2) = (e.1) (e.2);
(T F) (e.1) (e.2) = F (e.1) (e.2);
(F T) (e.1) (e.2) = F (e.1) (e.2);
(s.b s.c) (e.1 (s.b s.c) e.2) (e.3) = (e.1 (s.b s.c) e.2) (e.3);
(s.b s.c) (e.1) (e.2 (s.b s.c) e.4) = (e.1) (e.2 (s.b s.c) e.4);
(s.b s.c) (e.1) (e.2) = (e.1) (e.2 (s.b s.c));
}
* Построение минимального автомата.
* Обращение <ReMin Automat > , - структура автомата -
* (1 '=' ('1' 2) ('2' 3) ('3' 1) (() F) )
* (2 '=' ('1' 3) ('2' 2) (() T) )
ReMin {
(e.1) = <ReEnd <ReMin1 (<Spis 1 <CP 'zam' >>) (e.1) >>;
}
ReEnd {
(s.a '=' e.1) e.2 = <ReEnd1 s.a e.1> <ReEnd e.2>;
= ;
}
ReEnd1 {
s.a (Empty s.c) e1 = (<SYMB1 s.a> Empty <SYMB1 s.c>)
<ReEnd1 s.a e.1>;
s.a (s.b s.c) e1 = (<SYMB1 s.a> s.b <SYMB1 s.c>)
<ReEnd1 s.a e.1>;
s.a = ;
}
SYMB1 { T = T ;
F = F ;
s.a = <IMPLODE 'Q' <SYMB s.a>>;
}
Spis {
s.n s.n e.1 = ;
s.n s.m e.1 = s.n <Spis <Add (s.n) 1> s.m >;
}
ReMin1 {
(s.a e.Sp) (e.Aut) = <ReMin2 ((s.a)) (() e.Sp) (e.Aut) >;
}
ReMin2 {
(e.1 (s.a e.2)) ((e.3) s.b e.4) (e.Aut) =
<ReMin3
<ReEq () ((s.a s.b)) (e.Aut) (e.Aut)>
(e.1 (s.a e.2)) ((e.3) s.b e.4) (e.Aut)
>;
(e.1 (e.2)) (( )) (e.Aut) = <ReMin9 (e.1 (e.2)) (e.Aut) >;
(e.1 (e.2)) ((s.b e.3)) (e.Aut) =
<ReMin2 (e.1 (e.2) (s.b)) (() e.3) (e.Aut)>;
}
ReMin3 {
T (e.1 (s.a e.2)) ((e.3) s.b e.4) (e.Aut) = <ReMin2
(e.1 (s.a e.2 s.b)) ((e.3) e.4) (e.Aut) >;
F (e.1 (s.a e.2)) ((e.3) s.b e.4) (e.Aut) = <ReMin2
(e.1 (s.a e.2)) ((e.3 s.b) e.4) (e.Aut) >;
}
ReMin9 {
(e.1) (e.Aut) = <Putout 7 ' Min.Automat' >
<Out <ReMin8 (e.1) (e.Aut) >>;
}
ReMin8 {
(e.1) () = ;
(e.1 (s.a e.2) e3) ((s.a '=' e.4) e.5) =
(s.a '=' <ZamMin (e.1 (s.a e.2) e.3) e.4 > )
<ReMin8 (e.1 (s.a e.2) e.3) (e.5) > ;
(e.1) ((e.4) e.5) = <ReMin8 (e.1) (e.5)>;
}
ZamMin {
(e.1 (s.c e.2) e.3) (s.b s.c) e.7 = (s.b s.c)
<ZamMin (e.1 (s.c e.2) e.3) e7 >;
(e.1 (s.a e.2 s.c e.3) e.4) (s.b s.c) e.7 = (s.b s.a)
<ZamMin (e.1 (s.a e.2 s.c e.3) e.4) e.7 >;
(e.1) = ;
(e.1) (e.2) e.3 = (e.2) <ZamMin (e.1) e.3>;
}