ביטויים רגולריים

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

בואו נסתכל למשל בשפה \( L=\left\{ a^{n}b^{k}\ |\ n,k\in\mathbb{N}\right\} \). זו שפה רגולרית, ואפשר להציג אותה בתור \( \left\{ a\right\} ^{*}\cdot\left\{ b\right\} ^{*} \). אבל שתי דרכי הכתיבה שראינו עד כה הן מסורבלות - הן כוללות סימנים מיותרים. למה לא לכתוב \( a^{*}b^{*} \) וחסל? ובכן, זה בדיוק מה שנעשה. \( a^{*}b^{*} \) היא דוגמה פשוטה לביטוי רגולרי - בסך הכל שיטה נוחה לכתיבת שפות מסויימות, שיש בצידה בונוס רציני: כל שפה שמיוצגת על ידי ביטוי רגולרי היא אוטומטית שפה רגולרית, ואנחנו יודעים שכל שפה רגולרית יהיה ניתן לייצג בצורה כזו.

הפורמליזם פשוט: איחוד מסמנים עם \( + \) ולא עם \( \cup \), שרשור מסמנים עם \( \cdot \), ושמים סוגריים על הכל; אבל בפועל משמיטים סוגריים כאשר סדר הקדימויות הוא המתבקש (קודם \( * \), אחר כך \( \cdot \) ולבסוף \( + \)) ומשמיטים את \( \cdot \) כי לא צריך. לכן כותבים \( a^{*}b^{*} \) ולא \( \left(\left(a^{*}\right)\cdot\left(b^{*}\right)\right) \). בכל זאת, הנה הפורמליזם המדויק. הוא כולל שני חלקים - תחביר (סינטקס) וסמנטיקה. התחביר אומר לנו אילו מחרוזות של סימבולים הן ביטויים רגולריים חוקיים; הסמנטיקה אומרת לנו מה השפה שביטוי רגולרי חוקי נתון מגדיר (די דומה להגדרות שיש בלוגיקה, למשל בתחשיב הפסוקים - שם התחביר מגדיר מהי נוסחה לוגית חוקית, והסמנטיקה אומרת מה ערך האמת שלה בתוך הקשר מסויים).

כרגיל בדיונים על שפות רגולריות יש ברקע איזה אלפבית \( \Sigma \) שכל המילים נבנות רק עם אותיות שלו. בהינתן \( \Sigma \) כזה, כל הביטויים הרגולריים נבנים כך:

\( \emptyset \) הוא ביטוי רגולרי.
\( \varepsilon \) הוא ביטוי רגולרי.
\( \sigma \) הוא ביטוי רגולרי, לכל \( \sigma\in\Sigma \).
אם \( r_{1},r_{2} \) הם ביטויים רגולריים כך גם \( \left(r_{1}+r_{2}\right) \).
אם \( r_{1},r_{2} \) הם ביטויים רגולריים כך גם \( \left(r_{1}\cdot r_{2}\right) \).
אם \( r \) הוא ביטוי רגולרי כך גם \( \left(r^{*}\right) \).

שימו לב ש-\( \emptyset \) ו-\( \varepsilon \) כאן הם סימבולים. למשל, \( \emptyset \) אינו הקבוצה הריקה, בהקשר הזה - אנחנו לא אומרים משהו כמו “הקבוצה הריקה היא ביטוי רגולרי”. אנחנו אומרים “הסימבול \( \emptyset \) הוא ביטוי רגולרי. היי, במקרה או שלא במקרה זה גם הסימבול שבו אנחנו משתמשים כדי לתאר את הקבוצה הריקה!”. זו נקודה פדנטית ואם אתם לא מבינים למה אני מתעקש עליה, לא נורא.

החשיבות של הסוגריים היא בכך שהיא מבטיחה שלביטויים רגולריים תהיה קריאה יחידה. כלומר, בהינתן ביטוי רגולרי, תהיה רק דרך אחת “לפרש” אותו ולתת לו משמעות. למשל, בואו נסתכל על הביטוי נטול הסוגריים \( a+b^{*} \). מה המשמעות שלו? בסדר הקדימויות הרגיל, הוא מתאר את השפה \( \left\{ a\right\} \cup\left\{ b^{n}\ |\ n\in\mathbb{N}\right\} \), אבל אפשר גם לקרוא אותו אחרת - בתור \( \left(a+b\right)^{*} \), שמתאר את השפה \( \left\{ a,b\right\} ^{*} \) (שפת כל המילים מעל הא”ב \( \left\{ a,b\right\} \)). כלומר, הבעיה עם \( a+b^{*} \) היא שיש שתי דרכים שונות לקרוא אותו - גם בתור ביטוי מהצורה \( r_{1}+r_{2} \) (עם \( r_{1}=a \) ו-\( r_{2}=b^{*} \)) וגם בתור ביטוי מהצורה \( r^{*} \) (עם \( r=a+b \)), ובלי סוגריים אי אפשר לדעת מה מהן ה”נכונה” (סדר קדימויות פירושו, בשורה התחתונה, דרך מובלעת לשים סוגריים בביטוי).

הסוגריים מבטיחות שכל ביטוי רגולרי יהיה מאחת מהצורות 1-6, אבל רק מאחת מהן. לא ייתכן ביטוי רגולרי שהוא בו זמנית מהצורה \( \left(r_{1}+r_{2}\right) \) וגם \( \left(r_{1}\cdot r_{2}\right) \), למשל. זה מאפשר לנו להגדיר סמנטיקה עבור כל אחת משש הצורות. בהינתן ביטוי רגולרי \( r \), נסמן את השפה שהוא מגדיר ב-\( L\left[r\right] \). היא נקבעת באופן הבא:

\( L\left[\emptyset\right]=\emptyset \)
\( L\left[\varepsilon\right]=\left\{ \varepsilon\right\} \)
\( L\left[\sigma\right]=\left\{ \sigma\right\} \)
\( L\left[\left(r_{1}+r_{2}\right)\right]=L\left[r_{1}\right]\cup L\left[r_{2}\right] \)
\( L\left[\left(r_{1}\cdot r_{2}\right)\right]=L\left[r_{1}\right]\cdot L\left[r_{2}\right] \)
\( L\left[\left(r^{*}\right)\right]=L\left[r\right]^{*} \)

שום דבר מפתיע, כמובן.

כאן נגמר הפורמליזם המתמטי. יש עוד אי-אילו קיצורים שנהוג להשתמש בהם גם בכתיב מתמטי רגיל - למשל, לכתוב \( \Sigma \) במקום לכתוב \( \left(\sigma_{1}+\sigma_{2}+\dots+\sigma_{n}\right) \) (כאשר \( \Sigma=\left\{ \sigma_{1},\dots,\sigma_{n}\right\} \)). כך למשל \( \left(\Sigma\Sigma\right)^{*} \) היא שפת כל המילים מאורך זוגי מעל \( \Sigma \), אבל זהו בערך.

בעולם האמיתי זה כמובן לא מספיק.

אבל בואו נתחיל עם שאלה פשוטה - בשביל מה בכלל צריך ביטויים רגולריים בעולם האמיתי? התשובה גם כן פשוטה: בשביל לעשות חיפושים מתוחכמים. קרוב לודאי שכולכם ביצעתם חיפוש כלשהו במסמך. חיפושים "רגילים" תמיד מחפשים מחרוזת ספציפית אחת - רצף של תווים (לאו דווקא כזה שמרכיב מילה שלמה, אולי גם חלק ממילה). אבל לפעמים אנחנו רוצים לחפש משהו שאנחנו לא יודעים איך בדיוק הוא כתוב, אלא רק מה התבנית הכללית שלו; ולפעמים אנחנו רוצים לחפש הרבה דברים בבת אחת, ואנחנו יודעים מה התבנית המשותפת שלהם. בקיצור, אנחנו רוצים לבצע חיפוש אחרי איברים ששייכים לקבוצה כלשהי של מילים - שפה. לפעמים, כפי שרנדל מונרו מ-xkcd מדגים, זה יכול להציל חיים:

איך זה עובד בפועל? הרעיון הכללי הוא להשתמש בכלים שכבר הצגתי. בהינתן ביטוי רגולרי, אפשר לפענח אותו ולבנות אוטומט אי-דטרמיניסטי שמקבל אותו. את האוטומט הזה אפשר להריץ על טקסט ולראות אם האוטומט מגיע למצב מקבל. אם הוא מקבל, אז מצאנו מילה בשפה שהאוטומט מקבל שמתחילה בתחילת הטקסט ומסתיימת במקום שבו האוטומט הגיע למצב מקבל. אם לא מצאנו (ובפרט אם הגענו אל "בור" או שהחישוב נתקע) אז אנחנו יודעים שאפשר לדלג על האות הראשונה בטקסט ולהתחיל מחדש חיפוש באות הבאה, וכן הלאה. בנוסף, לא חייבים לעצור אחרי שמגיעים למצב מקבל - אפשר לנקוט בגישה "חמדנית" שבה ממשיכים עד המילה הארוכה ביותר שאותה מצליחים לקבל. תשאלו - איך מריצים אוטומט אי דטרמיניסטי? התשובה - בקלות. אם יש לאוטומט \( n \) מצבים, מחזיקים תוך כדי ריצה וקטור בינארי מאורך \( n \) שאומר לכל מצב האם אחת מהריצות של האוטומט נמצאת כרגע במצב הזה - כבר דיברנו על זה בהקשר של סילוק אי דטרמיניזם. זו בעצם הרצה מובלעת של האוטומט הדטרמיניסטי בלי לייצר אותו במפורש. אפשר, כמובן, גם לבנות את האוטומט הדטרמיניסטי מתוך האי-דטרמיניסטי ולהריץ אותו, אבל הבניה הנאיבית לא יעילה כך שצריך בניה יותר חכמה שבתקווה לא תיצור אוטומט גדול מדי; ובפועל משתמשים בשיטה הזו פחות. תשאלו - האם זה באמת מה שעושים? לא עושים משהו יותר מתוחכם? והתשובה היא שכמובן, בעולם האמיתי הסיפור יותר מורכב ואני בעצמי לא מכיר את רוב המימושים של מנועי ביטויים רגולריים. אבל מה שאני מתאר הוא הרעיון הבסיסי שעליו נבנים הדברים המתוחכמים. תשאלו - למה להסתפק בביטויים רגולריים ולא משהו מחוכם יותר? התשובה היא שעבורם זמן הריצה של אלגוריתם החיפוש הוא נמוך במיוחד, בגלל שיש לנו אובייקט פשוט כמו אוטומט שיודע לבצע את החיפוש. אבל בפועל אכן משתמשים במשהו מחוכם יותר, ואתן דוגמה עוד מעט. בעולם האמיתי רוב שפות התכנות תומכות ברמה זו או אחרת בביטויים רגולריים. אם באמצעות ספריה לא סטנדרטית (למשל ב-CPP יש ספריית ביטויים רגולריים של Boost), אם באמצעות ספרייה סטנדרטית (למשל בפייתון יש את הספריה re) ואם בתור חלק מהתחביר הבסיסי של השפה, למשל ברובי או בכלים ייעודיים שמתבססים על שימוש בביטויים רגולריים דוגמת sed ו-awk. גם במעבדי תמלילים לא טריוויאליים (למשל Emacs או Notepad++) יש תמיכה בחיפוש באמצעות ביטויים רגולריים. כמובן, באופן בלתי נמנע כשיש אינסוף מימושים לביטויים רגולריים באינסוף תוכנות שונות, יש גם וריאציות שונות על התחביר; אי אפשר סתם לקחת ביטוי רגולרי משפה אחת ולהשתמש בו בשפה אחרת ולקוות שהכל יעבוד כמו שצריך. לא בגלל הבדלים עקרוניים גדולים אלא בגלל ניואנסים קטנים. לכן אני אומר מראש שכל הביטויים הרגולריים שאכתוב בפוסט הזה מותאמים לרובי ולא לשפות אחרות (אבל כנראה יעבדו לא רע בשפות אחרות). ברובי הסטנדרט הוא לכתוב ביטויים רגולריים בין שני לוכסנים, כך שהם יופיעו בדוגמאות שאציג אבל צריך לזכור שהן לא חלק מהביטוי. הנה דוגמה לביטוי רגולרי (שלקחתי מכאן) עבור זיהוי של כתובות אימייל:

/[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}/

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

/chess/

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

/chess|checkers/

הוא ביטוי רגולרי שמייצג שתי מחרוזות שונות: המחרוזת chess והמחרוזת checkers. בשלב הזה כבר מתעוררת שאלה - רגע, למה הבחירה היא בין chess ו-checkers ולא בין s ו-c? כלומר, למה הביטוי הרגולרי לא מייצג בעצם את המחרוזות chessheckers ו-chescheckers? ובכן, כללי הקדימויות שכבר ראינו - שרשור קודם לאיחוד. כלומר, אם אנחנו רואים קו אנכי, זה אומר שיש לנו בחירה בין כל מה שימינו ובין כל מה שמשמאלו - אלא אם יש שימוש בסוגריים. כך למשל:

/che(s|cker)s/

זו דרך אחרת לכתוב את הביטוי שבוחר בין chess ובין checkers. והנה שאלה מתבקשת - אם אנחנו משתמשים ב-| בתור תו בקרה, איך נוכל לכתוב ביטוי רגולרי שמחפש בין היתר את הסימבול |? התשובה סטנדרטית - בכל פעם שאנחנו רוצים להשתמש בתו בקרה בתור תו רגיל, אנחנו עושים לו משהו שנקרא escaping - אנחנו כותבים אותו כשלפניו הלוכסן \. זוג התווים |\ ברצף אומר "הסימבול |". כך למשל הביטוי הרגולרי

/a\|b/

מתאים למחרוזת הבודדת "a|b”. בואו נעבור עכשיו למשהו יותר מעניין שיצריך שימוש בסגור קלייני. נניח שאנחנו קוראים מסמך שמכיל הרבה עילגויות מהצורה "rulez!!!!!!1”. מה התבנית הכללית של עילגויות כאלו? קודם כל המילה "rulez”. לאחר מכן מספר חיובי לא מוגדר כלשהו של סימני קריאה. לבסוף עשוי להגיע 1. אנחנו רוצים ללכוד את כל העילגויות הללו. אם נשתמש בביטוי הרגולרי

/rulez/

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

/rulez!+/

תופס את כל העילגויות מהצורה rulez!!!! אבל בלי ה-1 בסוף. עכשיו, ל-+ יש קדימות גבוהה. מה שאומר שאם יש לנו את הביטוי

/ab+/

הוא תופס מחרוזות מהצורה "a ואז מספר חיובי כלשהו של b-ים", ואילו הביטוי

/(ab)+/

תופס מחרוזות מהצורה "מספר חיובי כלשהו של חזרות על ab” (למשל abababab). עכשיו בואו נדבר על ה-1 שבסוף. בשביל להגיד "מופע אחד או אפס" משתמשים בסימן שאלה, ?. לכן הביטוי שאנחנו מחפשים הוא

/rulez!+1?/

אבל מה אם היינו רוצים להרשות ל-1 לחזור על עצמו יותר מפעם אחת? ובכן, * אומר "אפס או יותר חזרות", ואז יש לנו את הביטוי

/rulez!+1*/

בקיצור - סגור קלייני מיוצג כרגיל על ידי כוכבית, בזמן שבפלוס משתמשים כדי להגיד "כמו סגור קלייני אבל לפחות פעם אחת" (כלומר \( r^+=r\cdot r^* \)). אלו סימונים סטנדרטיים גם בביטויים רגולריים תיאורטיים, רק ששם קל להבדיל בין פלוס של "או" ובין פלוס של סגור קלייני מאורך 1 לפחות, כי הפלוס השני הוא במעריך החזקה. מן הסתם כשכותבים במחשב ההבחנה הזו הולכת לאיבוד. מה שראינו עד כה מאפשר לנו לכתוב כל ביטוי רגולרי חוקי. אבל זה לא אומר שיהיה לנו נוח לכתוב כל ביטוי רגולרי כזה. לכן בעולם האמיתי יש לנו עוד אינסוף קיצורים מועילים. בואו נראה חלק מהם. טריק ראשון הוא כתיב מסודר שמאפשר לנו לומר "אחד מבין התווים הבאים". למשל, לומר "תו אחד שהוא ספרה" או "תו אחד שהוא אות באנגלית". הדברים הללו נפוצים כל כך עד שיש שלל קיצורים עבורם. ראשית כל, התו . (נקודה) מייצג כל סימבול שהוא פרט לירידת שורה. שנית, כדי לכתוב קבוצה ספציפית של תווים, למשל a,b,3,@, אפשר מצד אחד להשתמש בביטוי הרגולרי

/(a|b|3|@)/

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

/[ab3@]/

אבל זה עדיין מסורבל מדי, כי לא נרצה לכתוב את כל אותיות הא"ב האנגלי בכל פעם. אז יש קיצור - אפשר להשתמש במקף כדי לחבר שני סימבולים בתוך סוגריים מרובעים והכוונה תהיה לכל התווים שביניהם ("ביניהם" - בסדר שבו תווים מופיעים ב-ASCII. מה שאומר, למשל, ש"בין" 0 ובין a יש את התו @, למשל). עכשיו אפשר כמעט לגמרי להבין את הביטוי הרגולרי של האימייל. בואו נראה אותו שוב:

/[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}/

מה שהביטוי הזה אומר: קודם כל תן לי סדרה של תו אחד או יותר מבין הבאים: אותיות גדולות באנגלית; ספרות; נקודה, קו תחתון, אחוז, פלוס או מינוס. אחר כך הסימבול @. אחר כך לפחות תו אחד מבין הבאים: אות גדולה באנגלית, ספרה, נקודה או מינוס. ואז מגיע \. שהוא escaping של תו הנקודה (כלומר, זו דרך להגיד - אני באמת רוצה לראות כאן נקודה, לא להשתמש בנקודה בתור "כל תו שהוא שאיננו ירידת שורה"). ואז הדבר היחיד שטרם הסברתי: בין 2 ל-4 אותיות גדולות באנגלית. באופן כללי, אם r הוא ביטוי רגולרי, אז {r{a,b פירושו "משהו ש-r תופס, לפחות a פעמים ולכל היותר b פעמים". אתם יכולים לתהות, ובצדק, לאן נעלמו בביטוי הרגולרי הזה האותיות הקטנות. התשובה היא שההנחה היא שמי שמשתמש בביטוי הרגולרי יצור אותו בתור ביטוי שהוא case insensitive - לא מבדיל בין אותיות גדולות וקטנות. זה משהו שצריך לעשות במפורש "מחוץ" לביטוי; ברובי עושים זאת על ידי הוספת תווי בקרה מצד ימין של הביטוי. עבור case insensitive צריך להוסיף את תו הבקרה i. כלומר, השימוש הנכון של הביטוי הרגולרי הזה ברובי הוא בתור

/[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}/i

עוד תווי בקרה ברובי שנכתבים מחוץ לביטוי: m אומר שתו הבקרה של נקודה יכול לתפוס גם ירידת שורה ו-x אומר לרובי להתעלם מרווחים בתוך הביטוי. לפעמים גם לכתוב 0-9 יכול להיות מעיק, ולכן יש עוד קיצורים מועילים. למשל, d\ הוא קיצור שבא במקום [0-9] (שימו לב - כאן דווקא d הוא סימבול חוקי ואילו ביצוע escaping לו הוא בעל משמעות שונה). לעומת זאת D\ (אות גדולה) הוא כל מה שאינו 0-9. באופן דומה w\ תופס תווים שהם אותיות באנגלית (קטנות/גדולות) או קו תחתון או ספרה ו-W\ את כל מה שאינו כאלו, ואילו s\ תופס את כל התווים ה"לבנים" כמו רווח, טאב וירידת שורה, ו-S\ את כל מי שאינם כאלו. באופן כללי אנחנו יכולים להגדיר קבוצת תווים על ידי "כל מי שאינו אחד מבין הבאים" על ידי כך שבתחילת הסוגריים המרובעים נשים גם ^. ועכשיו אני רוצה להציג את המרכיב שמפריד ביטויים רגולריים אמיתיים מאלו התיאורטיים. בעולם האמיתי משתמשים בביטויים רגולריים לעתים קרובות כדי ללכוד חלק מהטקסט שמתאים לביטוי. הטקסט ש"נלכד" נכנס לתוך משתנים שאחר כך אפשר להשתמש בהם, לקרוא אותם וכדומה. זו דרך חזקה מאוד לשלוף מידע מתוך קובץ טקסט. אתן דוגמה שהשתמשתי בה בפועל. כתבתי סקריפט שנכנס לדף שיש בו רשימה של לינקים לפקולטות שונות בטכניון, כשכל לינק מקשר לאותו מסמך אבל מעביר למסמך הזה פרמטר שונה שמציין את מספר הפקולטה, והטקסט של הלינק הוא שם הפקולטה. בנוסף לכך היה בדף הזה עוד הרבה מידע אחר שמבחינתי היה לא רלוונטי. אני רציתי לשלוף מהדף את הרשימה הבאה: מספרי פקולטות ושמות פקולטות. הנה הביטוי הרגולרי שבו השתמשתי:

/<A HREF=.*FAC=(\d+).*>(.+)<\/A>

בשלב הזה אני מקווה שאתם יכולים להבין את כל מה שהולך בביטוי, שאינו מורכב במיוחד, אבל שימו לב לסוגריים. זה נראה שאני משתמש בהם בצורה בלתי נחוצה בעליל, בכל הקשור לסדר הקדימויות של אופרטורים. הסיבה לכך היא שבביטויים רגולריים אמיתיים, הסוגריים משמשים קודם כל למטרה אחרת: להגיד "אני רוצה שתלכוד את הטקסט שמתאים לתת-ביטוי הרגולרי שבתוך הסוגריים". ברובי השתמשתי בביטוי הרגולרי הזה בתוך פקודת scan של המחרוזת שייצגה את מסמך ההטמל. הפקודה הזו פועלת כך, עבור ביטויים רגולריים שכוללים סוגריים: מחפשת את הביטוי הרגולרי במסמך. אם היא מצאה אותו, היא שולפת את המידע שאמור להילכד, שמה אותו במערך, ומוסיפה אותו לתוצאה הכללית. אחר כך היא ממשיכה לחפש את הביטוי הרגולרי מאותו מקום שבו המופע הקודם שלו נגמר, וכן הלאה. בסוף קיבלתי רשימה שאיבריה היו זוגות של מספר ושם - בדיוק מה שרציתי (ומה אם רוצים להשתמש בסוגריים "סתם" לצורך קדימות ולא ללכוד כלום? אז שמים ?: בתחילת הסוגריים). "לכידה" כזו היא לא משהו שאוטומטים עושים. הם עוברים על הטקסט תו-תו ושוכחים את התווים שהם כבר ראו. אין להם מקום לאחסן בו חתיכות מהטקסט. למחשבים כלליים יש מקום כזה. הם מריצים את האוטומט על הטקסט כחלק מאלגוריתם החיפוש, אבל אף אחד לא אמר שהם חייבים לשכוח את התווים שהאוטומט רואה. עד כאן, טוב ויפה - נראה שכל מה שעשינו הוא להוסיף לביטויים רגולריים יכולת שלא רלוונטית בכלל בדיון על שפות רגולריות ואוטומטים. אבל זה יותר מזה. אחת התכונות המעניינות של מנועים מודרניים של ביטויים רגולריים היא ביכולת שלהם לתמוך במה שנקרא "הפניה לאחור" - backreference. המשמעות של הפניה לאחור היא פשוטה: אם בשלב מוקדם יותר בביטוי לכדת משהו, אתה יכול להתייחס אליו בהמשך. האופן שבו עושים את זה הוא פשוט: לוכסן ואז מספר הסוגריים של ה"לכידה" (האם אלו הסוגריים הלוכדות הראשונות, השניות וכו'). הנה הדוגמה הקלאסית - ביטוי רגולרי שמזהה חזרה על אותה מילה פעמיים:

/(\w+)\s+\1/

הביטוי הזה אומר - קודם כל מילה כלשהי, שאני רוצה שתלכוד אז הקפתי אותה בסוגריים; אז מספר כלשהו של תווי רווח; ואז שוב פעם אותה המילה בדיוק, זה ה-1\ הזה. עכשיו, תעיפו את הרווח וקיבלנו ביטוי רגולרי עבור השפה \( L=\left\{ ww\ |\ w\in\Sigma^{*}\right\} \) שהיא די בבירור לא רגולרית (ובפוסט הבא נראה כיצד מוכיחים את זה פורמלית). אופס. ביטויים רגולריים בעולם האמיתי חזקים יותר מהתיאורטיים. האם זה אומר שאפשר לעשות הכל עם ביטויים רגולריים? ובכן, לא ממש. אני לא מכיר דרך לקבל את\( L=\left\{ a^{n}b^{n}\ |\ n\in\mathbb{N}\right\} \) עם ביטוי רגולרי אמיתי, למרות שאולי אפשר. והנה בעיה פרקטית. נניח שאנחנו רוצים לפרסר דף html אבל לא יודעים מה בדיוק לחפש כמו בדוגמה שנתתי למעלה, אלא רוצים פרסור כללי. הנה ביטוי רגולרי שמנסה לתפוס את כל מה שבתוך תג הטמל כלשהו, וגם לזכור מה התג עצמו:

/<([A-Z][A-Z0-9]*)[^>]*>(.*)<\/\1>/

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

<div id=”first”>bla</div><div id=”second”>blabla</div>

ועכשיו מה יקרה? הביטוי שלנו יחשוב שכל הדבר הזה הוא ב"אמצע" (קבוצת הלכידה השניה):

bla</div><div id=”second”>blabla

וזו כמובן טעות מרה. הבעיה היא שהוא לא זיהה מתי מגיע המופע של <div/> שסוגר את ה-div שאיתו הוא התחיל. אפשר לטעון שהבעיה כאן היא בכך שהביטוי הרגולרי הוא "חמדן" ומנסה לאכול מחרוזת ארוכה ככל הניתן. אפשר להגיד לו גם לא להיות חמדן, כך:

/<([A-Z][A-Z0-9]*)[^>]*>(.*?)<\/\1>/

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

הפעם מה שיילכד בתור ה"אמצע" הוא

וזה כמובן שגוי. שוב, הבעיה היא שהביטוי הרגולרי שלנו לא "סופר" - הוא לא יודע מתי כמות ה-<div/> שהוא ראה מתאזנת עם כמות ה-<div> שהוא ראה. בשל כך, ביטויים רגולריים הם לא משהו בשביל פרסור כללי של הטמל וצריך להשתמש בכלים חזקים יותר (שגם אליהם אגיע מתישהו בבלוג, בתקווה). ואם הגעתי לנקודה הזו, יש רק דרך אחת לסיים. באתר השאלות והתשובות stackoverflow מישהו שאל פעם בדיוק על זה - פרסור הטמל עם ביטויים רגולריים. הוא קיבל "תשובה" שאמנם קשה לומר שהיא תשובה מועילה יותר מדי, אבל היא אחד מהדברים המשעשעים ביותר שקשורים לביטויים רגולריים שאני מכיר (הו, יש המון! בדיחות ביטויים רגולריים זה אדיר!). היא כל כך מוצלחת שאני לא רק מקשר אליה אלא שם צילום מסך, שיהיה לתמיד (ולא, שום דבר לא מקולקל בצילום המסך או במחשב שלכם, כל הפונטים שם הם בכוונה):

נהניתם? התעניינתם? אם תרצו, אתם מוזמנים לתת טיפ: