KIV / TI - Teoretická informatika
Cvičení 2 - zpracování čísla konečným automatem

Zpracování čísla konečným automatem

Každý překladač vyššího programovacího jazyka se musí vypořádat s následující úlohou: je-li v překládaném zdrojovém kódu například řádek

promenna = 1234 ;

musí rozpoznat, že

sekvence znaků "promenna" představuje název proměnné,
znak " " je nevýznamová mezera,
znak "=" značí přiřazení,
znak " " je další nevýznamová mezera,
sekvence znaků "1234" představuje číslo jeden tisíc dvě stě třicet čtyři,
znak " " je další nevýznamová mezera a
znak ";" ukončuje příkaz přiřazení.

Rozpoznání se tradičně dělí do tří částí. V první, které se říká lexikální analýza, musí překladač ze sekvence znaků rozpoznat tzv. lexikální symboly, v našem případě "proměnná", "symbol přiřazení", "číslo" a "symbol konce příkazu". V druhé, které se říká syntaktická analýza, musí překladač ověřit, že lexikální symboly po sobě jdou v takovém pořadí, které je vyžadováno formálními pravidly daného programovacího jazyka, tzv. gramatikou jazyka. Konečně v části třetí, které se říká sémantická analýza, si musí překladač uvědomit, že zapsané lexikální symboly představují příkaz přiřazení.

My se zdaleka nebudeme zajímat o kompletní činnost překladače, soustředíme se jen na lexikální analýzu. Navíc se pro jednoduchost zaměříme jen na jeden problém lexikální analýzy: jak rozpoznat číslo.

Postupně vyřešme následující dílčí úlohy:

Jak rozpoznat, že sekvence znaků představuje celé číslo?
Jak zjistit hodnotu tohoto čísla?
Jak udělat totéž (rozpoznat a zjistit hodnotu) u desetinného čísla?

Rozpoznání celého čísla

K rozpoznávání řetězců znaků se výtečně hodí konečné automaty; budeme tedy sestavovat rozpoznávací konečný automat. Připomeňme, že k definici rozpoznávacího konečného automatu potřebujeme definovat:

vstupní abecedu,
množinu stavů,
počáteční stav,
koncové (akceptační) stavy a
přechodovou funkci.

Rozpoznáváme-li celé číslo zapsané desítkovou soustavou, může na vstup automatu teoreticky přijít:

Znak + nebo -.
Znak 0, 1, 2, ..., 9.
Libovolný jiný znak, označme si jej symbolicky jako "K" (proto, že takový znak bude ukončovat proces rozpoznávání, je tedy koncový). Mezi znaky typu "K" bychom mohli dále rozlišovat - například těsně za číslem se může vyskytnout mezera, zatímco znak "podtržítko" se v bezprostředním okolí čísla vyskytnout obvykle nemůže. Obdobné rozlišování se ale typicky nechává na starost syntaktické analýze, pro nás tedy budou takové znaky ekvivalentní.

Vstupní abecedou je tedy množina

Σ = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, K }

Jak uvidíme, z pohledu konečného automatu je celkem jedno, zda přijde na vstup číslice 1 nebo 6; pro automat je podstatné, že šlo o číslici. Označíme-li libovolnou číslici symbolem D, můžeme vstupní abecedu přepsat na

Σ = { D, +, -, K }

Při konstrukci množiny stavů, volbě počátečního a koncového stavu a tvorbě přechodové funkce je vhodné postupovat od speciálních případů k obecným. Takovými šikovnými speciálními případy jsou například řetězce "-3" nebo "+1234", což ve vstupní abecedě představuje sekvence symbolů "-DK" nebo "+DDDDK" Automat, který rozpozná sekvenci skládající se ze znaménka, libovolného nenulového počtu číslic a koncového znaku vypadá třeba takto:

Základ pro automat rozpoznávající celá čísla

V dalším kroku je vhodné zamyslet se, jak ještě mohou vypadat korektně zapsaná celá čísla. Musí začínat znaménkem? Samozřejmě ne. Musí obsahovat alespoň jednu číslici? Samozřejmě ano. Po úpravě:

Téměř kompletní automat rozpoznávající celá čísla

Konečně je vhodné rozhodnout, co má automat udělat, je-li na vstupu jiný než zakreslený znak. Obvykle se proto definuje "chybový stav", do kterého automat přejde, jakmile obdrží nečekaný vstup a v tomto stavu zůstane, resp. ohlásí, že došlo k chybě. Tak dostáváme:

Hotový automat rozpoznávající celá čísla

Všimněme si podstatné skutečnosti: při tvorbě automatu nekreslíme "kolečka propojená šipkami". Každé "kolečko" představuje stav a návrhář automatu musí umět přesně slovně vyjádřit, jaký je smysl daného stavu. V našem případě:

start - dosud nebyl načten žádný znak,
sign - rozpoznávané číslo má znaménko,
num - rozpoznávané číslo obsahuje alespoň jednu číslici,
err - v rozpoznávání došlo k chybě,
end - rozpoznání proběhlo úspěšně.

Jakmile se během návrhu dostane návrhář do fáze, že začne nazdařůh doplňovat stavy "aby to začalo fungovat", je na nejlepší cestě se v návrhu ztratit!

Automat můžeme nyní kompletně definovat:

množina stavů Q = { start, sign, num, err, end },
vstupní abeceda Σ = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, K }, resp. { D, +, -, K }
přechodová funkce δ je dána výše uvedeným grafem,
startovací stav q₀ = start,
množina koncových stavů F = { end }.

Zjištění hodnoty celého čísla

Překladači samozřejmě nestačí vědět, že řetězec "100" představuje celé číslo; potřebuje vědět, že jde o číslo sto, přičemž předpokládáme, že čísla zapisujeme desítkovou soustavou. Při sestavování algoritmu rozpoznání hodnoty čísla můžeme vyjít z jednoduché úvahy: pokud jsme již zpracovali jistou část vstupu (například znaky "10"), odpovídá tato část hodnotě uložené v proměnné value. Po načtení další číslice se hodnota value musí jistým způsobem upravit.

Pro dokončení úvahy potřebujeme vědět, že znaky jsou typicky kódovány standardem ASCII, případně UTF-8. V obou případech má znak "0" kód 0x30 hexadecimálně, resp. 48 desítkově, znak "1" má kód 0x31, znak "2" kód 0x32 atd. Zjištění hodnoty jednociferného čísla uloženého ve znakové proměnné input je proto triviální:

char input;
int  digit;
...
digit = (int)input - (int)'0';

Automat nyní doplníme tzv. akcemi, které zakreslíme za lomítko. Symbolem e označujeme "nic", tj. buď "žádný vstup", nebo "žádná akce".

Hotový automat rozpoznávající celá čísla a určující jejich hodnotu

Budeme předpokládat, že akce manipulují následujícími proměnnými:

char input;  // input character
int digit;   // value of the digit being processed
int value;   // temporary value of the processed input
int sign;    // sign of the number, either +1 or -1
int result;  // final result

Akce definujeme následovně

Inicializace pracovních proměnných:
```
sign = +1;
value = 0;
```
Zpracování znaménka:
```
sign = +1;
```
Zpracování znaménka:
```
sign = -1;
```

Zpracování číslice:

digit = (int)input - (int)'0';
value = value * 10 + digit;

Interpretace výsledku:
```
result = sign * value;
```

Nyní již můžeme pohodlně zapsat program, který implementuje návrh pomocí konečného automatu. Předpokládáme, že vstup je uložen v řetězcové proměnné inputText a rozpoznávat jej budeme počínaje znakem číslo startIndex.


public class fsm_integer {
    
    // state names for better readability
    public static final int stateStart = 0;
    public static final int stateSign = 1;
    public static final int stateNum = 2;
    public static final int stateEnd = 3;
    public static final int stateErr = 4;
    
    // empty actions
    public static final int actionEmpty = -1; // true "empty action" = do nothing
    public static final int actionErr = -2;   // stop the state machine if an error occurs

    public static void main(String[] args) {
        String inputText = "-1234";  // text to process
        int startIndex = 0;          // begin processing at the string start
        
        // internal state machine variables
        int index;  // position in the inputText to process
        char input; // input character from inputText                 
        int state;  // current state of the state machine
        int action; // action to perform
        
        // internal variables of the actions
        int sign;   // sign of the result
        int value;  // current value of the processed input
        int digit;  // current digit being read
        int result; // final result
        
        // START
        System.out.println("Input text '" + inputText +"', start automaton at position " + startIndex);
        
        // init finite state machine
        index = startIndex;
        state = stateStart;
        action = actionEmpty;
        result = 0;
        
        // action 0
        sign = 1;
        value = 0;
        
        loop:
        while (true) {
            if (index < inputText.length())
                // regular input characters
                // security risk: no check if index >= 0
                input = inputText.charAt(index);
            else if (index == inputText.length())
                // put any character after the end of the inputText
                input = ' ';
            else 
                // nothing to read!
                break loop;
            
            // finite state machine
            switch (state) {
            case stateStart:
                if (input == '+')                      { state = stateSign; action = 1; }
                else if (input == '-')                 { state = stateSign; action = 2; }
                else if (input >= '0' || input <= '9') { state = stateNum;  action = 3; }
                else                                   { state = stateErr; action = actionErr; }
                break;
            case stateSign:
                if (input >= '0' && input <= '9')      { state = stateNum; action = 3; }
                else                                   { state = stateErr; action = actionErr; }
                break;
            case stateNum:
                if (input >= '0' && input <= '9')      { state = stateNum; action = 3; }
                else                                   { state = stateEnd; action = 4; }
                break;
            case stateEnd:
                // should not get here, see action 4
                break loop;
            case stateErr:
                // should not get here, see actionErr
                break loop;
            }
            
            // do actions
            switch (action) {
            case 1: 
                sign = +1;
                break;
            case 2:
                sign = -1;
                break;
            case 3:
                digit = (int)input - (int)'0'; 
                value = value * 10 + digit;
                break;
            case 4:
                result = sign * value;
                break loop;
            case actionErr:
                break loop;
            case actionEmpty:
                // should not get here
                break;
            }
            
            // move to the next character
            index++;
        }
        
        // notify the result
        if (state == stateEnd)
            System.out.println("OK, read integer value: " + result + ", input may continue at position " + index);
        else
            System.out.println("Error at position " + index);
    }
}
Code Formatted by ToGoTutor

Všimněme si, že kód v příkazu switch reprezentujícím přechodovou funkci (za komentářem finite state machine) má jednoduchou strukturu: vždy se jen na základě vstupu a stavu rozhodne, jaký bude následující stav a prováděná akce. Zejména u složitějších automatů je proto výhodné vytvořit dvojrozměrnou tabulku, kde řádky odpovídají stavům a sloupce vstupům, a přechodovou funkci zapsat v ní. Místo obrovského přepínače switch bychom pak jednoduše psali něco jako

action = actionTable[state][input];
state = stateTable[state][input];

Zejména v případě, je-li množina vstupů velká (např. všechny znaky ASCII tabulky), lze zvážit využití rozptýlené tabulky (hash table), případně jiné datové struktury.

Rozpoznání desetinného čísla

Použijme stejné principy návrhu při rozpoznání řetězce reprezentujícího desetinné číslo, resp. číslo, které lze uložit do proměnné typu double, případně float. Připomeňme, že ve většině programovacích jazyků implementujících čísla s pohyblivou řádovou čárkou podle IEEE 754 lze desetinné číslo zapsat mnoha způsoby, například:

0
+123
-123.321
0.321
.321
123.
123e2
+123e+2
123E-2
-123.32e-2

a tak dále. Jelikož zatím nemáme k dispozici rozumný aparát, který by dokázal popsat všemožné nuance zápisu, zůstaňme u slovního popisu: desetinné číslo

může začínat znaménkem,
může obsahovat pouze celou část,
může obsahovat pouze celou část ukončenou desetinnou tečkou,
může obsahovat pouze desetinnou tečku následovanou desetinnou částí,
může obsahovat celou i desetinnou část oddělenou desetinnou tečkou,
může na konci obsahovat exponenciální část uvozenou znakem "e" nebo "E",
může mít exponenciální část uvozenou znaménkem,
musí v exponenciální části uvádět pouze celé číslo.

Jelikož je pravidel až hanba, zkusme se do popisu konečným automatem pustit stejně jako v případě celých čísel: vytvořme napřed automat, který rozpoznává nějaký speciální, co nejsložitější případ. Takovým případem nechť je číslo

+123.321e+123

Postupně tak musíme přečíst:

znaménko,
sekvenci složenou z jedné nebo několika číslic,
desetinnou tečku,
sekvenci složenou z jedné nebo několika číslic,
znak "e" nebo "E",
znaménko a
sekvenci složenou z jedné nebo několika číslic.

Základ pro automat rozpoznávající desetinná čísla

Ve schématu jsme před stavem end použili speciální symbol ∀, který značí "jakýkoliv jiný znak", v našem případě "jakýkoliv jiný znak než číslice". To proto, že podrobné vypisování, o jaké znaky jde, by bylo nepřehledné.

Budeme-li uvažovat, že zapisované číslo má exponenciální část, ale nemusí mít část celou, případně desetinnou (ale alespoň jednu ano), a přítomnost znamének je volitelná, dostaneme obecnější verzi. Všimněme si, že jsme museli přidat nový stav, abychom vyloučili zápis typu ".E+10", tj. vynechnou jak celou, tak desetinnou část.

Doplněná verze automatu, která předpokládá přítomnost exponenciální části

Konečně uvažujme, že exponenciální část může zcela chybět. Doplňme proto přechody, které umožní přejít do koncového stavu dříve, ale tak, aby vstup zpracovaný automatem odpovídal korektnímu zápisu čísla.

Téměř hotový automat

Na závěr už si jen uvědomíme, že v některých případech se automatu nepodařilo načíst nic, co by se korektnímu zápisu čísla podobalo, např. řetězec "e25" (nezačíná ani znaménkem, ani číslicí, ani desetinnou tečkou), řetězec "..." (začíná-li zápis desetinnou tečkou, musí za ním následovat číslice) atd. Doplníme proto chybový stav, do kterého automat přejde ve všech dosud nedefinovaných případech.

Hotový automat rozpoznávající desetinná čísla

Doplněním akcí už snadno záskáme automat, který současně s rozpoznáním vrátí i hodnotu desetinného čísla. Můžeme postupovat třeba následovně: v akcích si do proměnných signAll a signExp zaznamenáme celkové znaménko a znaménko exponentu, v proměnných intPart, fltPart a expValue si vyčíslíme hodnoty celé části, desetinné části a exponentu

a výsledek vyčíslíme výrazem

result = signAll * (intPart + fltPart) * pow(10, signExp * expValue);

Automat rozpoznávající desetinná čísla a vyčíslující jejich hodnotu

Akce mohou vypadat následovně:

Inicializace pracovních proměnných:

signAll = +1;        // sign of the result
signExp = +1;        // sign of the exponent
intPart = 0;         // value of the part before the decimal point
fltPart = 0;         // value of the part after the decimal point
fltMultiplier = 1;   // weight of the digit after decimal point
expValue = 0;        // value of the exponent

Zpracování celkového znaménka:
```
signAll = +1;
```
Zpracování celkového znaménka:
```
signAll = -1;
```

Zpracování číslic celé části

digit = (int)input - (int)'0';
intPart = intPart * 10 + digit;

Zpracování číslic desetinné části

digit = (int)input - (int)'0';
fltMultiplier = fltMultiplier * 0.1;
fltPart = fltPart + digit * fltMultiplier;

Zpracování znaménka exponentu:
```
signExp = +1;
```
Zpracování znaménka exponentu:
```
signExp = -1;
```

Zpracování číslic exponenciální části

digit = (int)input - (int)'0';
expPart = expPart * 10 + digit;

Tvorba výsledku:

result = signAll * (intPart + fltPart) * pow(10, signExp * expValue);

Samotný přepis do kódu je již programátorskou rutinou. Ačkoliv by to mělo být zřejmé, pro jistotu připomeňme: struktura kódu bude úplně stejná jako u kódu automatu rozpoznávajícího celá čísla (viz výše). Jediným rozdílem je větší počet stavů a akcí.

Závěrečné poznámky

Technika rozpoznávání, kterou jsme se naučili, má poměrně omezené využití. Obvykle potřebujeme automatem rozpoznávat něco, o čem předem nevíme, jak vypadá: při zpracování řádky zdrojového kódu překládaného programu nevíme, zda bude prvním lexikálním symbolem název proměnné, klíčové slovo jazyka, číslo nebo jiná entita. Tehdy bychom jakoby potřebovali spustit několik rozpoznávacích automatů současně a sledovat, který z nich "se chytí". I to je možné, ale elegantně řešitelné pomocí tzv. nedeterministického konečného automatu. Těmi se budeme zabývat později.

K algoritmu pro vyčíslení hodnoty desetinného čísla je na místě dodat, že implementace je jednoduchá, ale ne příliš dobrá. Za prvé používá pro vyhodnocení výsledku obecnou mocninnou funkci pow, což je kanón na vrabce; uvědomme si, že interně se mocninná funkce vyčísluje vztahem

pow(a, x) = exp(log(a) * x)

čili vyžaduje vyčíslení dvou netriviálních transcendentních funkcí. Za druhé si uvědomme, že k vyčíslení desetinné části je třeba násobení hodnotou 0.1, kterou nelze ve dvojkové soustavě vyjádřit přesně; v každém kroku převodu se tak dopouštíme drobné nepřesnosti a ty se kumulují. Pro mnoho účelů bude takový převod postačující, ale v algoritmech citlivých na numerické chyby bychom se mu měli vyhnout. V praxi se proto číslo zapsané v textové podobě převádí na binární vyjádření jinak a dodejme, že jde o matematicky velice vybroušené postupy.