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
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;
}
}
