ביצועים#

רוב הביטויים הרגולריים רצים בזמן ליניארי בערך על המחרוזת. תבנית כתובה היטב שמתאימה היא מהירה; תבנית כתובה היטב שאינה מתאימה היא גם מהירה. הצרה באה מתבניות שהיו יכולות להתאים בדרכים רבות ושונות — המנוע חוקר את האפשרויות הללו בזו אחר זו, ותבניות פתולוגיות עלולות לחקור באופן מעריכי.

פרק זה עוסק בזיהוי הצרה הזו, בהימנעות ממנה, וכאשר אי אפשר להימנע ממנה — בריסון שלה באמצעות כמתים רכושניים, קבוצות אטומיות, ומבנה מוקפד. החצי השני עוסק במנגנון שהמנוע מיישם בשקט עבורכם, וכיצד לכתוב תבניות שיאפשרו לאופטימיזציות הללו לפעול.

Perl משתמשת ב־NFA מסורתי — מנוע שמטייל בתבנית בהתאם להוראות הקלט ולא ההפך, שומר את מקומו בכל נקודת בחירה כדי שיוכל לחדש לאחר מבוי סתום. התכונה הזו היא שמאפשרת לכידות, הפניות לאחור, וסביבות הצצה; היא גם זו שהופכת את המקרה הגרוע ביותר למעריכי. כל מה שבפרק זה הוא תוצאה של עובדה אחת זו.

כיצד פועלת חזרה לאחור#

מנוע ביטויים רגולריים מטייל במחרוזת ובתבנית במקביל. כאשר הוא מגיע לבחירה — ברירה, כמת, קבוצה אופציונלית — הוא מקבל החלטה, זוכר את הבחירה במחסנית, וממשיך. אם מיקום מאוחר יותר בתבנית נכשל, הוא מוציא את הבחירה האחרונה, מנסה את ההחלטה הבאה הזמינה, וממשיך. זוהי חזרה לאחור.

כל ?, *, +, {…}, ו־| הוא נקודת חזרה לאחור פוטנציאלית. מחרוזת קצרה ומעט נקודות בחירה: מהיר. מחרוזת ארוכה, נקודות בחירה מקוננות, ואין התאמה: מעריכי.

דוגמה מפורטת מתוך perlre. כדי להוציא את המילה שאחרי foo מתוך Food is on the foo table.:

$_ = "Food is on the foo table.";
if (/\b(foo)\s+(\w+)/i) {
    print "$2 follows $1.\n";
}
# table follows foo.

המנוע מתאים תחילה את \b(foo) מול Food, וטוען את $1 ב־Foo. אחר כך הוא מחפש \s+ ומוצא d — כישלון. הוא חוזר לאחור, מקדם את מיקום ההתחלה, וממשיך לחפש עד שהוא מוצא את foo המילולי ואחריו רווח לבן, ואז מילה.

מקרה מאלף יותר. התבנית אומרת ״הכל בין foo ל־bar״:

$_ = "The food is under the bar in the barn.";
if (/foo(.*)bar/) {
    print "got <$1>\n";
}
# got <d is under the bar in the >

ה־.* החמדן רץ כל הדרך לסוף המחרוזת, ואז זחל חזרה שמאלה עד ש־bar יכול היה סוף סוף להתאים — ב־bar האחרון, לא בראשון. יש להשתמש ב־.*? כדי לעצור בראשון.

ל־perlre יש גרסה ארוכה יותר של זה עם שמונה וריאנטים — רובם שגויים, כולם מאלפים — תחת Backtracking. הלקח זהה בכל אחד מהם: כמת חמדן תמיד מחטיא את המטרה לראשונה; הצורה הנכונה (אילו עוגנים? לא־חמדן או מחלקה שלילית?) היא שמתקנת את ההתאמה, לא התאמת הכמת במקום.

עלות שמירת המצב#

המודל המכני של פרידל ראוי לזכירה. ב־NFA, ספירת המצבים השמורים היא בערך מספר התווים שתת־ביטויים תחת שליטת כמת התאימו. [0-9]+ מול 1234 שומר ארבעה מצבים — אחד לכל ספרה, מסמן כל אחד כנקודת ״ההתאמה יכולה להסתיים כאן״. כאשר המנוע נכשל בסופו של דבר בהמשך התבנית, הוא מוציא את ארבעת המצבים הללו אחד אחד, מנסה למצוא דרך להצליח את ההתאמה.

פרט עדין: הכמת + דורש את ההתאמה הראשונה שלו, ולכן הוא אינו שומר מצב עבור ״התאם כלום כאן״. * כן שומר, מכיוון שאפס התאמות מותרות. א־סימטריה זו מתבטאת בהשוואות מיקרו־בנצ’מרק של תבניות + מול *; על קלטים שבהם הכמת באמת חייב להתאים לפחות דבר אחד, + מהיר במקצת מכיוון שיש לו מצב אחד פחות לנהל בכישלון.

חזרה לאחור קטסטרופלית#

שקלו תבנית זו שמנסה להתאים מחרוזת ארוכה של a:

"aaaaaaaaaaaaaaaaaaaa" =~ /(a+)+b/;

התבנית אינה יכולה להתאים — אין b. אך המנוע צריך להוכיח זאת. ניתן לשייך כל a במחרוזת ל־+ הפנימי או ל־+ החיצוני בדרכים רבות. עבור מחרוזת בת 20 תווים אלה מיליוני שילובים; עבור מחרוזת בת 30 תווים, מיליארדים. המנוע מנסה את כולם.

הצורה הכללית שאליה יש לשים לב: כמתים בלתי־מוגדרים מקוננים על מחלקות חופפות.

/(a+)+/;             # dangerous
/(a|b)*c/;           # dangerous on a+b strings without trailing c
/(\w+)*\s/;          # dangerous on a run of word chars with no space
/([^"]|\\.)*"/;      # dangerous on long unterminated strings

לכל אחד מהם אותה צורה: כמת חיצוני על קבוצה שתכולתה הפנימית בלתי־מוגדרת בעצמה. הדוגמה המפחידה הקנונית של פרידל, הביטוי הרגולרי של מחרוזת במרכאות כפולות "(\.|[^"\\]+)*" המופעל היכן שאינו יכול להתאים, מתועד לוקח בערך 3.2 × 10²⁹ חזרות לאחור לפני שהוא מוותר — אורכי־חיי־יקום רבים אם המנוע באמת היה מנסה את כולם. בפועל תקרת עומק הרקורסיה מופעלת תחילה; התוכנית לא כל כך תקועה אלא נופלת בהילוך איטי.

המחלה זהה בכל מקרה. עבור כל תו נוסף שהקלט גדל, מספר הדרכים שבהן המנוע יכול לחלק תווים בין הכמת הפנימי לחיצוני מוכפל.

המרפא הוא דטרמיניזם: יש לכתוב את הביטוי הרגולרי כך שעבור כל קלט יש בדיוק דרך אחת שבה המנוע יכול לחלק את העבודה בין הכמת הפנימי לחיצוני. הסעיפים הבאים מכסים את שלוש הטכניקות שמשיגות זאת.

כמתים רכושניים#

כמת רכושני (++, *+, ?+, {n,m}+) הוא חמדן ולעולם אינו מוותר. הוא אומר למנוע: ״ברגע שהתאמתי את התווים הללו, הם שלי; אל תבקר בהחלטה הזו שוב בכישלון״.

/(a++)+b/;    # at most one backtrack point
/(\w++)*\s/;  # bounded — \w++ takes all word chars in one shot

הפשרה: אם חלק מאוחר יותר של התבנית זקוק לתווים הללו בחזרה, ההתאמה פשוט נכשלת. רכושני נכון כאשר באמת אין דרך אחרת שההתאמה תצליח באותה קידומת.

כמתים רכושניים הם סוכר תחבירי לקבוצה אטומית סביב האטום עם הכמת. הבאים שקולים:

צורה רכושנית	צורת קבוצה אטומית
`PAT*+`	`(?>PAT*)`
`PAT++`	`(?>PAT+)`
`PAT?+`	`(?>PAT?)`
`PAT{n,m}+`	`(?>PAT{n,m})`

הסימון הרכושני קצר יותר; סימון הקבוצה האטומית כללי יותר (ניתן לעטוף ברירות שרירותיות, לא רק אטומים עם כמת).

תוצאה של ״רכושני שווה לאטומי״: חלק מהשילובים אינם הגיוניים ו־Perl דוחה אותם.

צורה לא־חוקית	צורה חוקית שקולה
`X??+`	`X{0}`
`X+?+`	`X{1}`
`X{n,m}?+`	`X{n}`

לא־חמדן ורכושני סותרים זה את זה. יש להשתמש ב־X{0}, X{1}, או X{n} אם באמת רציתם להתאים בדיוק מספר זה.

קבוצות אטומיות#

(?>…) היא קבוצה לא־לוכדת שתכולתה, ברגע שהותאמה, מתחייבת. כמו כמת רכושני, אין חזרה לאחור בתוכה. ההבדל הוא שקבוצות אטומיות עוטפות תבניות שרירותיות, לא רק אטומים עם כמת.

"aaab"  =~ /a*ab/;       # matches — the a* gives back one 'a'
"aaab"  =~ /(?>a*)ab/;   # does not match — a* takes all, none to give

קבוצות אטומיות הן הכלי הכללי ביותר לשליטה בחזרה לאחור. יש להשתמש בהן סביב בלוק תבנית שאמור להתאים במלואו או לא להשתתף.

יישום קלאסי: סוגריים מאוזנים, מהיר על קלט גרוע.

# Unbounded: dangerous on unbalanced input
/ \( ( [^()]+ | \([^()]*\) )+ \) /x;

# With atomic group: fast failure on bad input
/ \( ( (?> [^()]+ ) | \([^()]*\) )+ \) /x;

ה־(?>[^()]+) הפנימי אומר: זלול כמה שיותר תווים שאינם סוגריים ואל תחזור. זה מסיר את הדו־משמעות שהופכת + מקונן ליקר.

(?>…) אינו משבית חזרה לאחור מחוצה לו. המנוע עדיין יכול לחזור לאחור מעבר למבנה כשלם, רק לא לתוכו. לכן ((?>a*)|(?>b*))ar מול bar עדיין מתאים: הברירה החיצונית יכולה לחזור לאחור בין ענפים.

קבוצות אטומיות מקוננות אינן ללא־פעולה. כל שכבה נוספת מצמצמת עוד יותר את מה שהחלקים הפנימיים יכולים לוותר. (?>a[bc]*c) מתאים abc; (?>a(?>[bc]*)c) לא, מכיוון ש־(?>[bc]*) הפנימי אכל את ה־c הנגרר ומסרב לשחרר אותו.

האיות הארוך (*atomic:…) מתקבל גם הוא; הוא נקרא טוב יותר בקוד תבנית שכבר משתמש בפעלים כמו (*positive_lookahead:…).

התאמת מחרוזות במרכאות — המקרה הקנוני#

הבעיה ״התאם מחרוזת במרכאות עם רצפי בריחה בלוכסן הפוך״ היא זו שכולם טועים בה בניסיון הראשון.

תמים:

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

בהינתן מחרוזת ארוכה ללא סיום כמו "aaaaaaaaa (ללא מרכאות סוגרות), זה חוזר לאחור באופן ריבועי על כל חלוקה של ה־a־ים בין שתי החלופות. הצורה הבטוחה:

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

ה־++ הפנימי לוקח את כל התווים שאינם מרכאות ואינם לוכסן הפוך בנגיסה אחת. ה־*+ החיצוני מסרב לוותר בין איטרציות. התאמה שנכשלה נכשלת בזמן ליניארי. המקבילה של הקבוצה האטומית זהה בהתנהגותה:

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

— ומדגימה מדוע הצורה הרכושנית עדיפה כאשר היא חלה. היא תמציתית יותר מבלי לאבד דבר.

פתיחת הלולאה#

הטכניקה היחידה והשימושית ביותר להחלפת תבנית לא־דטרמיניסטית בדטרמיניסטית. פרידל נתן לה שם; מנועים הפנימו אותה; כל מתכנת ביטויים רגולריים פעיל צריך להכיר אותה.

צורת התבנית:

opening normal* (special normal*)* closing

— כאשר normal ו־special הם תת־ביטויים שצורכים קבוצות זרות של תווים. המבנה מבטיח שיש בדיוק דרך אחת שבה המנוע יכול לחלק את הקלט ביניהם, ולכן חקירה מעריכית לעולם אינה מתחילה.

שלושה כללים, כולם חובה:

special ו־normal אינם יכולים להתחיל התאמה באותו מיקום. אם שניהם יכולים להתאים לאותו תו, יש למנוע חופש לבחור; החופש הזה הוא בדיוק מה שגורם להתפוצצות מעריכית.
special אינו יכול להתאים את המחרוזת הריקה. special שמתאים לאיון הוא בלתי נראה למנוע ומסיר את נקודת הביקורת שהופכת את המבנה לדטרמיניסטי.
יישום אחד של special אינו יכול להיות מכוסה על ידי מספר יישומים של special. אם special הוא \s+ ולקלט יש שלושה רווחים רצופים, המנוע יכול היה להתאים אותם כ־special אחד, שלושה special־ים, או שילובים שונים — ההתפוצצות המעריכית חוזרת.

דוגמה מפורטת: מחרוזות במרכאות כפולות#

צורה תמימה, נוטה לחזרה לאחור קטסטרופלית:

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

צורה פתוחה, ללא דו־משמעות מקוננת:

/"[^"\\]*(\\.[^"\\]*)*"/;

[^"\\]* הוא ה־normal* — הוא אוכל כל תו שאינו מיוחד. \\. הוא ה־special — הוא צורך לוכסן הפוך ובדיוק את התו שאחריו. השניים אינם יכולים לחפוף (normal* אינו יכול להכיל \\; special אינו יכול להתאים לתו שאינו \\), ו־special תמיד צורך בדיוק שני תווים.

הצורה הפתוחה רצה בזמן ליניארי על כל קלט — התאמה או לא. הצורה התמימה מעריכית על קלטים עם הרבה לוכסנים הפוכים וללא מרכאות סוגרות.

אותה בעיה עם כמתים רכושניים גם רצה בזמן ליניארי:

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

יש לבחור באיזו ששאר הצוות קורא בקלות רבה יותר. שתיהן עובדות.

דוגמה מפורטת: הערות C#

הבעיה ״התאם הערת C, ושרוד כוכביות בתוכה״. התאמת הערה תמימה \/\*.*?\*\/ עובדת אך איטית על הערות ארוכות מכיוון ש־.*? חייב להתרחב תו אחד בכל פעם.

פתוחה:

/\/\*[^*]*\*+([^/*][^*]*\*+)*\//;

קריאה משמאל לימין:

\/\* — /* הפותח.
[^*]* — normal*, אפס או יותר תווים שאינם כוכביות.
\*+ — לפחות כוכבית אחת.
([^/*][^*]*\*+)* — אפס או יותר איטרציות של: תו שאינו לוכסן ואינו כוכבית, ואז עוד תווים שאינם כוכביות, ואז עוד כוכביות. (החלק של אינו־לוכסן הוא מה שעוצר את הריצה: כוכבית ואחריה לוכסן הם התוחם שאנו רוצים.)
\/ — לוכסן סוגר.

המבנה גורם לכל איטרציה של ה־* החיצוני לצרוך לפחות תו אחד שאיטרציה אחרת לא יכלה לצרוך. התוצאה: זמן ליניארי, ללא דפוס של חזרה לאחור קטסטרופלית.

הערך הפדגוגי של עבודה דרך זה הוא בתהליך החשיבה, לא בשינון הביטוי הרגולרי הסופי. הסיבוך של הכוכביות־בפנים אוכף את האיבר הנוסף [^/*]; הזיהוי מדוע הוא מה שמלמד אתכם לזהות את המקרה הבא.

דוגמה מפורטת: הביטוי הרגולרי הזורם־חופשית#

כאשר יש מספר תת־ביטויים של ״דלג עליי״ (מחרוזות, הערות, קבועים בהקשר דמוי־מפענח), יש לבנות ביטוי רגולרי יחיד עם כולם בברירה וסעיף OTHER+ עבור עיקר הנתונים:

my $DOUBLE = qr/"[^"\\]*(?:\\.[^"\\]*)*"/;
my $SINGLE = qr/'[^'\\]*(?:\\.[^'\\]*)*'/;
my $COMMENT = qr/\/\*[^*]*\*+(?:[^\/*][^*]*\*+)*\//;
my $LINECOM = qr/\/\/[^\n]*/;
my $OTHER  = qr/[^"'\/]+/;

while ($source =~ / $DOUBLE | $SINGLE | $COMMENT | $LINECOM | $OTHER /xg) {
    ...
}

זרוע ה־$OTHER צורכת את עיקר הקלט בריצות ארוכות, כלומר המנוע מבלה כמעט את כל זמנו בתוך לולאה אחת בזמן ליניארי, לא בקפיצה־קדימה מנסה חלופות בכל תו לא־מעניין. הטכניקה מכרעת בעומסי עבודה דמויי־מפענח.

צמצום בחירה#

אם התבנית שלכם עובדת אך איטית, חפשו בחירה מזויפת:

עגנו היכן שניתן. ^pat ו־pat$ מאפשרים למנוע לדחות את רוב מיקומי ההתחלה מיידית. \A אפילו טוב מ־^ כאשר הכוונה היא ״תחילת המחרוזת״ — המנוע יכול לסרב לנסות שוב בכל מיקום ולא רק בתחילות שורות.
החליפו ברירה של תווים בודדים במחלקה. /a|b|c/ איטי בהשוואה ל־/[abc]/; המחלקה היא בחירה יחידה, הברירה היא שלוש.
שימו את החלופה הנפוצה ראשונה. ברירה נבדקת משמאל לימין, ו־Perl עוצרת בהצלחה הראשונה. אם 90% מהקלטים שלכם פוגעים בחלופה 3, סדרו מחדש.
חשפו קידומות משותפות. /this|that|them/ מסכל את אופטימיזציית המחרוזת הקבועה; /th(?:is|at|em)/ מספק למנוע את ה־th המילולי לסרוק תחילה.
העדיפו מחלקות תווים על פני .. [^\n] זולה מ־. מכיוון שהמנוע יודע שהיא לעולם לא תתאים בין שורות. אותו הדבר עבור [^"] במקום .*? בין מרכאות.
מחלקות תווים שליליות מנצחות .*?. הצורה הלא־חמדנית חייבת לעזוב את הלולאה הפנימית בכל איטרציה כדי לבדוק את הבא; המחלקה השלילית משתתפת במסלול המהיר של חזרה פשוטה. <([^>]+)> מהיר פי כמה מ־<(.+?)> וגם נכון יותר: המחלקה השלילית אינה יכולה לחצות > אפילו תחת לחץ של חזרה לאחור.

לקמפל פעם אחת, להתאים פעמים רבות#

בכל פעם שתבנית עם משתנים משובצים בשימוש, Perl בודקת האם הטקסט של התבנית השתנה. אם לא, הצורה המהודרת נעשית בשימוש חוזר. עבור תבניות שבאמת קבועות, התקורה קטנה אך אינה אפס.

qr מהדר תבנית פעם אחת ומפיק עצם שניתן לשימוש חוזר:

my $word = qr/\b[a-z]+\b/;
for my $text (@corpus) {
    while ($text =~ /$word/g) {
        ...
    }
}

שימוש ב־qr בלולאה חמה חוסך את שלב ה־הידור־מחדש־או־בדיקה והופך את הקוד לברור יותר. הוא גם מאפשר לבנות תבניות מורכבות מחלקים בשם, מה שמכריע עבור כל ביטוי רגולרי מעל עשר שורות בערך.

המתאם /o (״הידור פעם אחת״) היה המנגנון של Perl 4 עבור זה. הוא עדיין עובד אך לעיתים רחוקות הוא הכלי הנכון היום: qr// ברור יותר, מתחם טוב יותר, וניתן להרכבה.

הימנעות מתקורת לכידה#

קבוצות לכידה עולות מעט — המנוע צריך לעקוב אחרי מיקומי התחלה וסיום, והאופטימיזציות הסובבות (חזרה פשוטה במיוחד) עלולות להיות מושבתות. אם אינכם משתמשים בלכידה, אל תבקשו אותה.

# Capturing even though $1 is never read:
/(\d{4})-(\d{2})-(\d{2})/;

# Non-capturing:
/(?:\d{4})-(?:\d{2})-(?:\d{2})/;

המתאם /n הופך כל (…) ל־(?:…) ללא עריכת התבנית — שימושי עבור תבניות ארוכות. לכידות בשם עדיין לוכדות תחת /n.

אפילו סוגריים שאינם לוכדים עלולים לדכא את אופטימיזציית החזרה הפשוטה בחלק מהמנועים, ולכן (?:[a-z])+ לעיתים איטי יותר מ־[a-z]+. הסירו קיבוץ שאינו נחוץ; שטחו תבניות היכן שאפשר מבלי לפגוע בקריאוּת.

תבניות רקורסיביות#

ביטויים רגולריים של Perl תומכים ברקורסיה — תבנית יכולה להפנות בחזרה לאחת הקבוצות שלה. המבנה הוא (?R) (או (?0)) עבור התבנית כולה, (?N) עבור קבוצה N, (?-N) ו־(?+N) עבור הפניות יחסיות, ו־(?&NAME) עבור קבוצות בשם.

תבנית רקורסיבית עבור סוגריים מאוזנים, כל עומק:

my $bal = qr/
    (?(DEFINE)
        (?<paren>
            \(                  # opening paren
            (?:
                [^()]++         # run of non-paren, possessive
              | (?&paren)       # or a balanced sub-group, recursively
            )*+
            \)                  # closing paren
        )
    )
    (?&paren)
/x;

"((a)(b(c)))" =~ /^$bal$/;   # matches

תת־תבנית בשם המוצהרת בבלוק (?(DEFINE)...) רקורסיבית לעצמה, לא לכל התבנית העוטפת. שימוש ב־(?R) כאן יאלץ כל רמת רקורסיה להחיל מחדש את עוגני אתר הקריאה (^ ו־$), וזה לעיתים רחוקות מה שרוצים.

רקורסיה הופכת מבנים רקורסיביים באמת לניתנים להתאמה מבלי ליפול מה־DSL של הביטוי הרגולרי. היא גם אות חזק לכך שאתם אולי אוחזים בכלי הלא נכון. מפענח אמיתי לעיתים ברור יותר; השתמשו בביטויים רגולריים רקורסיביים כאשר אתם רוצים החלטת התאם־או־כשל בשורה אחת, לא עץ פענוח.

יש מגבלת עומק רקורסיה המהודרת לתוך המנוע (ניתן להעלות אותה על ידי בנייה מחדש מהמקור). תבניות שעוברות רקורסיה ללא צריכת קלט נכשלות מיידית ולא רצות לעולם — המנוע מזהה את המעגל.

האינטראקציה עם קבוצות לכידה ראויה לתשומת לב. כאשר קבוצה רקורסיבית לעצמה, לכידות שנקבעו בתוך הרקורסיה אינן גלויות לקורא לאחר שהרקורסיה חוזרת. זוהי הסיבה המעשית שרוב התבניות הרקורסיביות משתמשות בכמתים רכושניים ובקבוצות אטומיות עבור התוכן הפנימי: לכידתו אינה משרתת מטרה מכיוון שהנתונים לא יהיו שם כאשר ההתאמה החיצונית מסתיימת.

קוד מוטמע#

(?{ code }) מריץ קוד Perl בנקודה שהמנוע מגיע אליה. ערך ההחזרה של הקוד נקבע כ־$^R. שימושי למכשור ולטענות שהתנאי שלהן נכתב באופן טבעי יותר ב־Perl מאשר בתחביר ביטוי רגולרי:

my $tries = 0;
"aaaaab" =~ /a*(?{ $tries++ })b/;
print "engine tried $tries times\n";

שתי תכונות חשובות:

הבלוק בטוח לחזרה לאחור אם משייכים למשתני local. local $cnt = $cnt + 1 מבטל את עצמו כאשר ההתאמה הסובבת חוזרת לאחור מעבר לבלוק. השמה חשופה לא.
הבלוק רואה את אותו תחום לקסיקלי שבו הוא הודר. qr// המכיל (?{ ... }) סוגר על המשתנים הלקסיקליים שבתחום בזמן ההידור, לא בזמן ההתאמה. זהו אותו כלל ששולט בסגירות בכל מקום אחר ב־Perl.

$^N שימושי במיוחד בתוך (?{...}) — הוא מחזיק את הטקסט שהותאם על ידי קבוצת הלכידה האחרונה שנסגרה, כך שניתן לשמור התאמות מבלי לספור סוגריים:

$_ = "The brown fox jumps over the lazy dog";
/the (\S+)(?{ $color = $^N }) (\S+)(?{ $animal = $^N })/i;
print "color = $color, animal = $animal\n";
# color = brown, animal = fox

העלות הגדולה: (?{ ... }) משבית גלובלית אופטימיזציות מסוימות בתבנית. תבניות המכילות אותו עלולות לרוץ הרבה יותר לאט מתבניות בלעדיו, אפילו על קלטים שבהם בלוק הקוד רץ אפס פעמים.

(*{ code }) היא הצורה האופטימית, שהוצגה ב־Perl 5.37.7. אותו תחביר, אותה התנהגות, פרט לכך שהיא אינה משביתה אופטימיזציות. הפשרה: המנוע עשוי לבצע את הבלוק פחות פעמים ממה שהסמנטיקה הקפדנית של (?{...}) הייתה דורשת. על התאמה שנכשלה ייתכן שהוא לא ירוץ כלל. יש להשתמש ב־(?{...}) כאשר תלויים בתופעות לוואי שיופעלו בסדר מתועד; יש להשתמש ב־(*{...}) כאשר לא.

(??{ code }) הוא הביטוי הרגולרי הנדחה: ערך ההחזרה של הקוד מטופל כתבנית, מהודר אם הוא מחרוזת (או נעשה בו שימוש ישיר אם הוא עצם qr//), ומותאם באותו מיקום. הוא מאפשר תבניות שמעוצבות באמת בזמן ריצה:

my $inner = '(.)\1';
"ABBA" =~ /^(.)(??{ $inner })\1/;
print $1;   # 'A'

לתבנית הפנימית יש מצב לכידה משלה — לכידות בתוך (??{...}) אינן גלויות לתבנית החיצונית. עבור סוגריים מאוזנים או מבנים רקורסיביים אחרים, (?R)/(?N) יעיל יותר וגם ברור יותר.

קלט שסופק על ידי משתמש לעולם אסור שיגיע ל־(?{...}) או ל־(??{...}). Perl אוסרת זאת כברירת מחדל; use re 'eval' מסירה את אבזם הבטיחות ואסור לכם.

תדירות ביצוע של קוד מוטמע#

המספר המדויק של הפעמים ש־(?{...}) ו־(??{...}) מבצעים במהלך התאמה הוא בלתי מוגדר. המנוע מבטיח רק:

בהתאמה מוצלחת, בלוקים במסלול המקבל מתבצעים בסדר משמאל לימין, המספר המתאים של פעמים עבור הכמת שתחתיו הם יושבים.
בלוקים עשויים להתבצע אפס, פעם אחת, או פעמים רבות במהלך התאמות שנכשלו, בהתאם לאופטימיזציות שהמנוע מיישם.

לדוגמה, ב־"aaabcdeeeee" =~ /a(?{print "a"})b(?{print "b"})cde/, המספר המדויק של ה־a־ים וה־b־ים שמודפסים אינו מוגדר עבור התאמות שנכשלו. עבור התאמה מוצלחת כל בלוק רץ לפחות פעם אחת במסלול המקבל; אם b הודפס, a בהכרח הודפס לפחות פעם אחת לפניו.

בלוקים עם כמת מתנהגים אינטואיטיבית בהצלחה:

"good" =~ /g(?:o(?{ print "o" }))*d/;
# prints o twice

בלוקי קוד המיועדים לספור, לתעד, או לעקוב חייבים להשתמש בצורת (?{...}) (דטרמיניסטית בהצלחה); בלוקים שהם המלצה גרידא יכולים להשתמש ב־(*{...}) (ולקבל את ספירת הקריאות הנמוכה יותר בתמורה לאי־שבירת אופטימיזציות).

פעלי שליטה מיוחדים בחזרה לאחור#

Perl מספקת פעלים שמכוונים את המנוע בדיוק רב יותר מכפי שקבוצות אטומיות רגילות יכולות. כולם משתמשים בצורה (*VERB) או (*VERB:NAME). הם ברוחב־אפס (הם אינם צורכים קלט) ועושים משהו רק כאשר חוזרים אליהם לאחור בכישלון.

הפעלים מקיימים אינטראקציה עם שני משתני חבילה: $REGERROR ו־$REGMARK. לאחר התאמה הכוללת כל פועל המקבל NAME:

$REGMARK נקבע לשם של (*MARK:NAME) האחרון שבוצע, בהצלחה.
$REGERROR נקבע לשם הפועל שגרם לכישלון, בכישלון.

אלה משתנים גלובליים של חבילה (לא משתני קסם; לא מתוחמים אוטומטית); יש להשתמש ב־local אם דרוש תיחום.

`(PRUNE)` ו־`(PRUNE:NAME)`#

גוזם את עץ החזרה לאחור בנקודה הנוכחית. אחרי A(*PRUNE)B: אם B נכשל, המנוע אינו חוזר לאחור ל־A. כל ההתאמה נכשלת במיקום ההתחלה הנוכחי; הוא אינו מתקדם ומנסה שוב.

'aaab' =~ /a+b?(?{ print "$&\n"; $count++ })(*FAIL)/;
# Prints aaab, aaa, aa, a, aab, aa, a, ab, a — 9 times.

$count = 0;
'aaab' =~ /a+b?(*PRUNE)(?{ print "$&\n"; $count++ })(*FAIL)/;
# Prints aaab, aab, ab — 3 times.

(*PRUNE) הוא (?>...) חזק יותר: הוא שולט בחזרה לאחור בין מקטעי תבנית ולא בתוך תת־תבנית קבועה.

`(SKIP)` ו־`(SKIP:NAME)`#

כמו (*PRUNE), ובנוסף: מאותת שהטקסט המוביל אל הפועל אינו יכול להיות חלק של שום התאמה. המנוע מקדם את מיקום ההתחלה לנקודה שבה הפועל הופעל ומנסה שוב משם:

'aaabaaab' =~ /a+b?(*SKIP)(?{ print "$&\n"; $count++ })(*FAIL)/;
# Prints aaab, aaab — 2 times.

אם (*SKIP:NAME) מופעל ו־(*MARK:NAME) נקבע קודם לכן, מיקום ההתחלה החדש הוא מיקום הסימן, לא של הפועל. זוהי הדרך השפויה היחידה לעשות ״אם ענף X נכשל, התקדם מעבר למקום שבו ענף X התחיל״ בתבנית יחידה.

`(*MARK:NAME)`#

פסאודו־נקודת ביקורת בשם. אינו עושה דבר בעצמו — אך (*SKIP:NAME) משתמש בו כיעד, ו־$REGMARK לאחר התאמה מוצלחת מחזיק את שם הסימן שבוצע לאחרונה. הקיצור (*:NAME) זהה ל־(*MARK:NAME).

זה מאפשר לתבנית לתעד איזה ענף חלופי התאים מבלי להשתמש בקבוצת לכידה נפרדת לכל ענף:

/(?:foo(*MARK:F)|bar(*MARK:B)|baz(*MARK:Z))/;
# After a successful match, $REGMARK is "F", "B", or "Z".

האופטימייזר מטפל ב־MARK/SKIP ביעילות רבה יותר מ־/(?:(foo)|(bar)|(baz))/ מכיוון שאין לו צורך לעקוב אחרי שלושה מצבי לכידה מקבילים.

`(THEN)` ו־`(THEN:NAME)`#

בתוך ברירה: בכישלון של שאר התבנית, יש לחזור לאחור לחלופה הבאה של הקבוצה העוטפת הפנימית ביותר עם ברירות, ולדלג על ענפים מעל לרמה זו. מחוץ לברירה, שקול ל־(*PRUNE). באופן רופף: ״הענף הזה ורק הענף הזה; אם הוא נכשל, נסה את ענף האחים הבא״.

/(COND1 (*THEN) ACT1 | COND2 (*THEN) ACT2 | COND3 (*THEN) ACT3)/x;

נקרא כמו if/elsif/else בתוך הביטוי הרגולרי.

`(COMMIT)` ו־`(COMMIT:arg)`#

הבלם החזק ביותר. כמו (*SKIP), אך במקום לקדם את מיקום ההתחלה, המנוע מוותר לחלוטין. לא יותר ניסיונות למצוא התאמה בשום מקום במחרוזת.

'aaabaaab' =~ /a+b?(*COMMIT)(?{ print "$&\n"; $count++ })(*FAIL)/;
# Prints aaab — 1 time.

יש להשתמש כאשר התאמה חלקית צרכה מספיק כדי להוכיח שאין התאמה בשום מקום מאוחר יותר גם כן.

`(FAIL)` / `(F)`#

תמיד נכשל. שקול ל־(?!) אך קריא יותר. שימושי רק בשילוב עם (?{...}): כאשר רוצים לספור או לתעד כל ניסיון התאמה מבלי לקבל אותה אי פעם. (?!) מותאם פנימית ל־(*FAIL).

`(ACCEPT)` ו־`(ACCEPT:arg)`#

ההפך מ־(*FAIL). תמיד מצליח, ומסיים את ההתאמה מיידית. בתוך תבניות מקוננות או רקורסיה, רק התבנית הפנימית ביותר מסתיימת. קבוצות לכידה שנפתחו אך עדיין לא נסגרו מסומנות כמסתיימות במקום שבו (*ACCEPT) מופעל:

'AB' =~ /(A (A|B(*ACCEPT)|C) D)(E)/x;
# matches; $1 is "AB", $2 is "B", $3 is undef

(*ACCEPT) שימושי ביותר בתוך מבני (??{...}) או (?(condition)...) שבהם רוצים הצלחה במסלול מהיר מבלי לסיים את התבנית.

סיום התאמת אורך אפס#

תבנית חוזרת שיכולה להתאים את המחרוזת הריקה היא בעיה. באופן טריוויאלי:

'foo' =~ m{ ( o? )* }x;

כל איטרציה של ה־* החיצוני מתאימה למחרוזת הריקה, המיקום אינו מתקדם, האיטרציה הבאה מתאימה ריקה שוב — לולאה אינסופית בהמתנה. Perl שוברת את הלולאה הזו בשתי דרכים שונות בהתאם לסוג החזרה המעורב.

לולאות ברמה נמוכה — הכמתים *, +, {n,m} — נקטעות כאשר המנוע מזהה שאיטרציה התאימה אורך אפס. המבנה

(?: NON_ZERO_LENGTH | ZERO_LENGTH )*

מטופל בשקט כ

(?: NON_ZERO_LENGTH )* (?: ZERO_LENGTH )?

הענף באורך אפס יכול לרוץ, אך רק פעם אחת, לאחר שהענף שאינו אפס מסיים.

לולאות ברמה גבוהה — המתאם /g על m// ו־s///, ואופרטור ה־split — שומרות דגל בין איטרציות שמתעד האם ההתאמה הקודמת הייתה באורך אפס. לאחר התאמת אורך אפס, הניסיון הבא אסור להיות גם באורך אפס; המנוע לוקח במקום זאת את ההתאמה הטובה ביותר השנייה. ההדגמה הקנונית:

$_ = 'bar';
s/\w??/<$&>/g;
# Result: <><b><><a><><r><>

ה־\w?? הלא־חמדן מעדיף התאמה ריקה. לאחר ייצור אחת, האיטרציה הבאה אסורה להיות גם היא באורך אפס, לכן המנוע לוקח את ההתאמה השנייה־הטובה ביותר — תו \w בודד. ואז עוד התאמה ריקה, ואז עוד תו, וכן הלאה, לסירוגין עד שהמחרוזת נצרכת.

המצב ״ההתאמה הקודמת הייתה באורך אפס״ משויך למחרוזת המותאמת ומאופס בכל השמה ל־pos. התאמות אורך אפס בסוף ההתאמה הקודמת מתעלמים מהן גם במהלך split, ולכן split // מפיק תווים בודדים ולא קטע ריק נגרר.

שילוב תבניות: טוב יותר וגרוע יותר#

הסעיף ״Combining RE Pieces״ של perlre נותן תיאור מדויק של איזו התאמה המנוע מעדיף כאשר תבנית מאפשרת יותר מאחת. הכללים מכניים, ושווה להכירם עבור המקרים שבהם האינטואיציה נכשלת.

עבור שני חלקי תבנית משורשרים, ST:

אם S מתאים A טוב יותר מ־A', אז AB טוב יותר מ־A'B' (העדפת החלק השמאלי ביותר שולטת).
אם S מתאים גם A וגם A' באופן שווה, ההעדפה של T מכריעה.

עבור ברירה, S|T:

התאמת S תמיד טובה יותר מהתאמת T בלבד (בחירה משמאל לימין — סמנטיקת NFA מסורתי).

עבור כמתים חמדנים ולא־חמדנים:

S{n,m} שקול לניסיון S{m}, ואז S{m-1}, …, ואז S{n} (חמדן: המקסימום ראשון).
S{n,m}? שקול לניסיון S{n}, ואז S{n+1}, …, ואז S{m} (לא־חמדן: המינימום ראשון).

עבור קבוצות אטומיות, (?>S):

רק ההתאמה הטובה ביותר ל־S נשקלת; חזרה לאחור אסורה בפנים.

עבור הצצות סביב, (?=S) / (?<=S):

רק ההתאמה הטובה ביותר ל־S נשקלת (אותו דבר כמו אטומית). זה חשוב רק אם ל־S יש סוגריים לוכדים שתכולתם נמצאת בשימוש מחוץ.

הכללים שלעיל מתארים איזו התאמה נבחרת במיקום התחלה קבוע. כלל נוסף אחד מכסה בחירת מיקום: התאמה במיקום מוקדם יותר תמיד טובה יותר מהתאמה במיקום מאוחר יותר — תכונת הקפיצה־קדימה חשובה יותר מכל העדפה בתוך מיקום יחיד.

פנים המנוע — מה האופטימייזר עושה עבורכם#

מהדר של מנוע ביטוי רגולרי מריץ צבא קטן של ניתוחים על התבנית לפני שמתחילה ההתאמה. הכרתם מאפשרת לכם לכתוב תבניות שמאפשרות אותן, ולא כאלה שמסכלות אותן.

הבחנת התו הראשון#

אם התבנית חייבת להתחיל באחד מקבוצה קטנה של תווים (am|pm ⇒ [ap]), הקפיצה־קדימה יכולה לסרוק את הקלט אחר אחד מהתווים הללו באמצעות לולאה פנימית מהירה, ולהפעיל את המנוע המלא רק במיקומי המועמדים.

תבנית המתחילה ב־., או בברירה ברמה העליונה שהמנוע אינו יכול לראות דרכה, מסכלת זאת. מנועים מודרניים (PCRE2, RE2, ה־crate של regex ב־Rust) הולכים הרבה מעבר להבחנת התו הראשון — Boyer-Moore על מילוליים בקידומת, סריקה ברמת בייט עם SIMD, נפילה ל־Aho-Corasick עבור הרבה חלופות מילוליות. Perl 5.42 עושה את הצורה הפשוטה יותר היטב; הטכניקות האגרסיביות יותר הן הסיבה שבנצ’מרק עשוי להראות את RE2 מנצח את Perl על קלטים הנשלטים על ידי סריקה מילולית.

בדיקת מחרוזת קבועה#

מסלול מהיר לחזרה פשוטה#

x*, [a-f]+, .? ומבנים אחרים של ״אטום יחיד, כמת פשוט״ נשלחים ללולאה פנימית מהירה שעוקפת את מנגנון המנוע הכללי. עטיפת האטום בסוגריים לוכדים משביתה זאת. אפילו סוגריים שאינם לוכדים עלולים, בהתאם למבנה המדויק.

מודעות לאורך#

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

משמעות עוגן#

תבנית המתחילה ב־^ נוסה רק פעם אחת (או פעם אחת לשורה לוגית תחת /m). פחות באופן ברור, תבנית המתחילה ב־.* ואחריה תת־תבנית הניתנת לעגינה יכולה להיות מעוגנת באופן מרומז, מכיוון שעד שה־.* צרך את כל המחרוזת, אף מיקום התחלה מאוחר יותר אינו יכול להצליח. מנועים מודרניים מזהים זאת; אל תכתבו .* בתחילה אלא אם הכוונה כך.

מטמון הידור#

הידור ביטוי רגולרי לצורתו הפנימית אינו טריוויאלי. Perl שומרת תבניות מהודרות במטמון באגרסיביות — תבניות המוטמעות בקוד מהודרות פעם אחת כאשר תת־השגרה הסובבת מהודרת, ותבניות שמורכבות ממשתנים משובצים מהודרות מחדש רק כאשר הטקסט המתקבל באמת משתנה. qr// הופך זאת למפורש. המתאם /o היה המנגנון הישן יותר; qr// החליף אותו בניב.

התאמת מחרוזות רבות ביעילות#

אם יש לכם רשימה קבועה של מחרוזות להתאים והרשימה יציבה, בניית ברירה גדולה אחת היא לעיתים קרובות הניצחון הפשוט ביותר:

my @words = qw(the quick brown fox);
my $any = join '|', map quotemeta, @words;
my $re = qr/\b(?:$any)\b/;
for my $line (@lines) {
    next unless $line =~ /$re/;
    ...
}

quotemeta מגן על כל מילה מהכלת תווים מטא בטעות. ה־(?:…) אינו לוכד — לכידות מיותרות יעלו יותר ממה שהן משלמות. אם הרשימה גדולה (אלפי מחרוזות), מודול ייעודי שבונה מנגנון התאמה של Aho-Corasick או trie ינצח ברירה ענקית; המנוע המובנה מהדר את הברירה ל־NFA שהוא מהיר אך אינו אופטימלי אסימפטוטית עבור עומס עבודה זה.

מדידה#

טענות על מהירות ביטויים רגולריים זולות; מדידות אינן. Benchmark::timethese מקל להשוות שתי צורות על נתונים אמיתיים:

use Benchmark qw(timethese);

my $text = "..." x 10000;

timethese(1000, {
    greedy     => sub { $text =~ /"(?:[^"\\]|\\.)*"/ },
    possessive => sub { $text =~ /"(?:[^"\\]++|\\.)*+"/ },
});

תמיד יש לפרופיל לפני שמייעלים. תבניות ״ברור שאיטיות״ לעיתים אינן; ״ברור שמהירות״ לפעמים פתולוגיות על קלט אמיתי. הניסוח של פרידל נשאר הסיכום הטוב ביותר: התוכנית המהירה ביותר היא זו שמסיימת ראשונה.

כללי אצבע#

לכתוב את התבנית שנקראת הכי טוב; לפרופיל.
אם ההתאמה איטית, יש לחפש כמתים מקוננים על מחלקות חופפות.
יש לתקן אותם עם כמתים רכושניים, קבוצות אטומיות, או פתיחת לולאה.
לעגן ב־^, $, \A, \z, או \G בכל פעם שהתבנית יכולה להתחיל או להסתיים באופן לגיטימי רק במיקומים אלה.
להעדיף מחלקות על פני ברירות של תווים בודדים.
להעדיף מחלקות שליליות על פני כמתים לא־חמדנים כאשר הן מתארות את אותה הקבוצה.
להשתמש ב־qr// עבור תבניות הרצות בלולאה.
להשתמש ב־(?:…) עבור קבוצות שאינכם לוכדים, או ב־/n לדכא לכידות באופן גורף.
להשתמש ב־(*{...}) במקום (?{...}) כאשר בלוק הקוד הוא בגדר המלצה.
כאשר מפענח אמיתי יהיה ברור יותר מתבנית, לכתוב את המפענח.

ראו גם#

פרק quantifiers — צורות חמדן, לא־חמדן, רכושני.
פרק groups and captures — קבוצות אטומיות, תת־תבניות רקורסיביות, תבניות מותנות.
פרק alternation — סידור, החלופה השמאלית ביותר מנצחת.
פרק substitution — /g וסיום התאמת אורך אפס בהחלפה.
qr — לקמפל תבניות מראש לשימוש חוזר.
pos — קריאה או קביעה של מיקום ההתאמה של /g; גם מאפס את דגל התאמת אורך אפס.