#1 richard.zavodny
Za teorií parsování textových souborů je velmi hezká matematika. Nicméně, zkusím v kostce to popsat i bez ní.
Textové parsery typicky mají dvě nebo tři úrovně:
- lexikální. To je ona zmiňovaná tokenizace. Ve vašem případě by tokeny asi byly: identifikátor (to jsou ty názvy položek bez uvozovek), řetězec (texty v uvozovkách), rovnítko, levá_závorka, pravá_závorka, čárka.
- Syntaktická. Tato úroveň definuje strukturu textu. Ve vašem případě říká, že soubor se skládá ze seznamu závodů, každý závod obsahuje datum, místo konání a seznam škol, které se ho účastní. Každá škola má název a počet bodů a seznam soutěžících žáků, atd.
- Sémantická. Tato úroveň už pracuje s konkrétními významy a vy ji už asi nepotřebujete. V případě reálného programovacího jazyka například pracuje s datovými typy (můžete napsat syntakticky správný výraz, který ale sémanticky selže, protože např. sčítáte číslo a strukturu).
Tokenizace se typicky dělá pomocí konečných automatů. Je to jednoduchá, ale většinou dost nezajímavá práce, např.:
Token ziskejToken() {
Stav stav(INIT);
while(true) {
int znak(nactiDalsiZnak());
switch(stav) {
/* -- pocatecni stav */
case INIT:
/* -- konec vstupu */
if(znak == EOF) return TokenEof;
/* -- znak je pismeno, prejdi do stavu parsovani slova */
if(isalpha(znak)) stav = WORD;
/* -- znak je cislice, prejdi do stavu parsovani cisla */
if(isnum(znak)) stav = NUM;
/* -- znak je neco jineho, ignorujeme ho azustavame
ve stejnem stavu */
break;
/* -- parsujeme slovo */
case WORD:
/* -- dosli jsme na konec slova? */
if(znak == EOF || !isalpha(znak)) {
/* -- ano jsme na konci slova. Nacteny znak
vratime zpet do vstupu, protoze muze byt
soucasti nasledujiciho tokenu. */
vratZnakZpetDoVstupu(znak);
return TokenWord;
}
/* -- nejsme na konci slova, zustavame ve stejnem stavu */
break;
/* -- parsujeme cislo */
case NUM:
/* -- dosli jsme na konec cisla? */
if(znak == EOF || !isnum(znak)) {
/* -- ano jsme na konci cisla. Nacteny znak
vratime zpet do vstupu, protoze muze byt
soucasti nasledujiciho tokenu. */
vratZnakZpetDoVstupu(znak);
return TokenNum;
}
/* -- nejsme na konci cisla, zustavame ve stejnem stavu */
break;
}
}
}
Předchozí pseudokód tokenizuje slova a čísla z nějakého textu. Má tři stavy: init, word a num. Pokud v initu padne na písmenko, přejde do stavu word a v něm setrvá tak dlouho, dokud mu chodí písmenka. Podobně pokud padne na číslici, přejde do stavu num a v něm setrvá tak dlouho, dokud mu chodí číslice. Skutečný kód by byl podstatně složitější, protože také obvykle chceme vědět, jaké skutečné slovo nebo číslo jsme přečetli, takže je potřeba si načtené znaky někam schovávat. Ale doufám, že princip je z příkladu jasný.
Konečné automaty se dají zakódovat i jinak, než pomocí switch a if, ale tohle je asi nejčastější způsob, pokud se dělají ručně. Také ale existují jejich generátory - v případě lexikální analýzy se asi nejčastěji používá GNU flex. Ty obvykle používají nějaké tabulky.
Syntaktická analýza už pracuje se streamem tokenů. Existuje pro ni řada algoritmů. Nejjednodušší, a pro váš účel postačující, je asi něco, co se nazývá rekurzivní sestup (ve skutečnosti je to implementace algoritmu označovaného jako LL(1)). Ve vašem případě by vypadal nějak takhle (zjednodušil jsem si práci a neřeším tu čárky mezi hodnotami):
void parsujSoubor() {
while(true) {
Token token(dejNahled());
/* -- konec vstupu */
if(token == TokenEof) return;
/* -- ocekavame zavod */
if(token == TokenIdent && token.value == "zavod") {
srovnej(TokenIdent);
srovnej(TokenEqual);
srovnej(TokenLeftBrace);
parsujZavod();
srovnej(TokenRightBrace);
continue;
}
/* -- cokoliv jineho na vstupu je chyba */
skonciSChybou();
}
}
void parsujZavod() {
parsujHodnotu("misto");
parsujHodnotu("datum");
Token token(dejNahled());
if(token != TokenIdent || token.value != "skoly") {
skonciSChybou();
}
srovnej(TokenIdent);
srovnej(TokenEqual);
srovnej(TokenLeftBrace);
while(true) {
token = dejNahled();
/* -- pokud mam uzaviraci zavorku, seznam skol konci */
if(token == TokenRightBrace) {
/* -- konec seznamu skol */
srovnej(TokenRightBrace);
break;
}
/* -- oteviraci zavorka znamena novou skolu */
if(token == TokenLeftBrace) {
/* -- Oteviraci zavorku se nesnazime pozrat pomoci
srovnej(). To si udela parsujSkolu() samo. */
parsujSkolu();
}
/* -- cokoliv jineho je chyba */
skonciSChybou();
}
}
void parsujHodnotu(string jmeno) {
Token token(dejNahled());
if(token != TokenIdent || token.value != jmeno) {
skonciSChybou();
}
srovnej(TokenIdent);
srovnej(TokenEqual);
srovnej(TokenString);
}
Pro algoritmus potřebujete náhled jednoho tokenu - tzn. možnost přečíst token ze vstupu, aniž by se z něho odebral. To je používané tam, kde se parser potřebuje rozhodnout, kudy dál. Funkce parsujSoubor tak např. rozlišuje korektní ukončení vstupu, situaci, kdy má začít parsovat závod, anebo chybovou situaci.
Další důležitá operace je srovnání. To odebere token ze vstupu a případně ukončí parser s chybou, pokud token neodpovídá tomu, který dostal jako parametr.
Struktura dokumentu je pak v kódu pěkně vidět. Soubor se skládá ze seznamu závodů (cyklus tak dlouho, dokud dostávám závody). Závod se skládá z místa, data a seznamu škol (cyklus tak dlouho, dokud nedostanu uzavírací závorku).
I psaní syntaktického analyzátoru je poměrně nezajímavá a mechanická práce. Proto i zde je možné použít generátor. Nejznámější je asi GNU Bison. Nicméně ten používá výrazně komplikovanější algoritmus, než jsem popsal výše, takže jeho použití je už poněkud vyšší dívčí. Ale existují i jiné.
TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Návštěvník
Nahlásit jako SPAM
IP: 89.24.189.–
God of flame
Guru
Grafoman
Zjistit počet nových příspěvků
