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

10.2 DCG

פרולוג מאפשר לנו לכתוב דקדוקים באמצעות Definite Clause Grammars (DCG). Definite Clauses בפרולוג הם שם אחר לחוקים ולעובדות. צורת הכתיבה של DCG-ים נוחה וטבעית, ונראית כמעט זהה לצורת הכתיבה של דקדוקים חסרי הקשר שראינו קודם.

את הדקדוק שהצגנו קודם נכתוב כעת בצורת DCG כתכנית פרולוג:

s --> np,vp.
np --> n.
vp --> v,np.
vp --> v.
n --> [yossi].
n --> [daysa].
v --> [bishel].
v --> [axal].
התכנית להורדה.

באופן כללי, חוק DCG הוא מהצורה:

non-terminal --> expansion

כאשר expansion הוא אחד הבאים:

  1. סימן לא-טרמינלי (np).
  2. רשימה של סימנים טרמינלים ([yossi]).
  3. רכיב ריק, מיוצג באמצעות הרשימה הריקה [].
  4. מטרה רגילה בפרולוג מוקפת בסוגריים מסולסלים.
  5. רצף של סימנים לעיל מופרדים בפסיקים (np,vp).

איך יודע פרולוג להתייחס אל התכנית כאל דקדוק?

נבדוק את הייצוג הפנימי של של s, למשל:

?- listing(s).
s(A, B) :-
np(A, C),
vp(C, B).
Yes

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

אנו רואים ש-s הוא מתאר פרולוג רגיל שיש לו שני מתוארים, A ו-B, ומוגדר באמצעות המתארים np ו-vp. מה המשמעות של המתוארים A, B, C?

• A הוא רצף המילים שאותו מבקשים לנתח, נתון בצורת רשימה.
• B הוא רצף המילים ההתחלתי, להוציא המילים המרכיבות את ה-np ואת ה-vp.
• C הוא רצף המילים ההתחלתי, להוציא המילים המרכיבות את ה-np.

מנקודת מבט יותר הצהרתית:

• הורדת s מ-A נותן B
• הורדת np מ-A נותן C
• הורדת vp מ-C נותן B

אם נציג את השאילתא:

?- s([yossi,bishel,daysa],[]).

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

פרולוג עושה כאן שימוש ברשימות הפרשים לצורך החישוב. הרכיבים התחביריים (שם עצם, משפט וכולי) מיוצגים באמצעות הפרש בין שתי רשימות.
רשימת ההפרשים [yossi,bishel,daysa] ו-[] מייצגת משפט משום שאם מחסירים מהרשימה הראשונה את הרשימה השנייה מתקבל משפט. באופן דומה, ההפרש בין [yossi,bishel,daysa] לבין [bishel daysa] מייצג את הצירוף השמני יוסי.

הייצוג של פרולוג למילים עצמן, הסימנים הטרמינלים, הוא כזה:

?- listing(v).
v([bishel|A], A).
v([axal|A], A).
Yes

משמעות הקוד היא שכדי לזהות למשל את הפועל בישל, צריך לראות אותו ברצף המילים שהוא הקלט.

כעת, כשברור יותר כיצד עובדים עם DCG-ים, אנו מבינים כיצד ניתן להשתמש בהם כדי להציג לפרולוג שאילתות זיהוי כגון:

?- np([yossi,bashlan,dagul],[bashlan,dagul]).
Yes

אפשר גם לבקש את כל הצירופים השמניים המיוצרים על ידי הדקדוק:

?- np(NP, []).
NP = [yossi] ;
NP = [daysa] ;
No

ה-DCG עונה על השאלה הראשונה שהצבנו לעצמנו: "האם רצף המילים הוא חוקי על פי הדקדוק?"
הוא מזהה (recognizer) לדקדוק חסר הקשר.

משימה קשה יותר היא לכתוב מנתח (parser). זאת נעשה בפרויקט המסכם.

מבוא

נושאים בסיסיים

נושאים מתקדמים

סיכום

© כל הזכויות שמורות למערכת המידע איתן