Top-Down Parsing

Yazılım dilimizi formal tanımlayarak başlayalım:

⟨S⟩ → id = ⟨Expr⟩ ; | print ⟨Expr⟩ ;
 
⟨Expr⟩ → ⟨Term⟩ + ⟨Expr⟩ | ⟨Term⟩ - ⟨Expr⟩ | ⟨Term⟩
 
⟨Term⟩ → ⟨Factor⟩ * ⟨Term⟩ | ⟨Factor⟩ / ⟨Term⟩ | ⟨Factor⟩
 
⟨Factor⟩ → - ⟨Atom⟩ | + ⟨Atom⟩ | ⟨Atom⟩
 
⟨Atom⟩ → id | num | ( ⟨Expr⟩ )

Tokenizer'ın tanımladığı TK_INT, TK_FLOAT ve TK_IDENT'in yanında bizim kendi tanımladığımız tokenlerimiz olacak:

enum token_id {
        TK_PRINT,
        TK_LPAREN, TK_RPAREN,
        TK_PLUS, TK_MINUS,
        TK_STAR, TK_SLASH,
        TK_EQ,
        TK_SEMI,
};

Matematiksel ifade ve değişken içeren, basit bir dil. Bir önceki sayfada, benzer bir gramerin oluşturduğu ağacı göstermiştik, hatırlayın. Şimdi o ağacın tam nasıl oluşturulduğunu inceleyeceğiz.

Top-Down Parsing adı verilen yöntemde, başlangıç sembolünden başlayarak (örneğin ⟨S⟩) yaprakları aşağı doğru uzanan bir ağaç oluşturulur. Nonterminal'ler sırasıyla daha alt kurallara genişletilir ve en uçtaki kurallar da tamamlanana kadar depth-first yol izlenir. x = -5; ifadesini ele alalım:

Bu yöntem için önce recursive fonksiyon kullanan parser yazacağız. Sonrasında top-down parsing'deki sorunlarını ve elle her bir kural için fonksiyon yazmanın zorluğunu çözen bir kütüphane kullanacağız.

Recursive Descent Parser

struct parser {
        struct tokenizer tokenizer;
 
        struct map variables;
 
        struct token token;
        struct lexer lexer;
};

Parser'ın iç yapısı biraz karışık gelebilir. Parser elemanlarını yeri geldikçe açıklayacağız. Parser'ın esas fonksiyonlarıysa:

void parser_init(struct parser *parser);
 
void parser_eval(struct parser *parser, const char *text);

Top-down parser'ımız tokenleri okurken evaluate edecek. Şimdilik parser ve evaluation kısmını birleşik yazacağız, somut bir tree yapısı olmayacak.

Basmakalıp init/destroy fonksiyonlarımızı tanımlayalım:

void parser_init(struct parser *p)
{
        tokenizer_init(&p->tokenizer);
 
        /* Değişkenlerin değerini map'te tutacağız. */
        map_init(&p->variables, sizeof(double));
 
        /* Eşleştirilmekte olan token. */
        p->token.id = TK_NOTOKEN;
 
        /* Dilimizdeki keyword ve punctuation'ları tokenizer'a bildirelim. */
        tokenizer_add_keyword(&p->tokenizer, "print", TK_PRINT);
        tokenizer_add_punctuation(&p->tokenizer, "(", TK_LPAREN);
        tokenizer_add_punctuation(&p->tokenizer, ")", TK_RPAREN);
        tokenizer_add_punctuation(&p->tokenizer, "+", TK_PLUS);
        tokenizer_add_punctuation(&p->tokenizer, "-", TK_MINUS);
        tokenizer_add_punctuation(&p->tokenizer, "*", TK_STAR);
        tokenizer_add_punctuation(&p->tokenizer, "/", TK_SLASH);
        tokenizer_add_punctuation(&p->tokenizer, "=", TK_EQ);
        tokenizer_add_punctuation(&p->tokenizer, ";", TK_SEMI);
}
 
/* Basmakalıp destroyer fonksiyonu. */
void parser_destroy(struct parser *p)
{
        map_destroy(&p->variables);
 
        tokenizer_destroy(&p->tokenizer);
}

Lexer'da kullandığımız advance/peek tasarımını yine kullanıyoruz:

static size_t current_id(struct parser *p)
{
        return p->token.id;
}
 
static union seminfo current_seminfo(struct parser *p)
{
        return p->token.seminfo;
}
 
/* Sıradaki token'a geçer. */
static void consume(struct parser *p)
{
        p->token = tokenizer_next(&p->tokenizer);
 
        /* Tokenizer, lexeme'yi tüketmişse yeni lexeme çek. */
        if (current_id(p) == TK_NOTOKEN) {
                struct lexeme next_lexeme = lexer_next(&p->lexer);
 
                /* Lexeme'ler tükenmişse token TK_NOTOKEN olarak işaretle. */
                if (next_lexeme.kind == LEXEME_EOF) {
                        p->token.id = TK_NOTOKEN;
 
                        return;
                } else {
                        /* Yeni lexeme gelmişse ona geçmek için bu fonksiyonu
                         * tekrar çağır. */
                        tokenizer_feed(&p->tokenizer, next_lexeme);
 
                        return consume(p);
                }
        }
}
 
/* Beklenen token geldiyse tüketir ve true döner. */
static bool match(struct parser *p, size_t tk_id)
{
        if (current_id(p) == tk_id) {
                consume(p);
 
                return true;
        }
 
        return false;
}

Artık parser_eval() fonksiyonunu yazmaya başlayabiliriz:

void parser_eval(struct parser *p, const char *text)
{
        lexer_init(&p->lexer, text);
 
        /* init fonksiyonundan kalma TK_NOTOKEN'ı consume et. */
        consume(p);
 
        /* Tokenler bitmediği sürece devam et. */
        do {
                if (match(p, TK_PRINT)) {
                        eval_print(p);
                        continue;
                }
 
                if (current_id(p) == TK_IDENT) {
                        eval_asgn(p);
                        continue;
                }
 
                assert(0 && "Beklenmeyen token! IDENT ya da PRINT gelmeliydi."); // GCOVR_EXCL_LINE
        } while (current_id(p) != TK_NOTOKEN);
}
 
/* Bütün production rule'ları fonksiyon olarak tanımlayacağız. */
void eval_print(struct parser *p);
void eval_asgn(struct parser *p);
double eval_expr(struct parser *p);
double eval_term(struct parser *p);
double eval_factor(struct parser *p);
double eval_atom(struct parser *p);

Evaluation Fonksiyonları

Dilimizde iki çeşit statement var: print ve asgn. print, bir ifadeyi evaluate edip terminale yazdırırken asgn, onu değişkene kaydediyor.

void eval_print(struct parser *p)
{
        /* print'in hemen sonrasında bir expression olmalı. */
        double value = eval_expr(p);
 
        /* expression bitiminde ; olduğundan emin ol. */
        assert(match(p, TK_SEMI));
 
        printf("> %.2lf\n", value);
}
 
void eval_asgn(struct parser *p)
{
        size_t id = current_seminfo(p).ident_id;
        consume(p);
 
        /* eval fonksiyonunda id match etmiştik, ondan sonra = olmalı. */
        assert(match(p, TK_EQ));
 
        /* ='den sonraki expression'u evaluate et ve değişkene ata. */
        double new_value = eval_expr(p);
 
        assert(match(p, TK_SEMI));
 
        double *value = map_get2(&p->variables, &id, sizeof(size_t));
 
        if (value)
                *value = new_value;
        else
                map_insert2(&p->variables, &id, sizeof(size_t), &new_value);
}

Benzer mantıkla tanımlanmış expr, term ve factor kurallarını match ediyoruz:

double eval_expr(struct parser *p)
{
        double lhs = eval_term(p);
 
        /* expression, toplama ya da çıkarma içeriyorsa dallanmaya devam et. */
        if (match(p, TK_PLUS)) {
                double rhs = eval_expr(p);
 
                lhs += rhs;
        } else if (match(p, TK_MINUS)) {
                double rhs = eval_expr(p);
 
                lhs -= rhs;
        }
 
        return lhs;
}
 
double eval_term(struct parser *p)
{
        double lhs = eval_factor(p);
 
        /* term, expression'a benzer şekilde dallanır. */
        if (match(p, TK_STAR)) {
                double rhs = eval_term(p);
 
                lhs *= rhs;
        } else if (match(p, TK_SLASH)) {
                double rhs = eval_term(p);
 
                lhs /= rhs;
        }
 
        return lhs;
}
 
double eval_factor(struct parser *p)
{
        if (match(p, TK_PLUS))
                return eval_atom(p);
        else if (match(p, TK_MINUS))
                return -eval_atom(p);
        else
                return eval_atom(p);
 
}

Son olarak da sayısal değer ifade eden en küçük birimleri, atomları evaluate ediyoruz.

double eval_atom(struct parser *p)
{
        /* `match` fonksiyonu, bir sonraki tokene geçeceği için seminfo'yu
         * kaydet. */
        union seminfo s = current_seminfo(p);
 
        if (match(p, TK_INT)) {
                return (double) s.num_int;
        } else if (match(p, TK_FLOAT)) {
                return s.num_float;
        } else if (match(p, TK_IDENT)) {
                double *value = map_get2(&p->variables,
                                         &s.ident_id,
                                         sizeof(size_t));
 
                return value ? *value : 0;
        } else if (match(p, TK_LPAREN)) {
                double expr = eval_expr(p);
 
                assert(match(p, TK_RPAREN));
 
                return expr;
        }
 
        assert(0 && "Syntax error.");  // GCOVR_EXCL_LINE
}

İşlem Önceliği...

Bu kadar! Artık değişken ve matematiksel ifade içeren bir yazılım dilimiz var... sanıyorsanız yanılıyorsunuz. Yazdığımız koda şu ifadeyi verirsek büyük bir hüsrana uğrarız: print 10 - 2 - 3;

Bu işlemin matematiksel sonucu 5 olmalıdır. Fakat bizim parser'ımız ekrana 11 yazdırır! Top-down parsing'de parser'la evaluation'ı birlikte yazdığımız zaman işlem önceliğinin ters olmasından kurtulmanın kolay bir yolu yok. Bu sorunu nasıl çözeceğimizi, top-down parser'ların Mental Model'ini inceleyerek göreceğiz.