3 - Scanner
comp_p03.doc
3 Scanner Abychom pochopili pojem scanner, musíme o něm hovořit ve spojitosti s pojmem konečný automat KA (Finite State Machine -FSM). Scanner rozpoznává korektní lexémy nějakého programovacího jazyka. Konečný automat - KA rozpoznává korektní řetězce v nějakém programovacím jazyce. Příklad 1.
konečný automat - KA, který rozpoznává identifikátory Pascalu:
Konečný automat je mechanizmus, který písmeno, zobrazujeme pomocí grafu s dohodnutými písmeno číslice symboly. Symboly vyjadřují stavy, ve kterých S A se může automat nacházet, dále možné přechody mezi těmito stavy a podmínky, za kterých je možné každý přechod vykonat. V následující tabulce jsou uvedené značky KA, používané v těchto textech. Tabulka 3-1: Význam značek KA:
3.1
stav
ovál vyznačující místo, kde se na základě vstupního znaku rozhodujeme o dalším kroku
přechod
jsou označené znaky z množiny vstupních znaků
S
počáteční stav
každý KA má právě jeden, ve kterém automat začíná práci
A
koncový stav
může jich být jeden anebo víc. Pokud automat v takovém stavu končí činnost, je řetězec přijatý.
Charakteristika činnosti KA (konečného automatu):
• Svou činnost začíná v počátečním stavu (v našem příkladu je to stav S) • Vykonává přechody z jednoho stavu do druhého v závislosti na aktuální konfiguraci, to znamená na tom, ve kterém stavu se právě KA nachází a který znak je právě na vstupu. Z aktuálního stavu se vykoná ten přechod, jehož ohodnocení je shodné se vstupním znakem • KA zastaví svoji činnost v jednom z těchto případů: ⇒ buď je vstup už prázdný, ⇒ anebo ke vstupnímu znaku neexistuje označení přechodu. Tento znak není zařazený do pročítaného řetězce a musí být „vrácený“ na vstup. • Pročítaný vstupní řetězec je přijatý (akceptovaný) konečným automatem, když platí zároveň: ∧ celý řetězec je přečtený a ∧ automat skončil činnost v koncovém stavu. Příklad 2.
Konečný automat, který rozpoznává čísla v pevné řádové čárce: číslice číslice
C číslice
+|S
.
D
A
číslice
.
. B
číslice
Jako příklad můžeme uvést řetězce: ’1’, ’21’, ’32.1’, ’51.44’, ’1.2345’, ’+4’, ’-5’, ’+21.2’, ’-1.234’, ’.1’, ’.53’, ’+.1’, ’-.44’ ověřte je a uveďte další.
16. 3. 2007 - 7:22 © Benedikovič
1 / 15
3 - Scanner
comp_p03.doc
3.2
∗
FORMÁLNÍ DEFINICE Konečného automatu - KA Konečný automat - KA je pětice (Q, A, δ, q, F), kde význam symbolů je v tabulce: Název
Význam možné stavy automatu konečná množina znaků, kterými jsou označené hrany
Q množina stavů
A vstupní abeceda automatu
prvek z Q , v tomto stavu začíná automat práci podmnožina Q , v těchto stavech je řetězec přijatý
q počáteční stav F množina koncových stavů δ přechodová funkce
Q x E => Q , čti dále
Význam přechodové funkce vysvětlíme na příkladu. Máme případ δ(S, +) = A přechodové funkce z příkladu 2. Dvojice [S, +] je tzv. konfigurací automatu a znamená, že automat je ve stavu S a přečetl ze vstupu znak ‘+’. Uvedené pravidlo přechodové funkce způsobí přechod ze stavu S do stavu A. Příklad 3.
Pokračování příkladu 2:
Q množina stavů
A vstupní abeceda
q počáteční stav
F množina koncových stavů
{ S, A, B, C, D }
{ <číslice 0 až 9>, +, -, . }
stav S
{ C, D }
δ - přechodová funkce - může být zapsaná v některém z následujících tvarů: Seznam konfigurací
Přechodová tabulka
vyjmenování všech konfigurací konečného automatu
δ( S, + ) δ( S, - ) δ( S, . ) δ( S, číslice ) δ( A, číslice )
= = = = =
A A B C C
δ( A, . ) δ( B, číslice ) δ( C, . ) δ( C, číslice ) δ( D, číslice )
Matice konfigurací s cíly přechodů
= = = = =
B D D C D
S A B C D
+
-
.
číslice
A
A
B B
C C D C D
D
3.2.1 Existují dva druhy KA: 1) Deterministický Žádný stav nemá víc než 1 výstupní hranu se stejným označením. Každá hrana, která vychází ze stejného stavu má různé označení. (Předcházející příklad je deterministický) 2) Nedeterministický a) Stavy mohou mít i víc výstupních hran se stejným označením. b) Hrany mohou obsahovat hrany s označením ε (epsilon) pro prázdný řetězec. Konečný automat může vykonat ε- přechod bez přijetí aktuálního vstupního znaku. Příklad 4.
Nedeterministický automat, který rozpoznává také čísla v pevné řádové čárce:
číslice B číslice S
+|-|ε
číslice
A
číslice
číslice C
.
D číslice
. E
číslice
F
Předcházející automat vznikne jako výsledek přirozeného uvažování během jeho sestavování. Vznikl jako návrh relativně samostatných větví.
16. 3. 2007 - 7:22 © Benedikovič
2 / 15
3 - Scanner
comp_p03.doc
Přechod z S do A je společný pro všechny úvahy. Číslo může, ale nemusí mít znaménko. Větev z A do B vznikla jako automat pro přijetí celého čísla (posloupnost číslic). Větev z A do D předpokládá celočíselnou a desetinnou část čísla oddělenou desetinnou čárkou (tečkou). Poslední větev z A do F uvažuje přijetí desetinného čísla, u kterého je celočíselná část prázdná. Všimněme si, že konfigurace [ S, ε ] umožňuje přijmout i číslo bez znaménka. Dále ze stavu A vycházejí dva přechody se shodným ohodnocením (číslice). Tyto dvě vlastnosti způsobují, že uvedený automat je nedeterminovaným automatem. Tento automat, pokud má přijmout nějaký řetězec jako číslo v pevné řádové čárce, může po přečtení řetězce skončit v jednom ze tří stavů ( B, D, anebo F). Význam jednotlivých koncových stavů v automatu je vysvětlený v následující tabulce: B
Bylo přečteno číslo bez desetinné čárky "." např. 14 (desetinná čárka-tečka)
D
Uvnitř řetězce nebo na jeho konci byl přečtený znak "." např. 1997.25 anebo 125.
F
Znak "." byl přečtený na začátku posloupnosti číslic např. .82
Ve všech případech může (ale nemusí) být přečtené znaménko + anebo -.
3.3
Přechodová tabulka KA je:
S
+
-
A
A
.
číslice
ε A
A
E
B
B, C B
C
D
C
D
D
E
F
F F Pohled do této tabulky (na rozdíl od tvaru s vyjmenovanými případy přechodové funkce) nám hned napovídá, že konečný automat je nedeterministický. A to ze dvou důvodů – výskyt „prázdného“ vstupu (poslední sloupec) a druhý důvod je ten, že aspoň v jedné buňce tabulky jsou dva možné cílové stavy (v konfiguraci [A, číslice] stavy B a C).
∗
Říkáme, že Řetězec je přijatý, akceptovaný nedeterministickým KA (NDKA), pokud existuje posloupnost odvození z počátečního stavu, která končí v koncovém stavu a přitom čte celý přijímaný řetězec.
Sledujme činnost automatu při čtení řetězce +753 Po scannování 1
Může být v těchto stavech S
2
+
A
3
+
7
B
C
4
+7
5
B
C
5
+75
3
B
C
scannovaný znak
Koncový stav, => řetězec je přijatý
Při NDKA – nedeterministickém KA nastal problém v kroku č. 3. Pro který přechod se rozhodnout??
16. 3. 2007 - 7:22 © Benedikovič
3 / 15
3 - Scanner
comp_p03.doc
Pokud vybereme
- stav B, tak automat přijme číslo +753, protože časem zastaví ve stavu koncovém B. - stav C, tak po přečtení řetězce ukončí činnost v nekoncovém stavu C – t.j. chyba. Automat z příkladu 3 dokáže přijmout všechna čísla s danými vlastnostmi, nejen ta, která jsme uvedli. Všechny takové posloupnosti znaků, které je automat schopný přijmout, tvoří množinu, kterou nazýváme jazyk.
∗
Jazyk definovaný pomocí konečného automatu je množina řetězců přijatých tímto konečným automatem.
Jestliže M je konečný automat, potom označení L(M) znamená: „Jazyk definovaný automatem M“. Vraťme se však k problému nejednoznačnosti, se kterým jsme se setkali v příkladu 3, kde konfigurace (A, číslice) má dvě možná řešení přechodové funkce, buď přechod do stavu B, anebo do C. Následující věta nám pomůže řešit problém nejednoznačnosti při rozhodování, který přechod vybrat.
Věta:
'
Pro každý nedeterministický KA M existuje deterministický KA M , pro který platí: '
L(M) = L(M ) Jinými slovy: Nedělejme si starosti, že při návrhu vznikne NDKA. Existuje totiž možnost najít k němu ekvivalentní DKA. Důkaz této věty nebudeme na tomto místě uvádět.
3.4
∗
Formální definice regulárního výrazu: Regulární výraz je výraz splňující následující pravidla:
• Daná je abeceda A (množina znaků), • Existuje (nekonečná) množina A* řetězců délky >= 0 , sestavených ze znaků abecedy A. • Regulárním výrazem nazýváme každý výraz z podmnožiny množiny A*, který splňuje následující podmínky: 1. Prázdný řetězec ε je regulární výraz a označujeme ho: {""}, anebo {’’}. 2. Každý jednoznakový řetězec z A*obsahující znak z množiny A je regulární výraz a označujeme ho {"a"} (jazyk C), anebo {’a’} (jazyk Pascal). 3. Mějme množiny R ⊂ A a S ⊂ A. Pokud r resp. s jsou regulární výrazy složené ze znaků množin R resp. S (r ∈ R* resp. s ∈ S*), potom následující výrazy jsou také regulární výrazy: a) r | s znamená { u , kde u ∈ R* ∪ S* } b) r . s znamená { uv , kde u ∈ R*, v ∈ S* } c) r * znamená sjednocení Ri pro i od 0 do nekonečna, kde Ri je definované následovně: R0 = {ε} 1 R =R = {u |u∈R} R2 = { uv | u ∈ R, v ∈ R } R3 = { uvw | u ∈ R, v ∈ R, w ∈ R } ...atd. (Poznámka: znak "∈" znamená "je prvkem množiny " znak " ∪" znamená sjednocení) Regulární výraz ve tvaru zápisu například Backus-Naurovej formy vlastně zastupuje množinu řetězců určitých vlastností a představuje pravidlo pro jejich rozpoznání. Nemusíme tedy vyčerpávajícím způsobem vyjmenovávat všechny takové řetězce, protože jsou zapsané úplným způsobem jako regulární výraz. Příklad 5.
Sestrojíme regulární výraz pro zápis všech posloupností složených z číslic 6 a 8.
Vycházíme z abecedy, kterou tvoří znaky číslic a příslušného uzávěru, vytvořeného všemi možnými řetězci, ve kterých se nachází jen číslice...
A
= { 0,1, ... ,9 }
A*
= { "", "0", ... "9", "00", "01", ... , "56", ... , "99", "000", "001", ... }
Při následujících úvahách použijeme dvě podmnožiny uvedené abecedy.
16. 3. 2007 - 7:22 © Benedikovič
4 / 15
3 - Scanner
comp_p03.doc
Nechť
B C
={6}⊂A ={8}⊂A
V následující tabulce jsou příklady regulárních výrazů, tvořených jen ze znaků 6 a 8. Dané regulární výrazy definují určité množiny řetězců, vyhovující pravidlu regulárního výrazu Některé regulární výrazy
Obsah jejich množin
ε -epsilon
{""}
{‘’}
B
{"6"}
{‘6’}
C
{"8"}
{‘8’}
B|C
{"6", "8"}
B.C
{"68"}
(B | C )*
{"", "6", "8", "66", "68", "86", 88","666", "668", "686", ... }
Otázka: Odpověď:
K čemu jsou dobré regulární výrazy v souvislosti s kompilátory? Mohou se použít jako vstupy generátoru scanneru, pro každý token jeden regulární výraz.
Otázka: Odpověď:
Jak můžeme použít regulární výraz pro vytvoření scanneru? Konvertujeme regulární výrazy na konečné automaty.
Věty: 1. Pro každý regulární výraz r existuje KA M takový, že L(M) je množina řetězců určených pomocí r. 2. Pro každý KA M existuje regulární výraz r takový, že r vytváří jazyk L(M).
3.5
Postup vytváření konečného automatu z regulárního výrazu:
Naznačme si postup vytvoření konečného automatu z definice regulárního výrazu přes etapu úpravy na strom výrazu až po automat za účelem konstrukce scanneru. Rozdělíme tuto cestu do několika etap.
1) Vybudujeme strom pro regulární výraz. Strom vytváříme tím způsobem, že kořenem stromu dané metaoperace ve výrazu bude uzel příslušného metaoperátoru a přímí synové tohoto uzlu budou metaoperandy. Tuto komplikovanou větu vysvětlíme na příkladu zřetězení.
Strom metaoperace
<první> .
upravíme na
• ⇒⇒⇒
první
druhý
Metaoperaci mocnina bude , přirozeně, odpovídat podstrom s jedním synem. Operandy metaoperátorů nemusí být „čisté“ symboly jazyka, ale podstromy vnořených metaoperací. Konečný tvar stromu výrazu bude obsahovat uzly s následujícím významem: listy stromu symboly jazyka (například ε, a, písmeno, a pod...), vnitřní uzly operátory regulárního výrazu – metaoperátory Strom vytváříme tak, aby vnitřní uzly byly uspořádané podle priority od kořene (nejnižší priorita) směrem k listům s rostoucí prioritou použitého metaoperátoru ve výrazu. Musíme, samozřejmě, respektovat změnu jejich priority pomocí závorek. Příklad 6.
Vybudujeme strom pro následující regulární výraz:
. ( | <číslice> ) * Uvedený regulární výraz upravíme pomocí naznačených pravidel a dostaneme konečný tvar stromu, ve kterém na vrchole je zřetězení. Zpracuje se jako poslední, protože mocnina má vyšší prioritu zpracování a priorita metaoperace alternativy byla pomocí závorek zvýšená.
16. 3. 2007 - 7:22 © Benedikovič
5 / 15
3 - Scanner
comp_p03.doc
Strom výrazu •
∗
písmeno
|
Čti poznámku
Poznámka:
písmeno
číslice
Pro zřetězení symbolů pomocí metaoperátoru [ . ] používáme i termín Concat (Concatenation - zřetězení, spojení, konkatence). V zápise pravidla můžeme, pokud je z kontextu zřetězení zřejmé, metasymbol zřetězení vynechat.
2) Transformujeme jednotlivé metaoperace ze stromu do automatu. Při budování KA projděte každým uzlem stromu metodou post order. (čti Struktury dat!) Uvědomte si: při zpracování libovolného uzlu budou už konečné automaty každého syna daného uzlu vybudované a každý takový KA bude mít jen jeden koncový stav. Budeme s tímto synem nakládat tak, jako by to byl kompaktní uzel a šipku přechodu vedeme do jeho počátečního stavu. Následují pravidla pro úpravu fragmentů stromu na jejich ekvivalenty ve formě automatu. Při vytváření celého automatu postupujeme od listů směrem ke kořeni stromu.
Pravidla pro: a) vytvoření fragmentu konečného automatu KA pro listový uzel označení větve je buď ε, to znamená, že nebyl přečtený vstupní znak: S
ε
F
přijímá prázdný řeťězec
anebo pro vstupní znak "a", který je obsažený v abecedě A:
S
a
F
přijímá jeden znak
b) vytvoření fragmentu KA pro vnitřní uzel (pro každý uzel zvlášť): -i-
pro uzel typu „ | “ („or“ , „anebo“) chceme vytvořit podle přiloženého obrázku nedeterministický KA, který rozpozná buď jazyk regulárních výrazů reprezentovaných stromem P, anebo jazyk ve stromu R.
N:
P
| R
Nechť M(P) je konečný automat vytvořený pro uzel P; nechť M(R) je konečný automat vytvořený pro uzel R. Potom M(N) má tvar na následujícím obrázku. Indexy P, R anebo N označují stavy příslušejícím příslušným automatům M(P), M(R) anebo M(N). K automatům M(P) a M(R) přidáme stavy SN a FN nového automatu tak, že nový společný počáteční stav SN připojíme k počátečním stavům spojených automatů (SP a SR) pomocí přechodu s prázdným vstupem a koncový stav FN připojíme za koncové stavy spojených automatů (FP a FR) také pomocí přechodu s prázdným vstupem. Vznikne tak nový nedeterministický(!!) automat M(N).
16. 3. 2007 - 7:22 © Benedikovič
6 / 15
3 - Scanner
comp_p03.doc
M(N): M(P)
ε
ε
FP
SP
SN
FN M(R)
- ii -
FR
SR
ε
ε
pro uzel typu „ * “ (opakuj) – jde o opakovaný výskyt vstupních znaků stejného typu za sebou libovolněkrát vrácené případy prázdného řetězce v rámci této operace. Při opakování znaků jde buď o prázdný řetězec, anebo o jednoznakový řetězec, dvojznakový, atd. - (Kleene closure):
M(N):
N:
*
ε M(P)
SP,N
P
Může přijmout více případů
FP, Nic nepřijme
ε
Postup úpravy spočívá v přidání přechodu s prázdným vstupem ze stavu SP do stavu FP, který umožní přijmout přijetí prázdného řetězce a přechodu s prázdným vstupem ze stavu FP do stavu SP, který umožní přijmout vstup posloupnosti znaků stejného typu. Stavy SP a FP původního automatu M(P) jsou potom ztotožněné se stavy SN a FN výsledného nedeterministického automatu M(N).
- iii -
pro uzel typu „ . “ (Zřetězení, Concatenation) -
N:
přijme řetězec obsažený v uzle P, za kterým následuje řetězec obsažený v uzle R.
M(P) SP,N
FP
ε
. R
P M(R) SR
FR,N
Automaty M(P) a M(R) jsou sekvenčně za sebou připojené tím, že z koncového stavu FP automatu M(P) je přidaný přechod s prázdným vstupem do počátečního stavu SR automatu M(R). Stavy SN a FN jsou novými stavy nově vytvořeného automatu M(N), přičemž stav SN je ekvivalentní s počátečním stavem SP automatu M(P) a stav FN je ekvivalentní s koncovým stavem FR automatu M(R). Poznámka: ( ) - závorky v zápise metapravidla regulárního výrazu se používají pro seskupení případů do skupin za účelem změny priority metaoperací. Odstraní se, když jsou stromy výrazů vytvořené, takže nepotřebujeme řešit uzel pro případ typu "( )". V následujícím příkladu je tento případ použitý. Příklad 7.
Identifikátory Pascalu:
. ( | <číslice> ) *
16. 3. 2007 - 7:22 © Benedikovič
7 / 15
3 - Scanner
comp_p03.doc
a(6)
. b(1)
c(5)
písmeno
* |
e(2)
d(4) f(3)
písmeno
číslice
Jaký je význam značek (například a(6) ) uvedených nad uzly? • Písmeny jsou pojmenované jednotlivé uzly stromu a budou jimi pojmenované vytvořené částkové automaty. •
Čísla v závorkách asociují pořadí uzlů, ve kterém se budou zpracovávat uzly při vytváření automatu v pořadí post order.
Tento automat budeme budovat v následujících obrázcích. Nyní budeme vytvářet postupně automat pro každý uzel stromu. Uzly budeme zpracovávat postupně tak, že projdeme strom prohlídkou typu post order. Každý z následujících kroků vybuduje jeden automat podle principů uvedených v předcházejících úvahách. Následující tři kroky odpovídají zpracování uzlů podle číslic, které jsou uvedené v závorkách u příslušných uzlů v předcházejícím stromu. Začněme tedy v listech stromu. Malá písmena korespondují s označením uzlů, pro které budujeme automaty.
krok 1: M(b): list
Sb
krok 2: M(e): list
Se
krok 3: M(f): list
Sf
písmeno
písmeno
číslice
Fb
Fe
Ff
Listy jsou zpracované. Prohlídkou typu post order se přesuneme k vnitřním uzlům, ve kterých se nacházejí metaoperátory. Na řadě je metaoperace alternativy.
krok 4: M(d): | ε
M(e) Se
písmeno
Sd
Fd
M(f) Sf
ε
ε
Fe
číslice
Ff ε
Následuje unární metaoperace mocniny. Ve stromu je to uzel s jedním synem. Po zpracování vznikne automat odpovídající podstromu, jehož kořenem je uzel s označením c.
16. 3. 2007 - 7:22 © Benedikovič
8 / 15
3 - Scanner
comp_p03.doc
krok 5: M(c): *
ε
M(D):
M(e) ε
Se
písmeno
ε
Fe
Sc
Fc
M(f) číslic
Sf
ε
Ff
ε
ε
krok 6: M(a)
tento krok sa pokuste sestavit sami...
3.5.1 Odstranění nadbytečných hran Pokud si dobře prohlédneme výsledné automaty, na první pohled vidíme, že můžeme určité skupiny přechodů zjednodušit. Na následujících obrázcích je několik takovýchto zjednodušení: A
S2
ε
S4 Možno upravit na:
S1 ε
B
S3
S4
A
S1 B
S5
S5
Podobně je možné upravit i přechody s prázdnými vstupy do koncového stavu:
S1
A
S3
S1
ε
F5 S2
B
S5
Možno upravit na:
ε
S4
A
B
S2
Hrany se shodným počátkem a cílem je možné také sloučit: A A|B
S1
S2
na:
S1
S2
B
16. 3. 2007 - 7:22 © Benedikovič
9 / 15
3 - Scanner
comp_p03.doc
Pokud vznikne cyklus s hranami podle následujícího obrázku ohodnocenými prázdným vstupem ε, můžeme vykonat následující úpravu: ε A
B na:
B
S1
S2
S2
A
S3
S1
C
ε
C
3.5.2 Kompletování více automatů do jednoho Nyní už víme, jak psát regulární výrazy, i to, že regulární výrazy jsou použitelné pro specifikování tokenů. Také víme, jakým způsobem je možné vytvořit z regulárních výrazů odpovídající konečný automat. Nyní, když máme daný KA pro každý token, položme si otázku, jakým způsobem sestavíme scanner? Ten musí být schopný přijmout co nejdelší vstupný řetězec. Idea:
- všechny KA by měly běžet současně, - pro každý automat je třeba sledovat počet vložených znaků, - pokud všechny automaty ukončí práci, ... potom musíme rozhodnout mezi dvěma případy: 9 buď není žádný KA v koncovém stavu, potom byl vstupný řetězec chybný pro použité automaty a proto nebyl přijatý žádným z nich. Poznámka: pokud v automatu existuje případ přechodu z koncového stavu do nekoncového, potom budeme považovat tento přechod za chybný. Tato úvaha předpokládá, že z koncového stavu by neměl existovat žádný přechod do jiného stavu, ani do sebe samého. 9 anebo pokud aspoň jeden automat zastavil v koncovém stavu, potom vybereme ten, který přečetl nejvíc znaků a řekneme, že řetězec byl tímto automatem přijatý.
Příklad 8.
Mějme dva automaty rozpoznávající literály celých čísel bez znaménka a literály čísel v pevné řádové čárce bez znaménka:
Automat pro literál čísla v pevné rádové čárce Automat pro celočíselný literál
(a) S
Vstup
23 2.3
číslice
číslice F
(b) číslice
S .
číslice
A
B
číslice .
F
číslice
Výsledek činnosti obou automatů Oba dva automaty (a) i (b) přijmou všechny vstupní znaky, přičemž automat (a) je po ukončení v koncovém stavu, to znamená, že je rozpoznaný celočíselný literál. Automat (b) pro literál v pevné řádové čárce rozpozná víc znaků, takže je rozpoznaný literál hodnoty v pevné řádové čárce. Automat (a) sice skončí také v koncovém stavu, ale přijme jen „2“.
Máme tu další problém: V předcházející poznámce jsme uvedli, že problémy nastanou v tom případě, kdy existují v automatu koncové stavy, ze kterých vycházejí nějaké hrany (ať už do jiných stavů, anebo cyklicky na sebe). To znamená, že není možné exaktně rozhodnout o ukončení procesu rozpoznávání. Vzniká tím nebezpečí, že ukončíme příjem znaků předčasně.
16. 3. 2007 - 7:22 © Benedikovič
10 / 15
3 - Scanner
comp_p03.doc
Naznačíme možnosti pro úpravy automatu na odstranění této nepříjemné skutečnosti. Idea: krok 1 - provedeme v automatu následující úpravy: a) sloučíme hrany se společným začátkem a koncem, b) takový koncový stav, ze kterého vychází nějaká hrana, změníme na nekoncový tím, že přidáme k němu přechod do nového koncového stavu, přičemž tento přechod označíme množinou vstupních znaků, které tento přechod způsobí, c) příslušné hrany označíme potřebnými akcemi, například návrat toho znaku, který způsobil přechod automatu do koncového stavu na vstup (ten bude zpracovaný jiným automatem). krok 2 - zkombinujme konečné automaty do jediného KA. Příklad 9.
Úpravy ilustrujeme na automatu, rozpoznávajícím identifikátory Pascalu:
původní automat
po úpravě a) písmeno
S
písmeno
písmeno | číslice
F
písmeno
S
F
číslice
písmeno | číslice
po kroku b) S
písmeno
A
F
A - (písmeno | číslice)
A -Vstupní abeceda
vrátenie prečítaného znaku na
písmeno | číslica
po kroku c)
písmeno
S
(1) A
F
A - (písmeno | číslica)
Označení přechodu „A - (písmeno | číslice)“ ze stavu A do F znamená, že byl přečtený nějaký znak vstupní abecedy A , který není ani písmeno ani číslice. Označení (1) na hraně konečného automatu znamená akci, která se vykoná během analýzy při přechodu automatu ze stavu A do stavu F. Příklad 10.
Literály čísel v pevné řádové čárce:
původní automat
číslice číslice
S
změní se na
.
B
.
C
číslice
číslice
číslice S
číslice .
B C
F
číslice . číslice
(1) D
F
A - číslice
¾ Tím končí krok 1.
16. 3. 2007 - 7:22 © Benedikovič
11 / 15
3 - Scanner
comp_p03.doc
Nyní zkombinujeme automaty pro identifikátory, pro literály čísel v pevné řádové čárce, pro dvojtečku a automat pro operátor přiřazení. písmeno | číslice S
(1)
písmeno
:
A
číslice .
E
číslice
=
F
B
Σ - ‘=‘
(1)
F
A - (písmeno | číslice)
C
číslice (1)
D
.
F
A - (písmeno | číslice)
číslice
kde (1) znamená vrácení jednoho znaku na vstup A je vstupní abeceda
F
Poznámky k předcházejícímu obrázku: • •
Stavy C a D není možné sloučit, protože bychom tím umožnili přijetí řetězce “.“ jako čísla! Z obrázku je vidět, že všechny koncové stavy je možné sloučit bez ztráty přehlednosti do jediného společného koncového stavu (jsou také označené stejně - F).
¾ Tímto končí krok 2. 3.6
Jakým způsobem je možné použít KA pro sestavení scanneru ? Postup přepisu pravidel regulárního výrazu na scanner můžeme shrnout do čtyř kroků: 1. Sestavit (upravený) KA pro každý token gramatiky. 2. Zkombinovat je do jednoho KA. 3. Vytvořit řídící tabulku. 4. Přepsat tento KA do kódu.
ad 1 a 2: Sestavení KA pro tokeny a jejich sloučení: Kroky 1 a 2 jsme už podrobněji probrali. Proto se budeme věnovat dalším etapám. Příklad 11.
Následující KA rozpozná tokeny ID (identifikátor), ASSIGN (přiřazení), COLON (dvojtečku) a EOF (konec souboru). Výsledkem použití těchto kroků vzpomínaného postupu může být následující automat:
písmeno | číslice START
písmeno
: COLON EOF #4
A - (písmeno | číslice) ID
#1 =
#2
Σ-=
#3
END
V grafe jsou uvedené akce, které je potřebné vykonat v příslušném případu, kdy je vykonávaný přechod z jednoho stavu automatu do jiného stavu po načítaní vhodného vstupného symbolu.
16. 3. 2007 - 7:22 © Benedikovič
12 / 15
3 - Scanner
comp_p03.doc
Akce: označené jsou znakem #, za kterým je číslo akce, vykonávané při přechodu do jiného stavu. Vykoná se akce #1 #2 #3 #4 ERROR
vrátí zpět jeden znak na výstup vrátí zpět jeden znak na výstup
Výsledek akce token = IDENT token = ASSIGN token = COLON token = EOF
hlášení chyby
ad 3. Vytvoření řídící tabulky: Použitím řídící tabulky se určuje stav, do kterého je třeba se přesunout po přečtení příslušného aktuálního vstupního znaku. Například: - pokud je automat ve stavu START a na vstupu je , tak automat přejde do stavu ID, - pokud je automat ve stavu COLON a na vstupu je <číslice>, tak přejde k přechodu do stavu END, přičemž naposledy přečtený znak vrátí na vstup a výsledný token je odevzdaný jako - dvojtečka. Znaky... Stavy : = písmeno číslice EOF ERROR ERROR #4 START COLON START ID START END #1 #1 #1 ID END END ID ID END #3 #2 #3 #3 #3 COLON END END END END END Poznámka: pro koncový stav END netřeba rezervovat v tabulce samostatný řádek, protože z něho neexistují přechody, a tím by byl prázdný.
ad 4: Vykonávací strukturogram: Dříve, než vytvoříme vykonávací kód, je vhodné zapsat algoritmus ve tvaru vývojového diagramu anebo strukturogramu, aby byla posloupnost kroků čitelnější: a
začátek analýzy je ve stavu START
b
Opakuj kroky: ba
vyber znak ze vstupu
bb
použij tabulku pro nalezení výstupu: 1. vykonej akci a 2. přejdi na nový stav
bc
Podle akce přepiš do kódu hostitelského jazyka (v jazyku C je vhodné použít příkaz CASE pro každou akci podle položky tabulky.)
až po stav = END
- (až po stav označený jako konec činnosti)
Naznačený vykonávací kód k příkladu 12: Pro přepis tabulky například do hostitelského jazyka C je vhodné použít příkaz přepínače switch. aktualni_stav = STARTstav; // první stav START, v něm začíná automat práci do { // pokud jsou znaky na vstupu aktualni_znak = CtiZnak(); // prvý znak „:“ switch (aktualni_stav) { case STARTstav: switch (aktualni_znak) { case ':': aktualni_stav = COLONstav; break; case 'a'..'z', 'A'..'Z': aktualni_stav = IDstav; break;
16. 3. 2007 - 7:22 © Benedikovič
13 / 15
3 - Scanner
comp_p03.doc
case EOFznak:
token = EOFtoken; aktualni_stav = ENDstav; break; errorMessage(aktualni_znak);
default: }; break; case IDstav: switch (aktualni_znak) { case ':', '=', EOFznak: token = IDtoken; aktualni_stav = ENDstav; break; case 'a'..'z', 'A'..'Z', '0'..'9': aktualni_stav = IDstav; break; default: errorMessage(aktualni_znak); }; break; case COLONstav: switch (aktualni_znak) { case ':', 'a'..'z', 'A'..'Z', '0'..'9', EOFznak: token = COLONtoken; aktualni_stav = ENDstav; break; case '=': token = ASSIGNtoken; aktualni_stav = ENDstav; break; default: errorMessage(aktualni_znak); }; break; }; // tady je zpracovaný přečtený znak... } while ExistujeDalsiVstupniZnak();
3.7
Ještě několik poznámek ke scanneru
Scanner musí také vědět kromě jiného: Ignorovat poznámky a prázdná místa mezi lexémy – tzv. blanky (např. mezery, tabulátory a nové řádky). Ty jsou pro cílový kód nevýznamné. Slouží ve zdrojovém textu programu jen pro editační účely a zvyšují čitelnost zdrojového programu. Příklad 12.
Jiný typ poznámky START
A - ‘*‘
Následující KA bude rozpoznávat poznámky ohraničené znakem „ * “ * A Pokuste se navrhnout konečný automat na rozeznání S * pascalovských poznámek. Vrátit skutečné hodnoty některých tokenů ve tvaru vhodném pro výpočet anebo jiné vhodné použití (například pro token ID vrátí řetězec jméno identifikátoru, pro INT_LITERAL vrátí skutečnou číselnou hodnotu). Toto je možné docílit přidáním akce pro vložení informace do řetězce anebo bufferu.
Kdy nedokáže KA rozpoznat program? •
KA může rozpoznat jen konečnou třídu jazyků.
Příklad 13.
•
KA nedokáže rozpoznat jazyk vnořených závorek.
KA rozpoznává řetězec, ale nenabízí žádnou pomoc u struktur s prvky různé priority.
Příklad 14.
Jazyk aritmetických výrazů s operátory + a *
číslice + ( (+ | * ) číslice + ) * Konečný automat dokáže rozeznat řetězec 3+4*5, ale nedokáže rozhodnout, že * má vyšší prioritu, anebo ještě navíc výraz vyhodnotit.
16. 3. 2007 - 7:22 © Benedikovič
14 / 15
comp_p03.doc
3
3 - Scanner
SCANNER ..................................................................................................................................................... 1 3.1 CHARAKTERISTIKA ČINNOSTI KA (KONEČNÉHO AUTOMATU): .................................................................. 1 3.2 FORMÁLNÍ DEFINICE KONEČNÉHO AUTOMATU - KA.......................................................................... 2 3.2.1 Existují dva druhy KA: .................................................................................................................... 2 3.3 PŘECHODOVÁ TABULKA KA JE: ................................................................................................................ 3 3.4 FORMÁLNÍ DEFINICE REGULÁRNÍHO VÝRAZU: ........................................................................................... 4 3.5 POSTUP VYTVÁŘENÍ KONEČNÉHO AUTOMATU Z REGULÁRNÍHO VÝRAZU: ................................................. 5 3.5.1 Odstranění nadbytečných hran ....................................................................................................... 9 3.5.2 Kompletování více automatů do jednoho ...................................................................................... 10 3.6 JAKÝM ZPŮSOBEM JE MOŽNÉ POUŽÍT KA PRO SESTAVENÍ SCANNERU ? ................................................... 12 3.7 JEŠTĚ NĚKOLIK POZNÁMEK KE SCANNERU ............................................................................................... 14
16. 3. 2007 - 7:22 © Benedikovič
15 / 15
