Navigace se soukromím CoMaps postavena nad OpenStreetMap je nově k dispozici v Google Play, App Store i F-Droid. Jedná se o komunitní fork aplikace Organic Maps.
Vývojáři OpenMW (Wikipedie) oznámili vydání verze 0.49.0 této svobodné implementace enginu pro hru The Elder Scrolls III: Morrowind. Přehled novinek i s náhledy obrazovek v oznámení o vydání.
Masivní výpadek elektrického proudu zasáhl velkou část České republiky. Hasiči vyjížděli k většímu počtu lidí uvězněných ve výtazích. Výpadek se týkal zejména severozápadu republiky, dotkl se také Prahy, Středočeského nebo Královéhradeckého kraje. Ochromen byl provoz pražské MHD, linky metra se už podařilo obnovit. Výpadek proudu postihl osm rozvoden přenosové soustavy, pět z nich je nyní opět v provozu. Příčina problémů je však stále neznámá. Po 16. hodině zasedne Ústřední krizový štáb.
Po více než roce vývoje od vydání verze 5.40 byla vydána nová stabilní verze 5.42 programovacího jazyka Perl (Wikipedie). Do vývoje se zapojilo 64 vývojářů. Změněno bylo přibližně 280 tisíc řádků v 1 500 souborech. Přehled novinek a změn v podrobném seznamu.
Byla vydána nová stabilní verze 7.5 webového prohlížeče Vivaldi (Wikipedie). Postavena je na Chromiu 138. Přehled novinek i s náhledy v příspěvku na blogu.
Sniffnet je multiplatformní aplikace pro sledování internetového provozu. Ke stažení pro Windows, macOS i Linux. Jedná se o open source software. Zdrojové kódy v programovacím jazyce Rust jsou k dispozici na GitHubu. Vývoj je finančně podporován NLnet Foundation.
Byl vydán Debian Installer Trixie RC 2, tj. druhá RC verze instalátoru Debianu 13 s kódovým názvem Trixie.
Na čem pracují vývojáři webového prohlížeče Ladybird (GitHub)? Byl publikován přehled vývoje za červen (YouTube).
Libreboot (Wikipedie) – svobodný firmware nahrazující proprietární BIOSy, distribuce Corebootu s pravidly pro proprietární bloby – byl vydán ve verzi 25.06 "Luminous Lemon". Přidána byla podpora desek Acer Q45T-AM a Dell Precision T1700 SFF a MT. Současně byl ve verzi 25.06 "Onerous Olive" vydán také Canoeboot, tj. fork Librebootu s ještě přísnějšími pravidly.
Licence GNU GPLv3 o víkendu oslavila 18 let. Oficiálně vyšla 29. června 2007. Při té příležitosti Richard E. Fontana a Bradley M. Kuhn restartovali, oživili a znovu spustili projekt Copyleft-Next s cílem prodiskutovat a navrhnout novou licenci.
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... 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 :-}