img140

140

10. Metody ciągowe

repeat

getchar(ch);

State := transfunc(state, ch) until State in finalstates

rec := State;

end

10.3. Języki opisu obrazów (PDL) Shawa

Regularne języki oparte na kodach łańcuchowych mają dwie istotne zalety. Po pierwsze obraz d E D jest opisywany w prosty sposób, jak również prosta jest procedura czytania obrazu B : D —* X i automatycznego tworzenia kodu xEX (można sobie wyobrażać, że głowica czytająca porusza się wzdłuż pewnego szkieletu lub konturu i na podstawie kierunku ruchu wydaje kolejny symbol kodu z). Po drugie procedura rozpoznająca C ■ F : X — I (automat deterministyczny 21) jest najprostszą ze znanych tak w sensie jej tworzenia, jak i działania.

Z drugiej strony w trakcie konstrukcji gramatyki daje się zauważyć pewna rozrzutność w ilości produkcji p € (co Czytelnik mógł zobaczyć w szczególnie jaskrawej formie, gdyż ciąg uczący liczył jedynie cztery elementy). Co gorsza, istnieją klasy obrazów D, których wręcz nie można opisać językami regularnymi, ze względu na słabą moc generacyjną gramatyk regularnych. Dlatego też, w tym punkcie przedstawimy języki o istotnie większej mocy opisowej - PDL Shawa.

W przypadku języków Shawa £pnL, zbiór składowych pierwotnych X nie jest ustalony. Jedynym założeniem jest to, aby każda składowa pierwotna Xj 6 .V miała wyszczególnione: głowę i ogon. Wyszczególniamy natomiast zbiór pięciu prostych operacji na składowych pierwotnych (omówimy wersję PDL bez operatora indeksowania składowych). Przyjmijmy dwuelementowy zbiór składowych pierwotnych X jak na rysunku 10.2, oraz oznaczmy przez CAT operację katenacji (sklejenia) dwóch składowych. Możemy zdefiniować operację w następujący sposób:

a + b oznacza, że: głowa (a) CAT ogon (6) (rys. 10.2b), a x 6 oznacza, że: ogon (a) CAT ogon (b) (rys.10.2c), a — b oznacza, że: głowa (a) CAT głowa (6) (rys.10.2d),