Ποσοδείκτες

Ένας ποσοδείκτης λέει «αυτό το προηγούμενο πράγμα, N φορές». Συνδέεται με έναν μεμονωμένο χαρακτήρα, μια κλάση χαρακτήρων, ή μια ομάδα, και μετατρέπει μια αντιστοιχία ενός χαρακτήρα σε αντιστοιχία πολλών.

/a*/;       # zero or more 'a'
/\d+/;      # one or more digits
/colou?r/;  # 'color' or 'colour'

Οι βασικοί ποσοδείκτες

Ποσοδείκτης	Σημασία
a?	0 ή 1 φορά
a*	0 ή περισσότερες φορές
a+	1 ή περισσότερες φορές
a{n}	ακριβώς n φορές
a{n,m}	τουλάχιστον n, το πολύ m
a{n,}	τουλάχιστον n
a{,m}	το πολύ m

Τα *, + και ? είναι ακριβή συνώνυμα των {0,}, {1,} και {0,1}. Οι μορφές με άγκιστρα χρησιμοποιούνται κυρίως όταν τα n και m είναι συγκεκριμένοι μικροί αριθμοί· οι γυμνές μορφές διαβάζονται πιο φυσικά για «οποιοδήποτε πλήθος από αυτά».

Τα άνω όρια n και m δεν μπορούν να υπερβούν μια ενσωματωμένη στη μηχανή σταθερά (συνήθως 65534 — το πραγματικό όριο εμφανίζεται στο σφάλμα αν το υπερβείτε). Για «οποιονδήποτε λογικό αριθμό» αυτό είναι υπεραρκετό· μοτίβα που χτυπούν στο όριο είναι συνήθως αυτόματα παραγόμενα, όχι χειρόγραφα.

Οι λευκοί χαρακτήρες μέσα στα {…} είναι ανεκτοί αλλά όχι υποχρεωτικοί. Τα a{2, 4} και a{2,4} είναι ταυτόσημα.

/[a-z]+\s+\d*/;            # word, spaces, any number of digits
/y(es)?/i;                 # 'y', 'Y', 'yes', or 'YES'
$year =~ /^\d{2,4}$/;      # 2, 3, or 4 digits
$year =~ /^\d{4}$|^\d{2}$/;# better: exactly 2 or exactly 4

Ο ποσοδείκτης εφαρμόζεται στο άτομο αμέσως πριν από αυτόν:

• ab? — a και μετά προαιρετικό b.

• (ab)? — προαιρετικό ab.

• [ab]? — προαιρετικό a ή b.

Πρώτα ομάδα ή κλάση, μετά ποσοδείκτης.

Άπληστοι από προεπιλογή

Οι βασικοί ποσοδείκτες είναι άπληστοι: αρπάζουν όσο τους επιτρέπει η συμβολοσειρά και υποχωρούν μόνο αν το υπόλοιπο μοτίβο δεν μπορεί να ταιριάξει αλλιώς. Σκεφτείτε:

my $x = "the cat in the hat";
$x =~ /^(.*)(cat)(.*)$/;
# $1 = 'the '
# $2 = 'cat'
# $3 = ' in the hat'

Εδώ το .* στη μέση δουλεύει όπως θα περιμένατε — σταματά στο cat επειδή το cat είναι το μόνο σημείο όπου το υπόλοιπο μοτίβο μπορεί να ταιριάξει. Τώρα συγκρίνετε:

$x =~ /^(.*)(at)(.*)$/;
# $1 = 'the cat in the h'
# $2 = 'at'
# $3 = ''

Υπάρχουν δύο σημεία όπου εμφανίζεται το at — στο τέλος του cat και στο τέλος του hat. Το πρώτο .* αρπάζει όσο το δυνατόν περισσότερα αφήνοντας ακόμη χώρο για το at κάπου, οπότε αρπάζει μέχρι το τελευταίο at.

Ο άπληστος υποχωρεί μόνο όσο πρέπει

"about 24 characters long" =~ /^.*([0-9]+)/;
# $1 = '4'

Το άπληστο .* ταίριαξε πρώτα ολόκληρη τη συμβολοσειρά. Για να ταιριάξει το [0-9]+, έπρεπε να επιστρέψει αρκετούς χαρακτήρες ώστε να αποκαλύψει τουλάχιστον ένα ψηφίο. Επέστρεψε ακριβώς έναν, αφήνοντας το 4 για σύλληψη. Η διαίσθηση ότι το .* «σταματά στα ψηφία» είναι λανθασμένη — αρπάζει τα πάντα, και μετά η μηχανή ρωτά πόσο λίγα μπορεί να επιστρέψει.

Απληστία έναντι αντιστοίχισης

Η μηχανή δεν ταιριάζει πάντα με ό,τι υποδεικνύει η άπληστη ερμηνεία:

"27.625" =~ /(\d\d)([1-9]?)(\d+)/;
# $1 = '62'
# $2 = ''
# $3 = '5'

Η πρώτη απόπειρα αποτυγχάνει: το \d\d μπορεί να ταιριάξει με 27, αλλά ο επόμενος χαρακτήρας είναι ., οπότε καμία διακλάδωση του [1-9]? δεν αφήνει το \d+ να προχωρήσει. Ο κανόνας «κερδίζει η προγενέστερη θέση» μετακινεί την αρχή μέχρι το \d\d να προσγειωθεί στο 62. Εκεί, το [1-9]? δοκίμασε άπληστα το 5, αλλά τότε το \d+ δεν είχε εναπομένον ψηφίο — οπότε επέστρεψε το 5 και πήγε σε κενό, αφήνοντας το 5 για το \d+. Οι προαιρετικοί ποσοδείκτες προτιμούν τη μακρύτερη εναλλακτική (παίρνοντας τον χαρακτήρα) αλλά θα υποχωρήσουν αν χρειαστεί· ο κανόνας ταξινόμησης «κερδίζει η προγενέστερη θέση, μετά η μακρύτερη σε εκείνη τη θέση» περιορίζει μόνο ολόκληρη την αντιστοιχία, όχι τις επιμέρους συλλήψεις της.

Αρχές της αντιστοίχισης

Με άπληστους ποσοδείκτες, η μηχανή ακολουθεί τέσσερις αρχές με σειρά:

1. Κερδίζει η προγενέστερη θέση. Ολόκληρο το μοτίβο δοκιμάζεται ξεκινώντας από τη θέση 0, μετά τη 1, μετά τη 2, μέχρι να βρεθεί αντιστοιχία. Η προγενέστερη θέση εκκίνησης πάντα κερδίζει.

2. Κερδίζει η πιο αριστερή εναλλακτική (σε a|b|c).

3. Οι άπληστοι ποσοδείκτες αρπάζουν όσο το δυνατόν περισσότερα ενώ εξακολουθούν να επιτρέπουν στο υπόλοιπο μοτίβο να ταιριάξει.

4. Ο πιο αριστερός άπληστος ποσοδείκτης παίρνει προτεραιότητα. Αν δύο .* συναγωνίζονται για τους ίδιους χαρακτήρες, το πρώτο τους παίρνει.

Παραδείγματα:

my $x = "The programming republic of Perl";

$x =~ /^(.+)(e|r)(.*)$/;
# $1 = 'The programming republic of Pe'
# $2 = 'r'
# $3 = 'l'
# .+ is leftmost greedy; grabs everything it can while leaving
# room for (e|r) somewhere.

$x =~ /(m{1,2})(.*)$/;
# $1 = 'mm'    -- m{1,2} matches at first 'm' in 'programming',
# $2 = 'ing republic of Perl'
#                takes the maximum 2.

$x =~ /.*(m{1,2})(.*)$/;
# $1 = 'm'
# $2 = 'ing republic of Perl'
# .* grabs all the way to the last 'm', leaving only one 'm' for
# m{1,2}.

Μη άπληστοι ποσοδείκτες

Η προσθήκη ? σε οποιονδήποτε ποσοδείκτη τον γυρίζει από άρπαξε όσο το δυνατόν περισσότερα σε άρπαξε όσο το δυνατόν λιγότερα.

Μη άπληστος	Σημασία
a??	0 ή 1, προτιμά 0
a*?	0 ή περισσότερες, προτιμά λιγότερες
a+?	1 ή περισσότερες, προτιμά λιγότερες
a{n,m}?	n έως m, προτιμά n

Η συνολική αντιστοιχία πρέπει ακόμη να επιτύχει, οπότε η μηχανή θα επεκτείνει τον μη άπληστο ποσοδείκτη ένα βήμα τη φορά μέχρι να επιτύχει.

my $x = "The programming republic of Perl";

$x =~ /^(.+?)(e|r)(.*)$/;
# $1 = 'Th'
# $2 = 'e'
# $3 = ' programming republic of Perl'
# .+? grabs as little as possible while allowing the match.

Ο μη άπληστος είναι συνήθως αυτό που θέλετε όταν σαρώνετε ανάμεσα σε διαχωριστικά:

my $html = '<b>bold</b> and <i>italic</i>';
while ($html =~ /<(\w+)>(.*?)<\/\1>/g) {
    print "$1: $2\n";
}
# b: bold
# i: italic

Με άπληστο .* η αντιστοιχία θα κατάπινε το πρώτο </b> και θα σταματούσε στο τελικό </i>, καταστρέφοντας τη σύλληψη.

Όταν ο μη άπληστος χάνει από αρνημένη κλάση

Ένας σύνηθης ιδιωματισμός: <.*?> για αντιστοίχιση μιας ετικέτας. Ένα σύνηθες σφάλμα: το ίδιο μοτίβο, εφαρμοσμένο σε χαλασμένη είσοδο, επεκτείνει τον μη άπληστο ποσοδείκτη πέρα από περιεχόμενο που δεν θα έπρεπε. Η καθαρότερη μορφή χρησιμοποιεί αρνημένη κλάση χαρακτήρων:

"<a> body </a>"  =~ /<.+?>/;        # matches '<a>'  — fine
"<a> <b>foo"     =~ /<.+?>foo/;     # matches '<a> <b>foo' — wrong
"<a> <b>foo"     =~ /<[^>]+>foo/;   # matches '<b>foo' — locked to one tag

Όταν απαιτείται μια λεκτική μονάδα μετά το >, η μη άπληστη μορφή επεκτείνεται υπό την πίεση οπισθοχώρησης: η μηχανή δοκίμασε πρώτα το <a>, δεν βρήκε foo, και ανάγκασε το .+? να μεγαλώσει πέρα από το > και παραπέρα. Η αρνημένη κλάση δεν μπορεί να υποχωρήσει με αυτόν τον τρόπο — η [^>] είναι σκληρό φράγμα, οπότε η μηχανή μετακινεί τη θέση εκκίνησης στο <b> αντί να καταπιεί ενδιάμεσα >.

Μια αρνημένη κλάση είναι επίσης ταχύτερη: συμμετέχει στο γρήγορο μονοπάτι απλής επανάληψης της μηχανής, το οποίο η μη άπληστη μορφή απενεργοποιεί.

Χρησιμοποιείτε .+? μόνο όταν καμία αρνημένη κλάση δεν μπορεί να εκφράσει την ίδια απαίτηση. Χρησιμοποιείτε [^X]+ όποτε το διαχωριστικό είναι μεμονωμένος χαρακτήρας.

Κτητικοί ποσοδείκτες

Η προσθήκη + μετά από έναν ποσοδείκτη (όχι ?) τον κάνει κτητικό: άπληστο, αλλά αρνείται να επιστρέψει οτιδήποτε σε οπισθοχώρηση. Μόλις ταιριάξει, αυτοί οι χαρακτήρες βγαίνουν εκτός παιχνιδιού για το υπόλοιπο μοτίβο.

Κτητικός	Σημασία
a?+	0 ή 1, χωρίς υποχώρηση
a*+	0 ή περισσότερες, χωρίς υποχώρηση
a++	1 ή περισσότερες, χωρίς υποχώρηση
a{n,m}+	n έως m, χωρίς υποχώρηση

Το όφελος είναι ταχύτητα — σε μοτίβα που πρέπει να αποτύχουν, οι κτητικοί ποσοδείκτες αποτυγχάνουν άμεσα αντί να οπισθοχωρούν εξαντλητικά.

# Ordinary greedy: backtracks once per character on 'abc   ' when
# the second \w+ cannot match.
/^\w+\s+\w+$/;

# Possessive: once \w+ claims the word characters, it keeps them.
# No backtracking, no quadratic blowup on pathological input.
/^\w++\s+\w+$/;

Το κλασικό 'aaaa' =~ /a++a/:

'aaaa' =~ /a++a/;   # never matches

Το a++ καταβροχθίζει και τα τέσσερα a. Το τελικό a τότε δεν έχει με τι να ταιριάξει. Επειδή το a++ αρνείται να υποχωρήσει, η μηχανή αποτυγχάνει άμεσα. (Το ίδιο μοτίβο με άπληστο a+a ταιριάζει με 'aaaa' μετά από οπισθοχώρηση.)

Ένας σύνηθης ιδιωματισμός για αντιστοίχιση συμβολοσειρών σε εισαγωγικά χωρίς καταστροφή οπισθοχώρησης:

/"(?:[^"\\]++|\\.)*+"/;

Κάθε επανάληψη της εσωτερικής ομάδας είτε καταβροχθίζει μια απεριόριστη ακολουθία μη-εισαγωγικών, μη-ανάστροφων χαρακτήρων (κτητικά), είτε μία διαφυγή. Καμία εναλλακτική δεν είναι διατεθειμένη να υποχωρήσει, οπότε η αποτυχία είναι γρήγορη. Η πλήρης ανάλυση αυτού του μοτίβου βρίσκεται στο κεφάλαιο performance.

Ο κτητικός ισοδυναμεί με συντακτική ζάχαρη ατομικής ομάδας

Οι κτητικοί ποσοδείκτες είναι ακριβής συντακτική ζάχαρη για ατομική ομάδα γύρω από το ποσοδεικτημένο άτομο. Τα ακόλουθα είναι ισοδύναμα:

Κτητική μορφή	Μορφή ατομικής ομάδας
PAT*+	(?>PAT*)
PAT++	(?>PAT+)
PAT?+	(?>PAT?)
PAT{n,m}+	(?>PAT{n,m})

Η κτητική σημειογραφία είναι συντομότερη· η σημειογραφία ατομικής ομάδας γενικεύεται περισσότερο (μπορείτε να τυλίξετε αυθαίρετες εναλλαγές, όχι μόνο ποσοδεικτημένα άτομα). Το κεφάλαιο groups and captures καλύπτει τις ατομικές ομάδες λεπτομερώς.

Μη επιτρεπόμενοι συνδυασμοί κτητικού και μη άπληστου

Ο κτητικός και ο μη άπληστος είναι αντιφατικοί· η Perl απορρίπτει τους συνδυασμούς. Υπάρχει ισοδύναμη νόμιμη μορφή για κάθε έναν:

Μη επιτρεπτό	Νόμιμο ισοδύναμο
X??+	X{0}
X+?+	X{1}
X{n,m}?+	X{n}

Αν διαπιστώσετε ότι θέλετε «μη άπληστο και κτητικό», αυτό που στην πραγματικότητα θέλετε είναι σταθερό πλήθος.

Επιλέγοντας τον σωστό ποσοδείκτη

• Άπληστος — η προεπιλογή, και σωστός τις περισσότερες φορές.

• Μη άπληστος — όταν σαρώνετε ανάμεσα σε δείκτη αρχής και τέλους που μπορούν και οι δύο να εμφανίζονται νόμιμα πολλαπλές φορές.

• Κτητικός — όταν η αντιστοιχία είτε δουλεύει με ακριβώς έναν τρόπο είτε αποτυγχάνει, και η ταχύτητα στην αποτυχία έχει σημασία.

Όταν αμφιβάλλετε, γράψτε τον ως άπληστο και προσθέστε έναν έλεγχο που αποτυγχάνει αν τον έγραψατε λάθος.

Ποσοδεικτοποίηση μηδενικού πλάτους

Ένας ποσοδείκτης σε διεκδίκηση μηδενικού πλάτους είναι σχεδόν πάντα λάθος. Το \b* είναι συντακτικά νόμιμο αλλά ταιριάζει με την κενή συμβολοσειρά σε κάθε όριο λέξης, κάτι που δεν είναι χρήσιμο. Η μηχανή απορρίπτει κάποιους από αυτούς ρητά με την προειδοποίηση «matches null string many times» υπό use warnings· για τους υπόλοιπους, τα αποτελέσματα συνήθως δεν είναι αυτά που εννοούσε ο συγγραφέας.

Η ίδια επιφύλαξη ισχύει για ποσοδεικτημένες ομάδες των οποίων το εσωτερικό περιεχόμενο μπορεί να ταιριάξει με τίποτα. Αν το (\w*)* φτάσει σε επανάληψη όπου το \w* ταίριαξε με μηδέν χαρακτήρες, το εξωτερικό * θα έκανε αιώνιο βρόχο. Η Perl σπάει αυτόν τον βρόχο αυτόματα — δείτε το κεφάλαιο performance σχετικά με τον τερματισμό αντιστοιχίας μηδενικού μήκους.

Επεξεργασμένα παραδείγματα από την ενότητα οπισθοχώρησης του perlre

Οκτώ παραλλαγές του «βρες τα ψηφία στο τέλος μιας συμβολοσειράς». Κάθε μία αποτυγχάνει ή πετυχαίνει για διαφορετικό λόγο· η ανάγνωσή τους ως σύνολο είναι ένας γρήγορος τρόπος να αφομοιώσετε τη συμπεριφορά άπληστων και μη άπληστων.

$_ = "I have 2 numbers: 53147";

# Pattern              $1 captured              $2 captured
/(.*)(\d*)/         => "I have 2 numbers: 53147"  ""
/(.*)(\d+)/         => "I have 2 numbers: 5314"   "7"
/(.*?)(\d*)/        => ""                          ""
/(.*?)(\d+)/        => "I have "                   "2"
/(.*)(\d+)$/        => "I have 2 numbers: 5314"   "7"
/(.*?)(\d+)$/       => "I have 2 numbers: "       "53147"
/(.*)\b(\d+)$/      => "I have 2 numbers: "       "53147"
/(.*\D)(\d+)$/      => "I have 2 numbers: "       "53147"

Διαβάζοντας καθεμία:

• (.*)(\d*) — το άπληστο .* τρώει τα πάντα· το \d* ικανοποιείται από την κενή συμβολοσειρά. Ταιριάζει αλλά καμία σύλληψη δεν είναι αυτό που ήθελε ο συγγραφέας.

• (.*)(\d+) — το .* υποχωρεί όσο χρειάζεται ώστε να αποκαλύψει τουλάχιστον ένα ψηφίο, αλλά μόνο το τελευταίο ψηφίο της ακολουθίας.

• (.*?)(\d*) — και τα δύο μη άπληστα: προτιμούν την κενή αντιστοιχία· και οι δύο συλλήψεις είναι κενές.

• (.*?)(\d+) — το πρώτο μη άπληστο, το δεύτερο άπληστο. Το .*? επεκτείνεται μέχρι το \d+ να αρπάξει 2. Σταματά στην πρώτη ακολουθία ψηφίων.

• (.*)(\d+)$ — αγκυρωμένο: το \d+ πρέπει να είναι στο τέλος. Το άπληστο .* υποχωρεί ψηφία μέχρι το τελευταίο να είναι στο τέλος της συμβολοσειράς· το αποτέλεσμα είναι η ίδια παραδοξότητα «μόνο το τελευταίο ψηφίο».

• (.*?)(\d+)$ — μη άπληστο και αγκυρωμένο: το .*? επεκτείνεται μέχρι το \d+$ να αρπάξει ολόκληρη την τελική ακολουθία ψηφίων. Σωστό.

• (.*)\b(\d+)$ — αγκυρωμένο, με \b για να επιβληθεί το όριο πριν την ακολουθία ψηφίων. Ισοδύναμο.

• (.*\D)(\d+)$ — ρητό μη ψηφίο πριν την ακολουθία ψηφίων. Ισοδύναμο.

Τα μαθήματα:

1. Ο ποσοδείκτης (.* έναντι .*?) ελέγχει την απληστία, αλλά η αγκύρωση ($, \b, \D) είναι αυτό που ελέγχει ποια ακολουθία ταιριάζει.

2. Ο άπληστος σπανίως είναι «λάθος» από μόνος του· το λάθος είναι μια άγκυρα που λείπει.

Σημειώσεις μεταξύ μηχανών

Η σύνταξη ποσοδεικτών είναι μία από τις πιο αποκλίνουσες επιφάνειες ανάμεσα στις μηχανές regex. Ο πλήρης πίνακας βρίσκεται στο κεφάλαιο cross-engine· η περίληψη:

• Το POSIX BRE αντιμετωπίζει τα γυμνά + και ? ως κυριολεκτικούς χαρακτήρες. Χρησιμοποιήστε \+ και \? για τις μορφές μετα-χαρακτήρα.

• Το POSIX ERE έχει +, ?, {m,n} ως μετα-χαρακτήρες (όπως η Perl) αλλά χωρίς κτητικούς ποσοδείκτες και χωρίς ατομικές ομάδες.

• Η RE2 / Go έχει +, ?, *, *?, αλλά καθόλου κτητικούς ποσοδείκτες, ατομικές ομάδες, ή οπισθαναφορές. Η εγγύηση γραμμικού χρόνου αντικαθιστά την ανάγκη τους.

Δείτε επίσης

• Το κεφάλαιο performance — καταστροφική οπισθοχώρηση, ξετύλιγμα του βρόχου, και πού οι κτητικοί ποσοδείκτες δικαιολογούν τη χρήση τους.

• Το κεφάλαιο groups and captures — ατομικές ομάδες (?>…), η γενική μορφή του «χωρίς οπισθοχώρηση μέσα σε αυτή την κατασκευή».

• Το κεφάλαιο character classes — [^X]+ ως ταχύτερη, ασφαλέστερη εναλλακτική του .*?.

• Το κεφάλαιο cross-engine — διαθεσιμότητα ποσοδεικτών μεταξύ οικογενειών.

• m, s, qr — αναφορές τελεστών.