פרק 10: דקדוקים

10.1 CFG (דקדוק חסר הקשר)

פרולוג הפכה לכלי יעיל לפיתוח יישומים בתחומים רבים, בראשם בינה מלאכותית (Artificial Intelligence, AI) ועיבוד שפה טבעית (Natural Language Processing, NLP).
בפרק זה נפגוש לראשונה יישום בתחום ה-NLP – שימוש בפרולוג לשם תכנות דקדוק לשפה טבעית.

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

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

דקדוקים חסרי הקשר (Context Free Grammar, CFG) הם דקדוקים פורמליים שאינם חזקים דיים כדי לתאר את כל התופעות הלשוניות שנצפו בשפות טבעיות שונות בעולם, אבל מספיקים כדי לתאר את רובן. הם כלי יעיל לתיאור ולניתוח של שפות טבעיות ובעלי מבנה חוקים ברור וקל להבנה.

דקדוק חסר הקשר מכיל חוקים מהצורה הבאה:

A -> a B

<- מגדיר את החוק, A ו-B הם non-terminals (סימנים לא-טרמינלים), a הוא terminal (טרמינל). מצד שמאל יופיע לא-טרמינל אחד בלבד. מצד ימין יופיע רצף של טרמינלים ולא-טרמינלים.

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

		S -> NP VP

		NP -> N

		VP -> V (NP)

		N -> yossi

		N -> daysa

		V -> bishel

		V -> axal

הסימנים הלא-טרמינלים מתחילים באות גדולה ושמם לקוח מתחום הבלשנות: S הוא המשפט (Sentence); N משמעו שם-עצם (Noun), ו-NP הוא פשוט צירוף שמני (Noun Phrase); V הוא פועל (Verb), ו-VP הוא צירוף פעלי.
הסימנים הטרמינליים באותיות קטנות הם פשוט המילים שיש בשפה. כאן, ב"שפת הצעצוע" שלנו יש רק ארבע מילים: שני שמות עצם ושני פעלים.

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

		VP -> V NP

		VP -> V

ניתן לפרש את החוקים כהוראות כיצד ניתן להרכיב צירופים ומשפטים. את החוק הראשון נקרא כך "משפט מורכב מ-/ניתן לבנות מ- צירוף שמני ואחריו צירוף פעלי". החוק השני משמעו "צירוף פעלי מורכב מ-/ניתן לבנות מ- שם-עצם". החוק האחרון אומר "בישל הוא פועל".

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

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

תרשים כזה המתאר את מבנהו התחבירי של משפט קרוי עץ תחבירי (parse tree).
שימו לב שהסימנים הלא-טרמינליים נמצאים רק בגוף העץ, ואילו הסימנים הטרמינליים יושבים בתחתיתו.

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

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

שתי שאלות שנרצה להשיב עליהן בהינתן רצף מילים ודקדוק הן: