[Powered by Google Translate] [Séminaire: la recherche de correspondances avec les expressions régulières]
[Université John Mussman-Harvard]
[C'est CS50.-CS50.TV]
D'accord. Eh bien, bienvenue tout le monde. C'est CS50 2012.
Mon nom est John, et je vais parler aujourd'hui sur les expressions régulières.
Les expressions régulières est avant tout un outil, mais aussi parfois utilisés
dans le code activement pour correspondre essentiellement des modèles et des chaînes.
Alors, voici un comic web à partir de xkcd.
Dans cette bande dessinée il ya un mystère assassiner où le tueur a
puis quelqu'un en vacances, et les protagonistes doivent
chercher dans 200 mégaoctets de courriels à la recherche d'une adresse.
Et ils sont sur le point d'abandonner quand quelqu'un qui connaît les expressions régulières -
probablement un super-héros - s'abat et écrit du code
et résout le mystère assassiner.
On peut donc supposer que ce sera quelque chose que vous serez habilité à le faire
après ce séminaire.
Nous allons nous contenter de fournir une introduction concise à la langue
et vous donner suffisamment de moyens pour aller après plus de ressources sur votre propre.
>> Alors expressions régulières semblent fondamentalement comme ça.
Il s'agit d'une expression régulière dans Ruby.
Il n'est pas très différente selon les langues.
Nous avons juste à barres pour commencer et marquer l'expression régulière en Ruby.
Et c'est une expression régulière à rechercher dans l'adresse modèle de courriel.
Ainsi, nous voyons au premier bit cherche n'importe quel caractère alphanumérique.
C'est parce que les adresses e-mail doivent souvent commencer par un caractère alphabétique.
Et puis un caractère spécial suivi par le symbole @.
Et puis la même chose pour le nom de domaine.
Et puis entre 2 et 4 caractères pour chercher le. Com,. Net, et ainsi de suite.
Voilà donc un autre exemple de l'expression régulière.
Alors expressions régulières sont des protocoles pour trouver des motifs dans le texte.
Ils font des comparaisons, sélections, et de remplacements.
Ainsi, un troisième exemple est de trouver tous les numéros de téléphone se terminant par 54 dans un répertoire.
Donc, avant que David déchire le répertoire CS50 nous pourrions rechercher
un modèle où nous avons parenthèses puis 3 chiffres puis s'arrête parenthèse,
3 autres numéros, un tiret, 2 numéros, puis 54.
Et ce serait essentiellement comment nous arrivons à une expression régulière à rechercher pour cela.
>> Donc, il ya - nous avons fait certaines choses dans CS50 qui sont un peu comme
expressions régulières, etc - par exemple - dans le fichier dictionary.C
pour la vérification orthographique ensemble des problèmes que vous avez utilisé fscanf
à lire en un mot du dictionnaire.
Et vous pouvez voir le pourcentage 45s est à la recherche d'une chaîne de 45 caractères.
Donc, c'est un peu comme une expression régulière rudimentaire.
Et vous pouvez avoir toutes les 45 caractères qui correspondent au projet de loi en y
et choisir celles vers le haut.
Et puis le deuxième exemple le problème de programmation web les plus récents
fixé dans le code de distribution pour php nous avons en fait une expression régulière simple.
Et celui-ci est tout simplement à la recherche pour vérifier si la page Web qui est passé dans
correspond soit vous connecter ou se déconnecter de vous inscrire. PHP.
Et puis retourner vrai ou faux en fonction de cette correspondance d'expression régulière.
>> Ainsi, lorsque vous utilisez l'expression régulière?
Pourquoi êtes-vous ici aujourd'hui?
Donc, vous ne voulez pas utiliser l'expression régulière quand il ya quelque chose qui
fait le travail pour vous encore plus facilement.
Donc, XML et HTML sont en fait assez difficile
d'écrire des expressions régulières pour que nous verrons dans un peu.
Donc, il ya des analyseurs dédiés pour ces langues.
Vous devez également être en accord avec le compromis du commerce et de l'exactitude fréquemment.
Si vous essayez - si nous avons vu une expression régulière pour une adresse e-mail,
mais dites que vous vouliez une adresse électronique spécifique et peu à peu l'
expression régulière peut devenir plus complexe car il est devenu plus précis.
Donc, ce serait un compromis.
Vous devez être sûr que vous êtes bien faites avec l'expression régulière.
Si vous savez exactement ce que vous cherchez, il serait plus logique
à mettre dans le temps et d'écrire un analyseur plus efficace.
Et enfin il ya un problème historique avec la régularité
des expressions et des langues.
Les expressions régulières sont en réalité beaucoup plus puissant que
expressions régulières par dire dans un sens formel.
>> Donc, je ne veux pas aller trop loin dans la théorie formelle,
mais la plupart des langues que l'on code en fait ne sont pas régulières.
Et c'est pourquoi les expressions régulières ne sont pas toujours considérés comme tout ce qui sécurisé.
Donc, fondamentalement, il ya une hiérarchie de Chomsky pour les langues,
et les expressions régulières sont construites à l'aide de l'union, la concaténation,
et l'opération Kleene étoile que nous verrons dans quelques minutes.
Si vous êtes intéressé en théorie il est tout à fait beaucoup de choses là-bas sous le capot.
>> Ainsi, un bref historique - juste pour le contexte ici - ensembles réguliers venus
dans les années 1950, puis nous avons eu éditeurs simples que
incorporé des expressions régulières - recherche juste pour les chaînes.
Grep - qui est un outil de ligne de commande - était l'un des premiers
outils très populaire qui a incorporé des expressions régulières dans les années 1960.
Dans les années 80, Perl a été construit - est un langage de programmation qui
intègre des expressions régulières en très bonne place.
Et puis, plus récemment, nous avons eu Perl Compatible Regular Expression
protocoles essentiellement dans d'autres langues qui utilisent une grande partie de la même syntaxe.
Bien sûr, l'événement le plus important a été en 2008
où il y avait la première Journée nationale des expressions régulières,
qui je crois est le 1 Juin, si vous voulez fêter ça.
>> Encore une fois, juste un peu plus de théorie ici.
Donc, il ya deux manières différentes de construire des expressions régulières.
Une méthode simple consiste à construire l'expression que vous allez
fonctionner sur la chaîne interpréter - essentiellement construire un mini-programme peu que
analysera les pièces d'un string et de voir: «Oh, cela correspond à l'expression régulière ou non?"
Et puis exécuter cela.
Donc si vous avez une très petite expression régulière, c'est probablement
le moyen le plus efficace de le faire.
Et puis, si vous - une autre option est de garder la reconstruction de l'
expression que vous alliez, et que la possibilité de simuler.
Et ces premières tentatives d'algorithmes d'expressions régulières étaient
relativement simple et relativement rapide, mais n'a pas eu beaucoup de souplesse.
Alors, pour faire encore quelques-unes des choses que nous allons examiner
Aujourd'hui, nous avons eu à faire expression régulière plus complexe
implémentations qui sont potentiellement beaucoup plus lent, de sorte que c'est quelque chose à garder à l'esprit
Il ya aussi un déni expressions régulières de la variété d'attaque
que d'exploiter le potentiel de ces nouvelles implémentations d'
expressions régulières pour devenir très complexe.
Et dans la même logique que nous avons vu dans les attaques de dépassement de tampon,
vous avez des attaques que le travail en faisant des boucles récursives
dépassement de la capacité de la mémoire.
Et en passant Regexen est l'un des pluriels officielles de l'expression régulière
par analogie à bœufs dans les pays anglo-saxons.
>> Bon, alors la bibliothèque Python beaucoup d'entre vous ici en personne ont Macs,
de sorte que vous pouvez réellement tirer de cette place sur votre écran.
Les expressions régulières sont construites en Python.
Et si Python est préchargé sur Mac et également disponible en ligne sur ce lien.
Donc, si vous regardez vous pouvez mettre en pause et assurez-vous que Python
que nous jouons ici.
Il s'agit d'un manuel en ligne, donc si vous tapez simplement Python dans votre ordinateur
vous verrez que la version arrive dans le terminal.
Donc j'ai fourni un lien vers le manuel pour la version 2 de Python, ainsi qu'une feuille de triche.
Il existe une version 3 de Python, mais votre Mac n'a pas nécessairement
venir avec qui préchargé.
Donc, pas très différent.
Ok, donc quelques notions de base de l'utilisation des expressions régulières dans Python.
>> Donc ici j'ai utilisé une expression très simple, donc je n'ai Python import re
puis a pris la suite de re.search.
Et la recherche prend 2 arguments.
Le premier est l'expression régulière, et le second est le texte
ou la chaîne que vous souhaitez analyser.
Et puis j'ai imprimé le result.group.
Ce sont donc les 2 fonctions de base que nous allons voir aujourd'hui
en apprendre davantage sur les expressions régulières.
Il suffit donc de briser cette expression régulière ici
h, puis \ w puis m si \ w accepte n'importe quel caractère alphabétique à l'intérieur.
Donc, ici, nous sommes à la recherche d'un "h" et puis un autre caractère alphabétique
et puis m, alors voici qui correspondrait à jambon
In "Abraham Lincoln et sandwiches au jambon."
C'est le résultat de ce groupe.
Une autre chose que nous pouvons faire, c'est utiliser nos chaînes avant de texte en Python.
Donc je suppose que je vais aller de l'avant et tirer que vers le haut ici.
Python import re.
Et si je devais faire la même chose - disons texte est,
«Abraham», laissez-nous zoomer - là nous allons.
Le texte est: «Abraham mange du jambon."
Bon, et puis entraîner = re.search.
Et puis notre expression peut être h, puis je ferai dot m.
Alors dot prend n'importe quel caractère qui n'est pas une nouvelle ligne y compris les numéros,
signes de pourcentage, quelque chose comme ça.
Et puis le texte - boum - puis-result.group-yeah.
Donc, c'est juste la façon de mettre en œuvre des fonctionnalités de base ici.
Si nous avions un anneau de texte - ce texte fou - inclus dire beaucoup de barres obliques inversées
et cordes à l'intérieur et les choses qui pourraient ressembler à des séquences d'échappement,
alors nous voulons probablement d'utiliser l'entrée de texte brut pour s'assurer qui est acceptée.
Et qui ressemble à ça.
Donc, si nous étions à la recherche pour chacun d'entre eux là-bas, nous ne devrions pas trouver quoi que ce soit.
Mais c'est la façon dont vous souhaitez mettre en œuvre; juste avant la chaîne de
l'expression régulière que vous mettez la lettre r.
>> Ok, donc nous continuons.
Tout droit - alors penchons-nous sur quelques motifs répétitifs ici.
Donc, une chose que vous voulez faire est de répéter les choses
que vous êtes à la recherche à travers le texte.
Donc, pour faire un suivi par un nombre quelconque de b - vous faites ab *.
Et puis il ya une série d'autres règles trop.
Et vous pouvez regarder tous ces up, je vais courir à travers quelques-uns des
les plus couramment utilisés.
Donc ab + est un suivi de n'importe quel N supérieur à 0 de b.
ab? est suivi par un 0 ou 1 de b.
ab {N} est un suivi d'au N de B, puis ainsi de suite.
Si vous avez 2 numéros dans les accolades vous spécifiez une plage
qui peut être éventuellement appariés.
Nous allons donc examiner de plus près quelques motifs répétitifs dans une minute.
Donc, 2 choses à garder à l'esprit lors de l'utilisation de ces outils motif assortie ici.
Donc disons que nous voulons regarder le hm de "Abraham Lincoln fait des sandwichs au jambon."
J'ai donc changé le nom d'Abraham Lincoln à Abraham.
Et maintenant, nous sommes à la recherche pour ce qui est retourné par cette fonction de recherche,
et il ne revient jambon dans ce cas.
Et il le fait parce que recherche tout prend naturellement la plus à gauche file d'attente.
Et toutes les expressions régulières, sauf indication contraire vont le faire.
Si nous voulions trouver tout ce qu'il ya une fonction pour cela - vous trouverez tout.
Alors, qui pourrait tout ressembler à tous = re.findall ('h.m », texte)
puis all.group ().
Tout produit à la fois jambon et le jambon; dans ce cas, les deux chaînes dans chaque Abraham jambon.
Voilà donc une autre option.
>> Grande. L'autre chose à garder à l'esprit est que les expressions régulières prennent le plus intuitivement.
Penchons-nous sur cet exemple.
Nous l'avons fait plus à gauche recherche ici, et puis j'ai tenté une recherche plus
utilisant l'opérateur de Kleene étoiles.
Donc pour "Abraham Lincoln fait des sandwichs au jambon," et je ne revint
m à la suite.
La raison de cette erreur, c'est que j'aurais pu prendre n'importe quel nombre d'
h c'est parce que je n'ai pas précisé quoi que ce soit pour aller entre h et m.
Le seul exemple qui il avait m - les seuls exemples là-bas avec m en elle
et un certain nombre d'heures de la chaîne étaient juste m.
Ensuite, j'ai essayé à nouveau, j'ai dit: «Bon, nous obtenons le groupe réel plus ici."
Et puis je l'ai h. * M, de sorte que retourne n'importe quel nombre de caractères entre h et m.
Et si vous êtes débutant et de penser, "Oh, d'accord, eh bien ce sera
vous méprenez jambon, «il faut vraiment tout de l'h à Abraham Lincoln
sur toute la hauteur à la fin de jambon.
Elle est gourmande, elle voit h - tout cela autre texte - m,
et c'est ce qu'il faut po
Cela est particulièrement flagrant - c'est une caractéristique que nous pouvons également
préciser pour qu'il ne soit pas gourmand en utilisant d'autres fonctions.
Mais c'est quelque chose que nous devons garder à l'esprit en particulier
quand on regarde texte HTML, ce qui est une des raisons qui
les expressions régulières sont difficiles pour HTML.
Parce que si vous avez une balise HTML sont ouverts et puis beaucoup de choses dans le milieu
et puis un autre tag HTML fermé beaucoup plus tard dans le programme,
vous avez juste mangé beaucoup de votre code HTML peut-être par erreur.
>> Tous droits - personnages si plus spéciales, comme beaucoup d'autres langues,
nous échappons à l'aide de la barre.
Ainsi, nous pouvons utiliser la dot pour spécifier n'importe quel caractère sauf pour une nouvelle ligne.
Nous pouvons utiliser l'évasion w pour spécifier n'importe quel caractère alphabétique.
Et par analogie évasion d pour tout entier - caractère numérique.
Nous pouvons préciser - que nous pouvons utiliser des parenthèses pour spécifier expressions apparentées.
Donc, ce serait accepter a, b, c.
Et nous pouvons également préciser ou options pour a ou b.
Par exemple - si nous étions à la recherche pour de multiples possibilités
entre parenthèses, nous pourrions utiliser l'opérateur ou comme dans -
donc revenons à cet exemple ici.
Et maintenant, prenons - Revenons à notre exemple ici, puis
prendre ae - ce qui devrait revenir - je suppose que c'est encore Abraham.
Donc ceci - si nous le faisons tous - grand.
Alors laissez-nous actualiser le texte ici.
"Abraham mange du jambon, tout ourler son - tout ourlets." Grande.
Toutes les. Grande. Maintenant, nous arrivons au jambon, jambon, et à l'ourlet.
Alors ourlets - tout en fredonnant pour lui - tout en fredonnant à l'ourlet lui. Grande.
C'est la même chose.
Maintenant, tout retourne toujours juste, jambon et ourlet sans décrocher le bourdonnement ou le lui.
Grande - tant pis si nous voulions regarder non plus que - si nous pouvions aussi faire
lui ou - nous reviendrons à cela.
Ok - donc - tout droit - dans des positions que vous pouvez également utiliser le curseur ou le signe dollar
pour indiquer que vous êtes à la recherche de quelque chose au début ou à la fin d'une chaîne.
Ou le début ou la fin d'un mot.
C'est une façon de l'utiliser.
>> Okay - laissez-nous jouer avec un peu plus grand bloc de texte.
Disons cette ligne ici - cette déclaration ici.
La puissance de l'expression régulière, c'est qu'ils peuvent spécifier des modèles
pas seulement fixé caractères.
Faisons - nous appelons ce bloc.
Ensuite, nous allons lire tout cela po
Et puis avoir un - nous faisons tous =; donc quelles sont les choses que nous pourrions rechercher ici rentable?
Nous pourrions chercher l'oreille d'expression.
Pas très intéressant. Que diriez-vous cela? Nous allons voir ce qui se passe.
Je lui ai donné un problème.
Donc, un certain nombre de choses avant de les remettre tous.
Alors qu'il devrait tout depuis le début jusqu'à tout ré Peut-être une fois en couple retourner.
Et puis nous avons ici la puissance des expressions régulières, c'est qu'ils
peut spécifier des modèles non seulement personnages sont ici.
Donc, tout le chemin jusqu'à la finale re, il a commencé avec le plus à gauche et était avide.
Voyons - quoi d'autre pourrions-nous chercher.
Je pense une chose si vous étiez intéressé à regarder pour les pronoms elle et lui,
vous pouvez vérifier pour s étant égal à 0 ou 1
et l'expression lui, et qui ne va probablement pas à revenir -
oh, je suppose qu'il est revenu, il parce qu'il nous étudions la puissance, ce jour-là, voici.
Essayons de préciser que cela doit se faire au début de quelque chose.
Voyons si cela tombe.
Ainsi, nous pouvons faire la graisse, et il nous n'obtenons rien, car elle et lui
ne se produisent pas dans cette phrase.
Grande. Ok - donc retour au chat ici.
Alors modèles complexes est mal au cerveau.
Donc, c'est pourquoi nous utilisons des expressions régulières pour éviter ces problèmes.
>> Alors, voici quelques autres modes utiles que vous pouvez jouer avec.
Nous avons regardé recherche aujourd'hui, mais vous pouvez également utiliser correspondance, split, findall et groupes.
Ainsi, d'autres choses cool que vous pouvez faire avec les expressions régulières mais pas seulement
la recherche de modèles est de prendre un modèle et la tenue tous les matchs -
ses variables - et utiliser ceux dans votre code plus tard.
Cela peut être très utile. D'autres choses pourraient compter.
Ainsi, nous pouvons compter le nombre d'occurrences d'un modèle d'expression régulière,
et c'est ce que nous pouvons utiliser pour les groupes.
Et d'autres modes ainsi sont également possibles.
Donc, je veux juste parler un peu plus sur d'autres façons que vous pouvez utiliser des expressions régulières.
>> Donc, une application plus avancé est en correspondance floue.
Donc, si vous êtes à la recherche d'un texte pour l'expression, Jules César,
et vous voyez soit Gaius Julius Caesar ou le nom de Jules César dans d'autres langues,
alors vous pouvez également attribuer un certain poids à ces valeurs.
Et si elle est assez proche - si elle traverse un certain seuil - alors vous voulez
pour être en mesure d'accepter Jules César.
Donc, il ya un couple de différentes implémentations pour que dans quelques autres langues.
Voici quelques autres outils, Regex PAL - un peu soft très pratique en ligne pour
vérifier si vos expressions régulières sont composées correctement.
Il existe également des outils autonomes que vous pouvez exécuter à partir de votre ordinateur de bureau
comme Pico Ultra, et ainsi que des livres de recettes seulement.
Donc, si vous faites un projet qui implique une tonne d'expressions régulières
c'est probablement l'endroit où aller en dehors du champ d'aujourd'hui.
Et puis, juste pour vous donner une idée de combien il est courant
il ya grep sous Unix, Perl a built-in, et C, il est PCRE pour C.
Et puis toutes ces autres langues ont également des forfaits d'expressions régulières
qui fonctionnent avec essentiellement la même syntaxe que nous avons eu un avant-goût d'aujourd'hui.
PHP, Java, Ruby, et ainsi de suite.
>> Google Recherche de code est en fait digne de mention, il est l'un des
relativement peu d'applications là-bas qui permet au public d'accéder
sa base de données en utilisant des expressions régulières.
Donc, si vous regardez sur Google Recherche de code, vous pouvez trouver le code
Si vous cherchez un exemple de comment une fonction peut être utilisée,
vous pouvez utiliser une expression régulière pour trouver cette fonction étant utilisé dans toutes sortes de cas.
Vous pouvez chercher fwrite, et puis vous pouvez chercher le drapeau de l'écriture ou de lecture
si vous voulez un exemple de fwrite être utilisé dans ce cas.
Donc la même chose là-bas, et voici quelques références.
Ce sera disponible en ligne aussi, donc aller en avant si
vous voulez regarder Python, grep, Perl - vous voulez juste avoir un peu d'inspiration
ou si vous voulez regarder de plus à la théorie Voici quelques bonnes tremplin endroits.
Je vous remercie beaucoup.
[CS50.TV]