ROZDZIAŁ SZESNASTY DOAPSOWANIE DO WZORCA, INFORMATYKA, „THE ART OF ASSEMBLY LANGUAGE” [PL]

[ Pobierz całość w formacie PDF ]
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
WYŁĄCZNOŚĆ DO PUBLIKOWANIA TEGO TŁUMACZENIA
POSIADA
RAG
„THE ART OF ASSEMBLY LANGUAGE”
tłumaczone by KREMIK
Konsultacje naukowe: NEKRO
wankenob@priv5.onet.pl
nekro@pf.pl
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
ROZDZIAŁ SZESNASTY:
DOAPSOWANIE DO WZORCA
Ostatni rozdział omawiał ciągi znaków i różne działania na tych ciągach. Typowy program odczytuje
sekwencję ciągu od użytkownika i porównuje ciągi czy są dopasowane. Na przykład DOS’owski program
COMMAND.COM odczytuje linię poleceń od użytkownika i porównuje ciąg użytkownika z wpisanym stałym
ciągiem takim jak „COPY”, „DEL”, „RENAME” i tak dalej. Takie polecenia są łatwe do analizowania ponieważ
zbiór dostępnych poleceń jest skończony i stały. Czasami jednak ciągi jakie chcemy przetestować nie są stałe;
zamiast tego należą do (możliwie nieskończonego) zbioru różnych ciągów. Na przykład jeśli wykonujemy
DOS’owe polecenie „DEL .BAK”, MS-DOS nie próbuje usunąć pliku nazwanego „.BAK”. Zamiast tego usuwa
wszystkie pliki, do których pasuje ogólny wzorzec „.BAK”. To oczywiście jest każdy plik, który zawiera cztery
lub więcej znaków i kończą się „.BAK”. W świecie MS-DOS, ciąg zawierający znaki takie jak „*” i „?” są
nazywane symbolami wieloznacznymi; znaki symboli wieloznacznych po prostu dostarczają sposobu do
określenia różnych poprzez wzorce. DOS’owe znaki symboli wieloznacznych maja bardzo ograniczoną postać,
co jest znane jako wyrażenia regularne; wyrażenia regularne mają , generalnie, ograniczoną postać wzorca.
Rozdział ten opisuje jak stworzyć wzorzec, który dopasowuje różne ciągi znaków i pisać podprogramy
dopasowania do wzorca, aby zobaczyć czy szczególny ciąg dopasowany jest do danego wzorca.
16.1 WPROWADZENIE DO TEORII JĘZYKA FORMALNEGO (AUTOMATÓW)
Dopasowanie do wzorca jest ważnym tematem w informatyce. Istotnie, dopasowanie do wzorca jest głównym
paradygmatem programistycznym w kilku językach programowania takich jak Prolog, SNOBOL i Icon Kilka
programów używanych cały czas stosuje dopasowanie do wzorca jako ważną część ich pracy. MASM na
przykład używa dopasowania do wzorca do określenia czy symbole są poprawnie sformułowane, wyrażenia są
właściwe itd. Kompilatory języków wysokiego poziomu jak Pascal i C również używają dopasowania do wzorca
dla analizy pliku źródłowego określając czy jest on syntaktycznie poprawny. Niespodziewanie dość, ważne
wyrażenie znane jako Hipoteza Church’a sugeruje, że każda obliczalna funkcja może być zaprogramowana jako
problem dopasowania do wzorca. Oczywiście, nie ma żadnej gwarancji, że to rozwiązanie będzie wydajne
(zazwyczaj nie jest) ale możemy dojść do poprawnego rozwiązania. Prawdopodobnie nie będziemy musieli nic
wiedzieć o maszynie Turinga (temat hipotezy Church’a) jeśli interesuje nas pisanie, powiedzmy obliczanie
otrzymanych pakietów. Jednakże, jest wiele sytuacji gdzie możemy chcieć wprowadzić umiejętność
dopasowania jakiegoś ogólnego wzorca; więc zrozumienie teorii dopasowania do wzorca jest ważna. Te obszar
informatyki nazywa się teorią języka formalnego lub teorią automatów. Kursy z tego tematu są często mniej niż
popularne ponieważ wprowadzają one dużo dowodów, matematyki i , cóż, teorii. Jednakże, pojęcia poza
dowodami są całkiem proste i bardzo użyteczne. W rozdziale tym nie będziemy się zajmowali próbować
dowodzić wszystkiego o dopasowaniu do wzorca. Zamiast tego będziemy akceptować fakt, że działa to w
rzeczywistości i stosujemy to. Pomimo to musimy omówić pewne tematy z teorii automatów, więc bez dalszych
wstępów.
16.1.1 MASZYNY KONTRA JĘZYKI
Znajdziemy odniesienie do terminu „maszyna” w całej literaturze teorii automatów. Termin ten nie odnosi się do
jakichś określonych komputerów , na których wykonuje się program. Zamiast tego, jest to zazwyczaj jakaś
funkcja, która odczytuje ciąg symboli na wejściu i tworzy jeden lub dwa wyjścia :dopasowanie lub
niepowodzenie. Typowa maszyna (lub automat) dzieli wszystkie możliwe ciągi na dwa zbiory – te ciągi, która
akceptuje (lub dopasowuje) i te ciągi które odrzuca. Język akceptowany przez tą maszynę jest zbiór wszystkich
ciągów, które maszyna akceptuje. Zauważ, że ten język może być nieskończony, skończony lub zbiorem pustym
(tj. maszyna odrzuca wszystkie ciągi wejściowe). Zauważ też, że język nieskończony nie wskazuje, ze maszyna
akceptuje wszystkie ciągi. Jest całkiem możliwe, że maszyna akceptuje nieskończony liczbę ciągów a odrzuca
większą liczbę ciągów. Na przykład, bardzo łatwo jest zaprojektować funkcję, która akceptuje wszystkie ciągi
których długość jest wielokrotnością trzech. Funkcja ta akceptuje nieskończoną liczbę ciągów (ponieważ jest
nieskończona liczba ciągów , których długość jest wielokrotnością trzech) mimo to odrzuca dwa razy więcej
ciągów niż akceptuje. Jest to bardzo łatwa funkcja do napisania. Rozważmy poniższy program 80x86, który
akceptuje wszystkie ciągi o długości trzy (zakładając, że znak powrotu karetki kończy ciąg):
MatchLen3 proc near
getc
;pobiera znak #1
cmp
al., cr
;znak zera jeśli EOLN
je
Accept
getc
;pobranie znaku #2
cmp
al., cr
je
Failure
getc
;pobranie znaku #3
cmp
al., cr
jne
Match Len3
Failure:
mov
ax, 0
;zwraca zero oznaczające niepowodzenie
ret
Accept:
mov
ax, 1
;zwraca jeden oznaczające powodzenie
ret
MatchLen3
endp
Przez śledzenie całego kodu powinniśmy łatwo przekonać się sami, że zwraca jeden w ax jeśli powiodło się
(odczytano ciąg, którego długość jest wielokrotnością trzech) i zero w przeciwnym razie.
Maszyny są z natury rozpoznawaczami. Sama maszyna jest ucieleśnieniem wzorca. Rozpoznaje każdy ciąg
wejściowy, który dopasowuje do wbudowanego wzorca. Dlatego też, kodyfikacja tych automatów jest
podstawową pracą programisty, który chce dopasować jakieś wzorce.
Jest wiele różnych maszyn i języków, które one rozpoznają. Od prostych do złożonych, ważna klasyfikacją jest
deterministyczny skończony stan automatów (który jest ekwiwalentem niedeterministycznego skończonego
stanu automatów), deterministyczny automat stosowy, niedeterministyczny automat stosowy i maszyna Turinga.
Każda kolejna maszyna na tej liście dostarcza nadzbioru zdolności maszyn pojawiających się przed nią.
Jedynym powodem dla którego nie używamy maszyny Turinga dla wszystkiego, jest to, że jest dużo bardziej
złożone zaprogramowanie niż, powiedzmy, deterministycznego skończonego stanu automatu. Jeśli możemy
dopasować wzór używając deterministycznego skończonego stanu automatu, prawdopodobnie będziemy chcieli
zakodować go w ten sposób niż jako maszynę Turinga.
Każda klasa maszyny ma klasę języka z nią powiązaną. Deterministyczne i niedeterministyczne skończone stany
automatów rozpoznają ęzyk regularny. Niedeterministyczny automat stosowy rozpoznaje język bez
kontekstowy. Maszyna Turinga może rozpoznać wszystkie rozpoznawalne języki. Będziemy omawiali każdy z
tych zbiorów języków i ich właściwości po kolei.
16.1.2 JĘZYKI SKOŃCZONE
Języki skończone są najmniej złożonymi językami opisanymi w poprzedniej sekcji. Nie znaczy to, że są mniej
użyteczne; faktycznie, wzorce oparte o wyrażenia skończone są prawdopodobnie bardziej popularne niż inne
16.1.2.1 WYRAŻENIA SKOŃCZONE
Najbardziej zwartym sposobem określenia ciągów, które należą do języka skończonego jest wyrażenie
skończone. Zdefiniujemy wyrażenia skończone według następujących zasad :
• ∅ (zbiór pusty) jest jeżykiem skończonym i oznacza zbiór pusty
• ε jest wyrażeniem skończonym. Oznacza zbiór języków zawierających tylko pusty ciąg:
{ε}.
• Każdy pojedynczy symbol ,a ,jest wyrażeniem skończonym (będziemy używali małych
liter do oznaczania przypadkowych symboli). Ten pojedynczy symbol dopasowuje
dokładnie jeden znak w ciągu wejściowym, który to znak musi być równy pojedynczemu
symbolowi w wyrażeniu skończonym. Na przykład, wzorzec „m” dopasowuje pojedynczy
znak „m” w ciągu wejściowym.
 Zauważmy, że ∅ i ε nie są tym samym. Zbiór pusty jest skończonym językiem, który nie akceptuje żadnego
ciągu, wliczając ciągi o długości zero. Jeśli język skończony jest oznaczony przez {ε} wtedy akceptuje
dokładnie jeden ciąg, ciąg długości zero. Ten ostatni język skończony akceptuje coś, pierwszy nie.
Trzecia z powyższych zasad dostarcza nam podstaw dla definicji rekurencji. Teraz będziemy definiować
wyrażenie skończone rekurencyjnie. W następujących definicjach, zakładamy, że r , s i t są poprawnymi
wyrażeniami skończonymi.
• Konkatenacja. Jeśli r i s są wyrażeniami skończonymi, więc to rs. Wyrażenie skończone rs
dopasowuje każdy ciąg, który zaczyna się ciągiem dopasowanym przez r i kończy ciągiem
dopasowanym przez s
• Suma logiczna / Unia. Jeśli r i s są wyrażeniami skończonymi, więc r | s (czytamy to jako r
lub
s) Jest to odpowiednik dla r ∪ s (czytamy jako r unia s). To wyrażenie skończone
dopasowuje każdy ciąg , który dopasowuje r lub s
• Iloczyn logiczny. Jeśli r i s są wyrażeniami skończonymi, więc r ∩ s. Jest to zbiór
wszystkich ciągów, które dopasowują oba r
i
s.
• Kleene Star. Jeśli r jest wyrażeniem skończonym, więc r*. To wyrażenie skończone
dopasowuje zero lub więcej wystąpień r. To znaczy, dopasowuje ε, r, rr, rrr, rrrr,.......
• Różnica. Jeśli r i s są wyrażeniami skończonymi, więc r – s. To oznacza zbiór ciągów
dopasowanych przez r, które nie są dopasowane również przez s.
• Pierwszeństwo. Jeśli r jest wyrażeniem skończonym, więc (r ). To dopasowuje każdy ciąg
dopasowany przez samo r. Normalne algebraiczne prawa łączności i rozdzielności mają tu
zastosowanie, więc (r | s) t jest odpowiednikiem rt | st.
Operatory te wykorzystują zwykłe prawa łączności i rozdzielności mają następujące pierwszeństwo;
Najwyższe:
(r )
Kleene Star
Konkatenacja
Iloczyn logiczny
Różnica
Najniższe:
Suma logiczna
Przykłady:
(r | s) t = rt | st
rs* = r(s*)
r ∪ t – s = r ∪ (t – s)
r ∩ t – s = (r ∩ t) – s
Generalnie, będziemy używali nawiasów okrągłych aby uniknąć niejasności.
Chociaż ta definicja jest wystarczająca dla klasy teorii automatów, są praktyczne aspekty tej definicji,
która pozostawia trochę do życzenia. Na przykład, dla zdefiniowania wyrażenia skończonego, które
dopasowuje pojedynczy znak alfabetu, będziemy musieli stworzyć coś takiego jak (a | b | c |.... | y | z).
Trochę pisania jak na tak trywialny zbiór znaków. Dlatego też powinniśmy dodać jakąś notację aby
uczynić łatwiejszym określanie wyrażeń skończonych.
• Zbiór Znaków. Każdy zbiór znaków otoczonych przez nawiasy kwadratowe np. [abcdefg]
jest wyrażeniem skończonym i dopasowuje pojedynczy znak ze zbioru. Możemy określić
zakres znaków używając myślnika tj. „[a – z]” oznaczający zbiór małych liter a to
wyrażenie skończone dopasowuje pojedynczy znak małej litery
• Kleene Plus. Jeśli r jest wyrażeniem skończonym, więc r
+
. To wyrażenie skończone
dopasowuje jedno lub więcej wystąpień r. To znaczy, dopasowuje r, rr, rrr, rrrr,..
Pierwszeństwo Kleene Plus jest takie samo jak dla Kleene Star. Zauważmy, że r
+
= rr* .
• Σ przedstawia dowolny pojedynczy znak z dostępnego zbioru znaków. Σ* przedstawia
zbiór wszystkich możliwych ciągów. Wyrażenie skończone Σ* - r jest uzupełnieniem r –
to znaczy, zbiór wszystkich ciągów, których r nie dopasowało
Nadszedł czas aby omówić jak w rzeczywistości używamy wyrażeń skończonych przy specyfikacji
dopasowania do wzorca. Następujące przykłady powinny nam dać odpowiednie wprowadzenie
Identyfikatory: Większość języków programowania, takich jak Pascal lub C/C++ określa poprawne formy dla
identyfikatorów używając wyrażeń skończonych. Używając angielskiej terminologii określamy
je: „Identyfikator musi zaczynać się znakiem alfabetu i następuje po nim zero lub więcej
znaków alfanumerycznych lub znaku podkreślenia.” Używając składni wyrażenia skończonego
(WS) opisanej w tej sekcji, identyfikator to
[a-zA-Z][a-zA-Z0-9_]*
Stałe Całkowite: Wyrażenie skończone dla stałych całkowitych jest relatywnie łatwe do zaprojektowania .Stałe
całkowite składają się opcjonalnie z plus lub minusa i następujących po nich jednej lub więcej
cyfr. WS to
(+ | - | ε | ) [0-9]
+
.
Zauważ, że użycie pustego ciągu ( ε ) czyni plus lub minus opcjonalnym
Stałe rzeczywiste: stałe rzeczywiste są trochę bardziej złożone, ale łatwe do określenia przy użyciu WS. Nasz
definicja wzorca, która dla stałych rzeczywistych pojawia się w programie pascalowskim –
opcjonalnie plus lub minus, po którym następuje jedna lub więcej cyfr; opcjonalnie następuje
punkt dziesiętny i zero lub więcej cyfr; opcjonalnie następuje po „e” lub „E” z opcjonalnym
znakiem i jedną lub więcej cyframi:
( + | - | ε ) [0-9]
+
( „ .”[0-9]* | ε ) (((e | E) (+ | - | ε )[0-9]
+
) | ε)
Ponieważ WS jest relatywnie złożone, powinniśmy je rozłożyć kawałek po kawałku. Pierwszy człon w
nawiasach daje nam opcjonalny znak. Jedna lub więcej cyfr są obowiązkowe przed punktem
dziesiętnym, drugim dostarczonym członem. Trzeci człon pozwala ma punkt dziesiętny po
którym następuje zero lub więcej cyfr. Ostatni człon dostarcza opcjonalnego wykładnika
składającego się z „e” lub „E”, następujący po opcjonalnym znaku lub jednej lub więcej
cyfrach.
Słowa zarezerwowane: Jest bardzo łatwo dostarczyć wyrażenie skończone, które dopasowuje zbiór
zarezerwowanych słów. Na przykład, jeśli chcemy stworzyć wyrażenie skończone, które
dopasowuje słowa zarezerwowane MASM’a , możemy użyć WS podobnego do tego
(mov | add | and |... | mul)
Parzystość:
Wyrażenie skończone (ΣΣ)* dopasowuje wszystkie ciągi, których długość jest wielokrotnością
dwóch
Zdania:
Wyrażenie skończone:
(Σ* „ „ *)* run („ „
+
(Σ* „ „
+
| ε )) fast („ „ Σ*)*
Rysunek 16.1 NFA dla Wyrażenia Skończonego (+|-|e)[0-9]+(„.”[0-9]|e)(((e|E)(+|-e)[0-9]+)|e
dopasowuje wszystkie ciągi, które zawierają oddzielne słowa „run” następujące po nim „fast” gdzieś w linii. To
dopasowuje ciągi jakie „I want to run very fast” i „run as fast as you can” tak jak i „run fast”
Podczas gdy WS są dogodne do określania wzorca jaki chcemy rozpoznać, nie są one szczególnie
użyteczne tworzenia programów (tj. „maszyn”), które w rzeczywistości rozpoznają takie wzorce. Zamiast tego,
powinniśmy najpierw skonwertować WS do niedeterministycznego skończonego stanu automatu, lub NFA. Jest
bardzo łatwo skonwertować NFA do programu asemblerowego 80x86; jednakże takie programy rzadko są
wydajne tak jak mogłyby być. Jeśli wydajność jest dużym zmartwieniem, możemy skonwertować NFA do
deterministycznego skończonego stanu automatu (DFA) , który również jest łatwy do skonwertowania do kodu
asemblowanego 80x86, ale konwersja jest dużo bardziej sprawna
16.1.2.2 NIEDERTMINISTYCZNE SKOŃCZONE STANY AUTOMATÓW (NFA)
NFA jest bezpośrednim wykresem z liczbą stanów powiązanych z każdym węzłem i znakiem lub ciągiem
znaków powiązanych z każdym brzegiem wykresu. Stan wyróżniający się, stan startowy określa gdzie maszyna
zaczyna próbę dopasowania ciągu wejściowego. Maszyna w stanie startowym porównuje znaki wprowadzone
ze znakami lub ciągami na każdym brzegu wykresu. Jeśli zbiór znaków wejściowych jest dopasowany do
jednego z brzegów, maszyna może zmienić stan z węzła na początku brzegu (ogon) do stanu na końcu brzegu
(głowa)
Pewne inne stany, znane jako końcowy lub akceptowalny, są zazwyczaj również obecne Jeśli maszyna przeszła
do stanu końcowego po wyczerpaniu wszystkich znaków wejściowych, wtedy maszyna ta akceptuje lub
dopasowuje ten ciąg. Jeśli maszyna wyczerpała już wprowadzane znaki i przeszła do stanu, który nie jest stanem
końcowym, wtedy maszyna ta odrzuca ten ciąg. Rysunek 16.1 pokazuje przykład NFA dla zmienno
przecinkowego WS przedstawianego wcześniej.
Przez konwencję, zawsze będziemy zakładać, ze stan startowy to stan zero. Oznaczymy stany końcowe (których
może być więcej niż jeden) przez użycie podwójnego okręgu dla tego stanu ( powyżej stan osiem jest stanem
końcowym).
NFA zawsze zaczyna się ciągiem wejściowym w stanie startowym (stan zero). Na każdym brzegu wychodzącym
ze stanu jest albo ε, pojedynczy znak lub ciąg znaków. Pomoc przy nie zasłoniętym diagramie NFA, pozwoli na
wyrażenia w postaci „xxx | yyy | zzz |...” gdzie xxx, yyy, zzz są to ε , pojedynczym znakiem lub ciągiem
znaków. Odpowiada to wielokrotnym brzegom z jednego stanu do innego z pojedynczą pozycją na każdym
brzegu. W powyższym przykładzie :
+ | - | ε
0
1
jest odpowiednikiem
+
0
-
1
ε
Podobnie jak pozwolimy zbiorowi znaków, określonemu przez ciąg w postaci x – y, oznaczyć wyrażeniem x |
x+1 | x+2 | ... | y.
Zauważ, że NFA akceptuje ciąg jeśli jest jakaś ścieżka ze stanu startowego do stanu akceptowalnego, która
wyczerpuje ciąg wejściowy. To mogą być wielokrotne ścieżki od stanu startowego do różnych stanów
końcowych. Co więcej, to może być jakaś określona ścieżka ze stanu startowego do stanu nie akceptowalnego,
która wyczerpała ciąg wejściowy. Niekoniecznie to znaczy, że NFA odrzuca ten ciąg; jeśli jest jakaś inna
[ Pobierz całość w formacie PDF ]

  • zanotowane.pl
  • doc.pisz.pl
  • pdf.pisz.pl
  • tejsza.htw.pl

    •