[Powered by Google Translate] [Seminar: Pattern Matching Regulaaravaldised] [John Mussman-Harvard University] [See on CS50.-CS50.TV] Okei. Noh, tere tulemast kõigile. See on CS50 2012. Minu nimi on John ja ma siis räägime täna regulaaravaldiste. Regulaaravaldisi on eelkõige vahend, kuid mõnikord ka kasutatud koodi aktiivselt sisuliselt mustrina ja stringe. Nii et siin on web comic XKCD. In koomiline on müsteerium, kui tapja on millele keegi puhkusel ja peategelased on Otsige 200 megabaiti e-kirju otsivad aadress. Ja nad on umbes loobuma, kui keegi, kes teab, regulaaravaldiste - arvatavasti superkangelane - swoops maha ja kirjutab mõned kood ja lahendab müsteerium. Nii ilmselt, et on midagi, mida saab anda volitused teha pärast seda seminar. Me lihtsalt läheb annavad põhjaliku sissejuhatuse keel ja annab sulle piisavalt teabeta minna pärast rohkem ressursse oma. 

Nii regulaaravaldiste vaadata põhimõtteliselt niimoodi. See on regulaaravaldise Ruby. See ei ole väga erinev üle keelte. Peame lihtsalt edasi kaldkriipsud alustada ja tähistada regulaaravaldise Ruby. Ja see on regulaaravaldis otsima email muster. Nii näeme esimese natuke välja iga tähtnumbriline märk. Seda seetõttu, et e-posti aadressid on sageli alustada tähemärk. Ja siis mõni erimärk järgneb @ sümbol. Ja siis sama domeeninime. Ja siis 2 kuni 4 märki otsima. Com,. Net, ja nii edasi. Nii et on veel üks näide regulaaravaldis. Nii Regulaaravaldisi protokollide leidmiseks patters teksti. Nad teevad võrdlusi, valikud ja asendused. Nii Kolmas näide on leida kõik telefoninumbrid lõpeb 54 kataloogi. Nii et enne David rebib up CS50 kataloog võiksime otsida muster, kus meil on sulgudes, siis 3 arvu siis lõpuks sulgudes 3 rohkem numbreid, kriips, 2 numbrit, seejärel 54. Ja see oleks sisuliselt kuidas me tulla regulaaravaldis otsida seda. 

Seega on olemas - me oleme teinud mõningaid asju CS50, mis on natuke nagu regulaaravaldiste, et - näiteks - on dictionary.C fail jaoks õigekirja kontroll lahendamist, mida olete kasutanud fscanf lugeda sõna sõnaraamatust. Ja näete protsent 45s otsib string 45 tähemärki. Nii et see on pisut nagu algeline regulaaravaldis. Ja sul võib olla iga 45 märki, mis sobivad arve seal ja korja need üles. Ja siis teine ​​näide viimaste veebi programmeerimine probleem sätestatud distro kood php me tegelikult teha on lihtne regulaaravaldis. Ja see on vaid lihtsalt otsivad kontrollida, kas veebileht, mis on vastu võetud sobib kas login või logout registreeru. PHP. Ja siis jälle õige või vale põhineb sellel regulaaravaldise sobitamine. 

Nii et kui te kasutate regulaaravaldis? Miks sa siin oled täna? Nii et sa ei taha kasutada regulaaravaldiste, kui seal on midagi, mis ei töö teile isegi kergemini. Nii XML ja HTML on tegelikult üsna keeruline kirjutada regulaaravaldise kui näeme natuke. Seega on pühendatud parsereid nendest keeltest. Samuti peate olema okei kompromisse ja täpsus sageli. Kui sa üritad - nii nägime regulaaravaldis e-posti aadress, kuid öelda tahtsid konkreetse e-posti aadress ja järk-järgult regulaaravaldis võib muutuda keerulisemaks, kuna see sai täpsemaks. Nii et oleks üks kompromiss. Sa pead olema kindel, et teil on kõik korras tegemises regulaaravaldise. Kui tead täpselt, mida te otsite siis võib mõttekam et panna aega ja kirjutada tõhusam parser. Ja lõpuks on ajalooline küsimus korrektsuse väljendite ja keeltes. Regulaaravaldisi tegelikult palju võimsam kui regulaaravaldiste kohta öelda formaalses mõttes. 

Nii et ma ei taha minna liiga kaugele ametliku teooria, kuid enamik keeli et me koodi tegelikult ei ole korrektsed. Ja see on põhjus, miks regulaaravaldiste mõnikord ei peeta kõik, et turvaline. Nii et põhimõtteliselt on Chomsky hierarhia keeles ja regulaaravaldiste on ehitada kasutades Liit ahel, ja Kleene star operatsiooni, et me näeme mõne minuti. Kui olete huvitatud teooria on üsna palju toimub seal kapoti all. 

Nii lühike ajalugu - just seoses siin - regulaarne komplekti tulid 1950 ja siis oli meil lihtne toimetajad, et lisatud regulaaravaldiste - lihtsalt otsivad stringe. Grep - mis on käsurea vahend - oli üks esimesi väga populaarne tööriistu, mis sisalduvad regulaaravaldiste 1960. 80-ndatel, Perl ehitati - on programmeerimiskeel, mis sisaldab regulaaravaldiste väga nähtavalt. Ja siis veel viimasel ajal oleme olnud Perl sobib regulaaravaldis protokollid põhiliselt teistes keeltes, mis kasutavad palju sama süntaksit. Muidugi kõige olulisem sündmus oli 2008 kus oli esimene riiklik Regulaaravaldised Day, mis minu arvates on 1. juuni, kui soovite, et tähistada. 

Jällegi, lihtsalt natuke rohkem teooria siin. Seega on paar erinevat võimalust ehitamise regulaaravaldiste. Üks lihtne viis on ehitada väljend, et te ei kavatse sõitma string tõlgendama - põhimõtteliselt ehitada väike mini-programm, mis analüüsib tükki string ja vaata, "Oh, kas see sobib regulaaravaldis või mitte?" Ja seejärel käivitage see. Nii et kui teil on väga väike regulaaravaldise, on see tõenäoliselt Kõige tõhusam viis seda teha. Ja siis, kui sa - teine ​​võimalus on hoida rekonstrueerimiseks väljend lähete ja see on simuleerida võimalus. Ja need varased katsed regulaaravaldise algoritmid suhteliselt lihtne ja suhteliselt kiire, kuid ei olnud palju paindlikkust. Niisiis, mida teha isegi mõned asjad, mida me ei kavatse vaadata täna oleme pidanud tegema keerulisem regulaaravaldis rakendusi, mis on potentsiaalselt palju aeglasem, nii et see on midagi meeles pidada Seal on ka regulaaravaldiste keelamise rünnak erinevaid et kasutada ära nende uuemate rakendustega regulaaravaldiste muutunud väga keeruliseks. Ja sama palju tunde, et me nägime buffer overflow rünnakud, teil on rünnakute et tööd tehes rekursiivne silmuseid, mis ületatud mälumahuga. Ja muide Regexen on üks ametlik mitmus regulaaravaldise analoogia härjad on anglosaksi. 

Okei, nii et Python Library paljud teist siin isiklikult on Mac, nii et saate tegelikult tõmmake see üles ekraanil. Regulaaravaldisi ehitatud Python. Ja nii Python on eelsalvestatud Mac ja saadaval ka internetis aadressil seda linki. Nii et kui sa vaatad saate peatada ja veenduge, et olete Python kui me mängime siin. On manuaal online, nii et kui sa lihtsalt kirjutada Python arvuti näed, et versioon kerkib terminal. Nii et ma ette link käsiraamatu 2. versioon Python samuti petma lehte. On Version 3 Python, kuid Mac ei pruugi tulla, et peale keeratud. Seega ei ole väga erinev. Okei, nii et mõned põhitõdesid Regulaaravaldises Python. 

Nii et siin ma kasutasin väga lihtne väljend, nii et ma tegin Python import re ja siis võttis tulemus re.search. Ja otsing kestab 2 argumendid. Esimene on regulaaravaldis, ja teine ​​on tekst või string soovite analüüsida. Ja siis ma välja printida result.group. Nii et need on 2 põhifunktsiooni me näeme täna tundmaõppimisel regulaaravaldiste. Nii lihtsalt kui lagundada see regulaaravaldise siin h ja siis \ w ja siis olen nii \ w lihtsalt endale mingit täht seal. Nii et siin me otsime "h" ja siis teine ​​tähemärk ja siis m, nii siin, mis vastaks sink aastal, "Abraham Lincoln ja singi võileibu." See on tulemus, et grupp. Teine asi, mida me saame teha, on kasutada meie enne stringide teksti Python. Nii et ma arvan, et ma minna ja tõmmake see siin. Python import re. Ja kui ma seda sama asja - ütleme tekst on "Abraham" olgem suurendamiseks - seal me läheme. Tekst on "Abraham sööb sinki." Okei, ja siis tulemuseks = re.search. Ja siis meie väljend võib olla h, ja siis ma teen dot m. Nii dot lihtsalt võtab iga märk, mis ei ole uus liin sealhulgas numbrite protsent märke, midagi sellist. Ja siis tekst - buum - ja siis result.group--jah. Nii et on, kuidas rakendada põhifunktsioonide siin. Kui meil oleks tekst ring, et - et hull tekst - ka öelda palju kaldkriipsud ja stringid sees ja asju, mis võivad tunduda paojadade, siis me ilmselt tahad kasutada toores tekstisisestus veenduda, et on vastu võetud. Ja see ainult tundub nii. Nii et kui me otsisime igaüks sinna me ei peaks midagi leida. Aga see, kuidas sa seda rakendada vaid enne string regulaaravaldise paned kirja r. 

Okei, nii et andke meile edasi. Olgu - nii look paar korduvad mustrid siin. Nii et üks asi, mida sa tahad teha, on korrata asju kui otsite läbi teksti. Niisiis, mida teha, millele järgneb mis tahes arvu b - sa ab *. Ja siis on hulk teisi reegleid ka. Ja saab vaadata kõiki neid üles, ma lihtsalt joosta mõned Levinuim ones. Nii ab + on järgne N on suurem kui 0 ja b. ab? on järgneb 0 või 1 b. ab {N} on järgnevad N b, ja siis nii edasi. Kui teil on 2 numbrit looksulg olete täpsustatakse valik et võib olla võimalik sobitada. Nii me vaatame rohkem paar korduvad mustrid minut. Nii 2 asjad meeles pidada, kui kasutate neid mustrite tööriistu siin. Nii ütleme me tahame vaadata hm kohta, "Abraham Lincoln muudab singi võileibu." Nii ma muutsin Abraham Lincolni nime Abraham. Ja nüüd me otsime mis tagastatakse selle otsingu funktsiooni, ja see annab ainult singi käesolevas asjas. Ja see, et kuna otsing vaid loomulikult võtab vasakul kõige järjekorda. Ja kõik regulaaravaldiste kui te pole teisiti teen seda. Kui me tahame leida kõik seal on funktsioon, et - kõik. Nii et võiks lihtsalt nägema kõiki = re.findall (h.m ", tekst) ja siis all.group (). Kõik toodab nii sink ja sink, sel juhul on mõlemad stringid Abraham iga sink. Nii et on veel üks võimalus. 

Suur. Teine asi, mida meeles pidada on see, et regulaaravaldiste Võtke suurim intuitiivselt. Vaadakem seda näiteks. Me tegime seda vasakul kõige otsing siin ja siis ma proovisin suuremat otsing kasutades Kleene star operaator. Nii, "Abraham Lincoln muudab singi võileibu," ja sain ainult tagasi m tulemusena. Selle põhjuseks viga oli, et ma oleks võtnud mitmeid h, sest ma ei täpsustanud midagi minna vahel h ja m. Ainus näide olemas, mis oli m - ainult näiteid seal m see ja mis tahes arv h on olnud lihtsalt string m. Siis ma püüdsin seda uuesti, ma ütlesin: "Okei, olgem saada tegelik suurim rühm siin." Ja siis ma tegin h. * M, nii et lihtsalt tagastab suvalise arvu märkide vahel h ja m. Ja kui te olete hakanud just läbi ja mõtlesin: "Oh, okei, noh see mulle sinki, "see tegelikult võtab kõike h Abraham Lincoln kõik viis kuni lõpuni sink. See on ahne, ta näeb h - kõik see muu teksti - m, ja see on, mida ta võtab sisse See on eriti äärmuslikud - see on omadus, saame ka täpsustada see ole ahne kasutades muid funktsioone. Aga see on midagi, mida me peame meeles pidama, eriti vaadeldes HTML tekst, mis on üks põhjus, et regulaaravaldiste on raske HTML. Sest kui sul on HTML avatud tag ja siis palju kraami keskel ja siis mõne muu HTML suletud tag palju hiljem programmi te olete just söönud kuni palju oma HTML kood võib kogemata. 

Olgu - nii rohkem erimärke nagu paljudes teistes keeltes, me põgeneda kasutades kaldkriipsuga. Nii saame kasutada dot määrata iga märk, välja arvatud uus liin. Saame kasutada põgeneda w täpsustada iga tähemärk. Ja analoogia põgeneda d iga täisarv - numbriline iseloomu. Saame määrata - saame kasutada sulgudes täpsustada seotud väljendid. Nii, et see oleks valmis vastu võtma, b, või c. Ja me saame ka määrata või võimalusi a või b. Näiteks - kui otsisime mitu võimalikku Sulgudes saaksime kasutada või käitaja in - nii mingem tagasi selle näide. Ja nüüd võtkem - mingem tagasi selle näite siin ja siis võta ae - nii et see peaks tagasi - ma arvan, et see on ikka Abraham. Nii et see - kui me kõik - suurepärane. Tehkem teksti ajakohastada siin. "Abraham sööb singi samas palistamiseks tema - kuigi hemming." Suur. Kõik. Suur. Nüüd saame sink, sink ja hem. Kuigi hemming - kui koolibrid temale - kuigi koolibrid hem teda. Suur. Sama asi. Nüüd naaseb ikka lihtsalt sink, sink ja hem ilma pealevõtmine hum või teda. Great - mis siis, kui me tahtsime vaadata ka seda, et - nii et me võiks teha ka teda - me tuleme tagasi, et. Olgu - nii - kõik õige - ametikohtadel võid kasutada ka kelku või dollari märk täpsustada, et te otsite midagi alguses või lõpus stringi. Või algust või sõna lõpus. See on üks viis, kuidas seda kasutada. 

Olgu - nii meile mängida veidi suurem tekstilõik. Öelgem seda rida siin - see väide siin. Võimu regulaaravaldis on, et nad võivad määrata mustrid mitte ainult fikseeritud tähemärki. Tehkem - olgem nimetame seda blokeerida. Siis me lugeda kõik, et sisse Ja siis on - tehkem kõik =; Millised on mõned asjad, mida me võiks otsida siin kasumlikult? Me võiks otsida väljendit kõrva. Mitte väga huvitav. Kuidas nii? Eks me näe, mis juhtub. Ma andsin talle probleem. Nii tahes mitmeid asju enne uuesti ja kõik. Nii et peaks tagasi kõik algusest peale kuni kõik uuesti ehk paar korda. Ja siis on meil siin võimu regulaaravaldiste on, et nad saab määrata mustrid mitte ainult tegelased on siin. Nii et kõik viis kuni lõpliku re, see algas vasakul kõige ja oli ahne. Saame näha - Mida võiks veel otsida. Ma arvan, et üks asi, kui sa olid huvitatud otsivad asesõnad ta ja ta, võid kontrollida s on võrdne 0 või 1 ja väljendus ta, ja see on ilmselt ei kavatse naasta - Oh, ma arvan, et see tagastatakse tema, sest seal me praegu võime, et päev, siin on. Püüdkem täpsustades, et see peab tulema alguses midagi. Saame näha, kas see langeb välja. Nii et me saame teha rasva, ja seal me ei saa midagi, sest tema ja ta ei esine seda fraasi. Suur. Olgu - nii tagasi kass siin. Nii keeruline mustrid on haiget aju. Nii et on põhjus, miks me kasutame regulaaravaldiste vältida neid küsimusi. 

Nii et siin on mõned muud kasulikku režiimid saab mängida. Vaatasime otsingu täna, kuid võid kasutada ka mängu, split, findall ja rühmad. Nii teiste lahedaid asju saab teha regulaaravaldiste peale lihtsalt otsin mustreid astub muster ja hoides kõik kohtumised - oma muutujate - ja siis kasutades neid oma koodi hiljem. See võib olla üsna kasulik. Muud asjad võiks lugedes. Nii saame loota arvul regulaaravaldise, ja see on see, mida me saame kasutada rühmad. Ja muude transpordiliikide samuti on ka võimalik. Nii et ma tahan rääkida natuke rohkem muid võimalusi, mida saab kasutada regulaaravaldiste. 

Nii et üks rohkem arenenud taotlus on udune sobitamine. Nii et kui te otsite teksti väljend, Julius Caesar, ja sa näed kas Gaius Julius Caesar või nimi Julius Caesar teistes keeltes, siis võib ka soovi loovutada mõned kaalu need väärtused. Ja kui see on piisavalt lähedal - kui see ületab teatud piiri - siis sa tahad et oleks võimalik vastu võtta Julius Caesar. Nii on paar erinevate rakenduste jaoks, et mõne muu keele samuti. Siin on mõned muud vahendid, Regex Pal - käepärane väike app online Kontrollimaks, kas teie regulaaravaldiste koosnevad õigesti. On ka standalone tööriistu, mida saab käivitada otse oma töölaual nagu Ultra Pico ja samuti lihtsalt cookbooks. Nii et kui te teete projekt, mis hõlmab ton regulaaravaldiste see on ilmselt koht, kuhu minna väljapoole täna. Ja siis lihtsalt anda teile ettekujutuse, kuidas ühine see on on grep Unix, Perl on sisseehitatud ja C on PCRE eest C. Ja siis kõik need teised keeled ka regulaaravaldise paketid et opereerida sisuliselt sama süntaks saime maitsta täna. PHP, Java, Ruby, ja nii edasi. 

Google Code Search on tegelikult mainimist väärt, see on üks suhteliselt vähe rakendusi seal, mis võimaldab elanikele juurdepääsu oma andmebaasi kasutades regulaaravaldiste. Nii et kui sa vaatad Google Code Search leiad kood kui otsite näiteks selle kohta, kuidas funktsioon võidakse kasutada, mida saab kasutada regulaaravaldiste leida selle funktsiooni kasutatakse igasuguseid erinevaid juhtumeid. Sa võid otsida ümbernimetamisel nimega, ja siis võiks otsida lipu kirjutada või lugeda kui sa tahad näiteks ümbernimetamisel nimega kasutatakse sellisel juhul. Nii sama asi seal, ja siin on mõned viited. See on saadaval online samuti, et läheb edasi, kui soovite vaadata Python, grep, Perl - tahad lihtsalt natuke inspiratsiooni või kui sa tahad otsida rohkem teooria siin on mõned head hüpped off kohtades. Suur aitäh. [CS50.TV]