|
אחד ממאפייניה הבולטים של כל שפה אנושית הוא שחוקיה מכילים רקורסיה. למעשה, יש הטוענים שבכך מותר האדם מן הבהמה, שגם לה לעיתים יכולת לתקשר באמצעות שפה, אך כזו שאיננה רקורסיבית.
חוקים רקורסיביים הם אלה שמאפשרים לנו ליצור, לפחות באופן תיאורטי, אינסוף משפטים בשפתנו:
הסתכלו על הכלב!
הסתכלו על המלונה של הכלב!
הסתכלו על הגג של המלונה של הכלב!
.
.
.
ננסה להעניק לדקדוק שכתבנו עד כה יכולת לזהות משפטים עם רקורסיה, על ידי כך שנוסיף לו חוקים רקורסיביים.
הרקורסיה במשפטים לעיל היא ברמת הצירוף השמני. הצירוף המלונה של הכלב, למשל, בנוי משני צירופים שמניים, קרי המלונה והכלב, אשר מחוברים ביניהם על ידי של, אשר לענייננו נתייחס אליה כאל מילת חיבור (conjunction, או בקיצור conj).
נוסיף לדקדוק שכתבנו חוק רקורסיבי לצירוף שמני ומילת חיבור:
np --> np, conj, np.
conj --> [shel].
|
|
כעת פרולוג מזהה משפט עם רקורסיה כמשפטים חוקיים בשפה:
?- s([yossi, raa, meluna, shel, ha, kelev],[]).
Yes
?- s([yossi, raa, meluna, shel, ha, kelev, shel, yafa],[]).
Yes
יופי!
אבל, חשוב לבדוק גם שהחוק שכתבנו לא מאפשר לכתוב משפטים שאינם דקדוקיים. משפט כזה הוא למשל יוסי ראה מלונה של הכלב של אכל. ואמנם, פרולוג לא מזהה את המשפט כדקדוקי, אבל הוא גם לא מגלה שהמשפט איננו דקדוקי. הוא פשוט נכנס ללולאה אינסופית ומדווח על שגיאה:
?- s([yossi, raa, meluna, shel, ha, kelev, shel, axal],[]).
ERROR: Out of local stack
Exception: (42,310) np([axal], _G600) ? creep
Exception: (8) vp([raa, meluna, shel, ha, kelev, shel, axal], []) ? creep
מה קורה כאן? היכן מסתתרת לולאה אינסופית בתכנית שלנו?
נבחן בעיון את החוקים לצירוף שמני בתכנית:
np --> n.
np --> det, n.
np --> np, conj, np.
פרולוג מסתבך בנסיון למצוא מבנה חוקי של צירוף שמני במשפט (בצדק, אין כזה...). מכיוון שאחרי של צריך למצוא צירוף שמני, פרולוג מנסה להוכיח שהמילה אכל מהווה צירוף שמני. החוק הראשון לא עוזר (כי אכל הוא פועל v ולא שם n). גם מהחוק השני לא צומחת ישועה (אין ה הידיעה לפני הפועל). או אז מנסה פרולוג להשתמש בחוק השלישי של צירוף שמני. המטרה הראשונה שעליו להוכיח היא np. איך עושים זאת? מנסים את החוק הראשון, השני והשלישי של צירוף שמני. הראשון לא מצליח, גם השני לא, אז מנסים את השלישי. וחוזר וחלילה... כאן פרולוג נכנס ללולאה אינסופית.
איך נפתור את הבעיה?
האם אפשר לשנות את סדר המטרות בגוף החוק הרקורסיבי, כפי שהצענו כשלמדנו על רקורסיה?
ADD LINK TO RCRSN CHAPTER, WITH ANCHOR
התשובה היא לא, משום שסדר המטרות הנוכחי משקף את סדר המילים במשפטים תקינים בעברית. לא ניתן לומר בעברית של המלונה יוסי, ולכן אין לכתוב חוק שיאפשר סדר כזה.
הפתרון במקרה זה הוא להגדיר שני סוגים של צירוף שמני: צירוף שמני פשוט, וצירוף שמני מורכב הבנוי מצירוף שמני פשוט, מילת חיבור, ועוד צירוף שמני.
התכנית הסופית פועלת כמו שצריך:
?- s([yossi, raa, meluna, shel, ha, kelev],[]).
Yes
?- s([yossi, raa, meluna, shel, ha, kelev, shel, yafa],[]).
Yes
?- s([yossi, raa, meluna, shel, ha, kelev, shel, axal],[]).
No
|
