Regular expressions (‘κανονικές εκφράσεις’) είναι ένα ισχυρό εργαλείο που προέρχεται από τη θεωρία των τυπικών γλωσσών (formal languages), το οποίο επιτρέπει την ευέλικτη αναζήτηση και ‘ταίριασμα’ (matching) κειμένου σύμφωνα με μια προδιαγραφή (matching pattern).
Μπορούμε να φανταστούμε την προδιαγραφή αυτή ως μία μίνι-γλώσσα, η οποία χρησιμοποιείται για τη συγκρότηση μιας μηχανής ταιριάσματος (matching engine). Η μηχανή επεξεργάζεται το κείμενο εισόδου σύμφωνα με τις οδηγίες της προδιαγραφής και επιστρέφει
Μια προδιαγραφή regular expression μπορεί να αποτελείται από άλλες μικρότερες ή από ένα σύνολο εναλλακτικών υπο-προδιαγραφών. Οι προδιαγραφές απαρτίζονται από χαρακτήρες: είτε απλοί χαρακτήρες όπως το a που ταιριάζει μόνο το γράμμα a, είτε ειδικοί χαρακτήρες ελέγχου, όπως η τελεία . που ταιριάζει (σχεδόν) οποιοδήποτε γράμμα.
Η προδιαγραφή περνά από μια διαδικασία ‘μεταγλώττισης’ (compilation) και κατασκευάζεται ένα σύνολο οδηγιών για τη μηχανή ταιριάσματος. Η βασική μηχανή είναι γραμμένη συνήθως σε C και πολύ γρήγορη σε εκτέλεση.
Υπάρχουν δύο τύποι μηχανών:
Note
Η χρήση των regular expressions είναι δύσκολη για τους μη πεπειραμένους και πρέπει να γίνεται με προσοχή. Εξετάστε αν μπορείτε να λύσετε το πρόβλημά σας με πιο απλόν τρόπο πριν καταφύγετε στη λύση των regular expressions (RE).
Some people, when confronted with a problem, think 'I know, I'll use
regular expressions.' Now they have two problems.
-- Jamie Zawinski, alt.religion.emacs (08/12/1997)
Note
Πολλά από τα παραδείγματα που ακολουθούν βασίζοντια σε υλικό από το βιβλίο “Mastering Regular Expressions”, 2nd ed., Jeffrey E.F. Friedl, O’Reilly Media, July 2002.
Στην Python η υλοποίηση των regular expressions είναι αντικειμενοστρεφής.
Η υποστήριξη των regular expressions υπάρχει ενσωματωμένη στη γλώσσα, στο module re:
import re
Ξεκινάμε με την προδιαγραφή εκφρασμένη σε ένα string:
restr = r'([-+]?[0-9]+(\.[0-9]*)?)\s*([CF])'
Note
Το string restr του παραδείγματος περιγράφει μια regular expression που ταιριάζει βαθμούς θερμοκρασίας, με προαιρετικό πρόσημο, ακέραιο και προαιρετικό δεκαδικό μέρος, πιθανά κενά και μετά τα γράμματα C ή F. Μην ανησυχείτε αν δεν την καταλαβαίνετε ακόμα!
Παρατηρήστε πώς γράφεται το regular expression: η σταθερά string δίνεται ως r' .... ', κάτι που συμβολίζει ένα raw string. Δεν σχετίζεται ειδικά με τα regular expressions, απλά βολεύει στην περίπτωσή μας:
- Η Python σε σταθερές string αντικαθιστά όπως και η C τα \n, \t κλπ με τον αντίστοιχο χαρακτήρα newline, tab, κ.ο.κ.
- Σε raw σταθερά string όμως, η αντικατάσταση αυτή δε γίνεται: το r'\n' είναι πάντα 2 χαρακτήρες, το \ και το n.
- Οι regular expressions χρησιμοποιούν πολύ τον μηχανισμό \χαρακτήρα, έτσι πρέπει να πούμε στην Python να μην προχωρήσει σε μετατροπές.
Στη συνέχεια κατασκευάζουμε το αντικείμενο regular expression, το οποίο μπορούμε να θεωρήσουμε ως τη μηχανή ταιριάσματος. Είναι το αντικείμενο που μας παρέχει τις μεθόδους αναζήτησης και αντικατάστασης σύμφωνα με την προδιαγραφή του RE.
rexp = re.compile(restr)
Note
Το rexp του παραδείγματος συμβολίζει το αντικείμενο-RE και συνήθως κατασκευάζεται άπαξ, στην αρχή του προγράμματος. Στη συνέχεια, μπορούμε να το χρησιμοποιήσουμε όσες φορές θέλουμε για να ταιριάξουμε κείμενο.
Στις επόμενες παραγράφους αναφέρονται μερικά μόνο από τα εργαλεία της Python για regular expressions. Για την πλήρη περιγραφή του module re, δείτε στο http://docs.python.org/library/re.html.
που αναγνωρίζονται από την Python είναι:
| abc | ταιριάζει ακριβώς το γράμμα a, ακολουθούμενο από το b και μετά το c |
| a|b | είτε το a, είτε το b |
| [abc] | character class: ένα από τα a, b ή c (ΠΡΟΣΟΧΗ: ΕΝΑΣ ΧΑΡΑΚΤΗΡΑΣ ΜΟΝΟ) |
| [a-zA-Z] | όπως προηγουμένως, αλλά σε ένα πεδίο τιμών, από a έως και z και από A έως και Z |
| [^ab] | ένας οποιοσδήποτε χαρακτήρας, εκτός από a ή b |
| $ | ταιριάζει στο τέλος του string (ρυθμίζεται να ταιριάζει και στο τέλος κάθε γραμμής του string) |
| ^ | ταιριάζει στην αρχή του string (ρυθμίζεται να ταιριάζει και στην αρχή κάθε γραμμής του string) |
| . | ένας οποιοσδήποτε χαρακτήρας εκτός από newline (ρυθμίζεται να ταιριάζει και το newline) |
| * | 0 ή περισσότερες φορές ο χαρακτήρας που προηγείται |
| + | 1 ή περισσότερες φορές ο χαρακτήρας που προηγείται |
| ? | 0 ή 1 φορά ο χαρακτήρας που προηγείται |
| {n} {m,n} | n φορές / από n έως m φορές ο χαρακτήρας που προηγείται |
| \b | ταιριάζει στην αρχή και στο τέλος μιας λέξης |
| \w \W | οποιοσδήποτε αλφαριθμητικός / μη αλφαριθμητικός χαρακτήρας |
| \s \S | οποιοσδήποτε whitespace / μη whitespace χαρακτήρας |
| *? +? ?? | μη άπληστες (non-greedy) μορφές των *, + και ? (μόνο σε NFA, βλ. πιο κάτω) |
| () | group ομαδοποίησης τμημάτων μιας RE, συγκρατούν και το κείμενο που ταιριάζει στο τμήμα (NFA μόνο) |
| \1 \2 κλπ | μέσα στη RE αντικαθίστανται από το τι έχει ταιριάξει ως τώρα στο αντίστοιχο group (NFA μόνο) |
Με βάση τα πιο πάνω μπορούμε να συντάξουμε σύνθετες προδιαγραφές, όπως εκείνη του παραδείγματος με τη θερμοκρασία.
Note
Η Python μπορεί να χρησιμοποιήσει την ίδια προδιαγραφή regular expression τόσο σε strings όσο σε unicode strings. ΠΡΟΣΟΧΗ!! Αν η προδιαγραφή περιέχει μη ASCII χαρακτήρες, πρέπει να χρησιμοποιήσετε raw unicode string (ur'....') για αυτήν, αλλιώς δεν θα λάβετε τα αποτελέσματα που περιμένετε!
Η κύρια μέθοδος είναι η search() που παίρνει ως όρισμα ένα string και αναζητά ταιριάσματα οπουδήποτε μέσα στο string. Με το πρώτο ταίριασμα που θα βρεθεί, επιστρέφει ένα match object με τις πληροφορίες του ταιριάσματος. Αν δεν βρεθεί κανένα ταίριασμα, επιστρέφεται το κενό αντικείμενο (None).
>>> import re
>>> restr = r'([-+]?[0-9]+(\.[0-9]*)?)\s*([CF])'
>>> rexp = re.compile(restr)
>>> m = rexp.search('abcd12.23')
>>> print m
None
>>> m = rexp.search('abcd12.23 F')
>>> print m
<_sre.SRE_Match object at 0x7f73a22bfe70>
>>> m.group(0)
'12.23 F'
>>> m.group(1)
'12.23'
>>> m.group(2)
'.23'
>>> m.group(3)
'F'
>>> m.groups()
('12.23', '.23', 'F')
Note
Τι είναι τα groups; Στην προδιαγραφή της RE, οι παρενθέσεις παίζουν ειδικό ρόλο, ομαδοποιώντας υποσύνολα της RE. Επιπλέον, η μηχανή θυμάται τι ταίριαξε σε κάθε group.
Το group(0) συμβολίζει όλο το κείμενο που ταίριαξε.
Για κάθε παρένθεση που ανοίγει -μετρώντας από τα αριστερά- ορίζονται και τα άλλα groups.:
([-+]?[0-9]+(\.[0-9]*)?)\s*([CF]) ^ ^ ^ 1 2 3 |----------------------| |--------| |----|
Αν ένα σετ παρενθέσεων έχει μπει μόνο για την εξυπηρέτηση του *, +, ? κλπ και δεν θέλουμε τη συγκράτηση της τιμής του group, μπορούμε να χρησιμοποιήσουμε το (?:...). Δείτε εδώ τη διαφορά από το προηγούμενο. Πόσα groups υπάρχουν τώρα;
>>> import re
>>> restr = r'([-+]?[0-9]+(?:\.[0-9]*)?)\s*([CF])'
>>> rexp = re.compile(restr)
>>> m = rexp.search('abcd12.23 F')
>>> m.groups()
('12.23', 'F')
Παράδειγμα: βρείτε τη γάτα στην αρχή ή στο τέλος ενός string:
>>> rexp = re.compile(r'^cat')
>>> m = rexp.search('I see a cat')
>>> print m
None
>>> m = rexp.search('category')
>>> print m
<_sre.SRE_Match object at 0x7f01ec094850>
>>> m.group(0)
'cat'
>>> rexp = re.compile(r'cat$')
>>> m = rexp.search('in category')
>>> print m
None
>>> m = rexp.search('black cat')
>>> print m
<_sre.SRE_Match object at 0x7f01ec094850>
>>> if m: print 'found!'
...
found!
Για να ταιριάξουμε ένα άδειο string, θα μπορούσαμε (θεωρητικά -δεν χρειάζεται στην πράξη!) να χρησιμοποιήσουμε το '^$'.
Παράδειγμα: κλάσεις χαρακτήρων με το []. Θυμηθείτε ότι μέσα στην κλάση, οι χαρακτήρες ελέγχου χάνουν τον ειδικό τους χαρακτήρα και το ^ σημαίνει κάτι διαφορετικό!
>>> rexp = re.compile(r'gr[ae]y')
>>> m = rexp.search('a gray cat')
>>> if m: print 'found!'
...
found!
>>> m = rexp.search('a grey cat')
>>> if m: print 'found!'
...
found!
Παράδειγμα: Βρείτε a που δεν ακολουθείται από b
>>> rexp = re.compile(r'a[^b]')
>>> m = rexp.search('ab')
>>> print m
None
>>> m = rexp.search('acb')
>>> print m
<_sre.SRE_Match object at 0x7f01ec094850>
>>> print m.group(0)
ac
>>> m = rexp.search('ba')
>>> print m
None
Στο τελευταίο παράδειγμα βλέπουμε ότι ενώ το a δεν πρέπει να ακολουθείται από b, πρέπει όμως να ακολουθείται από κάτι άλλο!
Παράδειγμα: Βρείτε το gray ή grey με εναλλαγή (alternation): 2 σωστοί και ένας λάθος τρόπος
>>> rexp = re.compile(r'gray|grey')
>>> m = rexp.search('a gray cat')
>>> if m: print 'found!'
...
found!
>>> rexp = re.compile(r'gr(a|e)y')
>>> m = rexp.search('a gray cat')
>>> if m: print 'found!'
...
found!
>>> rexp = re.compile(r'gra|ey')
>>> m = rexp.search('a gray cat')
>>> print m
<_sre.SRE_Match object at 0x7f01ec094850>
>>> print m.group(0)
gra
>>> m = rexp.search('a grey cat')
>>> print m
<_sre.SRE_Match object at 0x7f01ec0948b8>
>>> print m.group(0)
ey
Στο τελευταίο παράδειγμα έχουμε ταίριασμα, δεν είναι όμως αυτό που θέλουμε! Η χρήση των παρενθέσεων είναι αναγκαία για το σωστό ταίριασμα!
Παράδειγμα: Γιατί πρέπει να προσέχουμε όταν γειτονεύουν * και +
>>> restr = r'^.*([0-9]+)'
>>> rexp = re.compile(restr)
>>> m = rexp.search('Copyright 2003')
>>> m.group(0)
'Copyright 2003'
>>> m.group(1)
'3'
>>>
Γιατί δεν μπήκε όλο το 2003 μέσα στο group(1); Το * είναι άπληστο και καταναλώνει όλο το string. Στη συνέχεια αποδεσμεύει το 3 για να επιτρέψει και στο + να πετύχει ταίριασμα. Η διαδικασία σταματά εδώ και ποτέ δεν δίνεται η ευκαιρία στο + να ταιριάξει όλο το 2003.
Note
Η παράθεση πολλαπλών * και + οδηγεί σχεδόν πάνοτε σε λάθος. Από την αποτυχία ταιριάσματος αυτού που θέλει ο χρήστης μέχρι την αποτυχία της ίδιας της μηχανής αναζήτησης! Έτσι, πρέπει πάντα να αποφεύγεται.
Η μέθοδος match() λειτουργεί ακριβώς όπως η search(), με τη διαφορά ότι προσπαθεί να βρεί ταίριασμα μόνο από την αρχή του string (κι όχι οπουδήποτε μέσα στο string όπως η search).
Δέχεται ως όρισμα ένα string και επιστρέφει ένα αντικείμενο iterator, το οποίο δίνει διαδοχικά όλα τα match objects για όλα τα σημεία ταιριάσματος μέσα στο string.
Παράδειγμα: χρήση της τελείας . για να ταιριάξουμε οτιδήποτε (εκτός από newline!)
>>> rexp = re.compile(r'a.c')
>>> mi = rexp.finditer('ab abc acc axc afc acb a\nc avc')
>>> for m in mi:
... print m.group(0)
...
abc
acc
axc
afc
avc
Παράδειγμα: color ή colour?
>>> rexp = re.compile(r'colou?r')
>>> mi = rexp.finditer('some write colour instead of color')
>>> for m in mi:
... print m.group(0)
...
colour
color
Παράδειγμα: Εύρεση λέξεων που αντιπροσωπεύουν “σωστή” ώρα σε 24ωρο format
>>> rexp = re.compile(r'\b([01]?[0-9]|2[0-3]):[0-5][0-9]\b')
>>> mi = rexp.finditer('4:24 3:56 25:02 12:45 9:62')
>>> for m in mi:
... print m.group(0)
...
4:24
3:56
12:45
Επιστρέφει όλα τα ταιριάσματα, αλλά ΠΡΟΣΟΧΗ!! Η επιστρεφόμενη τιμή δεν μοιάζει με εκείνες των προηγούμενων μεθόδων:
Αν δεν υπάρχουν groups στην RE, επιστρέφει απλά μια λίστα με τα strings που ταίριαξαν.
Αν υπάρχουν groups, επιστρέφει μόνο αυτά κι όχι το πλήρες ταίριασμα (δηλ. δεν σας δίνει το group(0)).
Παράδειγμα: Ταίριασμα ονομάτων μεταβλητών:
>>> rexp = re.compile(r'\b[a-zA-z_][a-zA-Z0-9_]*\b')
>>> l = rexp.findall('var1 1var _var')
>>> l
['var1', '_var']
Παράδειγμα: Ταίριασμα κειμένου μέσα σε “..”
>>> rexp = re.compile(r'"[^"]*"')
>>> l = rexp.findall('"RE" is a "better" name for "regular expressions"')
>>> l
['"RE"', '"better"', '"regular expressions"']
Παράδειγμα: Λέξεις 5 κεφαλαίων από Α ώς Ζ (αγγλικά)
>>> rexp = re.compile(r'\b[A-Z]{5}\b')
>>> l = rexp.findall('ABCDE aEFGHI AB ABCDEFGHIJ NNNNN')
>>> l
['ABCDE', 'NNNNN']
Παράδειγμα: Βρείτε τις ετικέτες σε κώδικα HTML. Ένας λάθος (λόγω απληστίας του + που προσπαθεί να ταιριάξει όσο το δυνατόν περισσότερο κείμενο) και 2 σωστοί τρόποι (με κλάση χαρακτήρων και τη μη άπληστη μορφή του +?)
>>> rexp = re.compile(r'<.+>')
>>> l = rexp.findall('this <b>is</b> a <em>HTML</em> text')
>>> l
['<b>is</b> a <em>HTML</em>']
>>> rexp = re.compile(r'<[^>]+>')
>>> l = rexp.findall('this <b>is</b> a <em>HTML</em> text')
>>> l
['<b>', '</b>', '<em>', '</em>']
>>> rexp = re.compile(r'<.+?>')
>>> l = rexp.findall('this <b>is</b> a <em>HTML</em> text')
>>> l
['<b>', '</b>', '<em>', '</em>']
Δέχεται ως πρώτο όρισμα ένα string αντικατάστασης και ως δεύτερο ένα string αναζήτησης. Επιστρέφει ένα νέο string, όπου όλα τα σημεία του string αναζήτησης που ταιριάζουν με την RE έχουν αντικατασταθεί από το string αντικατάστασης.
Παράδειγμα: απαλοιφή διπλών ίδιων συνεχόμενων λέξεων από ένα string (προσέξτε ότι το backreference \1 απαιτεί το 1ο όρισμα της sub να είναι raw string!)
>>> rexp = re.compile(r'\b([a-z]+)\s+\1\b', re.IGNORECASE)
>>> s = rexp.sub(r'\1','This this is a a known fact.')
>>> s
'This is a known fact.'
Ας δούμε ένα ολοκληρωμένο παράδειγμα που χρησιμοποιεί πολλά από όσα αναφέρθηκαν προηγουμένως.
Το ζητούμενο είναι η αφαίρεση των ετικετών από σελίδα HTML, έτσι ώστε να παραμένει το καθαρό κείμενο της σελίδας. Θα χρησιμοποιήσουμε τη μέθοδο sub() για να αντικαταστήσουμε ό,τι επιλέγουν οι RE με το κενό (space).
Η χρήση του <[^>]*> προσφέρει μια γρήγορη λύση, όπως έχουμε ήδη δει. Τι γίνεται όμως όταν συναντήσουμε (απολύτως νόμιμο) HTML κώδικα όπως <input type="text" name="tx1" value=">>>" />; Μια πιο σύνθετη λύση θα ήταν όσο βρισκόμαστε μεταξύ " (ή ') να αγνοούμε οτιδήποτε άλλο:
<("[^"]*"|'[^']*'|[^'">])*>
Στο προηγούμενο, ζητάμε να ταιριάξουμε μεταξύ < και >, 0 ή περισσότερες φορές
Πριν αφαιρέσουμε όλα τα tags, σε ένα πρώτο πέρασμα αφαιρούμε όλα τα σχόλια και το περιεχόμενό τους. Αυτό γίνεται εύκολα με το μή άπληστο *:
<!--.*?-->
Επίσης, πριν διαγράψουμε όλες τις ετικέτες, θα πρέπει να εξουδετερώσουμε εκείνες που περιέχουν styles ή scripts (θεωρήστε ότι το περιεχόμενο αυτών των ετικετών δεν μας ενδιαφέρει!):
<(script|style).*?</\1>
Στο προγούμενο εκτός του μη άπληστου (non-greedy) *?, χρησιμοποιούμε και το backreference \1, ώστε η ετικέτα κλεισίματος να ταιριάζει με εκείνη της αρχής. Η μέθοδος δεν είναι 100% ασφαλής (π.χ. ένα script σε javascript μπορεί να περιέχει ένα string “</script>”, αλλά θεωρούμε ότι καλυπτόμαστε από την πιο πάνω RE).
Στο πρόγραμμα που ακολουθεί εφαρμόζουμε τις 3 RE που αναφέραμε παραπάνω στο κείμενο μιας ιστοσελίδας. Επειδή διαβάζουμε όλη την ιστοσελίδα σε ένα string, χρειάζεται η επιλογή re.DOTALL, έτσι ώστε η τελεία . να ταιριάζει και τα εσωτερικά newlines του string.
#!/usr/bin/python
# -*- coding: UTF-8 -*-
"""
Sample app to strip comments and entire tags from HTML page.
Uses re module
"""
import urllib
import re
page = urllib.urlopen("http://di.ionio.gr/msc/")
pagetext = page.read() # page uses UTF-8, leave as is
page.close()
# prepare regex to remove comments and their content
rstr1 = r'<!--.*?-->'
rexp1 = re.compile(rstr1,re.DOTALL) # dot matches \n too
# remove comments
pagetext = rexp1.sub(' ',pagetext)
# prepare regex to remove script/style tags and enclosed content
rstr2 = r'<(script|style).*?</\1>'
rexp2 = re.compile(rstr2,re.DOTALL)
# remove script/style tags and enclosed content
pagetext = rexp2.sub(' ',pagetext)
# prepare regex to remove all remaining tags
rstr3 = r'<("[^"]*"|\'[^\']*\'|[^\'">])*>'
rexp3 = re.compile(rstr3,re.DOTALL)
# remove remaining tags
pagetext = rexp3.sub(' ',pagetext)
print pagetext