[Powered by Google Translate] [Seminář: Pattern Matching pomocí regulárních výrazů] [John Mussman-Harvard University] [Toto je CS50.-CS50.TV] Dobře. No, vítejte všichni. To je CS50 2012. Jmenuji se John, a já budu mluvit dnes o regulárních výrazech. Regulární výrazy je především nástroj, ale také se někdy používá v kódu aktivně v podstatě odpovídaly vzory a řetězce. Tak tady je to webový komiks od xkcd. V tomto komiksu je záhadné vraždy, kdy vrah má následovala někoho na dovolenou, a protagonisté musí prohledávat 200MB e-mailů, kteří hledají adresu. A oni se chystají vzdát, když někdo, kdo ví, regulární výrazy - pravděpodobně superhrdina - snášení dolů a píše nějaký kód a řeší záhadnou vraždu. Takže zřejmě to bude něco, co bude mít pravomoc dělat Po tomto semináři. My se právě chystá poskytnout stručný úvod do jazyka a dá vám dostatek prostředky jít po více prostředků na vlastní pěst. 

Takže regulární výrazy vypadají v podstatě takhle. To je regulární výraz v Ruby. To není příliš odlišný v různých jazycích. Máme jen na lomítka začít a označte regulární výraz v Ruby. A to je regulární výraz hledat v e-mailové adresy vzoru. Vidíme tedy, na prvním bitem hledá alfanumerické znaky. To je proto, že e-mailové adresy se často musí začínat abecedním znakem. A pak nějaký zvláštní znak následovaný symbolem @. A pak to samé pro název domény. A pak mezi 2 a 4 znaky hledat. Com,. Net, a tak dále. Tak, že je další příklad regulárního výrazu. Takže regulární výrazy jsou protokoly pro zjištění dekory v textu. Dělají porovnání, výběr a nahrazení. Takže Třetí příklad je najít všechna telefonní čísla končící na 54 v adresáři. Takže než potrhaný Davida až na CS50 adresáři můžeme hledat vzor, ​​kde máme závorky pak 3 čísla a pak je konec závorky, 3 další čísla, pomlčka, dvě čísla, a pak 54. A to by v podstatě, jak přijít s regulární výraz pro hledání za to. 

Takže tam jsou - jsme udělali některé věci CS50 které jsou trochu jako regulární výrazy, takže - například - v dictionary.C souboru pro problémové překlepů soubor, který může být použit fscanf číst slovem ze slovníku. A vidíte, procento 45s hledá řetězec 45 znaků. Tak to je něco jako rudimentární regulárního výrazu. A můžete mít nějaké 45 znaky, které budou slušet tam a vybrat ty nahoru. A pak druhý příklad v posledním problému programování pro web nastavit v distro kódu pro PHP jsme vlastně mají jednoduchý regulární výraz. A tohle je prostě chtějí zkontrolovat, zda je webová stránka, která je předán odpovídá buď přihlašte se nebo se zaregistrujte odhlášení. PHP. A pak se vracet true nebo false na základě tohoto porovnávání regulárního výrazu. 

Takže když používáte regulární výraz? Proč jste tady dnes? Takže nechcete použít regulární výraz, když je tu něco, co dělá práci za vás ještě snadněji. Takže XML a HTML jsou vlastně docela složité napsat regulární výrazy pro jak uvidíme za chvíli. Takže tam jsou vyhrazené pro analyzátory těchto jazyků. Také je potřeba být v pořádku s kompromisy a přesnost často. Pokud jste se snaží - a tak jsme viděli regulární výraz na e-mailovou adresu, ale že jste chtěl konkrétní e-mailovou adresu a postupně regulární výraz může být složitější, protože to se stalo přesnější. Tak, že by byl jeden kompromis. Můžete si být jisti, že jste v pořádku, aby se regulární výraz. Pokud přesně víte, co hledáte, by to mohlo dávat větší smysl aby v čase a napsat efektivnější analyzátor. A konečně je zde historický problém s pravidelností výrazů a jazyků. Regulární výrazy jsou ve skutečnosti mnohem silnější než regulární výrazy na řekněme ve formálním smyslu. 

Takže nechci jít příliš daleko do formální teorii, ale většina jazyků, které máme kód ve skutečnosti nejsou pravidelné. A to je důvod, proč se někdy regulární výrazy nejsou považovány za vše, co v bezpečí. Takže v podstatě je Chomského hierarchie jazyků pro jazyky, a regulární výrazy jsou budovány s použitím spojení, zřetězení, a Kleene hvězda operaci, uvidíme za pár minut. Pokud máte zájem o teoreticky tam je docela hodně to tam děje pod kapotou. 

Tak krátkou historií - jen pro kontext zde - pravidelné sady přišel v roce 1950, a pak jsme měli jednoduché editory, které začleněny regulární výrazy - jen vyhledávání řetězce. Grep - což je nástroj pro příkazovou řádku - byl jedním z prvních, velmi populární nástroje, které regulární výrazy obsažené v roce 1960. V 80. letech byla postavena Perl - je programovací jazyk, který obsahuje regulární výrazy velmi nápadně. A pak se v poslední době jsme měli Perl kompatibilní regulární výraz protokoly v podstatě v jiných jazycích, které používají hodně ze stejné syntaxe. Samozřejmě, že byl nejdůležitější událostí v roce 2008 kde byl první národní Regulární výrazy den, které podle mého názoru je červen 1 pokud chcete oslavit. 

Opět platí, že jen trochu víc teorie zde. Takže existuje několik různých způsobů, jak budovat regulární výrazy. Jeden jednoduchý způsob je vytvořit výraz, který hodláte běží na provázku interpretovat - v podstatě postavit malý mini-program, který bude analyzovat kousky provázku a uvidíme, "Oh, to hodí regulární výraz, nebo ne?" A pak spustit to. Takže pokud máte velmi malé regulární výraz, je to pravděpodobně nejúčinnější způsob, jak to udělat. A pak, pokud vás - další možností je, aby rekonstrukce Výraz as you go, a to je možnost simulovat. A tyto první pokusy u regulárních výrazů algoritmy byly poměrně jednoduché a relativně rychle, ale neměl velkou flexibilitu. Takže udělat ještě některé z věcí, které se budeme dívat na dnes jsme museli udělat složitější regulární výraz implementace, které jsou potenciálně mnohem pomaleji, tak to je něco, co je třeba mít na paměti, K dispozici je také pravidelné výrazy popírání útoku odrůdy že využití potenciálu těchto nových implementací regulární výrazy, aby se stal velmi složité. A v podstatě stejném smyslu, jako jsme viděli v útoků buffer overflow, Máte útoky, které pracují tím, že nutí rekurzivní smyčky překročení kapacity paměti. A mimochodem Regexen je jedním z oficiálních plurals regulárního výrazu obdobně na voly v anglosaském. 

Dobře, tak Python Library mnozí z vás osobně se Maců, takže se můžete skutečně vytáhnout to na obrazovce. Regulární výrazy jsou zabudovány do Pythonu. A tak Python je předinstalován na počítači Mac, a také k dispozici online na tomto odkazu. Takže pokud se díváte můžete pozastavit a ujistěte se, že máte Python jak hrajeme tady. K dispozici je manuální online, takže pokud jste jen psát Python do počítače uvidíte, že verze přichází do terminálu. Tak jsem poskytl odkaz manuálu pro verzi 2 Pythonu, stejně jako tahák. K dispozici je verze 3 Pythonu, ale váš Mac, nemusí nutně přišel s tím předem. Takže není příliš odlišný. Dobře, takže některé základy pomocí regulárních výrazů v Pythonu. 

Tak tady jsem použil velmi jednoduchý výraz, tak jsem to udělal Python import re a poté se výsledek re.search. A hledání trvá 2 argumenty. Prvním z nich je regulární výraz, a druhý je text nebo řetězec, který chcete analyzovat. A pak jsem vytisknout na result.group. Takže to jsou dvě základní funkce, které budeme dnes vidět dozvědět se o regulárních výrazech. Takže jen poškodí tento regulární výraz zde h a pak \ w a pak jsem tak \ w právě přijímá jakoukoli abecední znak tam. Tak tady jsme hledali "h" a pak další abecední znak, a poté klávesu m, takže zde by odpovídalo šunka v ", Abraham Lincoln a šunka sendviče." Toto je výsledkem této skupiny. Další věc, kterou můžeme udělat, je využít našich před textových řetězců v jazyce Python. Takže myslím, že budu pokračovat a vytáhnout, že až tady. Python import znovu. A pokud bych měl udělat totéž - řekněme text, "Abraham," pojďme přiblížit - jdeme na to. Text zní: "Abraham jí šunku." Dobře, a pak výsledek = re.search. A pak naše Výraz může být h, a pak to udělám dot m. Takže tečka prostě trvá libovolný znak, který není nový řádek včetně čísel, procentních znaky, něco podobného. A pak textu - boom - a pak result.group--jo. Tak, že je to, jak realizovat základní funkce zde. Pokud bychom měli textovou prsten, který - ten bláznivý textu - včetně říct spoustu zpětných lomítek a řetězce uvnitř a věci, které by mohl vypadat escape sekvencí, pak se pravděpodobně budete chtít používat syrové zadávání textu se ujistit, že je přijat. A to jen vypadá takhle. Takže pokud jsme hledali každý z nich tam bychom neměli nic najít. Ale to je, jak byste je provádět, těsně před řetězec regulární výraz vložíte písmeno R. 

Dobře, tak pojďme dál. Dobře - takže pojďme se podívat na několik opakujících se vzorců zde. Takže jedna věc, kterou chcete udělat, je opakovat věci jak jste prohledávání textu. Takže to následovaným libovolným počtem b - ty ab *. A pak existuje řada dalších pravidel taky. A můžete se podívat ve všech těchto nahoru, budu jen spustit přes některé Nejčastěji používaným ty. Takže ab + je následované libovolnou N větší než 0 z b. ab? je následuje 0 nebo 1 v B. ab {N} je následovaný N b, a tak dále. Máte-li dvě čísla ve složených závorkách jste zadali rozsah který může být případně přizpůsobeny. Takže se podíváme více na několik opakujících se vzorců za minutu. Takže dvě věci mít na paměti při použití těchto nástrojů pro porovnávání vzorků zde. Takže říci, chceme se podívat na HM na "Abraham Lincoln je šunkové sendviče." Tak jsem změnil Abraham Lincoln jméno Abrahamovi. A teď hledáme to, co je vrácená touto funkcí vyhledávání, a to jen vrátí šunka v tomto případě. A to proto, že hledání právě přirozeně má zcela vlevo fronty. A všechny regulární výrazy pokud neurčíte jinak to udělá. Pokud bychom chtěli najít vše, co je funkce, která - najít všechny. Takže mohl vypadat all = re.findall ("h.m", text) a pak all.group (). Všechny produkuje i šunka a šunka, v tomto případě obou řetězců v Abrahamovi každé šunky. Takže to je další možnost. 

Great. Další věc, kterou byste měli mít na paměti, že regulární výrazy se největší intuitivně. Podívejme se na tento příklad. Udělali jsme to zcela vlevo hledat zde, a pak jsem se pokusil o větší hledání pomocí Kleene hvězda operátora. Takže, "Abraham Lincoln dělá šunka sendviče," a mám jen zadní m jako výsledek. Důvodem pro tuto chybu, že jsem mohl vzít libovolný počet h je to proto, že jsem neuvedl nic, co by jít mezi h a m. Jediným příkladem je, že kdyby m - pouze příklady, tam se v ní m a libovolný počet H je byli jen řetězec metrů. Pak jsem to zkusil znovu, řekl jsem: "Dobře, pojďme si aktuální největší skupinu." A pak jsem h.. * M, tak aby právě vrací libovolný počet znaků mezi h a m. A pokud jste právě začínáte a myslí si: "Oh, bude v pořádku, dobře to mi šunku, "je to vlastně vezme vše od h do Abrahama Lincolna celou cestu až do konce šunky. Je to chamtivý, to vidí h - to vše jiný text - m, a to je to, co je potřeba dovnitř Toto je obzvláště pozoruhodné - to je vlastnost, můžeme také specifikovat pro to být chamtivý pomocí jiných funkcí. Ale to je něco, co musíme mít na paměti zejména při pohledu na HTML text, který je jedním z důvodů, které regulární výrazy jsou obtížné pro HTML. Protože pokud máte otevřenou HTML tag a pak spoustu věcí ve středu a některé další HTML uzavřený tag mnohem později v programu, jste právě snědli hodně kódu HTML možná omylem. 

V pořádku - takže další speciální znaky, jako mnoho jiných jazyků, utečeme pomocí lomítka. Takže můžeme použít tečku zadat libovolný znak kromě nového řádku. Můžeme použít únikovou w zadat jakýkoli abecední znak. A obdobně escape d pro nějaké celé číslo - číselné charakter. Můžeme určit - můžeme použít závorky pro určení související výrazy. Takže by to přijmout, b nebo c.. A také můžeme určit, nebo pro některé z možností A nebo B. Například - pokud bychom hledali více možností v závorce můžeme použít operátor OR jako v - takže vraťme se k tomuto příkladu zde. A teď pojďme - vraťme se k tomuto příkladu tady, a pak se ae - takže by to mělo vrátit - myslím, že je to stále Abraham. Takže to - pokud budeme dělat všechno - skvělé. Takže pojďme aktualizovat text. "Abraham jí šunku, zatímco jeho lemování -. Zatímco lemování" Great. Vše. Great. Nyní jsme si šunka, šunka, a lem. Zatímco lemování - při hučení mu - když bzučí na lemu něj. Great. To je totéž. Nyní vše vrací stále jen šunka, šunka a lem bez vyzvednutí na hučení nebo jím. Velký - tak co kdybychom chtěli podívat na jeden, který - a tak bychom mohli také udělat ho nebo - Vrátíme se k tomu. Dobře - tak - v pořádku - na pozicích, můžete také použít stříška nebo znak dolaru určit, že hledáte něco, co na začátku nebo na konci řetězce. Nebo na začátku nebo na konci slova. To je jeden způsob, jak využít to. 

Dobře - tak pojďme hrát s mírně větší blok textu. Řekněme, že tento řádek zde - toto prohlášení zde. Síla regulárního výrazu je to, že můžete zadat vzory nejen pevné postavy. Učiňme - nazvěme tento blok. Pak budeme číst všechno palců A pak - učiňme vše =, takže jaké jsou některé věci, které můžeme vyhledávat sem se ziskem? Mohli bychom hledat výraz ucha. Ne moc zajímavé. Co vy na to? Uvidíme, co se stane. Dal jsem to problém. Takže celá řada věcí, než znovu a všem. Tak, že by se měl vrátit vše od začátku až do všech re možná párkrát. A pak tady máme moc regulárních výrazů je, že Můžete zadat vzory nejsou jen postavy jsou zde. Takže celou cestu až do konečného re, začalo to nejvíce vlevo a byl nenasytný. Podívejme se - co jiného bychom mohli hledat. Myslím, že jedna věc, pokud jste byli zájem hledal zájmena ona a on, můžete zkontrolovat s je rovna 0 nebo 1 a výraz mu, a že se pravděpodobně nebude návratu - oh, myslím, že to vrátil, protože tam jsme se při pohledu na výkon, ten den, tady jsou. Pokusme se upřesňuje, že to má přijít na začátku něčeho. Uvidíme, jestli to klesá. Takže můžeme dělat tuk, a tam jsme se nedostali nic, protože ona a on se nevyskytují v této větě. Great. Dobře - takže zpátky ke kočce zde. Tak složité vzory poškozuje mozek. Takže to je důvod, proč používat regulární výrazy, aby se zabránilo těmto otázkám. 

Takže tady jsou některé další užitečné režimy, které můžete hrát s kolem. Podívali jsme se na hledání dnes, ale můžete také použít zápasu, Split, FindAll a skupiny. Takže další super věci, které můžete dělat s regulárními výrazy kromě právě hledají vzory bere vzor a drží všechny zápasy - jeho proměnné - a pak používat ty v kódu později. To může být docela užitečné. Ostatní věci, by mohlo být počítání. Takže můžeme spočítat počet instancí regulárního výrazu, a to je to, co lze použít pro skupiny. A ostatní druhy a jsou také možné. Tak jsem chtěl mluvit trochu víc o jiných způsobů, jak můžete použít regulární výrazy. 

Takže jeden z aplikací je ve fuzzy shody. Takže pokud hledáte nějaký text projevu, Julius Caesar, a uvidíte jeden Gaius Julius Caesar nebo název Julius Caesar v jiných jazycích, pak budete také chtít přiřadit nějakou váhu těchto hodnot. A pokud je to tak blízko, že - pokud to překročí určitou mez - pak chcete být schopni přijmout Julius Caesar. Takže existuje několik různých implementace pro to, že v několika dalších jazycích. Zde jsou některé další nástroje, Regex pal - šikovný malý app online Zkontrolujte, zda vaše regulární výrazy jsou tvořeny správně. K dispozici jsou také samostatné nástroje, které můžete spustit z počítače jako Ultra Pico, a stejně jako jen kuchařské knihy. Takže pokud děláte projekt, který zahrnuje spoustu regulárních výrazů to je pravděpodobně místo, kam jít mimo rámec dnes. A pak už jen, aby vám pocit, jak je to běžné je grep v Unixu, Perl má vestavěný a C je PCRE pro C. A pak to všechno ostatní jazyky mají také regulární výrazy balíčky které působí podstatě se stejnou syntaxi jsme dostali chuť dnes. PHP, Java, Ruby, a tak dále. 

Google Code Search je ve skutečnosti stojí za zmínku, je to jedna z poměrně málo aplikací tam, že umožňuje veřejnosti přístup k jeho databáze pomocí regulárních výrazů. Takže když se podíváte na Google Code Search najdete kód pokud hledáte pro instanci, jak by být funkce použita, můžete použít regulární výraz najít tuto funkci používán v nejrůznějších různých případů. Můžete se podívat na fwrite, a pak byste se mohli podívat na vlajku číst nebo psát pokud byste chtěli příklad fwrite použitého v tomto případě. Takže totéž tam, a zde jsou některé odkazy. To bude k dispozici on-line, stejně tak jde dopředu v případě Chcete-li se podívejme na Python, Perl, grep - stačí chtít získat nějakou inspiraci nebo chcete-li se podívat více na teorii zde jsou některé dobré Odrazovým místech. Děkuju mnohokrát. [CS50.TV]