הגענו לחלק האחרון, בו אנחנו עוברים על ה-AST ומבצעים את הכוונה של התוכנית.

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

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

אנחנו צריכים לדעת מה הפקודה שאנחנו הולכים לבצע. לקונספט הזה יש כמה שמות, ביניהם program counter (pc) או instruction pointer (ip). ייתכן שאפילו נרצה לשמור מחסנית של ״כתובות״ בהם ביקרנו בכל קריאה לפונקציה, כדי שנדע לאן לחזור ב return.

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

איפה כל המשתנים יושבים?

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

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

מבחינת קוד, מבנה הנתונים של הזכרון יראה כך:

typedef struct {
    unsigned* next_free_cell_index;
    Array memory;
} Memory;

Memory new_memory() {
    unsigned size = 1024;
    unsigned* next_free_cell_index = (unsigned*)calloc(1, sizeof(unsigned));
    int* mem = (int*)malloc(sizeof(int) * size);
    return (Memory){
        .next_free_cell_index = next_free_cell_index,
        .memory = {
            .length = size,
            .elements = mem,
        }
    };
}

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

איך אני יודע אילו משתנים זמינים לי בכל רגע נתון?

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

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

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

struct Cell {
    char* name;
    int* memory_cell;
    struct Cell* next;
};

typedef struct {
    struct Cell* next;
} Scope;

Scope new_scope() {
    return (Scope) { .next = NULL };
}

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

int* lookup(char* name, Scope scope) {
    struct Cell* cell = scope.next;
    while (cell != NULL) {
        if (strcmp(cell->name, name) == 0) {
            return cell->memory_cell;
        } else {
            cell = cell->next;
        }
    }
    return NULL;
}

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

Scope insert(char* name, int value, Memory memory, Scope scope) {
    if (*memory.next_free_cell_index + 1 < memory.memory.length) {
        int* memory_cell = &((int*)(memory.memory.elements))[*memory.next_free_cell_index];
        ++*memory.next_free_cell_index;
        *memory_cell = value;
        struct Cell* cell = (struct Cell*)malloc(sizeof(struct Cell));
        *cell = (struct Cell) {
            .name = name,
            .memory_cell = memory_cell,
            .next = scope.next,
        };
        Scope new_scope = (Scope) {.next = cell};
        return new_scope;
    }
    fprintf(stderr, "Error: out of memory.");
    exit(1);
}

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

רצים על התוכנית

נתחיל לעבור על התוכנית ועל הקוד מלמעלה למטה.

void execute(StmtArray stmts) {
    Memory memory = new_memory();
    Scope scope = new_scope();
    for (unsigned pc = 0; pc < stmts.length; ++pc) {
        Stmt stmt = stmts.stmts[pc];
        scope = interpret_stmt(stmt, memory, scope);
    }
}

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

משפט

בואו נסתכל איך מריצים משפט:

Scope interpret_stmt(Stmt stmt, Memory memory, Scope scope) {
    switch (stmt.tag) {
    case SET: {
        int result = eval_expr(stmt.data.Set.expr, memory, scope);
        int* memory_cell = lookup(stmt.data.Set.name, scope);
        if (memory_cell != NULL) {
            *memory_cell = result;
        } else {
            return insert(stmt.data.Set.name, result, memory, scope);
        }
        break;
    }
    case WHILE: {
        while (eval_expr(stmt.data.While.condition, memory, scope)) {
            Scope new_scope = scope;
            for (unsigned i = 0; i < stmt.data.While.block.length; ++i) {
                Stmt current = ((Stmt*)stmt.data.While.block.elements)[i];
                new_scope = interpret_stmt(current, memory, new_scope);
            }
            // free the part of the scope we are done with
            struct Cell* next = new_scope.next;
            while (next != NULL && next != scope.next) {
                struct Cell* nextnext = next->next;
                free(next);
                next = nextnext;
            }
        }
        break;
    }
    case EXPR:
        eval_expr(stmt.data.Expr.expr, memory, scope);
        break;
    }
    return scope;
}

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

ביטוי

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

• עבור ערך מספרי ליטרלי, התוצאה שלו היא עצמו.
• עבור משתנה, נשלוף אותו מהסביבה (ואם לא נצליח, נדווח על שגיאה ונצא).
• עבור פונקציה, נבדיל בין 3 פונקציות שאנחנו מממשים: print, add, ו-negate. כל אחת תחשב בצורה רקורסיבית את הפרמטרים שלה (שהם ביטויים בעצמם), ואחרי שנקבל ערכים מספריים מכל חישוב, נבצע עליהם את הפעולה המתאימה ב-C: חיבור, חיסור מ-0, או הדפסה לפלט הסטנדרטי. אם השם של הפונקציה לא מתאים לאף פונקציה שאנחנו מכירים, נחזיר שגיאה.

int eval_expr(Expr expr, Memory memory, Scope scope) {
    switch (expr.tag) {
    default:
    case LITERAL: {
        return expr.data.integer;
    }
    case VARIABLE: {
        int* result = lookup(expr.data.variable, scope);
        if (result == NULL) {
            fprintf(stderr, "Error: variable not found '%s'\n", expr.data.variable);
            exit(1);
        } else {
            return *result;
        }
    }
    case FUNCTION: {
        if (strcmp(expr.data.function.name, "print") == 0) {
            if (expr.data.function.args.length == 1) {
                int arg = eval_expr(((Expr*)expr.data.function.args.elements)[0], memory, scope);
                printf("%d\n", arg);
                return 0;
            } else {
                fprintf(stderr, "Error: print expects a single argument.\n");
                exit(1);
            }
        }
        else if (strcmp(expr.data.function.name, "add") == 0) {
            if (expr.data.function.args.length == 2) {
                int arg1 = eval_expr(((Expr*)expr.data.function.args.elements)[0], memory, scope);
                int arg2 = eval_expr(((Expr*)expr.data.function.args.elements)[1], memory, scope);
                return arg1 + arg2;
            } else {
                fprintf(stderr, "Error: negate expects a single argument.\n");
                exit(1);
            }
        }
        else if (strcmp(expr.data.function.name, "negate") == 0) {
            if (expr.data.function.args.length == 1) {
                int arg = eval_expr(((Expr*)expr.data.function.args.elements)[0], memory, scope);
                return 0 - arg;
            } else {
                fprintf(stderr, "Error: negate expects a single argument.\n");
                exit(1);
            }
        }
        else {
			fprintf(stderr, "Error: Unknown function '%s'. Only supporting: add, negate, print.\n", expr.data.function.name);
			exit(1);
		}
    }
    }
}

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

התחלנו את המסע עם תוכנית מאוד פשוטה שמחשבת את סכום המספרים מ1 עד 10 (כולל):

sum = 0
counter = 10

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

print(sum)

כעת, אם נריץ את המפרש שלנו, תודפס למסך השורה הבאה:

55

מקסים.

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

סיכום

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

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

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

אני רוצה עוד

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

אם שבעתם, מגניב! אני מקווה שנהנתם!

אבל אם אתם רוצים ללמוד עוד על התחום הזה, יש הרבה הרבה מאוד מידע בנושא, ברמות שונות של סיבוך ובגישות שונות ללימוד. אנסה להמליץ על כמה:

> Crafting Interpreters (ספר, חינם)

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

> Engineering a Compiler (ספר, בתשלום)

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

> CSE131 וגם CS4410 (קורסים, חינם)

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

> Compiler Design: Virtual Machines (ספר, בתשלום)

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

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

זה הכל, תודה שקראתם!

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