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

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

typedef struct {
    void* elements;
    unsigned length;
} Array;

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

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;

typedef struct {
    Stmt* stmts;
    unsigned length;
} StmtArray;

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

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

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

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

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

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

בואו נתחיל להסתכל על הקוד מלמעלה למטה:

StmtArray parse(TokenArray tokens) {
    unsigned tokens_index = 0;
    unsigned stmt_index = 0;
    Stmt* stmts = (Stmt*)malloc(tokens.length * sizeof(Stmt));

    while (tokens_index < tokens.length) {
        stmts[stmt_index] = parse_stmt(tokens, &tokens_index);
        ++stmt_index;
    }
    return (StmtArray){ .stmts = stmts, .length = stmt_index };
}

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

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

בואו נמשיך להסתכל פנימה. איך מפרסרים משפט?

משפטים

Stmt parse_stmt(TokenArray tokens, unsigned* tokens_index) {

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

    char* identifier = parse_identifier(tokens, tokens_index);

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

    // While
    if (is_while(identifier)) {
        Expr condition = parse_expr(tokens, tokens_index);
        StmtArray block = parse_block(tokens, tokens_index);

        return (Stmt) {
            .tag = WHILE,
            .data.While = {
                .condition = condition,
                .block = {
                    .elements = block.stmts,
                    .length = block.length,
                },
            },
        };
    }

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

    // Set
    else if (maybe_parse_token(tokens, tokens_index, EQUALS)) {
        Expr expr = parse_expr(tokens, tokens_index);

        return (Stmt) {
            .tag = SET,
            .data.Set = {
                .name = identifier,
                .expr = expr,
            },
        };
    }

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

    // Expression
    else if (maybe_parse_token(tokens, tokens_index, OPENPAREN)) {
        Expr expr = parse_function(tokens, tokens_index, identifier);

        return (Stmt) {
            .tag = EXPR,
            .data.Expr = {
                .expr = expr,
            },
        };
    }

אם אין לנו לא לולאה ולא הצבה, ננסה לפרסר פונקציה.

    // Error
    else {
        fprintf(stderr, "Parse error: Unexpected token. Expected '(' or '='");
        exit(1);
    }

לבסוף, אם לא הצלחנו לפרסר, נחזיר שגיאה.

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

char* parse_identifier(TokenArray tokens, unsigned* tokens_index);
int is_while(char* string);
int maybe_parse_token(TokenArray tokens, unsigned* tokens_index, TokenTag tag);
Expr parse_expr(TokenArray tokens, unsigned* tokens_index);
Expr parse_function(TokenArray tokens, unsigned* tokens_index, char* name);
StmtArray parse_block(TokenArray tokens, unsigned* tokens_index);

השלוש הראשונות דיי פשוטות ו-low-level, בואו נעיף אותן מהדרך ונסתכל עליהן ראשונות.

char* parse_identifier(TokenArray tokens, unsigned* tokens_index) {
    if (*tokens_index < tokens.length) {
        Token token = tokens.tokens[*tokens_index];
        ++(*tokens_index);
        if (token.tag != IDENTIFIER) {
            fprintf(stderr, "Parse error: got wrong token: %d, expected IDENTIFIER\n", token.tag);
            exit(1);
        }
        return token.data.identifier;
    } else {
        fprintf(stderr, "Parse error: unexpected end of text.\n");
        exit(1);
    }
}

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

אם התנאים כן מתקיימים, נבדוק את התגית. אם היא IDENTIFIER, נחזיר את הדאטה שלה.

int is_while(char* string) {
    if (strcmp("while", string) == 0) { return 1; }
    return 0;
}

נבדוק אם המילה שמצאנו היא while באמצעות strcmp.

void parse_token(TokenArray tokens, unsigned* tokens_index, TokenTag tag) {
    if (!(maybe_parse_token(tokens, tokens_index, tag))) {
        fprintf(stderr, "Parse error: unexpected token. Expected %d\n", tag);
        exit(1);
    }
}

int maybe_parse_token(TokenArray tokens, unsigned* tokens_index, TokenTag tag) {
    if (*tokens_index < tokens.length) {
        Token token = tokens.tokens[*tokens_index];
        if (token.tag == tag) {
            ++(*tokens_index);
            return 1;
        }
    }
    return 0;
}

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

בלוקים, ביטויים ופונקציות

נמשיך להיכנס פנימה ועכשיו נסתכל על בלוקים:

StmtArray parse_block(TokenArray tokens, unsigned* tokens_index) {
    parse_token(tokens, tokens_index, OPENCURLY);
    Stmt* stmts = (Stmt*)malloc((tokens.length - *tokens_index) * sizeof(Stmt));
    unsigned stmt_index = 0;
    while (*tokens_index < tokens.length && tokens.tokens[*tokens_index].tag != CLOSECURLY) {
        stmts[stmt_index] = parse_stmt(tokens, tokens_index);
        ++stmt_index;
    }
    parse_token(tokens, tokens_index, CLOSECURLY);
    return (StmtArray) {
        .stmts = stmts,
        .length = stmt_index,
    };
}

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

בואו נפרסר ביטוי:

Expr parse_expr(TokenArray tokens, unsigned* tokens_index) {
    if (*tokens_index < tokens.length) {
        Token token = tokens.tokens[*tokens_index];
        ++(*tokens_index);
        switch (token.tag) {
        case INTEGER: {
            return (Expr) {
                .tag = LITERAL,
                .data.integer = token.data.integer,
            };
        }
        case IDENTIFIER: {
            if (maybe_parse_token(tokens, tokens_index, OPENPAREN)) {
                return parse_function(tokens, tokens_index, token.data.identifier);
            } else {
                return (Expr) {
                    .tag = VARIABLE,
                    .data.variable = token.data.identifier,
                };
            }
        }
        default:
            fprintf(stderr, "Parse error: got wrong token: %d, expected IDENTIFIER or INTEGER\n", token.tag);
            exit(1);
        }
    } else {
        fprintf(stderr, "Parse error: unexpected end of text.\n");
        exit(1);
    }
}

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

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

Expr parse_function(TokenArray tokens, unsigned* tokens_index, char* name) {
    Expr* exprs = (Expr*)malloc((tokens.length - *tokens_index) * sizeof(Expr));
    unsigned expr_index = 0;
    while (*tokens_index < tokens.length && tokens.tokens[*tokens_index].tag != CLOSEPAREN) {
        exprs[expr_index] = parse_expr(tokens, tokens_index);
        ++expr_index;
        if (!maybe_parse_token(tokens, tokens_index, COMMA)) {
            break;
        }
    }
    parse_token(tokens, tokens_index, CLOSEPAREN);

    return (Expr) {
        .tag = FUNCTION,
        .data.function = {
            .name = name,
            .args = (Array) {
                .elements = exprs,
                .length = expr_index,
            },
        },
    };
}

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

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

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

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

void print_expr(Expr expr) {
    switch (expr.tag) {
    case LITERAL:
        printf("%d", expr.data.integer);
        break;
    case VARIABLE:
        printf("%s", expr.data.variable);
        break;
    case FUNCTION: {
        printf("%s(", expr.data.function.name);
        for (unsigned i = 0; i < expr.data.function.args.length; ++i) {
            print_expr(((Expr*)expr.data.function.args.elements)[i]);
            if (i +1 < expr.data.function.args.length) {
                printf(", ");
            }
        }
        printf(")");
        break;
    }
    }
}

void print_stmt(Stmt stmt, unsigned indentation) {
    for (unsigned i = 0; i < indentation; ++i) {
        printf("    ");
    }
    switch (stmt.tag) {
    case SET:
        printf("%s = ", stmt.data.Set.name);
        print_expr(stmt.data.Set.expr);
        break;
    case WHILE:
        printf("while ");
        print_expr(stmt.data.While.condition);
        printf(" {\n");

        for (unsigned i = 0; i < stmt.data.While.block.length; ++i) {
            print_stmt(((Stmt*)stmt.data.While.block.elements)[i], indentation + 1);
            printf("\n");
        }
        printf("}");
        break;
    case EXPR:
        print_expr(stmt.data.Expr.expr);
        break;
    }
}

void print_ast(StmtArray stmts) {
    for (unsigned i = 0; i < stmts.length; ++i) {
        print_stmt(stmts.stmts[i], 0);
        printf("\n");
    }
}

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

סיכום

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

כתבנו, מה שנקרא, Recursive decent parser, שבנוי ״מלמעלה למטה״ בצורה רקורסיבית בה אנחנו יוצרים פונקציות כ״אבסטרקציה״ לכל קונספט שאנחנו מנסים לפרסר. ובסופו של יום, הקוד מורכב מכמה if-ים, while-ים, וקריאות רקורסיביות לפונקציה.

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

> 🚧 חלק רביעי: פענוח

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

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

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

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

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

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

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

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

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

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

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