Parser bankovních výpisů aneb hrátky s Ragel

Tak nějak se mi přihodilo, že jsem potřeboval v jedné aplikaci zpracovávat větší než malé množství elektronických bankovních výpisů České spořitelny. Datové výpisy lze z běžného účtu vyexportovat buď ve formátu ABO, nebo CSV. ABO je jednoduchý formát s pevnou délkou polí a jeho zpracování by bylo velmi primitivní, nicméně textové popisy mohou být tím pádem nekompletní. V CSV exportu jsou texty sice kompletní, přístup banky k němu je ovšem poměrně kreativní:

"Account number","85732310/0800"
"Account currency","CZK"
"Statement number","11.00"
"Statement date","2007/11/30"
"Statement frequency","monthly"
"Account name","Vommit, Ltd."
"Total number of transactions","7"
"Pending transactions","0.00"
"Debit (-)","11 576.00"
"Credit","3 010.02"
"Initial balance","36 833.02"
"Final balance","28 267.04"

"Due date","Payment","Counter-acc. no.","Transaction","Currency", ... ,"-"
"2007/11/05","Trvalý příkaz","36443102/2400","-1 600.00","CZK", ... ,"-"
"2007/11/06","S24/IB JPU","80299027/0300","-16 138.50","CZK", ... ,"-"
"2007/11/11","Úhrada","52496/5500","3 961.00","CZK", ... ,"-"
"2007/11/30","Úrok kredit","/0800","27.02","CZK", ... ,"-"
"2007/11/06","Poplatek","/0800","-4.00","CZK", ... ,"-"
"2007/11/10","Poplatek","/0800","-7.50","CZK", ... ,"-"
"2007/11/10","Poplatek","/0800","-15.00","CZK", ... ,"-"

Údaje týkající se celého výpisu jsou v úvodu dokumentu s volnějším formátováním podobným CSV a po prázdném řádku následuje teprve řádek s názvy polí a řádky jednotlivých bankovních transakcí, tak jak je to v CSV běžné. Všimněte si i neobvyklého formátování čísel, kde mezi řádem tisíců a stovek je mezera. Občas se objeví i netradičně mezera po znaménku (- 100.00). Takovýto CSV soubor pak nelze jednoduchým způsobem načíst např. ani v Excelu nebo Calcu, protože čísla menší než tisíc jsou konvertována na číselný datový typ, ta větší (přesněji řečeno ta s mezerou) zůstávají jako text.

Pokusy s dostupnými parsery

Moje aplikace nicméně nebyla v Excelu, nýbrž v Ruby on Rails, kde jsem potřeboval připravit dávkové načítání transakcí z datových výpisů do databáze PostgreSQL. Ve standardní knihovně jazyka Ruby je sice jednoduchý CSV parser, ale ten se mi nepodařilo na souborech s výše uvedeným formátem uspokojivě rozchodit. Pak jsem se zahleděl do FasterCSV. Tahle knihovna rozhodně není špatná, nicméně mi na ní trochu vadilo, že se někdy rozhoduje až příliš samostatně. U standardních CSV souborů to sice vede k velmi pohodlnému použití, u nestandardních však někdy k problémům. Něco (mezery v číslech, konverze z CP1250 na UTF-8) lze sice nepříliš elegantně vyřešit naprogramováním vlastních konvertorů (FasterCSV je pak umí použít místo svých implicitních), nelze však ovlivnit, jaký konvertor FasterCSV kdy použije. Nepodařilo se mi např. jednoduše vyřešit korektní načtení referenčního čísla bankovní věty – FasterCSV se vzpíral uvěřit, že 1130E98001660 by mohl být obyčejný řetězec a ne číslo s plovoucí desetinou čárkou mimo povolený rozsah.

Nakonec jsem se rozhodl napsat si vlastní parser pomocí programu Ragel – což je kompilátor konečných automatů, který generuje z popisu automatu zdrojový kód v Ruby (příp. C/C++, Javě). Z dalších možností Ragelu stojí za zmínku vytvoření diagramu konečného automatu pomocí vizualizačního software Grap­hviz. Na Internetu lze najít spoustu článků doporučujících Ragel pro rychlý vývoj spolehlivých parserů. Na seriózní informace o Ragelu lze však narazit i poměrně bizarními způsoby. Příkladů se také dá nalézt poměrně dost, bohužel se téměř všechny týkají C/C++, ale ne už třeba Ruby nebo Javy. Nejvíce mi asi pomohl článek Hello World for Ruby on Ragel.

Instalace Ragelu

Nejnovější verze Ragelu je 6.0. Manuál i binární verze pro Windows se dá stáhnout, nicméně jsem nenašel RPM balíček šesté verze pro můj OpenSUSE 10.3. Stáhl jsem si tedy zdrojový archív, rozbalil a použil svatou trojkombinaci. Vše proběhlo bez problémů, dokonce i prefix pro instalaci byl implicitně nastaven logicky (/usr/local).

Začínáme s Ragelem

Vstupní informace pro Ragel je soubor (obvykle s příponou .rl), který obsahuje kód programu v cílovém jazyce (v našem případě tedy Ruby), do kterého je vnořen popis konečného automatu (včetně direktiv, kam a jak se má generovat kód v cílovém jazyce). Podívejme se ale, jak popsat parser pro výše uvedený bankovní výpis.

Na první pohled je jasné, že bankovní výpis obsahuje dvě hlavní části oddělené prázdným řádkem. První část se týká globálních informací a je formátována tak, že každý řádek obsahuje vždy nějaký atribut definovaný názvem a hodnotou. Jak název, tak i hodnota jsou uzavřeny v uvozovkách a odděleny čárkou.  Zkusme si napsat parser, který tuto první část výpisu načte do hashe (asociativního pole) v Ruby. Pro jednoduchost budeme předpokládat, že všechny hodnoty jsou textového typu a že se v názvu ani v hodnotě nemohou objevit uvozovky. Výsledný soubor vypis_parser.rl vypadá takto (čísla řádku jsou uvedena jen pro informaci, do souboru nepatří):

 1: %%{
 2:   machine parser_bank_vypis;
 3:
 4:   nazev_atr = ^'"'+
 5:             >{ nazev = "" }
 6:             ${ nazev << data[p] } ;
 7:
 8:   hodnota_atr = ^'"'+
 9:               >{ hodnota = "" }
10:               ${ hodnota << data[p] }
11:               %{ vypis[nazev]=hodnota } ;
12:
13:   globalni_atribut = '"' nazev_atr '","' hodnota_atr '"\r\n' ;
14:
15:   main := globalni_atribut+ '\r\n' ;
16: }%%
17:
18: %% write data;
19:
20: def parse_vypis(file_name)
21:   data = Array.new
22:   File.open(file_name, "rb") { |f| data = f.read.unpack("C*") }
23:
24:   vypis = Hash.new
25:
26:   %% write init;
27:   %% write exec;
28:
29:   p vypis
30: end
31:
32: parse_vypis 'vypis0711.csv'

Kromě vloženého popisu konečného automatu a direktiv jde o normální zdrojový kód v Ruby (zelený text). Na řádcích 20 až 30 je definována funkce (přesněji řečeno metoda) parse_vypis, na řádku 32 je pak volána s parametrem vypis0711.csv, což je jméno souboru s bankovním výpisem. Popis konečného automatu (černý text) je oddělen od kódu v Ruby buď uzavřením do speciálních závorek %%{ a }%% (pro souvislý blok – řádky 1 až 16), případně použitím dvojitých procent %% pro jednotlivé řádky (18, 26 a 27).

Ragel očekává vstup jako pole celých čísel v proměnné s názvem data (platí jen pro Ruby a Javu). Prvky pole reprezentují jednotlivé znaky zpracovávaného řetězce. Na řádku 22 je načtení CSV souboru do řetězce a jeho převod na požadované pole čísel pomocí standardní metody unpack třídy String (pozor, kdyby byl vstup v UTF-8, použijeme U* místo C*). Hash pro výsledek deklarujeme a inicializujeme na řádku 24.

Popis konečného automatu v Ragelu je vlastně stavebnice. Z jednodušších automatů tvoříme složitější. K přechodům mezi stavy pak můžeme přiřadit akce (pozor, akce jsou psány v cílovém jazyce). Je potřeba ještě vědět, že Ragel kromě pole data používá i další veřejné proměnné, mimo jiné:

• p – index právě zpracovávaného prvku pole data,
• pe – index posledního zpracovávaného prvku v poli data,
• cs – aktuální stav konečného automatu.

Podívejme se podrobněji na popis našeho konečného automatu: Na pojmenování automatu na řádku 2 není asi nic zajímavého. Pak následují definice velmi primitivních automatů ( nazev_atr na řádcích 4 až 6, hodnota_atr na řádcích 8 až 11), ze kterých je vytvořena definice automatu globalni_atribut (řádek 13). Automat globalni_atribut reprezentuje jeden řádek souboru se jménem a hodnotou globálního atributu. Konečně na řádku 15 definujeme konečný automat main, který odpovídá několika globálním atributům (tj. několika řádkům vstupního souboru) následovaných prázdným řádkem. Můžeme se všimnout odlišného znaku přiřazení u automatu main. Dvojice := znamená, že má být vytvořena instance tohoto automatu. Ostatní automaty jsou oproti tomu pouze definovány, nikoliv však instanciovány.

Všechny možnosti popisu a skládání automatů lze najít v manuálu, nicméně alespoň stručné vysvětlení použitých výrazů:

• řádky 4 a 8: ^'"'+ označuje jeden nebo více znaků kromě znaku uvozovky
• řádek 13: '"' nazev_atr '","' hodnota_atr '"\r\n' označuje posloupnost:
• uvozovky
• cokoliv, co přijme automat nazev_atr (tedy posloupnost znaků kromě uvozovek)
• uvozovky, čárka, uvozovky
• cokoliv, co přijme automat hodnota_atr (opět posloupnost znaků kromě uvozovek)
• uvozovky následované koncem řádku – znaky CR (návrat vozíku) a LF (nový řádek).
• řádek 15: jednou nebo vícekrát cokoliv, co přijme automat globalni_atribut, pak prázdný řádek

Kromě výrazů popisujících daný automat, jsou ještě použity akce (řádky 5,6 a 9 až 11). Jsou to fragmenty kódu v cílovém jazyce, které se provedou při určitých přechodech mezi stavy konečného automatu. V příkladu jsou použity tyto typy akcí:

• > – akce se vykoná při vstupu do daného automatu (např. řádek 9: při vstupu do automatu hodnota_atr se proměnná se jménem hodnota inicializuje prázdným řetězcem)
• $ – akce se vykoná při libovolném přechodu daného automatu (např. řádek 10: při každé změně stavu automatu hodnota_atr se na konec řetězce v proměnné hodnota přidá právě zpracovávaný znak)
• % – akce se vykoná při opuštění daného automatu (např. řádek 11: při opuštění automatu hodnota_atr se proměnná hodnota přiřadí do hashe vypis s klíčem  nazev)

Popis automatu negeneruje žádný kód. Ten je vygenerován až direktivami (řádky 18, 26 a 27). Z označení je asi celkem jasné, že první direktiva deklaruje data potřebná pro automat, druhá jej inicializuje a třetí vkládá výkonný kód.

Spuštění

Nejprve je potřeba vygenerovat cílový kód konečného automatu:

$ ragel -R vypis_parser.rl

Vytvoří se soubor se stejným názvem, ale příponou .rb, který můžeme spustit v interpretu Ruby:

ruby vypis_parser.rb

Výsledkem pak je:

{"Final balance"=>"28 267.04", "Pending transactions"=>"0.00", "Initial balance"=>"36 833.02", "Statement frequency"=>"monthly", "Statement number"=>"11.00", "Debit (-)"=>"11 576.00", "Credit"=>"3 010.02", "Total number of transactions"=>"7", "Account name"=>"Vommit, Ltd.", "Account currency"=>"CZK", "Statement date"=>"2007/11/30", "Account number"=>"85732310/0800"}

Dokončení a vylepšení

Výše uvedený příklad je velmi jednoduchý a rozhodně poskytuje prostor pro zlepšení. Například přidávat k řetězci znak po znaku nebude asi ta nejefektivnější varianta. Lepší řešení by mohlo být zapamatovat si při vstupu do automatu pozici – tj. proměnnou p a při opuštění automatu převést na řetězec příslušnou oblast pole data najednou (metoda pack).  Dále opakující se nebo složitější akce bývá vhodné pojmenovat a deklarovat zvlášť – mimo daný automat (viz např. řádky 6 až 9 nebo 11 až 15 ve výpisu níže) . Pokud bychom rozšířili úvodní příklad, aby zpracovával celý bankovní výpis, mohl by zdrojový soubor vypadat například takto:

 1: %%{
 2:   machine parser_bank_vypis;
 3:
 4:   action uloz_pozici { p0 = p }
 5:
 6:   action zacatek_transakce {
 7:     i = 0  # vynulovat index pole
 8:     vypis[:transactions] << Hash.new
 9:   }
10:
11:   action zpracuj_pole {
12:     nazev = vypis[:field_names][i]
13:     vypis[:transactions][-1][nazev] = data[p0..p-1].pack("C*")
14:     i += 1
15:   }
16:
17:   cokoliv_krome_uvozovek = ^'"'+ ;
18:
19:   nazev_atr = cokoliv_krome_uvozovek
20:             >uloz_pozici
21:             %{ nazev = data[p0..p-1].pack("C*") } ;
22:
23:   hodnota_atr = cokoliv_krome_uvozovek
24:               >uloz_pozici
25:               %{ vypis[nazev]=data[p0..p-1].pack("C*") } ;
26:
27:   eol = '\r\n' ;
28:
29:   globalni_atribut = '"' nazev_atr '","' hodnota_atr '"' eol ;
30:
31:   nazev_pole = cokoliv_krome_uvozovek
32:              >uloz_pozici
33:              %{ vypis[:field_names] << data[p0..p-1].pack("C*") } ;
34:
35:   nazvy_poli = ('"' nazev_pole '",')* ('"' nazev_pole '"') eol ;
36:
37:   pole = cokoliv_krome_uvozovek*
38:        >uloz_pozici
39:        %zpracuj_pole ;
40:
41:   transakce = ( ('"' pole '",')* ('"' pole '"') eol )
42:             >zacatek_transakce ;
43:
44:   main := globalni_atribut+ eol nazvy_poli transakce* ;
45: }%%
46:
47: %% write data;
48:
49: def parse_vypis(file_name)
50:   data = Array.new
51:   File.open(file_name, "rb") { |f| data = f.read.unpack("C*") }
52:
53:   vypis = Hash.new
54:   vypis[:field_names] = Array.new
55:   vypis[:transactions] = Array.new
56:   i = 0
57:
58:   %% write init;
59:   %% write exec;
60:
61:   p vypis
62: end
63:
64: parse_vypis 'vypis0711.csv'

Do hashe vypis se tak ještě přidá pole s názvy sloupců (polí) transakcí. Transakce jsou pak uloženy tamtéž jako pole hashů. Vlastní zdrojový kód v Ruby je opět označen zeleně, zbytek je popis automatu pro parsování. Bylo by samozřejmě ještě vhodné zkontrolovat, zda se zpracoval celý soubor (hodnoty proměnných p a pe se musejí rovnat), případně přidat nějakou rozumnou reakci na chyby. Ještě by bylo potřeba převést hodnoty z řetězců na odpovídající datové typy a texty do UTF-8, ale to bych osobně řešil až v rámci následného zpracování v Ruby.

Závěr

Napsat jednoduchý parser pomocí Ragelu je opravdu rychlé a jednoduché i pro vývojáře, kteří nepíší konečné automaty každý den. Nicméně i tak je potřeba důkladně přečíst manuál. Mne osobně třeba Ragel nachytal na švestkách, když prováděl akci specifikovanou pro přechod do cílového stavu automatu pro každý přechod. Až když jsem si nechal vykreslit diagram, pochopil jsem, že po minimalizaci má automat jen jeden stav, který musí být přirozeně i cílový.

A úplně nakonec shrnutí výhod a nevýhod:

Výhody Ragelu

• multiplatformní (Linux, Windows, Mac)
• žádné závislosti na externích knihovnách
• jednoduché použití (není potřeba znát moc teorie)
• možnost vygenerovat diagram
• minimalizace konečného automatu
• údajně generuje velmi rychlý cílový kód v C/C++ (nezkoušel jsem)
• možnost přechodu do jiného jazyka (gramatika se nemění, jen akce)

Nevýhody

• nenahrazuje plně dokonalejší kompilátory založené na LALR nebo LL(*) gramatikách (YACC, ANTLR)
• horší práce s mixem cílového kódu a popisu automatu
• problematičtější ladění cílového kódu

Soubory ke stažení

• vypis0711.csv
• vypis_parser.rb
• vypis_parser.rl
• vypis_parser_komplet.rb
• vypis_parser_komplet.rl