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

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

בין מפרשים ומהדרים יש הרבה מאוד דברים דומים. השלב האחרון הוא זה ששונה בדרך כלל (תרגום קוד מול הרצה), אבל גם יש להם אילוצים שונים כמו לדוגמא שמהדרים יכולים לקחת את הזמן כדי ליצור תוכנית אופטימלית ומפרשים בד"כ צריכים להתחיל לרוץ כמה שיותר מהר גם אם התוכנית עצמה לא תהיה הכי מהירה, וגם שכדי שהביצועים של מפרש יהיו טובים מומלץ להשתמש בשפה יותר "low-level" ועבור מהדרים זה קצת פחות עקרוני והרבה מהדרים כתובים בשפות מאוד "high-level".

תהליך

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

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

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

בצורת קוד, התהליך נראה כך:

#include "ast.h"
#include "lex.h"
#include "parse.h"
#include "execute.h"

void run(char* code, unsigned length) {
    TokenArray tokens = lex(code, length);
    StmtArray program = parse(tokens);
    execute(program);
}

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

הגדרת השפה

בואו נתחיל בלראות דוגמה של תוכנית קצרה בשפה ומשם נגזור את הפיצ'רים שאנחנו צריכים ואיך לייצג אותם בקוד:

sum = 0
counter = 10

while counter {
    sum = add(sum, counter)
    counter = add(counter, negate(1))
}

print(sum)

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

אז איזה פיצ'רים אנחנו צריכים בשפה שלנו?

> ערכים מסוג מספרים שלמים (ליטרלים)

כדי שנוכל לרשום 0, 1 ו-10

> הצבת ערך במשתנה

כדי שנוכל להציב ערכים בשמות המשתנים sum ו-counter

> שימוש במשתנים

כדי שנוכל להשתמש בשם במקום בערך

> לולאת while

כזו שמקבלת פרמטר אחד שהוא מספר, המספר 0 אומר להפסיק וכל מספר אחר אומר להמשיך

> קריאה לפונקציות

עם הפונקציות print, add ו-negate. גם חשוב שיהיה ניתן לקונן אותן

למעשה אנחנו אפילו יכולים לקטלג את הפיצ'רים למעלה לשתי קטגוריות:

> ביטויים

תחת הקטגוריה הזו נופלים המספרים (ליטרלים), השימוש במשתנים, וקריאה לפונקציות

> פקודות/משפטים

תחת הקטגוריה הזו נופלים הצבת ערך במשתנים, לולאת הwhile, והרצת ביטוי (בשביל print).

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

עץ תחביר אבסטרקטי

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

בשפה ממשפחת ML, כמו Haskell או OCaml, יש פיצ'ר שנקרא טיפוסים אלגבריים. בעזרתו אפשר להגדיר את ה-AST שלנו באמצעות כמה טיפוסים שלהם כמה וריאנטים. לדוגמא בהסקל:

-- Representing our expressions
data Expression
  = Num Integer
  | Var String
  | Fun String [Expression]

אנחנו יכולים להגדיר טיפוס חדש בשם Expression שלו שלושה סוגים של ערכים אפשריים שכל אחד מהוריאנטים האלה מלווים עם "תגית". במקרה הזה התגיות הן Num, Var ו-Fun.

ואז לדוגמא ערכים אפשריים של הטיפוס Expression הם:

• Var "counter"
• Num 10
• Fun "negate" (Num 1)

ובשפות האלה התגיות והדאטה הולכות ביחד, אי אפשר לערבב לדוגמא את התגית Num עם הערך "counter", וגם אפשר להגדיר טיפוסים רקורסיביים (וגם מספר טיפוסים רקורסיביים בצורה הדדית) בקלות. מה שהופך את הפיצ'ר הזה למאוד חזק במיוחד עבור מימוש שפות תכנות.

לצערנו, ל-C אין את הפיצ'ר הזה בדיוק, אבל אנחנו בכל זאת הולכים לנסות לחקות אותו עם הכלים שברשותינו באמצעות struct, enum ו-union ונגדיר את הטיפוסים שלנו. נתחיל ב-Expr:

// I want to know the length of an array.
typedef struct {
    void* elements;
    unsigned length;
} Array;

// An expression.
typedef struct {
    enum {
        LITERAL,
        VARIABLE,
        FUNCTION,
    } tag;
    union {
        int integer;
        char* variable;
        struct { char* name; Array args; } function;
    } data;
} Expr;

הרעיון הכללי הוא: שדה הtag עבור כל טיפוס מחזיק את סוג הטיפוס, ושדה הdata מחזיק את המידע הנלווה המתאים לכל תג. לדוגמא ביטוי בצורת מספר ליטרלי (התג) והערך 10 בוריאציה integer (הדאטה), או קריאה לפונקציה בה הדאטה הוא שם הפונקציה לה אנחנו רוצים לקרוא, ומערך של פרמטרים (וכאן אנחנו קצת מרמים עם void* שמייצג מצביע לכל סוג דאטה (אנחנו נשתמש בו רק לExpr, מבטיח!)

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

נגדיר גם טיפוס עבור "משפטים/פקודות", ובזה נסיים את הגדרת ה-AST של השפה:

// A statement.
typedef struct {
    enum {
        SET,
        WHILE,
        EXPR,
    } tag;
    union {
        struct { char* name; Expr expr; } Set;
        struct { Expr condition; Array block; } While;
        struct { Expr expr; } Expr;
    } data;
} Stmt;

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

אם אתם רוצים לדעת יותר על ההבדלים בין הגישה הפונקציונלית (שאנחנו לוקחים) לגישה המונחית עצמים, תמצאו הרבה מאוד מידע אם תחפשו את המושג "The Expression Problem".

הלאה

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

כשאני כותב מימושים של שפות תכנות בשפה כמו הסקל, אני אוהב ללכת לכיוון השני קודם, מאחר שזה גם קל להגדיר את ה-AST, גם קל לכתוב ביד את הייצוג של קוד תוכנית הדוגמא כ-AST, וגם כי קל לכתוב את שלב ההרצה באמצעות רקורסיה ופיצ'ר שנקרא Pattern Matching. אך מאחר ואנחנו כותבים ב-C והמחשבה של לכתוב את הדוגמה שלנו כ-AST של C בקוד מעוררת בי חלחלה, נלך לכיוון הראשון ונלמד לקרוא את קוד המקור ולתרגם אותו ל-AST.

נתראה בפוסט הבא:

> חלק שני: ניתוח לקסיקלי

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

תוכן עניינים בסדרת - המפרש הראשון שלי

> חלק ראשון: הקדמה ושפה

נדבר קצת על תהליך הפירוש ונגדיר את השפה אותה נממש.

> חלק שני: ניתוח לקסיקלי

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

> חלק שלישי: ניתוח תחבירי

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

> 🚧 חלק רביעי: הרצה

מעבר על תוכנית הריצה לפי סדרה וביצוע הפעולות אותה כל פקודה מייצגת.

רוצים להגיב? בדקו מהי שאלת הסינון בעמוד הראשי.