Konečný překladový automat

Konečný automat je rozpoznávací funkcí, která určí, zda-li zadaný vstup patří do daného regulárního jazyka (výstup: true, false). Občas je ale zapotřebí navíc získat určitý komplexní výstup, který není binární (např. překlad vstupního řetězce nebo výpočet na jeho základě). Proto je zapotřebí konečný automat obohatit na přechodových hranách o funkce, které se při průchodu automatem provedou. Tímto způsobem vznikne konečný překladový automat.


Příklad

Konečný překladový automat
Konečný překladový automat

Vytvořte konečný překladový automat přijímající řetězce reprezentující decimální (19875), hexadecimální (0x1FA570) a oktalová (01764) čísla, vracející jejich decimální hodnotu.

Popis

Začínáme v uzlu S (start), pokud nám přijde číslo 1-9, pak se jedná o desítkové číslo a přejdeme do stavu D, při přechodu provedeme akci, která nám dané číslo uloží do paměti (A1). V uzlu D zpracováváme přicházející číslo (A1), dokud nám přichází vstup. Uzel D je koncový.

Pokud nám ovšem v uzlu S přijde nula, tak nevíme, jestli se jedná o hexadecimální nebo oktalové číslo, to se dozvíme až podle dalšího vstupu. Každopádně 0 je korektní číslo, proto je uzel H/O koncový.

Když přijde za nulou nějaké číslo, tak je zřejmé, že se jedná o oktalové číslo, které budeme převádět akcí A2, pokud přijde x, tak se jedná o hexadecimální číslo, zpracovávané akcí A3. U hexadecimálního čísla musíme ještě projít právě přes uzel x, který není koncový, protože číslo 0x není v korektním formátu.

Kód

/**
 * konecny prekladovy automat
 * @author Pavel Micka
 */
public class TranslationFiniteStateMachine {
    /**
     * index, na kterem se pri prekladu nachazime
     */
    private int index = 0;
    /**
     * prekladany retezec
     */
    private String s;
    /**
     * hodnota, kterou to vrati
     */
    private int hodnota = 0;

    public TranslationFiniteStateMachine(String s) {
        this.s = s;
    }
    /**
     * prelozi vstup automatu ve tvaru
     * 124689 - decimalni cislo
     * 02345 - oktalove cislo
     * 0x56AF5 - hexadecimalni cislo
     * na decimalni cislo
     * @return decimalni reprezentace
     */
    public int translate() {
        final String ERROR = "spatny vstup";
        final String EMPTY = "spatny vstup / retezec je prazdny";
        char in = readNext();
        if (in >= '1' && in <= '9') { //cislice, nezacina nulou, pujde o dekadicke cislo
            do {
                hodnota = hodnota * 10 + (in - 48); //48 == znak 0 v ascii, akce A1
            } while ((in = readNext()) != 0 && in - 48 >= 0 
                && in - 48 <= 9); //dokud nejsme na konci vstupu 
				      //nebo neprisel nesmysl
            if (in == 0) {
                return hodnota;
            } else {
                throw new IllegalArgumentException(ERROR + " " + in);
            }
        } else if (in == '0') {//oct or hexa
            in = readNext();
            if (in == 'x') { //hexa
                boolean readed = false; //jesli byl uz precten alespon jeden 
                                        //znak samotneho cisla - 0x nebereme
                while (((in = readNext()) != 0) && (in >= '0' && in <= '9') 
                    || (in >= 'A' && in <= 'F')) {
                    readed = true;
                    if (in >= '0' && in <= '9') { //cislo
                        hodnota = hodnota * 16 + (in - 48); //48 == znak 0 v ascii, akce A3
                    } else { //cislo nad 9...cili A - F
                        hodnota = hodnota * 16 + (in - 65 + 10); 
                        //65 == znak A v ascii, +10 protoze A == 10 v hexa
                    }
                }
                //dokud nejsme na konci vstupu				    
                //nebo neprisla blbost
                if (in == 0 && readed) {
                    return hodnota;
                } else {
                    throw new IllegalArgumentException(ERROR + " " + in);
                }
            } else if (in >= '0' && in <= '7') {//octa
                do {
                    hodnota = hodnota * 8 + (in - 48); //48 == znak 0 v ascii, akce A2
                } while ((in = readNext()) != 0 && in >= '0' && in <= '7'); 
                                                       //dokud nejsme na konci vstupu 
                                                       //nebo neprisel nesmysl
                if (in == 0) {
                    return hodnota;
                } else {
                    throw new IllegalArgumentException(ERROR + " " + in);
                }
            } else if(in == 0){ //na vstupu byla jenom nula, ted uz tam nic neni
                return 0;
            }
        } else if (in == 0) {
            throw new IllegalArgumentException(EMPTY);
        }
        throw new IllegalArgumentException(ERROR + " " + in);
    }

    /**
     * vrati dalsi znak na vstupu
     * @return znak na vstupu nebo 0 v pripade konce retezce
     */
    private char readNext() {
        if (index >= s.length()) {
            return 0;
        }
        char ret = s.charAt(index);
        index++;
        return ret;
    }
}







Doporučujeme