ביטוי רגולרי

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

שימוש נפוץ בביטויים רגולריים הוא לחיפוש והחלפה של טקסטים במעבד תמלילים. כמו כן יש להם שימוש רב בשפות תיכנות כמו perl ו-Tcl לצורת עיבוד נתונים טקסטואליים, אך הפופולריות של הביטויים הרגולריים גברה בעקבות הפונקציונליות שלהם בפקודות ה-UNIX הנפוצות: grep ו-sed.

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

תוכן עניינים

1 שימושים במדעי המחשב
2 הגדרה פורמלית
3 דוגמאות
4 הוכחת השקילות בין ביטויים רגולריים ושפות רגולריות
- 4.1 ביטוי רגולרי יוצר שפה רגולרית
- 4.2 לכל שפה רגולרית קיים ביטוי רגולרי
5 לקריאה נוספת
6 קישורים חיצוניים

[עריכה] שימושים במדעי המחשב

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

באופן כללי, אם נסביר על ידי דוגמה, הביטוי 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 הפקודה הבאה:

%s/gr[ea]y/white/

תחליף כל הופעה של המילה grey או gray במילה white. (% מפעיל את הפקודה על כל השורות ו-s פירושו החלפה, substitute).

התוכנה grep היתפתחה מפקודה שהייתה נפוצה בעורך הטקסט הישן, ed, ופירוש שמה הוא:

search globally for lines matching the regular expression, and print them כלומר, אם למשל נרצה להדפיס את כל השורות בקובץ בשם input.txt המתחילות בספרה 2,3,4 או 5 נעשה זאת כך:

grep "^[2-5]" in.txt

בתוכנת sed, נוכל למשל למחוק כל שורה ריקה או שיש בה רק רווחים (* פירושו 0 או יותר מופעים, $ פירושו סוף השורה):

sed -e '/^ *$/d' in.txt

בשפת perl השימוש בביטויים רגולריים נמצא בשורשה של השפה וקיימת תמיכה ברמה הגבוהה ביותר בכל סוגי הביטויים. רמה זאת הפכה לסטנדרט אליו מושווה רמת התמיכה בשפות ותוכנות אחרות. הפקודה הבאה תחליף כל מקום בו מופיעה המילה grey ב-blue אך רק כאשר לאחריה (סימן שאלה והסימן שווה פירושו "הצץ קדימה") מופיעה המילה sky.

$line=~s/grey(?= sky)/blue/g

תוכנת Oralce מאפשרת לשלב ביטויים רגולריים בשאילתות SQL החל מגירסה 10. השאילתה הבאה תציג את כל הרשומות שבהן יש במיקוד (השדה zip) סימנים כלשהם שאינם ספרות:

SELECT zip FROM zipcode WHERE REGEXP_LIKE(zip, '[^[:digit:]]')

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

[עריכה] הגדרה פורמלית

בהינתן אלף בית סופי $\ \Sigma$ , ביטוי רגולרי מעל האלף בית מוגדר בצורה הרקורסיבית הבאה:

$\ \emptyset$ (הקבוצה הריקה) היא ביטוי רגולרי, שמתאר את השפה $\ \emptyset$ (השפה הריקה).
$\ \varepsilon$ (המילה הריקה) היא ביטוי רגולרי שמתאר את השפה $\ \left\{\varepsilon\right\}$ (השפה שמכילה רק את המילה הריקה).
$\ a$ , לכל $\ a\isin\Sigma$ , הוא ביטוי רגולרי שמתאר את השפה $\ \left\{a\right\}$ .

כמו כן, אם $\ R,S$ הם ביטויים רגולריים ו- $\ L\left[R\right],L\left[S\right]$ השפות המתאימות להם, אז:

$\ \left(R+S\right)$ הוא ביטוי רגולרי המייצג את השפה $\ L\left[R\right]\cup L\left[S\right]$ .
$\ \left(R\cdot S\right)$ הוא ביטוי רגולרי המייצג את השפה $\ L\left[R\right]\cdot L\left[S\right]$ . (כלומר, השפה שכל מילה בה מורכבת משני חלקים, שהראשון שבהם שייך ל- $\ L\left[R\right]$ והשני ל- $\ L\left[S\right]$ ).
$\ \left(R^*\right)$ הוא ביטוי רגולרי המייצג את השפה $\ L\left[R\right]^*$ (כלומר, השפה שבה כל מילה מורכבת ממספר כלשהו - כולל 0 - של חלקים, וכל חלק שייך לשפה $\ L\left[R\right]$ ).

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

סוגריים: $\ \left(,\right)$ - הפעולות שבתוך הסוגריים תמיד יתבצעו לפני הפעולות שמחוץ להן.
איטרציה: $\ r^*$ .
כפל: $\ r\cdot s$ . כאשר אין חשש לבלבול משמיטים את סימן הכפל לחלוטין: $\ rs$ .
חיבור: $\ r+s$ .

[עריכה] דוגמאות

הביטוי הרגולרי $\ R=1^*0^*$ מסמל את השפה שבה יש מספר כלשהו של 1-ים ואחריו מספר כלשהו של 0-ים: $\ L\left[R\right]=\left\{1^m0^n|m,n\ge0\right\}$ .
הביטוי הרגולרי $\ R=1\left(0+2\right)^*\left(1+\varepsilon\right)\left(0+2\right)^*$ מסמל את השפה שכל מילה בה מתחילה ב-1 ואחר כך כוללת רצף כלשהו של 0 ו-2, כאשר 1 יכול להופיע פעם אחת נוספת במילה.

[עריכה] הוכחת השקילות בין ביטויים רגולריים ושפות רגולריות

[עריכה] ביטוי רגולרי יוצר שפה רגולרית

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

[עריכה] לכל שפה רגולרית קיים ביטוי רגולרי

כיוון זה מסובך יותר. בהינתן שפה רגולרית $\ L$ על פי ההגדרה קיים אוטומט סופי דטרמיניסטי $\ A$ המקבל אותה. הביטוי הרגולרי נבנה בהתבסס על האוטומט. לצורך נוחות מסמנים את קבוצת המצבים שלו במספרים הטבעיים: $\ Q=\left\{q_1,\dots,q_n\right\}$ , כאשר $\ q_1$ הוא המצב ההתחלתי.

לצורך ההוכחה מוגדרות שפות עזר: $\ L_{ij}^k$ מוגדרת כשפת כל המילים שמעבירות את האוטומט מהמצב $\ q_i$ למצב $\ q_j$ מבלי שהמסלול ייכנס וייצא ממצב שמספרו גדול מ- $\ k$ . ברור כי $\ L(A)=\bigcup_{j:q_j\isin F} L_{1j}^n$ - השפה שמקבל האוטומט היא אוסף כל המילים שמעבירות את האוטומט מהמצב הראשון למצב מקבל כלשהו, כאשר אין הגבלה על המצבים שמותר למסלול לעבור בדרך.

בשל כך מספיק להראות כיצד ניתן לקבל ביטוי רגולרי עבור השפה $\ L_{ij}^k$ . הביטוי נבנה באופן רקורסיבי בהתבסס על ערכו של $\ k$ . כאשר $\ k=0$ השפה $\ L_{ij}^0$ היא אוסף כל המילים שמעבירות את האוטומט מהמצב $\ q_i$ למצב $\ q_j$ מבלי לעבור שום מצב ביניים בדרך (שכן מספרו של כל אחד מהמצבים גדול מ-0). כלומר, מילים אלו הן אותיות או המילה הריקה. לכן לשפה $\ L_{ij}^0$ קיים ביטוי רגולרי פשוט.

עבור $\ k>0$ מתבססים על האבחנה הבאה: אם מילה שייכת ל- $\ L_{ij}^k$ , או שהיא מעבירה את האוטומט מ- $\ q_i$ אל $\ q_j$ מבלי לעבור במצב $\ q_k$ - ואז היא שייכת גם ל- $\ L_{ij}^{k-1}$ , או שהאוטומט בריצתו על המילה כן עובר במצב $\ q_k$ מספר כלשהו של פעמים.

אם האוטומט עובר ב- $\ q_k$ ניתן לחלק את ריצתו לשלושה חלקים: הריצה עד שהוא מגיע אל $\ q_k$ לראשונה; המשך הריצה עד שהוא מגיע ל- $\ q_k$ בפעם האחרונה; והמשך הריצה עד ההגעה אל $\ q_j$

הרישא של המילה, שמעבירה את האוטומט מ- $\ q_i$ אל $\ q_k$ שייכת לשפה $\ L_{ik}^{k-1}$ , ובצורה דומה גם הסיפה של המילה, שמעבירה את האוטומט מ- $\ q_k$ אל $\ q_j$ שייכת ל- $\ L_{kj}^{k-1}$ . החלק הפנימי של המילה, שגורם לאוטומט לצאת מ- $\ q_k$ ולחזור אל $\ q_k$ מספר כלשהו של פעמים שייך ל- $\ \left(L_{kk}^{k-1}\right)^*$ .

מכאן נובע שאם $\ r_{ij}^k$ הוא הביטוי הרגולרי המתאים לשפה $\ L_{ij}^k$ , הרי שמתקיים:

$\ r_{ij}^k=r_{ik}^{k-1}\left(r_{kk}^{k-1}\right)^*r_{kj}^{k-1}+r_{ij}^{k-1}$ . בצורה זו ניתן לבנות ביטוי רגולרי לכל אחת מהשפות $\ L_{ij}^k$ תוך התבססות על הביטויים שכבר נבנו עבור ערכים קטנים יותר של $\ k$ .

[עריכה] לקריאה נוספת

שמואל זקס ונסים פרנסיז, אוטומטים ושפות פורמליות, האוניברסיטה הפתוחה, 2000.

[עריכה] קישורים חיצוניים

מקור: http://he.wikipedia.org../../../%D7%91/%D7%99/%D7%98/%D7%91%D7%99%D7%98%D7%95%D7%99_%D7%A8%D7%92%D7%95%D7%9C%D7%A8%D7%99.html

קטגוריה: חישוביות

ביטוי רגולרי

מתוך ויקיפדיה, האנציקלופדיה החופשית

תוכן עניינים

[עריכה] שימושים במדעי המחשב

[עריכה] הגדרה פורמלית

[עריכה] דוגמאות

[עריכה] הוכחת השקילות בין ביטויים רגולריים ושפות רגולריות

[עריכה] ביטוי רגולרי יוצר שפה רגולרית

[עריכה] לכל שפה רגולרית קיים ביטוי רגולרי

[עריכה] לקריאה נוספת

[עריכה] קישורים חיצוניים

Views

ניווט

קהילה

חיפוש

שפות אחרות