שפות תכנות — מרחב למידה אישי

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

1. תחביר בטון מול תחביר מופשט: הדרך מהטקסט למבנה

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

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

תחביר מופשט (Abstract Syntax Tree - AST): ייצוג היררכי של מבנה התוכנית, לרוב כעץ, המדגיש את המרכיבים הסמנטיים המהותיים ומתעלם מפרטים תחביריים שאינם משפיעים על המשמעות (כגון סוגריים מיותרים).

תחביר בטון

מיועד לקריאה וכתיבה אנושית.
כולל פרטים כמו סוגריים, נקודה-פסיק, רווחים.
דוגמה: if (x > 0) { y = 1; } else { y = 0; }

תחביר מופשט (AST)

מיועד לעיבוד על ידי מהדרים ומפרשים.
מייצג את המבנה הלוגי של התוכנית.
דוגמה: עץ עם צומת "If", שלושה ילדים: "Condition" (x > 0), "Then" (y = 1), "Else" (y = 0).

תפקיד ה-AST בפיתוח שפות

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

2. סמנטיקה אופרציונלית: הגדרת משמעות התוכנית

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

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

כיצד פועלת סמנטיקה אופרציונלית?

היא מגדירה "כללי מעבר" (transition rules) המציינים כיצד ביטוי או פקודה מסוימת משנה את מצב המערכת (למשל, את ערכי המשתנים בסביבה). כללים אלו מנוסחים בדרך כלל כזוגות (תוכנית, מצב) -> (תוכנית', מצב'), המייצגים צעד חישוב בודד (סמנטיקה אופרציונלית בצעד קטן - small-step) או את התוצאה הסופית (סמנטיקה אופרציונלית בצעד גדול - big-step). בקבצים כמו interp.scm, אנו רואים מימוש של כללי סמנטיקה אופרציונלית.

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

3. ייצוג נתונים וסביבות ריצה

כדי שתוכנית תוכל לרוץ, עלינו לייצג לא רק את מבנה הקוד (באמצעות AST), אלא גם את הנתונים שהיא מעבדת ואת הסביבה שבה היא רצה.

ייצוג נתונים (Data Representation): האופן שבו ערכים (מספרים, בוליאנים, מחרוזות, פונקציות וכו') מיוצגים באופן פנימי בתוך המפרש או המהדר.

סביבת ריצה (Environment): מיפוי ממשתנים לערכיהם. סביבות משמשות לניהול היקף (scope) של משתנים ולשמירת מצב התוכנית במהלך הביצוע.

הקשר בין AST, סמנטיקה, נתונים וסביבות

המפרש (interp.scm) מקבל AST ומפעיל עליו את כללי הסמנטיקה האופרציונלית. כללים אלו משתמשים בסביבה (environments.scm) כדי למצוא את ערכיהם של משתנים, ויוצרים ייצוגי נתונים (data-structures.scm) עבור התוצאות הביניים והסופיות של החישובים. לדוגמה, בעת הערכת ביטוי כמו x + 5, המפרש יחפש את ערכו של x בסביבה, יקבל ייצוג נתונים של x, יבצע את פעולת החיבור עם 5, ויפיק ייצוג נתונים חדש עבור התוצאה.

שאלות לדיון

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

נקודות לתשובת מודל

AST מול תחביר בטון: AST לוכד את המבנה הלוגי והסמנטי של התוכנית, מתעלם מפרטים תחביריים שאינם מהותיים (כמו סוגריים מיותרים), ובכך מפשט את תהליך הניתוח והעיבוד הסמנטי. הוא מהווה ייצוג קומפקטי ונוח לעיבוד ממוחשב.
יתרונות הסמנטיקה האופרציונלית: מספקת הגדרה מדויקת, חד-משמעית ופורמלית של התנהגות התוכנית, צעד אחר צעד. היא מאפשרת הוכחת נכונות של תוכניות, השוואה בין שפות, ומהווה בסיס איתן למימוש מפרשים ומהדרים נכונים.
ייצוג פקודת if:
- תחביר בטון: if (condition) { then_branch; } else { else_branch; } (כולל מילות מפתח, סוגריים, נקודה-פסיק).
- AST: צומת מסוג If, שלושה ילדים: צומת Condition (עבור condition), צומת Then (עבור then_branch), צומת Else (עבור else_branch).
- סמנטיקה אופרציונלית: כלל המגדיר שאם הערכת condition מניבה true, יש לבצע את then_branch; אחרת, יש לבצע את else_branch. כלל זה יכלול מעברים ממצב אחד למשנהו בהתאם לתוצאת ה-condition.
אינטראקציה בין ASTs, סביבות ונתונים: המפרש משתמש ב-AST כדי לדעת איזה ביטוי או פקודה יש להעריך. במהלך ההערכה, הוא ניגש לסביבת הריצה כדי למצוא את הערכים הנוכחיים של משתנים (למשל, כאשר הוא נתקל ב-identifier ב-AST). התוצאות של הערכות ביניים וערכים סופיים מיוצגים באמצעות ייצוגי נתונים פנימיים של השפה (למשל, אובייקטים המייצגים מספרים, בוליאנים או פונקציות).

מצאתם טעות או שחסר משהו?