Počítačová hra Tetris slaví 40 let. Alexej Pažitnov dokončil první hratelnou verzi 6. června 1984. Mezitím vznikla celá řada variant. Například Peklo nebo Nebe. Loni měl premiéru film Tetris.
MicroPython (Wikipedie), tj. implementace Pythonu 3 optimalizovaná pro jednočipové počítače, byl vydán ve verzi 1.23.0. V přehledu novinek je vypíchnuta podpora dynamických USB zařízení nebo nové moduly openamp, tls a vfs.
Canonical vydal Ubuntu Core 24. Představení na YouTube. Nová verze Ubuntu Core vychází z Ubuntu 24.04 LTS a podporována bude 12 let. Ubuntu Core je určeno pro IoT (internet věcí) a vestavěné systémy.
Databáze DuckDB (Wikipedie) dospěla po 6 letech do verze 1.0.0.
Intel na veletrhu Computex 2024 představil (YouTube) mimo jiné procesory Lunar Lake a Xeon 6.
Na blogu Raspberry Pi byl představen Raspberry Pi AI Kit určený vlastníkům Raspberry Pi 5, kteří na něm chtějí experimentovat se světem neuronových sítí, umělé inteligence a strojového učení. Jedná se o spolupráci se společností Hailo. Cena AI Kitu je 70 dolarů.
Byla vydána nová verze 14.1 svobodného unixového operačního systému FreeBSD. Podrobný přehled novinek v poznámkách k vydání.
Společnost Kaspersky vydala svůj bezplatný Virus Removal Tool (KVRT) také pro Linux.
Grafický editor dokumentů LyX, založený na TeXu, byl vydán ve verzi 2.4.0 shrnující změny za šest let vývoje. Novinky zahrnují podporu Unicode jako výchozí, export do ePub či DocBook 5 a velké množství vylepšení uživatelského rozhraní a prvků editoru samotného (např. rovnic, tabulek, citací).
Byla vydána (𝕏) nová verze 7.0 LTS open source monitorovacího systému Zabbix (Wikipedie). Přehled novinek v oznámení na webu, v poznámkách k vydání a v aktualizované dokumentaci.
Na regulární výrazy existuje několik pohledů. Pro ty, kteří je používat neumí, se jedná o magickou sekvenci znaků, které se nikdy nesnaží porozumět. Pro ty, kteří je používají, se jedná o mocný nástroj pro práci s textem, který lze použít při hledání, pro úpravy, nebo pro ověření vstupního řetězce. No a pro ty, kteří něco vědí o teoretické informatice, se jedná o větu jazyka typu 3. Navíc ta poslední skupina lidí tuší něco o konečném automatu a jeho vztahu k regulárním jazykům, výrazům.
Pochopitelně se nám tu vynořuje otázka. Pokud jsou regulární výrazy výsledkem gramatiky typu 3, to znamená nejméně mocné formy, proč se jimi vůbec zabývat? Proč nenasadit rovnou prostředky klasického programovacího jazyka, který je nepochybně mocnější a zvládne více věcí? Důvodů je několik. Předně síla jazyků typu 3 na většinu úloh stačí (a navíc současné výrazy u moderních nástrojů už patří do vyšších typů). Druhým důvodem je stručnost a (ne)přehlednost zápisu, oproti programové implementaci (jak se přesvědčíte dále). Kniha Art Of Unix Programming se v osmé kapitole zabývá minijazyky pro řešení specializovaných úloh, mezi něž se řadí i regulární výrazy. Obvykle je jednodušší napsat regulární výraz, než vytvořit jeho programovou implementaci.
Snad každého někdy napadlo — Jak to ten
Vezměme jednoduchý výraz grep
(sed
, perl
, ...) vlastně dělá? Jaká je posloupnost kroků od zadaného výrazu až po kód, který jej provádí?x*y+
, který značí vezmi libovolný počet znaků x, následovaný alespoň jedním znakem y.
Člověk, který o regulárních výrazech neslyšel, by pravděpodobně začal daný problém řešit asi takto:
function hledej1(inp) { byloX = false; // promenne udavajici byloY = false; // stav resene ulohy zac = 0; kon = 0; for (i = 0; i != inp.length; i++) { ch = inp.charAt(i); if (!byloX && !byloY && ch != "x" && ch != "y") { continue; } if (!byloX && !byloY && ch == "x") { byloX = true; zac = i; } if (!byloX && !byloY && ch == "y") { byloY = true; zac = i; } if ( byloX && !byloY && ch == "y") { byloY = true; } if ( byloX && byloY && ch != "y") { break;} kon++; } msg1 = "hledej1(\""+inp+"\") --> x*y+ "; msg3 = "\n"; if (!byloY) { msg2 = "nenalezen"; } else { msg2 = "nalezen (" + zac + ", " + kon + ")";} return msg1+msg2+msg3; }
Dlouho jsem přemýšlel, jaký jazyk zvolit pro příklady — C, C++, Javu, Python? Nakonec jsem se rozhodl pro Javascript a to z toho důvodu, že všechny příklady jsou jednoduché a navíc mohou být spuštěny přímo v prohlížeči. Bohužel mi dalo trochu práce ladění, protože se zdá, že některé konstrukce v jistých prohlížečích nepracují, jako třeba foreach
(Opera, MSIE) a indexování řetězců (MSIE). Nicméně skripty jsou úspěšně otestovány v prohlížečích Mozilla Firefox 1.5, Internet Explorer 6.0 a Konqueror 3.5 a Opera 9.0. Výsledek (dynamicky generovaný Javascriptem) máte zde:
Je nutné poznamenat, že tento způsob implementace je velice (velice jemně řečeno) nevhodný. Kód je zmatený, složitý, špatně se chápe a tím poskytuje prostor pro chyby (ostatně moje implementace pracuje špatně). Navíc, byť i jednoduchá změna, znamená, že je nutné celý program změnit.
Tím, co kód znepřehledňuje nejvíc, jsou stavové proměnné. Respektive jejich složité vztahy, které musíme v programu uhlídat pomocí složitých podmínek. Pokud se nám v kódu (v lepším případě v návrhu) podobné věci množí, bývá konečný automat nejvhodnějším řešením. Formálně je (nedeterministický, bude vysvětleno dále) konečný automat pětice M = (Q, Σ, δ, q0 ∈ Q, F ⊂ Q)
Nejdůležitějším pojmem u konečného automatu je stav. Koneckonců se někdy nazývají stavovými automaty (Finite State Automata v angličtině). Automat lze graficky znázornit:
Jak vidíte, automat se sestává se 3 stavů S, X a Y, přičemž S je startovacím stavem a Y koncovým. Ne náhodou je tento automat ekvivalentní regulárnímu výrazy x*y+
. Ve startovacím stavu S automat čeká na některý ze znaků x, nebo y. V případě příchodu znaku x se přepne do stavu X a ten neopustí, dokud nenačte znak y. Potom se přepne do stavu koncového stavu Y. Znak ¬y značí cokoliv mimo y, takže se ze stavu X můžeme dostat do počátku. Praktická implementace by mohla vypadat takto (přidal jsem 4. stav F, abych nemusel používat goto
, nebo cyklus while
):
function hledej2(inp) { states = { S : 0, X : 1, Y : 2, F : 3 } st = states.S; zac = kon = 0; for (i = 0; i != inp.length; i++) { ch = inp.charAt(i); switch (st) { case states.S: if (ch == "x") { st = states.X; zac = i;} if (ch == "y") { st = states.Y; zac = i;} break; case states.X: if (ch == "y") { st = states.Y; } else if (ch != "x") { st = states.S; } break; case states.Y: if (ch != "y") { kon = i - 1; st = states.F;} break; default: break; }; kon++; if (st == states.F) { st = states.Y; break;} } msg1 = "hledej2(\""+inp+"\") --> x*y+ "; msg3 = "\n"; if (st != states.Y) { msg2 = "nenalezen";} else { msg2 = "nalezen (" + zac + ", " + kon + ")";} return msg1+msg2+msg3; }
Tato, byť na počet řádků delší, ale jednoznačně přehlednější implementace konečného automatu, je přesně to, co mnoho programátorů s úspěchem používá. Je nutné říct, že takto natvrdo
naprogramovaný stroj trpí špatnou rozšiřitelností, ale místo konstrukce switch
case
lze z výhodou použít hashovací pole.
Ovšem i toto řešení trpí malou obecností. Pokud chceme změnit regulární výraz, nezbude nám, než kód přeprogramovat (anebo použít dynamické jazyky a hashovací pole místo konstrukce case
). Ovšem je tu ještě jedna možnost - jiný pohled na konečné automaty a to tabulka přechodů. Prakticky stejně jsou implementovány všechny pomocné knihovny pro konečné automaty.
Stav | S | X | Y |
x | X | X | S |
y | Y | Y | Y |
... |
Ještě než budeme pokračovat, zbývá nám vysvětlit jeden pojem. Deterministický (DKA), versus nedeterministický automat (NKA). U DKA je přechod jednoznačně dán příští stav aktuálním stavem a podmínkou. NKA může mít na jednu podmínku následujících stavů více. Oba automaty jsou ekvivalentní, ale nedeterministické jsou rychlejší, protože nemusí prohledávat všechny možnosti a vyberou si vždy správnou větev. Nevýhodou je, že naše počítače, jak je známe dnes, jsou deterministické, což znamená, že nedeterministické stroje se stejně musejí převést na deterministické. Fragment NKA je zobrazen na následujícím obrázku.
Mluvím o tom z toho důvodu, že běžně používaný algoritmus převádí regulární výrazy právě na NKA. Pokud se narazí na větev, která vede na více možností, program začne prozkoumávat jednotlivé cílové stavy (backtracking). Klasický postup skončí v případě nálezu prvního vyhovujícího výrazu. Posixová varianta v případě použité konstrukce "nebo" najde všechny vyhovující a vrátí nejdelší řetězec, ale tuto variantu běžné nástroje neimplementují, protože je nejpomalejší. Druhou možností je paralelní provádění všech cest, díky čemuž stačí jeden průchod a není třeba se vracet. Nevýhodou je skutečnost, že si nemůžete zapamatovat podvýrazy.
Toto byl pouze lehký úvod do problematiky konečných automatů. Zcela jsem vynechal problematiku stavových akcí, pojmy jako Mealy a Moorův automat. Nemluvili jsme o greedy regulárních výrazech a podobně. Navíc jsem tvorbu stroje pro provádění regulárních výrazů lehce odbyl. Jednak dnešní nástroje obecně regulární výrazy podporují. A v případě, že ne, je nejlepším způsobem jednoduše použít knihovnu PCRE (Perl Compatible Regular Expressions), která je syntakticky i sémanticky kompatibilní s regulárními výrazy Perlu. Což je defakto norma, protože skutečná norma POSIX se používá méně a její regulární výrazy nejsou tolik silné. Tuto knihovnu používají open source projekty Exim (pro nějž byla původně napsána), Apache, PHP, Postfix, nebo KDE.
Pokud chcete automaty vidět
na vlastní oči, podívejte se na Animace Teoretické informatiky, jedná se o flashové animace konečných (DKA i NKA) automatů, převodů NKA na DKA a mnoho dalších zajímavých věcí.
V dalším díle se zvolna přesuneme k problematice překladačů, na řadě je totiž syntaxe.
Nástroje: Tisk bez diskuse
Tiskni Sdílej:
V případě příchodu znaku x se přepne do stavu X a ten neopustí, dokud nenačte znak yV tom případě máš drobnou chybku v obrázku u svislé šipky ze stavu X do Y.
deb http://ftp.cz.debian.org/debian jessie main contrib non-free
deb http://ftp.cz.debian.org/debian jessie main contrib non-free
hledej1("y") --> x*y+ nalezen (0, 1)
To je velmi optimistický výsledek... Nemělo by to na osamocené „y“ mlčet?
Moc pekny clanek, jak funguje grep me vzdycky zajimalo.
Jenom tenhle kus kodu mi prijde nejaky podezrely. javascript neznam, ale misto toho prvniho break bych videl radsi case ;)
break states.Y: if (ch != "y") { kon = i - 1; st = states.F;} break;
ostatně moje implementace pracuje špatněPomohla by pridat pred posledni podminku jeste jednu ?
if ( byloX && !byloY && ch != "y") { byloX = false; zac = 0; kon = 0;}
Dotaz 5: Opravil by muj navrh na pridani podminky tu implementaci ?
Diky moc za pripadne odpovedi a srry za takovou zbesilou tapetu, ale pro lidi co nemaji potrebnou vysokou skolu je dobre, kdyz se i v trivialitach ujisti. Je to lepsi nez stavet na necem co je blbe
To x nad sipkou ze stavu X do Y je samozrejme spatne -- patri tam y (to je to alespon jedno y, ktere tam musi byt kvuli +). NFA je to proto, ze z jednoho stavu vede vice sipek s x. To je ten nedeterminismus. Konecny automat cte ze vstupni pasky jednotliva pismenka a kdyz dorazi do stavu X a zrovna ma cist dalsi pismenko x, tak nevi, kudy ma jit. Pokud by byl ten obrazek spravne (viz vyse), bude ten automat DFA (deterministicky), protoze v zadnem ze stavu neni moznost jit vice jak jednou cestou skrze jeden znak.Njn, pokud je nad sipkou "y" a pokud not(y) znamena cokoliv jineho krome x a y, pak nepovede z jednoho kolecka vice sipek ze stejnym pismenkem => je to spis DKA podle toho co rikas. Pokud ale not(y) zahrnuje i moznost "x" (bezohledu na to, ze tato moznost uz je tam konkretne zminena tou kruhovou sipkou), pak opravdu bude kolecko X s vice stejnymi moznostmi "uniku" a pak je to jednoznacne NKA jak pises. A pokud by byl obrazek spravne tak by opet bylo vice stejnych vetvi s jednoho kolecka a pak by to spis byl NFA ne ? Ted mi teda zbyva otazka, jak je to s tim not(y) v tomto pripade ? PS: jinak ostatni bylo velice pochopitelne napsano, diky :-}