ביטוי רגולרי – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף
אין תקציר עריכה
אין תקציר עריכה
שורה 1:
'''ביטוי רגולרי''' (ב[[עברית]], "ביטוי מתוקנן") הוא מונח אשר זכה להגדרות שונות במקצת בתחומי דעת שונים, אך בהגדרתו הכללית ביותר פירושו ביטוי ב[[שפה רגולרית]] ("שפה מתוקננת") שמוגדרת בעצמה כשני [[מחרוזת|מחרוזות]] או יותר הכפופים לתקנות [[תחביר]] מסוימות (יהיו תקנות אלה אשר יהיו).
ב[[מדעי המחשב]], '''ביטוי רגולרי''' (ב[[אנגלית]]: '''Regular Expression''' או בקיצור '''regex'''{{הערה|במסמכים מסוימים נכתב גם regexp.}}) הוא [[מחרוזת (מדעי המחשב)|מחרוזת]] (רצף של [[תו (מחשב)|תווים]]) אשר המאפיין העיקרי שלו הוא שימוש בתווי-מטא (Meta characters) כגון '''.''' (נקודה), '''\''' (לוכסן אחורי) ועוד, אשר מאפשרים לבצע עליו פעולות שונות של טיפול במידע (בפרט [[חיפוש והחלפה]]). תווי המטא הללו נבדלים לפי הגדרה מתווים רגילים (אותיות, כמו האותיות א' ו-ב' או A ו-B).
 
ב[[מדעי המחשב]], '''ביטוי רגולרי''' (ב[[אנגלית]]: '''Regular Expression''' או בקיצור '''regex'''{{הערה|במסמכים מסוימים נכתב גם regexp.}}) הוא [[מחרוזת (מדעי המחשב)|מחרוזת]] (רצף של [[תו (מחשב)|תווים]]) אשר המאפיין העיקרי שלו הוא שימוש בתווי-מטא (Meta characters).
ביטויים רגולריים מקבלים את שמם מתוקף כך שהם מתארים [[שפה רגולרית]], שבהגדרה הינה מחרוזת אחת או יותר המקיימת כללי [[תחביר]] מסוימים (יהיו כללים אלה אשר יהיו).
 
תויי-מטא לדוגמה הם '''.''' (נקודה), '''\''' (לוכסן אחורי), ^ (משולש עילי) ועוד, אשר מאפשרים לבצע במסמך ממוחשב פעולות שונות של טיפול במידע (בפרט [[חיפוש והחלפה]]). תווי המטא הללו נבדלים לפי הגדרה מתווים רגילים (אותיות, כמו האותיות א' ו-ב' או A ו-B); כאשר תו רגיל משקף את עצמו (למשל, האות א' היא תו שמסמל כמובן את האות א'), תו-מטא מסמל משהו אחר שאינו עצמו (למשל, משולש עילי משקף את הערך "תחילת השורה") ולכן נהוג להגיד על תווי-מטא שהם מסמלים "משהו אחר מעצמם".
בתורת ה[[שפה פורמלית|שפות הפורמליות]], '''ביטוי רגולרי''' הוא ביטוי שמסוגל לתאר אוסף של מילים (שפה) באמצעות שימוש בשלוש פעולות בסיסיות. חשיבותם של הביטויים הרגולריים נובעת מהקשר שלהם ל[[שפה רגולרית|שפות הרגולריות]]: כל שפה רגולרית (כלומר, המתקבלת על ידי [[אוטומט סופי|מכונת מצבים סופית]]) ניתנת להצגה באמצעות ביטוי רגולרי, וכל ביטוי רגולרי מייצג שפה רגולרית (כלומר, ישנה [[יחס שקילות|שקילות]] בין השפות הרגולריות והביטויים הרגולריים).
 
במחשבים מודרניים נפוץ תחביר ספציפי של ביטויים רגולריים הנקרא PERL (שזה ראשי תיבות של Perl Compatible Regular Experssions) ולביטויים רגלוריים אלה סט ייחודי של תווי-מטא המבדיל אותם מתחבירים אחרים.
 
לביטויים רגולריים שימושים רבים ב[[שפות תכנות]] (בעיקר שפות [[סקריפט]]ים ו[[מעטפת פקודה|מעטפות פקודה]], כגון [[perl]], [[bash]] וכיוצא בזה).
שימוש נפוץ בביטויים רגולריים הוא לחיפוש והחלפה של טקסטים, ו[[עיבוד נתונים]] טקסטואליים. הפופולריות של הביטויים הרגולריים גברה בעקבות הפונקציונליות שלהם ב[[פקודה (מחשב)|פקודות]] ה-[[UNIX]] הנפוצות: [[grep]] ו-[[sed]], אך כיום הם משמשים למגוון משימות מבוססות טקסט, לרבות יישומי רשת ([[XML]], [[HTML]]), מסדי-נתונים (שפת [[SQL]]), ועוד.
 
הפופולריות של הביטויים הרגולריים גברה בעקבות הפונקציונליות שלהם ב[[פקודה (מחשב)|פקודות]] ה-[[UNIX]] הנפוצות: [[grep]] ו-[[sed]], אך כיום הם משמשים למגוון משימות מבוססות טקסט, לרבות יישומי רשת ([[XML]], [[HTML]]), מסדי-נתונים (שפת [[SQL]]), ועוד.
==הגדרה פורמלית==
בהינתן [[אלפבית]] סופי <math>\ \Sigma</math>, ביטוי רגולרי מעל האלפבית מוגדר בצורה ה[[רקורסיה|רקורסיבית]] הבאה:
*<math>\ \emptyset</math> (הקבוצה הריקה) היא ביטוי רגולרי, שמתאר את השפה <math>\ \emptyset</math> (השפה הריקה).
*<math>\ \varepsilon</math> (המילה הריקה) היא ביטוי רגולרי שמתאר את השפה <math>\ \left\{\varepsilon\right\}</math> (השפה שמכילה רק את המילה הריקה).
*<math>\ a</math>, לכל <math>\ a\isin\Sigma</math>, הוא ביטוי רגולרי שמתאר את השפה <math>\ \left\{a\right\}</math>.
 
בתורת ה[[שפה פורמלית|שפות הפורמליות]], '''ביטוי רגולרי''' הוא ביטוי שמסוגל לתאר אוסף של מילים (שפה) באמצעות שימוש בשלוש פעולות בסיסיות. חשיבותם של הביטויים הרגולריים נובעת מהקשר שלהם ל[[שפה רגולרית|שפות הרגולריות]]: כל שפה רגולרית (כלומר, המתקבלת על ידי [[אוטומט סופי|מכונת מצבים סופית]]) ניתנת להצגה באמצעות ביטוי רגולרי, וכל ביטוי רגולרי מייצג שפה רגולרית (כלומר, ישנה [[יחס שקילות|שקילות]] בין השפות הרגולריות והביטויים הרגולריים).
כמו כן, אם <math>\ R,S</math> הם ביטויים רגולריים ו-<math>\ L\left[R\right],L\left[S\right]</math> השפות המתאימות להם, אז:
*<math>\ \left(R+S\right)</math> הוא ביטוי רגולרי המייצג את השפה <math>\ L\left[R\right]\cup L\left[S\right]</math>.
* <math>\ \left(R\cdot S\right)</math> הוא ביטוי רגולרי המייצג את השפה <math>\ L\left[R\right]\cdot L\left[S\right]</math>. (כלומר, השפה שכל מילה בה מורכבת משני חלקים, שהראשון שבהם שייך ל-<math>\ L\left[R\right]</math> והשני ל-<math>\ L\left[S\right]</math>).
* <math>\ \left(R^*\right)</math> הוא ביטוי רגולרי המייצג את השפה <math>\ L\left[R\right]^*</math> (כלומר, השפה שבה כל מילה מורכבת ממספר כלשהו - כולל 0 - של חלקים, וכל חלק שייך לשפה <math>\ L\left[R\right]</math>).
 
כדי לקצר את הכתיבה ולהמעיט ככל הניתן בשימוש בסוגריים, נהוגים '''כללי קדימויות'''. סדר הקדימויות מזכיר למדי את זה שנהוג ב[[אריתמטיקה]]:
#סוגריים: <math>\ \left(,\right)</math> - הפעולות שבתוך הסוגריים תמיד יתבצעו לפני הפעולות שמחוץ להן.
#איטרציה: <math>\ r^*</math>. אופרטור הכוכב נקרא גם [[תורת האוטומטים - מונחים|סגור קלין]].
#כפל: <math>\ r\cdot s</math>. כאשר אין חשש לבלבול משמיטים את סימן הכפל לחלוטין: <math>\ rs</math>.
#חיבור: <math>\ r+s</math>.
 
===דוגמאות===
# הביטוי הרגולרי <math>\ R=1^*0^*</math> מסמל את השפה שבה יש מספר כלשהו של 1-ים ואחריו מספר כלשהו של 0-ים: <math>\ L\left[R\right]=\left\{1^m0^n|m,n\ge0\right\}</math>.
# הביטוי הרגולרי <math>\ R=1\left(0+2\right)^*\left(1+\varepsilon\right)\left(0+2\right)^*</math> מסמל את השפה שכל מילה בה מתחילה ב-1 ואחר כך כוללת רצף כלשהו של 0 ו-2, כאשר 1 יכול להופיע פעם אחת נוספת במילה.
 
==הוכחת השקילות בין ביטויים רגולריים ושפות רגולריות==
כאמור לעיל, כל ביטוי רגולרי מתאר שפה רגולרית, ולכל שפה רגולרית קיים ביטוי רגולרי המתאר אותה.
 
===ביטוי רגולרי יוצר שפה רגולרית===
ההוכחה היא באינדוקציה פשוטה. קל להראות שהשפה הריקה וכל שפה שמכילה מילה אחת היא [[שפה רגולרית|רגולרית]], וכן שהשפות הרגולריות [[סגירות (אלגברה)|סגורות]] תחת איחוד, [[שרשור (מחרוזות)|שרשור]] ואיטרציה ([[תורת האוטומטים - מונחים|סגור קלין]]). מכיוון שהשפה שיוצר כל ביטוי רגולרי מתקבלת על ידי ביצוע פעולות של איחוד, שרשור ואיטרציה על אבני בניין בסיסיות שהן השפה הריקה ושפות שמכילות רק מילה אחת, הטענה נובעת מיד.
 
===לכל שפה רגולרית קיים ביטוי רגולרי===
טענה זו מסובכת יותר להוכחה. בהינתן שפה רגולרית <math>\ L</math> על פי ההגדרה קיים אוטומט סופי דטרמיניסטי <math>\ A</math> המקבל אותה. הביטוי הרגולרי נבנה בהתבסס על האוטומט. לצורך נוחות מסמנים את קבוצת המצבים שלו במספרים הטבעיים: <math>\ Q=\left\{q_1,\dots,q_n\right\}</math>, כאשר <math>\ q_1</math> הוא המצב ההתחלתי.
 
לצורך ההוכחה מוגדרות שפות עזר: <math>\ L_{ij}^k</math> מוגדרת כשפת כל המילים שמעבירות את האוטומט מהמצב <math>\ q_i</math> למצב <math>\ q_j</math> מבלי שהמסלול ייכנס וייצא ממצב שמספרו גדול מ-<math>\ k</math>. ברור כי <math>\ L(A)=\bigcup_{j:q_j\isin F} L_{1j}^n</math> - השפה שמקבל האוטומט היא אוסף כל המילים שמעבירות את האוטומט מהמצב הראשון למצב מקבל כלשהו, כאשר אין הגבלה על המצבים שמותר למסלול לעבור בדרך.
 
בשל כך מספיק להראות כיצד ניתן לקבל ביטוי רגולרי עבור השפה <math>\ L_{ij}^k</math>. הביטוי נבנה באופן רקורסיבי בהתבסס על ערכו של <math>\ k</math>. כאשר <math>\ k=0</math> השפה <math>\ L_{ij}^0</math> היא אוסף כל המילים שמעבירות את האוטומט מהמצב <math>\ q_i</math> למצב <math>\ q_j</math> מבלי לעבור '''שום''' מצב ביניים בדרך (שכן מספרו של כל אחד מהמצבים גדול מ-0). כלומר, מילים אלו הן אותיות או המילה הריקה. לכן לשפה <math>\ L_{ij}^0</math> קיים ביטוי רגולרי פשוט.
 
עבור <math>\ k>0</math> מתבססים על האבחנה הבאה: אם מילה שייכת ל-<math>\ L_{ij}^k</math>, או שהיא מעבירה את האוטומט מ-<math>\ q_i</math> אל <math>\ q_j</math> מבלי לעבור במצב <math>\ q_k</math> - ואז היא שייכת גם ל-<math>\ L_{ij}^{k-1}</math>, או שהאוטומט בריצתו על המילה כן עובר במצב <math>\ q_k</math> מספר כלשהו של פעמים.
 
אם האוטומט עובר ב-<math>\ q_k</math> ניתן לחלק את ריצתו לשלושה חלקים: הריצה עד שהוא מגיע אל <math>\ q_k</math> לראשונה; המשך הריצה עד שהוא מגיע ל-<math>\ q_k</math> בפעם האחרונה; והמשך הריצה עד ההגעה אל <math>\ q_j</math>
 
הרישא של המילה, שמעבירה את האוטומט מ-<math>\ q_i</math> אל <math>\ q_k</math> שייכת לשפה <math>\ L_{ik}^{k-1}</math>, ובצורה דומה גם הסיפא של המילה, שמעבירה את האוטומט מ-<math>\ q_k</math> אל <math>\ q_j</math> שייכת ל-<math>\ L_{kj}^{k-1}</math>. החלק הפנימי של המילה, שגורם לאוטומט לצאת מ-<math>\ q_k</math> ולחזור אל <math>\ q_k</math> מספר כלשהו של פעמים שייך ל-<math>\ \left(L_{kk}^{k-1}\right)^*</math>.
 
מכאן נובע שאם <math>\ r_{ij}^k</math> הוא הביטוי הרגולרי המתאים לשפה <math>\ L_{ij}^k</math>, הרי שמתקיים:
:<math>\ r_{ij}^k=r_{ik}^{k-1}\left(r_{kk}^{k-1}\right)^*r_{kj}^{k-1}+r_{ij}^{k-1}</math>. בצורה זו ניתן לבנות ביטוי רגולרי לכל אחת מהשפות <math>\ L_{ij}^k</math> תוך התבססות על הביטויים שכבר נבנו עבור ערכים קטנים יותר של <math>\ k</math>.
 
==שימושים בתכנות==
לביטויים רגולריים שימוש נרחב ביישומי תכנות למיניהם. מכיוון שכל ביטוי מזוהה עם מכונה אוטומטית סופית, קל לתרגם ביטוי רגולרי לתוכנה המזהה את קבוצת המילים המוגדרות על ידי אותו ביטוי. לדוגמה, [[מספר טלפון]] ב[[ישראל]] ניתן לזיהוי על ידי ביטוי רגולרי מהצורה <math>R=(0(\Gamma+\epsilon)\Gamma-\Gamma^7))</math>, כאשר האלפבית הוא כלל הספרות ומקף, ו<math>\Gamma=(0+1+2+3+4+5+6+7+8+9)</math>.
לכל [[שפת תכנות]] דרך שונה לייצג ביטוי רגולרי, אך כלל הייצוגים שקולים אלו לאלו, ולהגדרה הפורמלית המוצגת לעיל. למשל, בסטנדרט הנהוג ב-[[UNIX]], ייכתב הביטוי לעיל בצורה <math>0[0-9][0-9]?-[0-9]\{7\}</math>.
 
דוגמה נוספת, הביטוי 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 וכו').
 
*ב-[[Vi]], מעבד התמלילים הנפוץ במערכות UNIX, הפקודה הבאה:
<div style="text-align: left; direction: ltr; margin-left: 1em;">
:%s/gr[ea]y/white/
</div>
תחליף כל הופעה של המילה grey או gray במילה white. (% מפעיל את הפקודה על כל השורות ו-s פירושו החלפה, substitute).
 
*התוכנה grep התפתחה מפקודה שהייתה נפוצה בעורך הטקסט הישן, ed, ופירוש שמה הוא:
search '''g'''lobally for lines matching the '''r'''egular '''e'''xpression, and '''p'''rint them
כלומר, אם למשל נרצה להדפיס את כל השורות בקובץ בשם input.txt המתחילות בספרה 2,3,4 או 5 נעשה זאת כך:
<div style="text-align: left; direction: ltr; margin-left: 1em;">
grep "^[2-5]" input.txt
</div>
 
*בתוכנת sed, נוכל למשל למחוק כל שורה ריקה או שיש בה רק רווחים (* פירושו 0 או יותר מופעים, $ פירושו סוף השורה):
<div style="text-align: left; direction: ltr; margin-left: 1em;">
sed -e '/^ *$/d' in.txt
</div>
 
*בשפת perl השימוש בביטויים רגולריים נמצא בשורשה של השפה וקיימת תמיכה ברמה הגבוהה ביותר בכל סוגי הביטויים. רמה זאת הפכה לסטנדרט אליו מושווה רמת התמיכה בשפות ותוכנות אחרות. הפקודה הבאה תחליף כל מקום בו מופיעה המילה grey ב-blue אך רק כאשר לאחריה (סימן שאלה והסימן שווה פירושו "הצץ קדימה") מופיעה המילה sky.
<div style="text-align: left; direction: ltr; margin-left: 1em;">
$line=~s/grey(?= sky)/blue/g
</div>
 
* בסביבת ה[[דוט נט]] ישנה מחלקה מיוחדת לטיפול בביטויים רגולריים (System.Text.RegularExpressions) שבאמצעותה ניתן לאתר, להחליף תת-מחרוזות, ולקבל רשימה של התאמות במחרוזת לפי ביטויים רגולריים.
 
*תוכנת [[אורקל (בסיס נתונים)|Oracle]] מאפשרת לשלב ביטויים רגולריים בשאילתות SQL החל מגרסה 10. השאילתה הבאה תציג את כל הרשומות שבהן יש במיקוד (השדה zip) סימנים כלשהם שאינם ספרות:
<div style="text-align: left; direction: ltr; margin-left: 1em;">
SELECT zip FROM zipcode WHERE REGEXP_LIKE(zip, '[^[:digit:] ]')
</div>
 
כיום ניתן למצוא תמיכה בביטויים רגולריים כמעט בכל שפת תכנות נפוצה. כדאי להעיר שבמרבית המקרים, התמיכה שיש בשפות התכנות בביטויים רגולריים מרחיבה את הביטויים האפשריים גם לכאלו שמבחינה תאורטית אינם רגולריים. במנועי חיפוש כמעט ולא מוצאים אופציות לשימוש בביטויים רגולריים אך דוגמה חיובית לכך היא מנוע החיפוש של גוגל לקטעי קוד. דוגמה למנוע חיפוש פנימי באתר גדול, שהייתה בו בעבר תמיכה מוגבלת בביטויים רגולריים, אך היא בוטלה, הוא [[eBay]]. פירוט לגבי כל סוגי התווים המשמשים בביטויים רגולריים אפשר למצוא בקישורים בתחתית ערך זה.
 
== לקריאה נוספת ==
* אוטומטים ושפות פורמליות, {{פא"ר|מספר=418|שם הספר=חלק א|כותב=שמואל זקס ו[[נסים פרנסיז]]|שנה=2000}} ו{{פא"ר|מספר=419|שם הספר=חלק ב||שנה=2000}}
* Jeffrey Friedl, Mastering Regular Expressions. O'Reilly Media 2006
 
== קישורים חיצוניים ==
{{מיזמים|ויקיספר=אוטומטים ושפות פורמליות}}
* {{לא מדויק|2015/01/29/regular_expressions|ביטויים רגולריים}}
*[http://gskinner.com/RegExr/ אתר לבניית ובדיקת ביטויים רגולריים]
*[http://www.regular-expressions.info/reference.html מדריך בסיסי לשימוש בביטויים רגולריים] וכן [http://www.regular-expressions.info/tutorial.html מדריך לימוד מלא], שניהם ב[[אנגלית]], באתר [http://www.regular-expressions.info regular-expressions]
*[http://www.addedbytes.com/cheat-sheets/regular-expressions-cheat-sheet/ A quick reference guide for regular expressions (regex) to get you started], באתר addedbytes
* [http://www.johndcook.com/cpp_regex.html ביטויים רגולריים] ב[[ספריית התבניות התקנית]] של שפת ++C
* [http://docs.python.org/library/re.html ביטויים רגולריים] ב[[פייתון]]
* [http://perl.eitan.ac.il/main.php?id=00106 ביטויים רגולרים בשפת פרל], אתר אית"ן
 
==הערות שוליים==
{{הערות שוליים}}
 
[[קטגוריה:שפות פורמליות]]