Loading AI tools
רצף תווים שמגדיר תבנית חיפוש מוויקיפדיה, האנציקלופדיה החופשית
ביטוי רגולרי (מאנגלית: Regular expression או regex) הוא רצף תווים שמגדיר תבנית חיפוש. בהגדרתו הכללית ביותר פירושו ביטוי בשפה רגולרית (שפה מתוקננת), שמוגדרת כשתי מחרוזות או יותר הכפופות לתקנות תחביר מסוימות (יהיו תקנות אלו אשר יהיו).
תווי-מטא (Meta characters) משתנים מעט משפה רגולרית אחת לאחרת אך דוגמאות נפוצות לתווי מטא הם למשל נקודה (.), לוכסן אחורי (\), גג (^) ועוד, אשר מאפשרים לבצע במסמך ממוחשב פעולות שונות של טיפול במידע (בפרט חיפוש והחלפה). תווי המטא הללו נבדלים לפי הגדרה מתווים רגילים (כמו האותיות a ו-b); בעוד שתווים רגילים מסמלים את עצמם תווי-מטא מסמלים משהו אחר שאינו הם עצמם (למשל, גג משקף את הערך "תחילת השורה").
לביטויים רגולריים שימושים רבים בשפות תכנות (בעיקר שפות סקריפטים ומעטפות פקודה, כגון perl, bash ועוד). שימוש נפוץ נוסף של ביטויים רגולריים הוא בעריכת טקסט בעורכי טקסט כגון Notepad++ או Vim.
תחביר נפוץ במיוחד שלהם הוא PCRE (ראשי תיבות של Perl Compatible Regular Expressions) ולביטויים רגולריים אלה סט ייחודי של תווי-מטא המבדיל אותם מתחבירים אחרים.
הפופולריות של הביטויים הרגולריים גברה בעקבות הפונקציונליות שלהם בפקודות ה-UNIX הנפוצות: grep ו-sed, אך כיום הם משמשים למגוון משימות מבוססות טקסט, לרבות יישומי רשת (XML, HTML), מסדי-נתונים (שפת SQL) ועוד.
בתורת השפות הפורמליות, ביטוי רגולרי הוא ביטוי שמסוגל לתאר אוסף של מילים (שפה) באמצעות שימוש בשלוש פעולות בסיסיות. חשיבותם של הביטויים הרגולריים נובעת מהקשר שלהם לשפות הרגולריות: כל שפה רגולרית (כלומר, המתקבלת על ידי מכונת מצבים סופית) ניתנת להצגה באמצעות ביטוי רגולרי, וכל ביטוי רגולרי מייצג שפה רגולרית (כלומר, יש שקילות בין השפות הרגולריות והביטויים הרגולריים).
בהינתן אלפבית סופי , ביטוי רגולרי מעל האלפבית מוגדר בצורה הרקורסיבית הבאה:
כמו כן, אם הם ביטויים רגולריים ו- השפות המתאימות להם, אז:
כדי לקצר את הכתיבה ולהמעיט ככל הניתן בשימוש בסוגריים, נהוגים כללי קדימויות. סדר הקדימויות מזכיר למדי את זה שנהוג באריתמטיקה:
כאמור לעיל, כל ביטוי רגולרי מתאר שפה רגולרית, ולכל שפה רגולרית קיים ביטוי רגולרי המתאר אותה.
ההוכחה היא באינדוקציה פשוטה. קל להראות שהשפה הריקה וכל שפה שמכילה מילה אחת היא רגולרית, וכן שהשפות הרגולריות סגורות תחת איחוד, שרשור ואיטרציה (כוכב קלין). מכיוון שהשפה שיוצר כל ביטוי רגולרי מתקבלת על ידי ביצוע פעולות של איחוד, שרשור ואיטרציה על אבני בניין בסיסיות שהן השפה הריקה ושפות שמכילות רק מילה אחת, הטענה נובעת מיד.
טענה זו מסובכת יותר להוכחה. בהינתן שפה רגולרית על פי ההגדרה קיים אוטומט סופי דטרמיניסטי המקבל אותה. הביטוי הרגולרי נבנה בהתבסס על האוטומט. לצורך נוחות מסמנים את קבוצת המצבים שלו במספרים הטבעיים: , כאשר הוא המצב ההתחלתי.
לצורך ההוכחה מוגדרות שפות עזר: מוגדרת כשפת כל המילים שמעבירות את האוטומט מהמצב למצב מבלי שהמסלול ייכנס וייצא ממצב שמספרו גדול מ-. ברור כי - השפה שמקבל האוטומט היא אוסף כל המילים שמעבירות את האוטומט מהמצב הראשון למצב מקבל כלשהו, כאשר אין הגבלה על המצבים שמותר למסלול לעבור בדרך.
בשל כך מספיק להראות כיצד ניתן לקבל ביטוי רגולרי עבור השפה . הביטוי נבנה באופן רקורסיבי בהתבסס על ערכו של . כאשר השפה היא אוסף כל המילים שמעבירות את האוטומט מהמצב למצב מבלי לעבור שום מצב ביניים בדרך (שכן מספרו של כל אחד מהמצבים גדול מ-0). כלומר, מילים אלו הן אותיות או המילה הריקה. לכן לשפה קיים ביטוי רגולרי פשוט.
עבור מתבססים על האבחנה הבאה: אם מילה שייכת ל-, או שהיא מעבירה את האוטומט מ- אל מבלי לעבור במצב - ואז היא שייכת גם ל-, או שהאוטומט בריצתו על המילה כן עובר במצב מספר כלשהו של פעמים.
אם האוטומט עובר ב- ניתן לחלק את ריצתו לשלושה חלקים: הריצה עד שהוא מגיע אל לראשונה; המשך הריצה עד שהוא מגיע ל- בפעם האחרונה; והמשך הריצה עד ההגעה אל
הרישא של המילה, שמעבירה את האוטומט מ- אל שייכת לשפה , ובצורה דומה גם הסיפא של המילה, שמעבירה את האוטומט מ- אל שייכת ל-. החלק הפנימי של המילה, שגורם לאוטומט לצאת מ- ולחזור אל מספר כלשהו של פעמים שייך ל-.
מכאן נובע שאם הוא הביטוי הרגולרי המתאים לשפה , הרי שמתקיים:
לביטויים רגולריים שימוש נרחב ביישומי תכנות למיניהם. מכיוון שכל ביטוי מזוהה עם מכונה אוטומטית סופית, קל לתרגם ביטוי רגולרי לתוכנה המזהה את קבוצת המילים המוגדרות על ידי אותו ביטוי. לדוגמה, מספר טלפון בישראל ניתן לזיהוי על ידי ביטוי רגולרי מהצורה , כאשר האלפבית הוא כלל הספרות ומקף, ו. לכל שפת תכנות דרך שונה לייצג ביטוי רגולרי, אך כלל הייצוגים שקולים אלו לאלו, ולהגדרה הפורמלית המוצגת לעיל. למשל, בסטנדרט הנהוג ב-UNIX, ייכתב הביטוי לעיל בצורה .
דוגמה נוספת, הביטוי ab[2-5]de מתאים למילים ab2de,ab3de,ab4de ו-ab5de כיוון שפירושו הוא: כל המחרוזות בהם מופיעה האות a, לאחריה b, לאחריה מספר בין 2 ל-5 ואחר כך d ו-e. באופן דומה, הביטוי a.b פירושו האות a ו-b וביניהן כל תו, והביטוי ab*c פירושו האותיות a ו-c וביניהן האות b בכמות כלשהי (ac,abc,abbc,abbbbbbbc וכו').
תחליף כל הופעה של המילה grey או gray במילה white. (% מפעיל את הפקודה על כל השורות ו-s פירושו החלפה, substitute).
search globally for lines matching the regular expression, and print them כלומר, אם למשל נרצה להדפיס את כל השורות בקובץ בשם input.txt המתחילות בספרה 2,3,4 או 5 נעשה זאת כך:
grep "^[2-5]" input.txt
sed -e '/^ *$/d' in.txt
$line=~s/grey(?= sky)/blue/g
SELECT zip FROM zipcode WHERE REGEXP_LIKE(zip, '[^[:digit:] ]')
כיום ניתן למצוא תמיכה בביטויים רגולריים כמעט בכל שפת תכנות נפוצה. כדאי להעיר שבמרבית המקרים, התמיכה שיש בשפות התכנות בביטויים רגולריים מרחיבה את הביטויים האפשריים גם לכאלו שמבחינה תאורטית אינם רגולריים. במנועי חיפוש כמעט ולא מוצאים אופציות לשימוש בביטויים רגולריים, דוגמה חיובית לכך הייתה מנוע החיפוש של גוגל לקטעי קוד, Google Code Search, שפעל בין 2006—2012. דוגמה למנוע חיפוש פנימי באתר גדול, שהייתה בו בעבר תמיכה מוגבלת בביטויים רגולריים, אך היא בוטלה, הוא eBay. אתר ויקיפדיה תומך בחיפוש ביטויים רגולריים בחיפוש בקוד המקור (insource://). פירוט לגבי כל סוגי התווים המשמשים בביטויים רגולריים אפשר למצוא בקישורים בתחתית ערך זה.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.