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

שפות מורכבות

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

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

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

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

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

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

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

סוגי ספריות

הסיבה השניה היא סוג הספריות איתן התחלתי.

ישנם כל מני סוגי אלגוריתמים שונים לניתוח תחבירי שלהם פשרות שונות כמו מורכבות, ביצועים, אקספרסיביות, ועוד. לדוגמא Pratt, Earley, Recursive decent. בנוסף, ישנן סוגי ספריות שונות שכל אחת מהן נותנת ממשק אחר לכתיבת פרסר, כגון parser combinators, generators, tree sitter. הספריות השונות משתנות גם באיכות השגיאות שהן מוציאות, התאוששות משגיאות, היכולת לפרסר בצורה אינקרמנטלית או חלקית, והתאימות עם כלים שונים (לדוגמא syntax highlighting), ועוד.

יש הרבה מאוד אופציות והרבה מהן מאוד מורכבות כדי לתמוך בשפות מורכבות ויכולות מורכבות.

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

הסיבה השלישית

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

אז הנה אנחנו פה, אחרי שבחרנו שפה קלה יחסית ובגישה "פשוטה" יחסית, נתחיל בלבצע את השלב הראשון - ניתוח לקסיקלי!

ניתוח לקסיקלי (lexing)

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

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

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

כרגיל, לפני שניגש לכתיבת האלגוריתם, בואו נגדיר מהם האסימונים האפשריים שלנו בצורת טיפוסים:

typedef enum {
    IDENTIFIER,
    INTEGER,
    OPENPAREN,
    CLOSEPAREN,
    OPENCURLY,
    CLOSECURLY,
    EQUALS,
    COMMA,
} TokenTag;

typedef struct {
    TokenTag tag;
    union {
        char* identifier;
        int integer;
    } data;
} Token;

typedef struct {
    Token* tokens;
    unsigned length;
} TokenArray;

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

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

TokenArray lex(char* txt, unsigned length) {
    // We'll put tokens we lexed successfully here.
    Token* tokens = (Token*)malloc(length * sizeof(Token));
    // Where to put the next token in tokens.
    unsigned tokens_index = 0;

    // The index for the input.
    unsigned txt_index = 0;
    while (txt_index < length && txt[txt_index] != '\0') {
        switch (txt[txt_index]) {
        // Ignore spaces, tabs and newlines
        case ' ': {
            ++txt_index;
            break;
        }
        case '\t': {
            ++txt_index;
            break;
        }
        case '\n': {
            ++txt_index;
            break;
        }
        // EQUALS
        case '=': {
            tokens[tokens_index] = (Token){ .tag = EQUALS, .data.integer = 0, };
                                  // note ^: `.data.integer = 0` above is a dummy value.
            ++tokens_index;
            ++txt_index;
            break;
        }
        // COMMA
        case ',': {
            tokens[tokens_index] = (Token){ .tag = COMMA, .data.integer = 0, };
            ++tokens_index;
            ++txt_index;
            break;
        }
        // OPENPAREN
        case '(': {
            tokens[tokens_index] = (Token){ .tag = OPENPAREN, .data.integer = 0, };
            ++tokens_index;
            ++txt_index;
            break;
        }
        // CLOSEPAREN
        case ')': {
            tokens[tokens_index] = (Token){ .tag = CLOSEPAREN, .data.integer = 0, };
            ++tokens_index;
            ++txt_index;
            break;
        }
        // OPENCURLY
        case '{': {
            tokens[tokens_index] = (Token){ .tag = OPENCURLY, .data.integer = 0, };
            ++tokens_index;
            ++txt_index;
            break;
        }
        // CLOSECURLY
        case '}': {
            tokens[tokens_index] = (Token){ .tag = CLOSECURLY, .data.integer = 0, };
            ++tokens_index;
            ++txt_index;
            break;
        }
        // Complex cases and errors.
        default: {
            // Identifiers.
            if (is_identifier_char(txt[txt_index])) {
                char* word = malloc(128);
                unsigned word_index = 0;
                while (txt_index < length && txt[txt_index] != '\0' && is_identifier_char(txt[txt_index]) && word_index < 128) {
                    word[word_index] = txt[txt_index];
                    ++word_index;
                    ++txt_index;
                }
                tokens[tokens_index] = (Token){ .tag = IDENTIFIER, .data.identifier = word, };
                ++tokens_index;
            }
            // Integers.
            else if (is_numeric(txt[txt_index])) {
                char word[9] = { '\0' };
                unsigned word_index = 0;
                while (txt_index < length && txt[txt_index] != '\0' && is_numeric(txt[txt_index]) && word_index < 9) {
                    word[word_index] = txt[txt_index];
                    ++word_index;
                    ++txt_index;
                }
                int integer = atoi(word);
                tokens[tokens_index] = (Token){ .tag = INTEGER, .data.integer = integer, };
                ++tokens_index;
            }
            // Not a token.
            else {
                printf("unexpected character '%c'", txt[txt_index]);
                exit(1);
            }
        }
        }
    }
    return (TokenArray){ .tokens = tokens, .length = tokens_index };
}

// Here we also decide which characters are valid for identifiers.
int is_identifier_char(char c) {
    return c == '_' || ('a' <= c && c <= 'z');
}

int is_numeric(char c) {
    return ('0' <= c && c <= '9');
}

זה כל הקוד. הוא לא הכי מקסים אבל הוא דיי פשוט וישיר.

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

IDENTIFIER 'sum'
EQUALS
NUMBER 0
IDENTIFIER 'counter'
EQUALS
NUMBER 10
IDENTIFIER 'while'
IDENTIFIER 'counter'
OPENCURLY
IDENTIFIER 'sum'
EQUALS
IDENTIFIER 'add'
OPENPAREN
IDENTIFIER 'sum'
COMMA
IDENTIFIER 'counter'
CLOSEPAREN
IDENTIFIER 'counter'
EQUALS
IDENTIFIER 'add'
OPENPAREN
IDENTIFIER 'counter'
COMMA
IDENTIFIER 'negate'
OPENPAREN
NUMBER 1
CLOSEPAREN
CLOSEPAREN
CLOSECURLY
IDENTIFIER 'print'
OPENPAREN
IDENTIFIER 'sum'
CLOSEPAREN

void print_TokenArray(TokenArray tokens) {
    unsigned token_index = 0;
    while (token_index < tokens.length) {
        Token token = tokens.tokens[token_index];
        ++token_index;
        switch (token.tag) {
        case IDENTIFIER:
            printf("IDENTIFIER '%s'\n", token.data.identifier);
            break;
        case INTEGER:
            printf("NUMBER %d\n", token.data.integer);
            break;
        case OPENPAREN:
            printf("OPENPAREN\n");
            break;
        case CLOSEPAREN:
            printf("CLOSEPAREN\n");
            break;
        case OPENCURLY:
            printf("OPENCURLY\n");
            break;
        case CLOSECURLY:
            printf("CLOSECURLY\n");
            break;
        case EQUALS:
            printf("EQUALS\n");
            break;
        case COMMA:
            printf("COMMA\n");
            break;
        }
    }
}

ועם זה, הרבה יותר קל לעבוד.

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

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

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

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

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

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

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

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

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

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

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

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

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