[Powered by Google Translate] [Seminár: Pattern Matching pomocou regulárnych výrazov]
[John Mussman-Harvard University]
[Toto je CS50.-CS50.TV]
Dobre. No, vitajte všetci. To je CS50 2012.
Volám sa John, a ja budem hovoriť dnes o regulárnych výrazoch.
Regulárne výrazy je predovšetkým nástroj, ale tiež sa niekedy používa
v kóde aktívne v podstate zodpovedali vzory a reťazca.
Tak tu je to webový komiks od xkcd.
V tomto komikse je záhadné vraždy, kedy vrah má
nasledovala niekoho na dovolenku, a protagonisti musia
prehľadávať 200MB e-mailov, ktorí hľadajú adresu.
A oni sa chystajú vzdať, keď niekto, kto vie, regulárne výrazy -
pravdepodobne superhrdina - znášanie dole a píše nejaký kód
a rieši záhadnú vraždu.
Takže zrejme to bude niečo, čo bude mať právomoc robiť
Po tomto seminári.
My sa práve chystá poskytnúť stručný úvod do jazyka
a dá vám dostatok prostriedky ísť po viac prostriedkov na vlastnú päsť.
>> Takže regulárne výrazy vyzerajú v podstate takhle.
To je regulárny výraz v Ruby.
To nie je príliš odlišný v rôznych jazykoch.
Máme len na lomítka začať a označte regulárny výraz v Ruby.
A to je regulárny výraz hľadať v e-mailovej adresy vzoru.
Vidíme teda, na prvom bitom hľadá alfanumerické znaky.
To je preto, že e-mailovej adresy sa často musí začínať abecedným znakom.
A potom nejaký zvláštny znak nasledovaný symbolom @.
A potom to isté pre názov domény.
A potom medzi 2 a 4 znaky hľadať. Com,. Net, a tak ďalej.
Tak, že je ďalší príklad regulárneho výrazu.
Takže regulárne výrazy sú protokoly pre zistenie dekory v texte.
Robia porovnanie, výber a nahradenie.
Takže Tretí príklad je nájsť všetky telefónne čísla končiace na 54 v adresári.
Takže ako potrhaný Dávida až na CS50 adresári môžeme hľadať
vzor, ​​kde máme zátvorky potom 3 čísla a potom je koniec zátvorky,
3 ďalšie čísla, pomlčka, dve čísla, a potom 54.
A to by v podstate, ako prísť s regulárny výraz pre hľadanie za to.
>> Takže tam sú - sme urobili niektoré veci CS50 ktoré sú trochu ako
regulárne výrazy, takže - napríklad - v dictionary.C súbore
pre problémové preklepov súbor, ktorý môže byť použitý fscanf
čítať slovom zo slovníka.
A vidíte, percento 45s hľadá reťazec 45 znakov.
Tak to je niečo ako rudimentárne regulárneho výrazu.
A môžete mať nejaké 45 znakmi, ktoré pristanú tam
a vybrať tie hore.
A potom druhý príklad v poslednom probléme programovanie pre web
nastaviť v distro kódu pre PHP sme vlastne majú jednoduchý regulárny výraz.
A toto je jednoducho chcú skontrolovať, či je webová stránka, ktorá je odovzdaný
zodpovedá buď prihláste sa alebo sa zaregistrujte odhlásenia. PHP.
A potom sa vracať true alebo false na základe tohto porovnávania regulárneho výrazu.
>> Takže keď používate regulárny výraz?
Prečo ste tu dnes?
Takže nechcete použiť regulárny výraz, keď je tu niečo, čo
robí prácu za vás ešte ľahšie.
Takže XML a HTML sú vlastne celkom zložité
napísať regulárne výrazy pre ako uvidíme za chvíľu.
Takže tam sú vyhradené pre analyzátory týchto jazykov.
Tiež je potrebné byť v poriadku s kompromismi a presnosť často.
Ak ste sa snaží - a tak sme videli regulárny výraz na e-mailovú adresu,
ale že ste chcel konkrétnu e-mailovú adresu a postupne
regulárny výraz môže byť zložitejšie, pretože to sa stalo presnejšie.
Tak, že by bol jeden kompromis.
Môžete si byť istí, že ste v poriadku, aby sa regulárny výraz.
Ak presne viete, čo hľadáte, by to mohlo dávať väčší zmysel
aby v čase a napísať efektívnejšie analyzátor.
A konečne je tu historický problém s pravidelnosťou
výrazov a jazykov.
Regulárne výrazy sú v skutočnosti oveľa silnejšie ako
regulárne výrazy na povedzme vo formálnom zmysle.
>> Takže nechcem ísť príliš ďaleko do formálnej teóriu,
ale väčšina jazykov, ktoré máme kód v skutočnosti nie sú pravidelné.
A to je dôvod, prečo sa niekedy regulárne výrazy nie sú považované za všetko, čo v bezpečí.
Takže v podstate je Chomského hierarchia jazykov pre jazyky,
a regulárne výrazy sú budované s použitím spojenia, zreťazenie,
a Kleene hviezda operáciu, uvidíme za pár minút.
Pokiaľ máte záujem o teoreticky tam je celkom veľa to tam deje pod kapotou.
>> Tak krátkou históriou - len pre kontext tu - pravidelné sady prišiel
v roku 1950, a potom sme mali jednoduché editory, ktoré
začlenené regulárne výrazy - len vyhľadávanie reťazca.
Grep - čo je nástroj pre príkazový riadok - bol jedným z prvých,
veľmi populárne nástroje, ktoré regulárne výrazy obsiahnuté v roku 1960.
V 80. rokoch bola postavená Perl - je programovací jazyk, ktorý
obsahuje regulárne výrazy veľmi nápadne.
A potom sa v poslednej dobe sme mali Perl kompatibilný regulárny výraz
protokoly v podstate v iných jazykoch, ktoré používajú veľa z rovnakého syntaxe.
Samozrejme, že bol najdôležitejšou udalosťou v roku 2008
kde bol prvý národný Regulárne výrazy deň,
ktoré podľa môjho názoru je jún 1 ak chcete osláviť.
>> Opäť platí, že len trochu viac teórie tu.
Takže existuje niekoľko rôznych spôsobov, ako budovať regulárne výrazy.
Jeden jednoduchý spôsob je vytvoriť výraz, ktorý hodláte
beží na povrázku interpretovať - ​​v podstate postaviť malý mini-program, ktorý
bude analyzovať kúsky špagátu a uvidíme, "Oh, to hodí regulárny výraz, alebo nie?"
A potom spustiť to.
Takže ak máte veľmi malé regulárny výraz, je to pravdepodobne
najúčinnejší spôsob, ako to urobiť.
A potom, ak vás - ďalšou možnosťou je, aby rekonštrukcia
Výraz as you go, a to je možnosť simulovať.
A tieto prvé pokusy u regulárnych výrazov algoritmy boli
pomerne jednoduché a relatívne rýchlo, ale nemal veľkú flexibilitu.
Takže urobiť ešte niektoré veci, ktoré sa budeme pozerať na
dnes sme museli urobiť zložitejšie regulárny výraz
implementácie, ktoré sú potenciálne oveľa pomalšie, tak to je niečo, čo je potrebné mať na pamäti,
K dispozícii je tiež pravidelné výrazy popieranie útoku odrody
že využitie potenciálu týchto nových implementácií
regulárne výrazy, aby sa stal veľmi zložité.
A v podstate v rovnakom zmysle, ako sme videli v útoky buffer overflow,
Máte útoky, ktoré pracujú tým, že núti rekurzívne slučky
prekročení kapacity pamäte.
A mimochodom Regexen je jedným z oficiálnych plurals regulárneho výrazu
obdobne na voly v anglosaskom.
>> Dobre, tak Python Library mnohí z vás osobne sa Macu,
takže sa môžete skutočne vytiahnuť to na obrazovke.
Regulárne výrazy sú zabudované do Pythone.
A tak Python je predinštalovaný na počítači Mac, a tiež k dispozícii online na tomto odkaze.
Takže ak sa pozeráte môžete pozastaviť a uistite sa, že máte Python
ako hráme tu.
K dispozícii je manuálny online, takže ak ste len písať Python do počítača
uvidíte, že verzia prichádza do terminálu.
Tak som poskytol odkaz manuálu pre verziu 2 Pythone, rovnako ako ťahák.
K dispozícii je verzia 3 Pythone, ale váš Mac, nemusí nutne
prišiel s tým vopred.
Takže nie je príliš odlišný.
Dobre, takže niektoré základy pomocou regulárnych výrazov v Pythone.
>> Tak tu som použil veľmi jednoduchý výraz, tak som to urobil Python import re
a potom sa výsledok re.search.
A hľadanie trvá 2 argumenty.
Prvým z nich je regulárny výraz, a druhý je text
alebo reťazec, ktorý chcete analyzovať.
A potom som vytlačiť na result.group.
Takže to sú dve základné funkcie, ktoré budeme dnes vidieť
dozvedieť sa o regulárnych výrazoch.
Takže len poškodí tento regulárny výraz tu
h a potom \ w a potom som tak \ w práve prijíma akúkoľvek abecedný znak tam.
Tak tu sme hľadali "h" a potom ďalšie abecedný znak,
a potom kláves m, takže tu by zodpovedalo šunka
v ", Abraham Lincoln a šunka sendviče."
Toto je výsledkom tejto skupiny.
Ďalšia vec, ktorú môžeme urobiť, je využiť našich pred textových reťazcov v jazyku Python.
Takže myslím, že budem pokračovať a vytiahnuť, že až tu.
Python import znova.
A ak by som mal urobiť to isté - povedzme text,
"Abrahám," poďme priblížiť - ideme na to.
Text znie: "Abrahám jej šunku."
Dobre, a potom výsledok = re.search.
A potom naše Výraz môže byť h, a potom to urobím dot m
Takže bodka jednoducho trvá ľubovoľný znak, ktorý nie je nový riadok vrátane čísel,
percentuálnych znaky, niečo podobné.
A potom texte - boom - a potom result.group--jo.
Tak, že je to, ako realizovať základné funkcie tu.
Ak by sme mali textovú prsteň, ktorý - ten bláznivý texte - vrátane povedať veľa spätných lomítok
a reťazca vnútri a veci, ktoré by mohol vyzerať escape sekvencií,
potom sa pravdepodobne budete chcieť používať surové zadávanie textu, aby sa ubezpečil, že je prijatý.
A to len vyzerá takto.
Takže ak sme hľadali každý z nich tam by sme nemali nič nájsť.
Ale to je, ako by ste ich vykonávať, tesne pred reťazec
regulárny výraz vložíte písmeno R.
>> Dobre, tak poďme ďalej.
Dobre - takže poďme sa pozrieť na niekoľko opakujúcich sa vzorcov tu.
Takže jedna vec, ktorú chcete urobiť, je opakovať veci
ako ste prehľadávanie textu.
Takže to nasledovaným ľubovoľným počtom b - ty ab *.
A potom existuje rad ďalších pravidiel taky.
A môžete sa pozrieť vo všetkých týchto hore, budem len spustiť cez niektoré
Najčastejšie používaným ty.
Takže ab + je nasledované ľubovoľnú N väčšie ako 0 z b
ab? je nasleduje 0 alebo 1 v B.
ab {N} je nasledovaný N b, a tak ďalej.
Ak máte dve čísla v zložených zátvorkách ste zadali rozsah
ktorý môže podľa potreby prispôsobiť.
Takže sa pozrieme viac na niekoľko opakujúcich sa vzorcov za minútu.
Takže dve veci mať na pamäti pri použití týchto nástrojov pre porovnávanie vzoriek tu.
Takže povedať, chceme sa pozrieť na HM na "Abraham Lincoln je šunkové sendviče."
Tak som zmenil Abraham Lincoln meno Abrahámovi.
A teraz hľadáme to, čo je vrátená touto funkciou vyhľadávania,
a to len vráti šunka v tomto prípade.
A to preto, že hľadanie práve prirodzene má úplne vľavo fronty.
A všetky regulárne výrazy ak neurčíte inak to urobí.
Ak by sme chceli nájsť všetko, čo je funkcia, ktorá - nájsť všetky.
Takže mohol vyzerať all = re.findall ("h.m", text)
a potom all.group ().
Všetky produkuje aj šunka a šunka, v tomto prípade oboch reťazcov v Abrahámovi každej šunky.
Takže to je ďalšia možnosť.
>> Skvelé. Ďalšia vec, ktorú by ste mali mať na pamäti, že regulárne výrazy sa najväčšie intuitívne.
Pozrime sa na tento príklad.
Urobili sme to úplne vľavo hľadať tu, a potom som sa pokúsil o väčšie hľadanie
pomocou Kleene hviezda operátora.
Takže, "Abraham Lincoln robí šunka sendviče," a mám len zadnú
m ako výsledok.
Dôvodom pre túto chybu, že som mohol vziať ľubovoľný počet
h je to preto, že som neuviedol nič, čo by ísť medzi h a m
Jediným príkladom je, že keby m - len príklady, tam sa v nej m
a ľubovoľný počet H je boli len reťazec metrov.
Potom som to skúsil znova, povedal som: "Dobre, poďme si aktuálne najväčšiu skupinu."
A potom som h. * M, tak aby práve vracia ľubovoľný počet znakov medzi h a m
A ak ste práve začínate a myslí si: "Oh, bude v poriadku, dobre to
mi šunku, "je to vlastne vezme všetko od h do Abrahama Lincolna
celú cestu až do konca šunky.
Je to chamtivý, to vidí h - to všetko iný text - m,
a to je to, čo je potreba dovnútra
Toto je obzvlášť pozoruhodné - to je vlastnosť, môžeme tiež
špecifikovať pre to byť chamtivý pomocou iných funkcií.
Ale to je niečo, čo musíme mať na pamäti najmä
pri pohľade na HTML text, ktorý je jedným z dôvodov, ktoré
regulárne výrazy sú ťažké pre HTML.
Pretože ak máte otvorenú HTML tag a potom veľa vecí v stredu
a niektoré ďalšie HTML uzavretý tag oveľa neskôr v programe,
ste práve zjedli veľa kódu HTML možná omylom.
>> V poriadku - takže ďalšie špeciálne znaky, ako mnoho iných jazykov,
utečieme pomocou lomítka.
Takže môžeme použiť bodku zadať ľubovoľný znak okrem nového riadku.
Môžeme použiť únikovú w zadať akýkoľvek abecedný znak.
A obdobne escape d pre nejaké celé číslo - číselné charakter.
Môžeme určiť - môžeme použiť zátvorky pre určenie súvisiace výrazy.
Takže by to prijať, b alebo c.
A tiež môžeme určiť, alebo pre niektoré z možností A alebo B.
Napríklad - ak by sme hľadali viac možností
v zátvorke môžeme použiť operátor OR ako v -
takže vráťme sa k tomuto príkladu tu.
A teraz poďme - vráťme sa k tomuto príkladu tu, a potom
sa ae - takže by to malo vrátiť - myslím, že je to stále Abrahám.
Takže to - ak budeme robiť všetko - skvelé.
Takže poďme aktualizovať text.
"Abrahám jej šunku, zatiaľ čo jeho lemovanie -. Kým lemovanie" Skvelé.
Všetko. Skvelé. Teraz sme si šunka, šunka, a lem.
Kým lemovanie - pri hučaní mu - keď bzučí na leme neho. Skvelé.
To je to isté.
Teraz všetko vracia stále len šunka, šunka a lem bez vyzdvihnutie na hučanie alebo ním.
Veľký - tak čo keby sme chceli pozrieť na jeden, ktorý - a tak by sme mohli tiež urobiť
ho alebo - Vrátime sa k tomu.
Dobre - tak - v poriadku - na pozíciách, môžete tiež použiť strieška alebo znak dolára
určiť, že hľadáte niečo, čo na začiatku alebo na konci reťazca.
Alebo na začiatku alebo na konci slova.
To je jeden spôsob, ako využiť to.
>> Dobre - tak poďme hrať s mierne väčšou blok textu.
Povedzme, že tento riadok tu - toto vyhlásenie tu.
Sila regulárneho výrazu je to, že môžete zadať vzory
nielen pevné postavy.
Urobme - nazvime tento blok.
Potom budeme čítať všetko palcov
A potom - urobme všetko =, takže aké sú niektoré veci, ktoré môžeme vyhľadávať sem so ziskom?
Mohli by sme hľadať výraz ucha.
Nie moc zaujímavé. Čo vy na to? Uvidíme, čo sa stane.
Dal som to problém.
Takže celá rada vecí, než znova a všetkým.
Tak, že by sa mal vrátiť všetko od začiatku až do všetkých re možná párkrát.
A potom tu máme moc regulárnych výrazov je, že
Môžete zadať vzory nie sú len postavy sú tu.
Takže celú cestu až do konečného re, začalo to najviac vľavo a bol nenásytný.
Pozrime sa - čo iného by sme mohli hľadať.
Myslím, že jedna vec, ak ste boli záujem hľadal zámená ona a on,
môžete skontrolovať s je rovná 0 alebo 1
a výraz mu, a že sa pravdepodobne nebude návratu -
oh, myslím, že to vrátil, pretože tam sme sa pri pohľade na výkon, ten deň, tu sú.
Pokúsme sa upresňuje, že to má prísť na začiatku niečoho.
Uvidíme, či to klesá.
Takže môžeme robiť tuk, a tam sme sa nedostali nič, pretože ona a on
sa nevyskytujú v tejto vete.
Skvelé. Dobre - takže späť ku mačke tu.
Tak zložité vzory poškodzuje mozog.
Takže to je dôvod, prečo používať regulárne výrazy, aby sa zabránilo týmto otázkam.
>> Takže tu sú niektoré ďalšie užitočné režimy, ktoré môžete hrať s okolo.
Pozreli sme sa na hľadanie dnes, ale môžete tiež použiť zápasu, Split, findall a skupiny.
Takže ďalšie super veci, ktoré môžete robiť s regulárnymi výrazmi okrem práve
hľadajú vzory berie vzor a drží všetky zápasy -
jeho premenné - a potom používať tie v kóde neskôr.
To môže byť celkom užitočné. Ostatné veci, by mohlo byť počítanie.
Takže môžeme spočítať počet inštancií regulárneho výrazu,
a to je to, čo sa dá použiť pre skupiny.
A ostatné druhy a sú tiež možné.
Tak som chcel hovoriť trochu viac o iných spôsobov, ako môžete použiť regulárne výrazy.
>> Takže jeden z aplikácií je vo fuzzy zhody.
Takže ak hľadáte nejaký text prejavu, Julius Caesar,
a uvidíte jeden Gaius Julius Caesar alebo názov Julius Caesar v iných jazykoch,
potom budete tiež chcieť priradiť nejakú váhu týchto hodnôt.
A ak je to tak blízko, že - ak to prekročí určitú hranicu - potom chcete
byť schopní prijať Julius Caesar.
Takže existuje niekoľko rôznych implementácia pre to, že v niekoľkých ďalších jazykoch.
Tu sú niektoré ďalšie nástroje, Regex pal - šikovný malý app online
Skontrolujte, či vaše regulárne výrazy sú tvorené správne.
K dispozícii sú aj samostatné nástroje, ktoré môžete spustiť z počítača
ako Ultra Pico, a rovnako ako len kuchárske knihy.
Takže ak robíte projekt, ktorý zahŕňa veľa regulárnych výrazov
to je pravdepodobne miesto, kam ísť mimo rámec dnes.
A potom už len, aby vám pocit, ako je to bežné
je grep v Unixe, Perl má vstavaný a C je PCRE pre C.
A potom to všetko ostatné jazyky majú tiež regulárne výrazy balíčky
ktoré pôsobia podstate s rovnakou syntax sme dostali chuť dnes.
PHP, Java, Ruby, a tak ďalej.
>> Google Code Search je v skutočnosti stojí za zmienku, je to jedna z
pomerne málo aplikácií tam, že umožňuje verejnosti prístup k
jeho databázy pomocou regulárnych výrazov.
Takže keď sa pozriete na Google Code Search nájdete kód
ak hľadáte pre inštanciu, ako by byť funkcia použitá,
môžete použiť regulárny výraz nájsť túto funkciu používaný v najrôznejších rôznych prípadov.
Môžete sa pozrieť na fwrite, a potom by ste sa mohli pozrieť na vlajku čítať alebo písať
ak by ste chceli príklad fwrite použitého v tomto prípade.
Takže to isté tam, a tu sú niektoré odkazy.
To bude k dispozícii on-line, rovnako tak ide dopredu v prípade
Ak chcete sa pozrime na Python, Perl, grep - stačí chcieť získať nejakú inšpiráciu
alebo ak sa chcete pozrieť viac na teórii tu sú niektoré dobré Odrazovým miestach.
Ďakujem mnohokrát.
[CS50.TV]