Tokenizer

"Gereksiz detaylardan" kurtulmayı bu aşamada yapacağız. if, int gibi keyword'leri ya da punctuation'ları string formatında saklamaktansa onlara sayısal ID'ler atayacağız.

enum token_id {
        TK_IF,
        TK_ELSE,
        TK_TY_INT,
        TK_PLUS,
        TK_MINUS,
        // ...
};

Keyword ve punctuation'lara karşılık gelen token ID'lerimizi, tasarlayacağımız dile göre bu enum içinde tanımlayacağız. Diğer tokenlerin ID'lerini de tokenizer kendisi tanımlamıştır:

token ID
TK_NOTOKEN	tokenizer_feed() ile verilen lexemenin bittiğini belirtir.
TK_INT	Tam sayı token ID'si.
TK_FLOAT	Ondalık sayı token ID'si.
TK_IDENT	Identifier token ID'si.

Benzer şekilde identifier'lara da sayısal ID'ler atayacağız. Tokenizer, daha önce karşılaşmadığı bir identifier gelince ona sıradaki ID'yi atayacak.

Ayrıca Bakınız

Veri Yapıları

identifier	ID
degisken1	0
baska_bir_degisken	1
...

Bunları yapınca elde edeceğimiz, tamamen soyut bir token yapısı:

union seminfo {
        double num_float;
        intmax_t num_int;
        size_t ident_id;
};
 
struct token {
        union seminfo seminfo;
 
        size_t id;
};

Tokenizer Tasarımı

Önce elde etmek istediğimiz işlevi ele alarak başlayalım. Lexerin ürettiği lexemelerdeki tokenleri çıkaracak bir yapı istiyoruz, yani:

void tokenizer_feed(struct tokenizer *tokenizer, struct lexeme lexeme);
 
struct token tokenizer_next(struct tokenizer *tokenzier);

Bir lexeme'de birden fazla token olabileceği için bu yapıyı kurduk. Punctuation'ları tokenize ederken bu yapı daha da mantıklı gelecek.

struct tokenizer {
        struct map ident_map;
        size_t last_id;
 
        struct map keywords;
        struct map punctuations;
 
        struct lexeme current_lexeme;
};

Basma kalıp init ve destroy fonksiyonlarımızı yazalaım:

void tokenizer_init(struct tokenizer *t)
{
        /* string -> ID (size_t), identifier ID için kullanılacak */
        map_init(&t->ident_map, sizeof(size_t));
 
        t->last_id = 0;
 
        /* bunlara birazdan geleceğiz */
        map_init(&t->keywords, sizeof(size_t));
        map_init(&t->punctuations, sizeof(size_t));
 
        /* tokenizer'ın boş olduğunu belirtmek için mevcut işlenen lexemeyi
         * LEXEME_EOF yapalım.
         *
         * clear_lexeme'nin tek yaptığı
         *      t->clear_lexeme.kind = LEXEME_EOF
         */
        clear_lexeme(t);
}
 
void tokenizer_destroy(struct tokenizer *t)
{
        map_destroy(&t->ident_map);
 
        map_destroy(&t->keywords);
        map_destroy(&t->punctuations);
}

Keyword ve punctuation tokenlerimizi enum olarak tanımladık, ancak onların string karşılıklarını da tanımlamamız gerekiyor. İşte tanımladığımız keywords ve punctuations map'leri burada devreye girecek:

tokenizer_add_keyword(&t, "if", TK_IF);
tokenizer_add_keyword(&t, "else", TK_ELSE);
tokenizer_add_keyword(&t, "int", TK_TY_INT);
 
tokenizer_add_punctuation(&t, "+", TK_PLUS);
tokenizer_add_punctuation(&t, "-", TK_MINUS);

tokenizer_add_keyword() ve tokenizer_add_punctuation(), kodun okunabilirliğini artırmak için tanımlanmış basit fonksiyonlar (thin wrapper):

void tokenizer_add_keyword(struct tokenizer *t,
                           const char *keyword,
                           size_t id)
{
        map_insert(&t->keywords, keyword, &id);
}
 
void tokenizer_add_punctuation(struct tokenizer *t,
                               const char *punctuation,
                               size_t id)
{
        map_insert(&t->punctuations, punctuation, &id);
}

Bahsettiğimiz identifier'lara sayısal ID atamaysa aşağıdaki fonksiyonlarla gerçekleşiyor:

/* Null-terminated stringler için kısayol. */
size_t tokenizer_ident_id(struct tokenizer *t, const char *ident)
{
        return tokenizer_ident_id2(t, ident, strlen(ident));
}
 
size_t tokenizer_ident_id2(struct tokenizer *t,
                          const char *ident, size_t ident_len)
{
        size_t *id_in_map = map_get2(&t->ident_map, ident, ident_len);
 
        /* Daha önce ID atanmışsa onu dön ya da yenisini ata. */
        if (id_in_map) {
                return *id_in_map;
        } else {
                size_t id = t->last_id++;
 
                map_insert2(&t->ident_map, ident, ident_len, &id);
 
                return id;
        }
}

Şimdi tokenize etmeye başlayabiliriz.

void tokenizer_feed(struct tokenizer *t, struct lexeme lexeme)
{
        assert(t->current_lexeme.kind == LEXEME_EOF &&
               "Tokenizerda zaten bir lexeme mevcut. Önce tokenizer_next çağırın.");
 
        t->current_lexeme = lexeme;
}

Tokenizing

tokenizer_next() fonksiyonunu daha yakından inceleyelim. Bu fonksiyon, lexeme tipine göre yardımcı fonksiyon çağıran dağıtıcı işlevine sahip:

struct token tokenizer_next(struct tokenizer *t)
{
        switch (t->current_lexeme.kind) {
        case LEXEME_EOF:
                return (struct token) { .id = TK_NOTOKEN };
 
        case LEXEME_IDENT:
                return consume_ident(t);
 
        case LEXEME_PUNCT:
                return consume_punct(t);
 
        case LEXEME_INT:
        case LEXEME_FLOAT:
                return consume_num(t);
        }
 
        assert(0);  // GCOVR_EXCL_LINE: unreachable
}

Tokenizer'ın karakter parçalarını anlamlandırmasını irdeleyelim. TK_INT ve TK_FLOAT üretmek, nispeten daha düz mantık:

static struct token consume_num(struct tokenizer *t)
{
        char num[t->current_lexeme.seminfo_len + 1];
 
        /* Lexeme'den gelen seminfo null terminated değildir ve devamında diğer
         * tokenleri içerebilir. Onu bir char[]'a kopyalayarak stringden sayı
         * dönüşümünü yapıyoruz. */
        num[t->current_lexeme.seminfo_len] = '\0';
        memcpy(num, t->current_lexeme.seminfo, t->current_lexeme.seminfo_len);
 
        struct token tk;
 
        if (t->current_lexeme.kind == LEXEME_INT) {
                tk.id = TK_INT;
                tk.seminfo.num_int = strtoimax(num, NULL, 10);
        } else {
                tk.id = TK_FLOAT;
                tk.seminfo.num_float = strtod(num, NULL);
        }
 
        clear_lexeme(t);
        return tk;
}

Lexer'da grupladığımız identifier ve punctuation'ları şimdi anlamlandıracağız. Lexer keyword ve identifier ayrımını yapmamıştı, şimdi tokenizer'da karakter grubunun keyword olup olmadığına bakıp token üreteceğiz:

static struct token consume_ident(struct tokenizer *t)
{
        /* Identifier'ın keyword olup olmadığına bakıyoruz. */
        size_t *keyword_id = map_get2(&t->keywords,
                               t->current_lexeme.seminfo,
                               t->current_lexeme.seminfo_len);
 
        clear_lexeme(t);
        if (keyword_id) {
                return (struct token) { .id = *keyword_id };
        } else {
                size_t ident_id = tokenizer_ident_id2(t,
                                       t->current_lexeme.seminfo,
                                       t->current_lexeme.seminfo_len);
 
                return (struct token) { .id = TK_IDENT, .seminfo.ident_id = ident_id};
        }
}

Tek parça olarak gruplanmış punctuation'ları böleceğiz.

static struct token consume_punct(struct tokenizer *t)
{
        size_t *punct_id;
        size_t i;
 
        /* Uzun punctuation'lardan başlayarak tek tek punctuation map'ten ID
         * arar. Örneğin hem `*` hem de `**` operatörü varsa `1 ** 2` ifadesini
         * uygun şekilde tokenize etmek için uzun punctuation'lardan başlamak
         * gerekir. */
        for (
             i = MAX_PUNCT_LEN > t->current_lexeme.seminfo_len ?
                t->current_lexeme.seminfo_len : MAX_PUNCT_LEN;
             i > 0;
             i--) {
                punct_id = map_get2(&t->punctuations,
                             t->current_lexeme.seminfo, i);
 
                if (punct_id) {
                        t->current_lexeme.seminfo += i;
                        t->current_lexeme.seminfo_len -= i;
 
                        break;
                }
        }
 
        /* i'in 0'a kadar inmesi, hiçbir punctuation bulunamamıştır demektir. */
        assert(i != 0 && "Bilinmeyen punctuation.");
 
        /* punctuation lexemenin tamamı tüketilmişse current_lexemeyi temizle. */
        if (t->current_lexeme.seminfo_len == 0)
                clear_lexeme(t);
 
        return (struct token) { .id = *punct_id };
}

Soyut syntax elemanlarını, tokenleri, ürettik. Artık yazılım dilimizin söz dizimini, gramerini, tasarlayabiliriz: Parser