Κανονικές Εκφράσεις

Μια κανονική έκφραση [, ] είναι ένας σύντομος και σαφής τρόπος έκφρασης ενός μοτίβου αναζήτησης χαρακτήρων. Χρησιμοποιούνται διάφορες συντομογραφίες για τις κανονικές εκφράσεις όπως: RegExp, RegEx ή και RE. Οι κανονικές εκφράσεις αποτελούνται από συνδυασμό κανονικών χαρακτήρων με έναν ή περισσότερους μεταχαρακτήρες. Οι μεταχαρακτήρες είναι χαρακτήρες με ειδική σημασία. Οι κανονικές εκφράσεις χρησιμοποιούνται κυρίως για έλεγχο συμβολοσειρών ή για εύρεση συγκεκριμένων στοιχείων μέσα σε μια συμβολοσειρά (ή γενικότερα σε ένα αρχείο) ή και για εύρεση και αντικατάσταση ενός μοτίβου με ένα άλλο αν για παράδειγμα σε ένα αρχείο θέλουμε να αντικαταστήσουμε τις ημερομηνίες της μορφής ΗΗ/ΜΜ/ΕΕΕΕ (πχ. 10/03/2015) με την μορφή EEEE-MM-HH (πχ. 2015-03-10).

Η ιδέα των κανονικών εκφράσεων εμφανίστηκε τον 1950, όταν ο Αμερικανός μαθηματικός Stephen Kleene επισημοποίησε την περιγραφή μιας «Κανονικής Γλώσσας» (Regular Language). Οι Κανονικές Εκφράσεις χρησιμοποιήθηκαν ευρέως στο UNIX με τις εντολές ed, sed, grep, vi, awk κα.

Οι Κανονικές Εκφράσεις δεν είναι μόνο δυνατότητα του Unix. Στο Unix χρησιμοποιούνται ιδιαίτερα λόγω των προγραμμάτων που αναφέρθηκαν, αλλά η χρήση τους είναι θέμα υποστήριξης από τις εφαρμογές που χρησιμοποιούμε.

Όλες σχεδόν οι γλώσσες προγραμματισμού υποστηρίζουν κανονικές εκφράσεις. Είτε μέσω βιβλιοθηκών, όπως οι C, C++, είτε ενσωματωμένες στη γλώσσα. Όλες οι νέες γλώσσες προγραμματισμού έχουν ενσωματωμένη τη δυνατότητα χειρισμού κανονικών εκφράσεων, όπως οι perl, php, JavaScript, κ.ά.

Στο παρόν κεφάλαιο θα μελετήσουμε τις κανονικές εκφράσεις μέσα από τη χρήση της εντολής grep (global regular expression print) []. Σε μεταγενέστερο κεφάλαιο θα μελετήσουμε τη χρήση των κανονικών εκφράσεων με την εντολή sed.

Δομή κανονικών Εκφράσεων

Μια κανονική έκφραση είναι παρόμοια με μια μαθηματική έκφραση. Μια μαθηματική έκφραση αποτελείται από τελεστέους (operands) και τελεστές (operators). Μια κανονική έκφραση αποτελείται από atoms και operators. Το atom προσδιορίζει αυτό που αναζητούμε ή το σημείο του κειμένου, ενώ ο τελεστής προσδιορίζει τις πράξεις ή σύνθετους συνδυασμούς μεταξύ των atoms.

Ένα atom μπορεί να είναι κάτι από τα παρακάτω:

• Ένας απλός χαρακτήρας: δηλώνει αναζήτηση του συγκεκριμένου χαρακτήρα.
• Ο ειδικός χαρακτήρας ".": δηλώνει αναζήτηση ενός οποιουδήποτε χαρακτήρα.
• Μια κλάση χαρακτήρων οριζόμενη με τις αγκύλες []: δηλώνει αναζήτηση ενός χαρακτήρα που ορίζεται στην κλάση.
• Ένας ειδικός χαρακτήρας Άγκυρα (anchor): δηλώνει θέση.
• Αναφορά προς τα πίσω (back reference): δηλώνει αναζήτηση κάποιου στοιχείου που έχει ήδη ξαναβρεθεί.

Από την άλλη μεριά, μια πράξη μπορεί να είναι μια από τις παρακάτω:

• Πράξη ακολουθίας (sequence): Δεν συμβολίζεται με κανέναν χαρακτήρα.
• Πράξη Ή (OR): δηλώνει εναλλακτική κανονική έκφραση. Συμβολίζεται με τον χαρακτήρα "|".
• Πράξη Επανάληψης (repetition): Δηλώνει επανάληψη του προηγούμενου atom. Υπάρχουν πολλές πράξεις επανάληψης και τα σύμβολα είναι: "*", "+", "?", "{n,m}", "{n}", "{n,}".
• Πράξη ομαδοποίησης (group): Συμβολίζεται με τις παρενθέσεις.
• Πράξη αποθήκευσης (save): Συμβολίζεται με τις παρενθέσεις επίσης.

Τα atoms

Ένας απλός χαρακτήρας

Η πιο απλή περίπτωση ενός atom είναι ένας απλός χαρακτήρας. Στο παρουσιάζεται η πιο απλή περίπτωση μιας κανονικής έκφρασης που αποτελείται μόνο από ένα atom. Έστω ότι αυτό το atom είναι ο απλός χαρακτήρας “L”. Μια κανονική έκφραση ελέγχεται ώστε να εξακριβωθεί αν ταιριάζει σε κάποια συμβολοσειρά (string). Έστω ότι ελέγχουμε την προηγούμενη κανονική έκφραση επάνω στη συμβολοσειρά "HELLO". Εσωτερικά, το όποιο σύστημα ελέγχου, προσπαθεί να ταιριάξει την κανονική έκφραση στη συμβολοσειρά κάνοντας όλους τους δυνατούς ελέγχους μέχρι να ταιριάξει η έκφραση σε κάποιο σημείο ή μέχρι να εξαντληθούν όλοι οι δυνατοί συνδυασμοί.

Στο φαίνεται ότι εξαντλούνται οι δυνατοί συνδυασμοί και η κανονική έκφραση "Κ" δεν ταιριάζει στη συμβολοσειρά "HELLO". Τότε το τελικό αποτέλεσμα του ελέγχου είναι αρνητικό.

Η πράξη της Ακολουθίας

Εφόσον δεν υπάρχει κάποιο σύμβολο πράξης, εννοείται η πράξη της ακολουθίας. Στο παρακάτω παράδειγμα (), η κανονική έκφραση που αναζητούμε είναι η "ELL". Ουσιαστικά, αναζητούμε τον χαρακτήρα "E", ο οποίος πρέπει να ακολουθείται από τον χαρακτήρα "L", ο οποίος πρέπει να ακολουθείται από τον χαρακτήρα "L". Ο μηχανισμός ελέγχου κανονικών εκφράσεων θα πραγματοποιήσει όλους τους δυνατούς συνδυασμούς, μέχρι να πετύχει ταίριασμα, ξεκινώντας τις συγκρίσεις από τον πρώτο χαρακτήρα.

Το atom "."

Το επόμενο atom που αναφέραμε είναι ο ειδικός χαρακτήρας ".". Σημαίνει «οποιοσδήποτε χαρακτήρας», ακόμη και αν αυτός ο χαρακτήρας δεν φαίνεται, δηλαδή είναι κάποιος χαρακτήρας ελέγχου. Στο παράδειγμα (), αναζητούμε την πιο απλή περίπτωση, την κανονική έκφραση ".". Όπως φαίνεται και στο σχήμα, η "." θα ταιριάξει στον πρώτο δυνατό χαρακτήρα.

Το επόμενο σχήμα () δείχνει ακόμη δυο απλές περιπτώσεις. Η πρώτη περίπτωση είναι αναζήτηση της κανονικής έκφρασης "Ε.", δηλαδή αναζήτηση του "Ε" που να ακολουθείται από έναν οποιοδήποτε χαρακτήρα. Αυτή η κανονική έκφραση θα ταιριάξει στο τμήμα της συμβολοσειράς "EL", δηλαδή η "." θα ταιριάξει στο γράμμα "L". Προφανώς, θα μπορούσε να ταιριάξει σε οποιοδήποτε γράμμα ή σύμβολο εκτός από το «τίποτα». Στο δεύτερο παράδειγμα, γίνεται αναζήτηση της κανονικής έκφρασης "Ο.". Το μόνο σημείο που υπάρχει ο χαρακτήρας "Ο" είναι στο τέλος της συμβολοσειράς "HELLO". Όμως, μετά το "Ο" δεν ακολουθεί άλλος χαρακτήρας, συνεπώς, η "." δεν μπορεί να ταιριάξει με κάτι. Άρα η δεύτερη κανονική έκφραση "Ο." δεν ταιριάζει στο "HELLO".

Το atom κλάσης χαρακτήρων

Το atom κλάση χαρακτήρων ορίζει ένα σύνολο χαρακτήρων του συνόλου χαρακτήρων που χρησιμοποιείται (ASCII, ISO-8859, UTF-8 κτλ.). Η κλάση χαρακτήρων ορίζεται όπως στους χαρακτήρες μπαλαντέρ του κελύφους (Βλέπε ). Η μόνη διαφορά με τα σύνολα των χαρακτήρων μπαλαντέρ είναι ότι δεν μπορεί να χρησιμοποιηθεί ο χαρακτήρας "!" για άρνηση, παρά μόνο ο "^".

Επίσης, υπάρχουν και τα προκαθορισμένα σύνολα χαρακτήρων που αναφέρθηκαν στον . Τα προκαθορισμένα σύνολα χαρακτήρων μπορούν να χρησιμοποιηθούν σε μια κλάση όπως οποιοδήποτε εύρος χαρακτήρων. Έτσι, στο παρακάτω παράδειγμα, συνδυάζουμε μέσα σε μια κλάση ένα προκαθορισμένο σύνολο και τους χαρακτήρες "," και "+". Η χρήση των προκαθορισμένων συνόλων προτιμάται, όπου είναι βέβαια εφικτή, διότι ακολουθεί τους κανόνες του συνόλου χαρακτήρων (charset) που χρησιμοποιείται κάθε φορά. Παράδειγμα το [[:upper:]] θα δουλέψει σωστά σε όλες τις γλώσσες και για όλα τα γράμματα, είτε Αγγλικά, είτε Ελληνικά, είτε Κυριλλικά, είτε ... Κινέζικα. Αν ο προγραμματιστής μιας εφαρμογής δεν επιθυμεί να χρησιμοποιήσει το [[:upper:]], αλλά το [A-ZA-Ω], τότε καλύπτει μόνο δυο γλώσσες (Αγγλικά-Ελληνικά) και βέβαια η κανονική έκφραση (και το πρόγραμμα που θα την περιέχει) θα πρέπει να είναι γραμμένη με τη σωστή κωδικοποίηση χαρακτήρων.

[[:digit:],+] ⇔ [0-9,+] ⇔ [0123456789,+]

Η χρήση των προκαθορισμένων συνόλων όπως το [:upper:] θα πρέπει να προτιμάται έναντι των ισοδύναμων ορισμών από τον χρήστη-προγραμματιστή.

Το atom άγκυρα

Οι άγκυρες δεν αντιστοιχούνται με χαρακτήρες της συμβολοσειράς εισόδου αλλά με θέσεις μέσα στη συμβολοσειρά. Χρησιμοποιούνται για να αντιστοιχήσουμε την υπόλοιπη κανονική έκφραση σε συγκεκριμένο τμήμα της συμβολοσειράς εισόδου.

Στον βλέπουμε τη σημασία του κάθε συμβόλου, ενώ στο με τα κόκκινα βέλη φαίνονται τα σημεία που μπορεί να ταιριάξει η κάθε άγκυρα μέσα στη συμβολοσειρά "One line of text.". Η αρχή λέξης ( \<) στο συγκεκριμένο παράδειγμα ταιριάζει και στην αρχή συμβολοσειράς. Εάν πριν από την πρώτη λέξη υπήρχε κάποιο κενό διάστημα, τότε η αρχή λέξης δεν θα ταυτιζόταν με την αρχή συμβολοσειράς. Επίσης παρατηρούμε ότι το τέλος λέξης δεν ταυτίζεται με το τέλος συμβολοσειράς, επειδή υπάρχει ο χαρακτήρας "." αμέσως μετά τη λέξη και πριν από το τέλος.

Τελεστές

Ο τελεστής ακολουθίας

Στην παρουσιάστηκε ο τελεστής ακολουθίας. Θυμίζουμε ότι ο τελεστής ακολουθίας συμβολίζεται με την απουσία κάποιου συμβόλου. Όταν, δηλαδή, σε μια κανονική έκφραση υπάρχουν δυο atoms συνεχόμενα, τότε εννοείται ενδιάμεσα ο τελεστής ακολουθίας. Στο παρουσιάζεται ακόμη ένα παράδειγμα, όπου χρησιμοποιείται ο τελεστής ακολουθίας σε συνδυασμό με το atom ".". Εδώ θα πρέπει να παρατηρήσουμε ότι, όσο μεγαλώνουν οι κανονικές εκφράσεις και όσο γίνονται πιο γενικές (το atom "." δημιουργεί μια γενικότητα), τότε και τα βήματα και επομένως ο χρόνος ελέγχου της κανονικής έκφρασης αυξάνεται.

Μερικά παραδείγματα με τον τελεστή ακολουθίας παρουσιάζονται στον .

Ο τελεστής εναλλαγής (OR)

Ο τελεστής OR δηλώνει στην κανονική έκφραση εναλλακτική περίπτωση. Το κάθε τμήμα δεξιά και αριστερά του OR (|) αποτελεί μια πλήρη κανονική έκφραση και μεταξύ τους είναι ανεξάρτητες.

Ο τελεστής επανάληψης

Ο τελεστής επανάληψης (repetition operator) καθορίζει πόσες φορές πρέπει να επαναληφθεί το atom που υπάρχει ακριβώς πριν την επανάληψη. Η γενική σύνταξη του τελεστή επανάληψης είναι

{n,m}

και δηλώνει πως το προηγούμενο atom θα πρέπει να επαναληφθεί από n έως m το πολύ φορές. Εάν το m παραλείπεται, τότε εννοείται το άπειρο (∞). Στην περίπτωση που το n είναι ίσο με το m, τότε χρησιμοποιείται η σύνταξη: {n}.

Οι περισσότερο συχνοί (κατά τη χρήση) συνδυασμοί είναι οι (n=1, m=∞), (n=0, m=∞), (n=0, m=1). Γι’ αυτούς τους συνδυασμούς που είναι συχνοί, υπάρχουν οι συντομογραφίες "+", "*" και "?", όπως περιγράφονται στον .

Όταν ο τελεστής επανάληψης είναι ένας μόνο αριθμός, παράδειγμα {5}, στην πραγματικότητα αποτελεί απλά συντομογραφία της κανονικής έκφρασης. Αντί, λοιπόν, να γράψουμε "ΑΒΒΒΒΒC", γράφουμε "ΑΒ{5}C". Κάτι τέτοιο δεν αυξάνει την πολυπλοκότητα ελέγχου της κανονικής έκφρασης.

Στην άλλη περίπτωση, αν ο τελεστής επανάληψης περιέχει εύρος, παράδειγμα {2,7}, τότε δημιουργεί πολλές εναλλακτικές κανονικές εκφράσεις. Έτσι το "ΑΒ{2,7}C", είναι ισοδύναμο με "ΑΒΒC|ABBBC|ABBBBC|ABBBBB|ABBBBBBC|ABBBBBBBC". Αυτό στην ουσία αυξάνει πολύ την πολυπλοκότητα ελέγχου, αφού θα πρέπει να ελεγχθούν 5 κανονικές εκφράσεις αντί για μια. Προφανώς, οι βιβλιοθήκες κανονικών εκφράσεων εμπεριέχουν βελτιστοποιήσεις, ώστε να αποφεύγονται περιττοί έλεγχοι. Παρόλα αυτά, υπάρχει αυξημένη πολυπλοκότητα.

Ειδικά, αν περιλαμβάνεται στην κανονική έκφραση ο τελεστής "*", όπου δεν υπάρχει άνω όριο, δημιουργούνται ιδιαίτερα πολλοί δυνατοί συνδυασμοί. Ένα μικρό παράδειγμα παρουσιάζουμε στο , για να δείξουμε την αύξηση πολυπλοκότητας. Στο συγκεκριμένο παράδειγμα, οι δυνατοί συνδυασμοί που ελέγχονται είναι σχετικά λίγοι, διότι η κανονική έκφραση είναι απλή (εφαρμόζεται ο τελεστής επανάληψης σε χαρακτήρα και όχι σε κλάση ή "."). Επιπλέον, η συμβολοσειρά ελέγχου είναι μικρή. Παρόλα αυτά, όπως φαίνεται στο , απαιτούνται τουλάχιστον 14 έλεγχοι.

Η χρήση των τελεστών επανάληψης αυξάνει ιδιαίτερα τον χρόνο ελέγχου. Για αυτό, θα πρέπει να γίνεται προσεκτική «κατασκευή» μιας κανονικής έκφρασης, ώστε να μην δημιουργεί άχρηστους συνδυασμούς, ιδίως εάν πρόκειται να ελεγχθεί σε μεγάλο όγκο δεδομένων (πχ. log files).

Στον , παρουσιάζονται μερικά παραδείγματα με τον τελεστή επανάληψης. Ιδιαίτερη προσοχή θα πρέπει να δοθεί στα τρία τελευταία παραδείγματα. Στο [AB]{2,3} η επανάληψη αφορά την κλάση χαρακτήρων, αλλά όχι τον χαρακτήρα που ταίριαξε. Ομοίως και στις επόμενες δυο περιπτώσεις. Στην τελευταία περίπτωση, οι συνδυασμοί που θα ταιριάξουν είναι οι:

1. 000,
2. 001,
3. 010,
4. 011,
5. 100,
6. 101,
7. 110,
8. 111,

δηλαδή όλοι οι δυνατοί συνδυασμοί. Αν θα θέλαμε μια κανονική έκφραση η οποία να ταιριάξει μόνο στους συνδυασμούς 000 ή 111 ή 555 ή 777, τότε το [0157]{3} δεν είναι η σωστή λύση. Θα δούμε στην ποιος είναι ο σωστός και μοναδικός τρόπος να το πετύχουμε αυτό.

Τελεστής Ομαδοποίησης (Group Operator)

Με την ομαδοποίηση ενοποιούμε ένα σύνολο από atoms, ώστε να εφαρμοστεί στο σύνολο ένας τελεστής (επανάληψης ή εναλλαγής). Οι παρενθέσεις χρησιμοποιούνται σχεδόν όπως και στις μαθηματικές εκφράσεις. Έτσι, το (ΑΒ){2} σημαίνει ότι πρέπει να εφαρμοστεί ο τελεστής επανάληψης στο τμήμα "ΑΒ". Άρα, ουσιαστικά το προηγούμενο είναι ισοδύναμο με ΑΒΑΒ.

Αντίστοιχα τπ A(AB){1,3}XY είναι ισοδύναμο με:

• AABXY
• AABABXY
• AABABABXY

δηλαδή, τελικά με: AABXY|AABABXY|AABABABXY

Μπορεί να υπάρχει και φωλευμένη ομαδοποίηση, όπως για παράδειγμα Α((ΧΖ){2}Ρ{3}){3}. Το προηγούμενο είναι ισοδύναμο με: A(XZXZPPP){3} και τελικά ισοδύναμο με AXZXZPPPXZXZPPXZXZPP.

Όταν χρησιμοποιείται η ομαδοποίηση για τον τελεστή εναλλαγής, χρησιμοποιείται, για να ομαδοποιηθούν οι εναλλακτικές επιλογές. Έτσι, η κανονική έκφραση (This|That) is (a|an|the) θα ταιριάξει στους συνδυασμούς που παρουσιάζονται στον .

Αναφορά Πίσω (Back Reference)

Με τη χρήση παρενθέσεων και την ομαδοποίηση δίνεται συγχρόνως και «εντολή αποθήκευσης σε αποταμιευτή» (buffer) της συμβολοσειράς που ταίριαξε στο τμήμα της κανονικής έκφρασης που είναι στις παρενθέσεις. Υπάρχουν εννιά αποταμιευτές (buffers) που μπορούν να χρησιμοποιηθούν για αποθήκευση. Οι αποταμιευτές αυτοί συμβολίζονται με \1, \2, \3, ..., \9 και χρησιμοποιούνται όπως οι μεταβλητές. Με τις παρενθέσεις γεμίζουν δεδομένα, με την αναφορά (πχ: \2) χρησιμοποιούνται τα δεδομένα. Όσες παρενθέσεις υπάρχουν, τόσοι αποταμιευτές γεμίζουν. Οι χαρακτήρες που θα ταιριάξουν στην πρώτη παρένθεση θα αποθηκευτούν στο "\1", αυτά που θα ταιριάξουν στη δεύτερη παρένθεση στο "\2" κ.ο.κ. Στον παρουσιάζονται μερικά παραδείγματα χρήσης της αναφοράς πίσω.

Η αναφορά πίσω (back reference) και οι αποταμιευτές \1, \2,...\9 είναι ο μόνος τρόπος, ώστε σε μια κανονική έκφραση να διατυπώσουμε την έννοια της επανάληψης κάποιων χαρακτήρων.

Ειδικοί χαρακτήρες και ο χαρακτήρας «\»

Ο χαρακτήρας «\» (backslash) χρησιμοποιείται είτε για να αποδώσει ειδική σημασία στον χαρακτήρα που ακολουθεί είτε για να αναιρέσει την ειδική σημασία του (αν είναι ειδικός χαρακτήρας). Έτσι, σε μια κανονική έκφραση, αν πρέπει να συμπεριληφθεί ο χαρακτήρας "*" και όχι ο τελεστής "*", θα πρέπει να ακυρωθεί η ειδική του σημασία με το "\". Άρα, * σημαίνει τελεστής επανάληψης, ενώ το \* σημαίνει ο χαρακτήρας "*".

Από την άλλη μεριά, το "\" χρησιμοποιείται και για να προσδώσει ειδική σημασία στον χαρακτήρα που ακολουθεί όπως οι περιπτώσεις \<, \1, \2, ... κ.ά.

Σε αυτό το σημείο θα πρέπει να παρατηρηθεί πως κάποιοι χαρακτήρες αποκτούν ή χάνουν ειδική σημασία ανάλογα με το σημείο που βρίσκονται μέσα στην κανονική έκφραση. Για παράδειγμα, αναφέραμε για τον "^" ότι σημαίνει αρχή συμβολοσειράς. Επίσης, σημαίνει άρνηση, όταν εμφανίζεται μέσα σε κλάση χαρακτήρων. Αυτές οι δυο ειδικές λειτουργίες ισχύουν μόνο σε συγκεκριμένες θέσεις. Για παράδειγμα, το "^" σημαίνει αρχή συμβολοσειράς μόνο όταν εμφανίζεται στην αρχή της κανονικής έκφρασης. Αν εμφανίζεται σε οποιοδήποτε άλλο σημείο, είναι απλά ο χαρακτήρας "^". Αντίστοιχα, μέσα σε κλάση χαρακτήρων σημαίνει άρνηση μόνο όταν βρίσκεται αμέσως μετά το άγκιστρο που ανοίγει. Παράδειγμα [^A] σημαίνει ένας οποιοσδήποτε χαρακτήρας εκτός από τον "Α", ενώ [A^] σημαίνει ο χαρακτήρας "Α" ή ο "^".

Σε όλες τις προηγούμενες περιπτώσεις, εαν θέλουμε να αναιρέσουμε την ειδική σημασία ενός χαρακτήρα, χρησιμοποιούμε τον χαρακτήρα "\". Επίσης, ο χαρακτήρας "\" σε πολλές περιπτώσεις προσδίδει ειδική σημασία στον χαρακτήρα που ακολουθεί. Αυτό συνηθίζεται στις περισσότερες γλώσσες προγραμματισμού. Για παράδειγμα, στην C και στην Java είναι χαρακτηριστική η χρήση του \n το οποίο σημαίνει αλλαγή γραμμής (new line). Ο ίδιος κανόνας επεκτείνεται και στις κανονικές εκφράσεις, με διαφορετικά βέβαια σύμβολα. Στον pinaka παρουσιάζονται μερικές περιπτώσεις χρήσεις του "\" στις Κανονικές Εκφράσεις.

Σύνολα κανονικών εκφράσεων

Υπάρχουν διάφορα Σύνολα Κανονικών Εκφράσεων και όχι σε όλα συμβατά μεταξύ τους. Τα δυο βασικότερα Σύνολα Κανονικών Εκφράσεων είναι αυτά που ορίζονται από το πρότυπο της IEEE POSIX και είναι τα:

• Βασικές Κανονικές Εκφράσεις (Basic Regular Expressions) και συμβολίζεται ως BRE.
• Εκτεταμένες Κανονικές Εκφράσεις (Extended Regular Expressions) και συμβολίζεται ως ERE.

Τα δυο παραπάνω σύνολα κανονικών εκφράσεων μοιάζουν πάρα πολύ μεταξύ τους, όμως διαφέρουν στους συμβολισμούς που αναφέρονται στον . Οι τελεστές επανάληψης ?, + και { } καθώς και η ομαδοποίηση και η εναλλαγή απαιτούν τον χαρακτήρα "\". Στον επιπλέον παρουσιάζονται τρία παραδείγματα διατύπωσης μιας κανονικής έκφρασης σε ERE και η ακριβώς αντίστοιχη σε BRE. Είναι εμφανές ότι δεν υπάρχουν ουσιαστικές διαφορές.

Επίσης, ολοκληρωμένο σύνολο κανονικών εκφράσεων ορίζεται και στη γλώσσα perl, καθότι οι κανονικές εκφράσεις είναι βασικό συστατικό της γλώσσας perl. Οι κανονικές εκφράσεις της perl είναι πάρα πολύ κοντά στο σύνολο ERE.

Εκτός αυτών η κάθε γλώσσα προγραμματισμού ορίζει και χρησιμοποιεί το δικό της σύνολο κανονικών εκφράσεων και τη δική της βιβλιοθήκη. Όλες οι νέες γλώσσες προγραμματισμού (όπως η php και η javascript) υποστηρίζουν κανονικές εκφράσεις. Μάλιστα η php είχε αναπτύξει δικό της μηχανισμό κανονικών εκφράσεων, αλλά πλέον καταργήθηκε και χρησιμοποιείται ο μηχανισμός της perl από τη βιβλιοθήκη preg.

Η οικογένεια εντολών grep

Το όνομα των εντολών προέρχεται από τα αρχικά Global Regular Expressions Print. Οι εντολές αυτές [] χρησιμοποιούνται για την αναζήτηση μιας κανονικής έκφρασης μέσα σε αρχεία δεδομένων ή σε ροές δεδομένων (data streams). Η κανονική συμπεριφορά των εντολών αυτών είναι να εμφανίζουν τις γραμμές του αρχείου που ταιριάζουν στην κανονική έκφραση που δόθηκε. Η γενική σύνταξη της εντολής grep αλλά και των συγγενικών εντολών είναι:

grep [OPTIONS] regexp [files]

Οι βασικότερες παραλλαγες της grep είναι οι:

• fgrep: Fast grep. Δεν υποστηρίζει κανονικές εκφράσεις, αλλά μόνο αναζήτηση σταθερών συμβολοσειρών. Είναι η πιο γρήγορη από όλες της οικογενείας εξαιτίας των λίγων δυνατοτήτων της^*. Μπορεί να εκτελεστεί και ως grep -F.
• grep: Η βασική εντολή της οικογένειας. Υποστηρίζει το BRE.
• egrep: Extended grep. Υποστηρίζει το ERE. Μπορεί να εκτελεστεί και ως grep -E.
• rgrep: Recursive grep. Κάνει αναδρομική αναζήτηση σε αρχεία και καταλόγους. Είναι συντόμευση για τη σημαία "-r" της grep και μπορεί να εκτελεστεί και ως: grep -r.

Για τις ανάγκες του μαθήματος και για εκπαιδευτικούς λόγους προτείνεται να χρησιμοποιείτε την egrep, διότι το ERE είναι πιο απλό στη διατύπωση, καθώς απαιτεί λιγότερο τη χρήση του χαρακτήρα "\". Απαιτείται όμως προσοχή όταν χρησιμοποιείται, ιδίως όταν η αναζήτηση γίνεται σε πολλά ή πολύ μεγάλα αρχεία, διότι, όπως έγινε σαφές νωρίτερα στο παρόν κεφάλαιο, ο έλεγχος μιας περίπλοκης κανονικής έκφρασης είναι μια διαδικασία απαιτητική σε υπολογιστική ισχύ.

Στον αναφέρονται οι περισσότερο συχνές σημαίες των εντολών grep. Για περισσότερες λειτουργίες και λεπτομέρειες μπορείτε να ανατρέξετε στο εγχειρίδιο χρήσης της εντολής (man grep).

Ακολουθούν μερικά παραδείγματα χρήσης. Στο παρακάτω παράδειγμα γίνεται αναζήτηση της λέξης "unix" αγνοώντας τον διαχωρισμό κεφαλαίων-πεζών χαρακτήρων στο αρχείο με όνομα file. Σε αυτήν την περίπτωση μπορεί να χρησιμοποιηθεί οποιαδήποτε εντολή της οικογένειας grep. Εφόσον, όμως, δεν αναζητείται κανονική έκφραση, αλλά μια σταθερή ακολουθία χαρακτήρων, προτειμάται η εντολή fgrep.

asidirop@dellpc:/tmp$ grep -i unix file 
1 Εισαγωγή στα Λειτουργικά Συστήματα και το Unix
ενδιαφέρεται να μάθει για τα βασικά στοιχεία του Λειτουργικού Συστήματος UNIX ή 
προγραμματισμού στο UNIX. Στόχος του μαθήματος είναι οι φοιτητές να μελετήσουν 
asidirop@dellpc:/tmp$ fgrep -i unix file 
1 Εισαγωγή στα Λειτουργικά Συστήματα και το Unix
ενδιαφέρεται να μάθει για τα βασικά στοιχεία του Λειτουργικού Συστήματος UNIX ή 
προγραμματισμού στο UNIX. Στόχος του μαθήματος είναι οι φοιτητές να μελετήσουν 

Στο επόμενο παράδειγμα, αναζητούμε τη λέξη 'apa' μέσα στο αρχείο /etc/passwd. Στο αποτέλεσμα που παρουσιάζουμε έχουμε παραλείψει μερικά στοιχεία καθώς και αρκετές γραμμές αποτελέσματος. Η επόμενη εντολή, στην οποία αναζητείται και η αρχή συμβολοσειράς, θα εμφανίσει μόνο τις γραμμές που ξεκινούν από 'apa'. Για την περιγραφή της μορφής του αρχείου /etc/passwd, δείτε το .

asidirop@aetos:~$ grep 'apa' /etc/passwd
anpapad:x:x:x:Papadopoulos Anastasios:/home/student/x/anpapad:/bin/bash
anpap:x:x:x:Papagiannakis Anastasios:/home/student/x/anpap:/bin/bash
antpapad:x:x:x:Papadopoulos Antonios:/home/student/e/antpapad:/bin/bash
apamp:x:x:x:Ampatzoglou Apostolos:/home/staff/ektaktoi/apamp:/bin/bash
apapadop:x:x:x:Papadopoulos Anastasios:/home/student/x/apapadop:/bin/bash
apapado:x:x:x:Papadopoulos Alexandros:/home/student/x/apapado:/bin/bash
apapad:x:x:x:Papadopoulos Aristeidis:/home/student/x/apapad:/bin/bash
asidirop@aetos:~$ grep '^apa' /etc/passwd
apamp:x:x:x:Ampatzoglou Apostolos:/home/staff/ektaktoi/apamp:/bin/bash
apapadop:x:x:x:Papadopoulos Anastasios:/home/student/x/apapadop:/bin/bash
apa:x:x:x:Papadopoulos Alexandros:/home/student/x/apapado:/bin/bash

Oι παρακάτω εντολές αναζητούν στο αρχείο /etc/passwd τον χρήστη που το όνομα χρήστη (username) ξεκινά με 'asidiro'. Εντοπίζονται δυο γραμμές στο αρχείο. Αν θέλαμε να βρούμε τον χρήστη με ακριβώς username 'asidiro', τότε θα έπρεπε με κάποιον τρόπο να εξαιρεθεί από τα αποτελέσματα η γραμμή που ξεκινά με 'asidirop', δηλαδή η γραμμή που μετά από τη συμβολοσειρά αναζήτησης περιέχει ακόμη ένα γράμμα. Αυτό θα μπορούσαμε να το πετύχουμε με την επόμενη εντολή, δηλαδή μετά από το 'asidiro' να ακολουθεί κάτι που δεν είναι [a-z]. Αν υπήρχε, όμως, γραμμή που ξεκινούσε με 'asidiro5' θα την εμφάνιζε. Εφόσον γνωρίζουμε ότι ο τερματισμός του ονόματος χρήστη καθορίζεται με τον χαρακτήρα ":", ο πλέον ασφαλής τρόπος είναι να χρησιμοποιηθεί η τελευταία εντολή.

asidirop@aetos:~$ grep '^asidiro' /etc/passwd
asidirop:x:x:x:Sidiropoulos Antonis,,,:/home/staff/it/asidirop:/bin/bash
asidiro:x:x:x:Sidiropoulos Alexios:/home/student/xx/asidiro:/bin/bash
asidirop@aetos:~$ grep '^asidiro[^a-z]' /etc/passwd
asidiro:x:x:x:Sidiropoulos Alexios:/home/student/xx/asidiro:/bin/bash
asidirop@aetos:~$ grep '^asidiro:'  /etc/passwd
asidiro:x:x:x:Sidiropoulos Alexios:/home/student/xx/asidiro:/bin/bash

Κανονικές Εκφράσεις με grep και οι χαρακτήρες μπαλαντέρ του κελύφους

Οι κανονικές εκφράσεις μοιάζουν με τα μπαλαντέρ που χρησιμοποιεί το κέλυφος για το ταίριασμα των ονομάτων αρχείων. Όμως διαφέρουν και στη χρήση και στη σύνταξη. Τα μπαλαντέρ ερμηνεύονται από το κέλυφος και ταιριάζουν σε ονόματα αρχείων, ενώ οι κανονικές εκφράσεις συνήθως πρέπει να ερμηνευτούν από εντολές (πχ: grep).

Αρκετοί από τους χαρακτήρες που χρησιμοποιούνται σε μια κανονική έκφραση είναι ειδικοί χαρακτήρες και για το κέλυφος, όπως οι "*", "[]", "?". Όμως, υπάρχει διαφορετική σημασία και χρήση των χαρακτήρων αυτών. Αν το κέλυφος αναγνωρίσει σε μια γραμμή εντολής κάποιον ειδικό χαρακτήρα, θα προσπαθήσει να τον ερμηνεύσει. Αυτή η ενέργεια, όμως, δεν είναι επιθυμητή στην περίπτωση που η γραμμή εντολής περιέχει μια Κανονική Έκφραση, η οποία θέλουμε να ερμηνευτεί από την εντολή (πχ. grep). Γι’ αυτόν τον λόγο, θα πρέπει να χρησιμοποιούνται τα εισαγωγικά, ώστε να αποτραπεί το κέλυφος από το να ερμηνεύσει τους ειδικούς χαρακτήρες.

Στο παρακάτω παράδειγμα εμφανίζονται αρχικά τα περιεχόμενα του αρχείου file3. Η εντολή grep 'fi*t' file3 θα δώσει δυο γραμμές αποτελέσματος, δηλαδή τις γραμμές που περιέχουν τον χαρακτήρα "f", μετά το "i" μηδέν ή περισσότερες φορές και έπειτα το "t". Στην επόμενη εντολή, όπου δεν χρησιμοποιούνται εισαγωγικά, η εντολή grep δεν εμφανίζει κανένα αποτέλεσμα. Γιατί;

asidirop@dellpc:~/tmp/unix$ ls -l
total 40
-rw-r--r-- 1 asidirop asidirop   28 Μάρ  19  2012 f*
-rw-r--r-- 1 asidirop asidirop   17 Μάρ  19  2012 file
-rw-r--r-- 1 asidirop asidirop   32 Μάρ  19  2012 -file
-rw-r--r-- 1 asidirop asidirop   77 Μάρ  12  2012 file1.txt
-rw-r--r-- 1 asidirop asidirop  101 Μάρ  12  2012 file2.txt
-rw-r--r-- 1 asidirop asidirop  274 Απρ   4  2012 file3
-rw-r--r-- 1 asidirop asidirop 3080 Μάρ  12  2012 image1.jpg
-rw-r--r-- 1 asidirop asidirop   17 Μάρ  19  2012 test
-rw-r--r-- 1 asidirop asidirop   35 Μάρ  19  2012 test file
asidirop@dellpc:~/tmp/unix$ cat file3
All characters except the 
listed special characters 
match a single instance 
of themselves. { and } are literal 
characters, unless they're part 
of a valid regular expression 
token (e.g. the {n} quantifier).
this line must match fiiiitttt
this line must match also fttt
asidirop@dellpc:~/tmp/unix$ grep 'fi*t' file3
this line must match fiiiitttt
this line must match also fttt
asidirop@dellpc:~/tmp/unix$ grep fi*t file3
asidirop@dellpc:~/tmp/unix$ 

Aν δοκιμάσουμε να δώσουμε όλη την τελευταία εντολή ως όρισμα στην εντολή echo, η echo απλά θα μας εμφανίσει τη συμβολοσειρά που της δόθηκε ως όρισμα.

asidirop@dellpc:~/tmp/unix$ echo grep fi*t file3
grep file1.txt file2.txt file3
asidirop@dellpc:~/tmp/unix$ 

Βλέπουμε, λοιπόν, παρακάτω ότι η echo θα μας εμφανίσει: grep file1.txt file2.txt file, το οποίο σημαίνει ότι το κέλυφος ερμήνευσε το fi*t και το μετέφρασε στα ονόματα αρχείων file1.txt και file2.txt. Έτσι τελικά, στην εντολή grep δίνονται τρία ορίσματα. Το πρώτο όρισμα (εφόσον δεν είναι σημαία) θεωρεί η grep ότι είναι η κανονική έκφραση προς αναζήτηση. Δηλαδή, στην grep δόθηκε ως κανονική έκφραση το "file1.txt". Όλα τα υπόλοιπα ορίσματα θα εκφράζουν ονόματα αρχείων. Συνεπώς, η grep αυτό που θα κάνει είναι να αναζητήσει την κανονική έκφραση "file1.txt" μέσα στα αρχεία file2.txt και file. Αυτή η ενέργεια απέχει κατά πολύ από την ενέργεια που θα εκτελεστεί χρησιμοποιώντας τα εισαγωγικά.

Ασκήσεις για εξάσκηση

Στόχος

Εξάσκηση με τις κανονικές εκφράσεις και την εντολή grep (egrep).

Άσκηση 1

Στο δοκιμάστε διάφορες κανονικές εκφράσεις. Επίσης, δοκιμάστε τις κανονικές εκφράσεις "to", "t.n" και "a[o-t].".

Εξάσκηση στο Τερματικό

Δημιουργήστε μέσα από ένα τερματικό τα τρία παραπάνω αρχεία χρησιμοποιώντας τον vi. Δοκιμάστε με την εντολή grep, αναζήτηση του "to" στο file1, του "t.n" στο file2 και τουλάχιστον"a[o-t]." στο file3.

Αν χρησιμοποιήσετε στην grep τη σημαία "--color", τότε θα χρωματίζει τα σημεία κάθε γραμμής που ταίριαξαν στην κανονική έκφραση (όπως στο διαδραστικό σχήμα). Παράδειγμα:

grep --color 'to' file1

Άσκηση 2

Εξάσκηση στο τερματικό

Δημιουργήστε μέσα από ένα τερματικό το αρχείο “telephones” χρησιμοποιώντας τον vi. Χρησιμοποιήστε την εντολή egrep, για να βρείτε τις γραμμές που αντιστοιχούν στις παραπάνω ερωτήσεις. Για τις ερωτήσεις 5 και 7 χρησιμοποιήστε τη σημαία -v της grep, ώστε να απλοποιήσετε την κανονική έκφραση.

Άσκηση 3

Πειραματιστείτε και δοκιμάστε τις παρακάτω κανονικές εκφράσεις. Βρείτε σε τι αντιστοιχεί η κάθε μια:

1. 'a?'
2. '(a|b)+'
3. '.{2}'
4. '.{2,}'
5. '(.)\1'
6. '(.).*\1'
7. '(..).*\1'
8. '(.{3}).*\1'

Εξάσκηση στο τερματικό

Δημιουργήστε μέσα από ένα τερματικό το αρχείο “file_test” χρησιμοποιώντας τον vi με τα παραπάνω περιεχόμενα. Χρησιμοποιήστε τις παραπάνω κανονικές εκφράσεις με την εντολή egrep, για να βρείτε τις γραμμές που αντιστοιχούν στις παραπάνω ερωτήσεις.

Άσκηση 4

Εξάσκηση στο Τερματικό

Δημιουργήστε μέσα από ένα τερματικό το αρχείο “file4” χρησιμοποιώντας τον vi με τα παραπάνω περιεχόμενα. Χρησιμοποιήστε τις κανονικές εκφράσεις που βρήκατε με την εντολή egrep για να βρείτε τις γραμμές που αντιστοιχούν στις παραπάνω ερωτήσεις.

Άσκηση 5

ls -l | grep '^d'

asidirop@aetos:~$ cd /tmp
asidirop@aetos:/tmp$ ls -l
total 116
-rw------- 1 kvisnia  x1415    57 Μάρ  23 21:11 adminer.invalid
-rw-r--r-- 1 gpseirak x1415   158 Μάρ  20 22:08 ankanogradiel
-rw-r--r-- 1 antomi   x1415  1737 Μάρ  20 18:40 Domi
-rw-r--r-- 1 asidirop it       17 Μάρ  30 17:09 file1
-rw-r--r-- 1 asidirop it       25 Μάρ  30 17:09 file2
-rw-r--r-- 1 asidirop it       22 Μάρ  30 17:09 file3
-rw-r--r-- 1 aspyros  x1415    28 Μάρ  21 00:07 first
-rw-r--r-- 1 asidirop it    17686 Μάρ  30 17:34 index.html
-rw-r--r-- 1 kxouvero x1415    93 Μάρ  25 12:01 JustATest
-rw-r--r-- 1 gkintzon x1415    41 Μάρ  20 21:13 kintzovi
drwxr-xr-x 2 asidirop it     4096 Μάρ  27 15:39 lab5
drwxr-xr-x 2 malexiou e1314  4096 Μάρ  27 12:34 lab5m
drwxr-xr-x 2 ekastia  e1314  4096 Μάρ  27 12:44 lab5x
drwx------ 2 root     root  16384 Ιαν  31  2014 lost+found
-rw-r--r-- 1 arika    x1314    58 Μάρ  25 21:59 TEST
asidirop@aetos:/tmp$ ls -l | grep '^d'
drwxr-xr-x 2 asidirop it     4096 Μάρ  27 15:39 lab5
drwxr-xr-x 2 malexiou e1314  4096 Μάρ  27 12:34 lab5m
drwxr-xr-x 2 ekastia  e1314  4096 Μάρ  27 12:44 lab5x
drwx------ 2 root     root  16384 Ιαν  31  2014 lost+found
asidirop@aetos:/tmp$ 

Δημιουργήστε σε έναν κατάλογο της επιλογής σας τα αρχεία f1, f2, f3, f4, f5, f6 ,f7 με τα εξής δικαιώματα:

• f1, 757
• f2, 313
• f3, 010
• f4, 642
• f5, 551
• f6, 133
• f7, 111

Με χρήση της εντολής ls -l και διασωλήνωση με egrep να βρείτε τα αρχεία όπου:

1. Ο ιδιοκτήτης (user) και οι υπόλοιποι (others) έχουν ακριβώς τα ίδια δικαιώματα.
2. Ο ιδιοκτήτης (user), η ομάδα (group) και οι υπόλοιποι (others) έχουν ακριβώς τα ίδια (μεταξύ τους) δικαιώματα.
3. Ο ιδιοκτήτης (user), η ομάδα (group) και οι υπόλοιποι (others) έχουν τα ίδια δικαιώματα (μεταξύ τους) για write και execute.
4. Ο ιδιοκτήτης (user), η ομάδα (group) και οι υπόλοιποι (others) έχουν τα ίδια δικαιώματα (μεταξύ τους) για write.
5. Ο ιδιοκτήτης (user), η ομάδα (group) και οι υπόλοιποι (others) έχουν τα ίδια δικαιώματα (μεταξύ τους) για read και execute.
6. Ο ιδιοκτήτης (user) και οι υπόλοιποι (οthers) έχουν τα ίδια δικαιώματα (μεταξύ τους) για read και execute.

Εναλλακτικά, δοκιμάστε τις κανονικές εκφράσεις στο παρακάτω περιβάλλον ().

Άσκηση 6

Συνδεθείτε στον υπολογιστή aetos (ή σε όποιο σύστημα με πολλούς χρήστες έχετε πρόσβαση). Θεωρήστε ότι στο 5^ο πεδίο του αρχείου /etc/passwd βρίσκεται το ονοματεπώνυμο χρήστη με πρώτο το «Επώνυμο»«κενό διάστημα»«Όνομα». Το πρώτο πεδίο περιέχει το όνομα χρήστη (username). Τα πεδία μεταξύ τους διαχωρίζονται με ":". Ελέγχοντας αυτό το αρχείο και κάνοντας χρήση της εντολής egrep (χρησιμοποιήστε την επιλογή -i, για να μη γίνεται διάκριση μεταξύ κεφαλαίων και πεζών), να βρείτε όλους τους χρήστες του συστήματος που:

1. Τουλάχιστον τα 7 πρώτα γράμματα του επιθέτου τους αποτελούν μέρος και του ονόματος χρήστη (username) τους.
2. Τουλάχιστον τα 4 πρώτα γράμματα του επιθέτου τους και τα 4 πρώτα γράμματα του ονόματός τους αποτελούν μέρος και του ονόματος χρήστη (username) τους
3. Τουλάχιστον τα 5 πρώτα γράμματα του επιθέτου τους και τα 5 πρώτα γράμματα του ονόματός τους αποτελούν μέρος και του ονόματος χρήστη (username) τους

Σημείωση: Για τις περιπτώσεις 2 και 3 θα πρέπει να συνδυάσετε δυο εντολές egrep, παράδειγμα:

egrep '^a' file1 | egrep 'b$'

Αναφορές