מכמתים#

מכמת אומר ״הדבר הקודם הזה, N פעמים.״ הוא מתחבר לתו יחיד, מחלקת תווים או קבוצה, והופך התאמה של תו יחיד להתאמה של רבים.

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

המכמתים הבסיסיים#

מכמת

משמעות

a?

0 או פעם אחת

a*

0 פעמים או יותר

a+

פעם אחת או יותר

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' לאחר חזרה לאחור.)

אידיום נפוץ להתאמת מחרוזות בגרשיים ללא קטסטרופת חזרה לאחור:

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

כל איטרציה של הקבוצה הפנימית בולעת או רצף בלתי־מוגבל של תווים שאינם גרש ואינם לוכסן הפוך (בקניינות), או תו escape יחיד. אף חלופה אינה מוכנה להחזיר, ולכן הכישלון מהיר. הטיפול המלא בתבנית זו נמצא בפרק 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 — מדריכי עיון של האופרטורים.