librdesc

librdesc'in çözümü:

• Madem left-recursion sonsuz döngüye sebep oluyor, biz de grameri right-associative olarak tanımlarız.
• Call stack'taki fonksiyon çağrılarının oluşturduğu ağacı kolay bir şekilde döndüremiyorsak, biz de kendi stack implementasyonumuz üzerinden parse edelim. Kendi stack'imizde istediğimiz gibi döndürme yaparız.

librdesc GitHub repository: https://github.com/metwse/rdesc/
librdesc online documentation: https://metwse.github.io/rdesc/

O zaman librdesc'i indirerek başlayalım:

git clone https://github.com/metwse/rdesc --branch=v0.3.0-preview
 
cd rdesc/
 
sudo make FEATURES='full' -j install

Tabii proje taslağını kullanıyorsanız librdesc otomatik indirilecek. Ancak tavsiyem yine de sisteme kurmanızdır, böylece tüm metin editörlerinin librdesc fonksiyonlarını görüp uygun önerilerde bulunabilir.

Grameri librdesc Makrolarına Dökmek

Kendi stack implementasyonunu kullanıp CST kuran bu parser'ı çalıştırmak için, kütüphanenin rule_macros.h başlığındaki makroları kullanacağız.

Önceki sayfalarda sonsuz döngüye girmemek için gramerimizi mecburen right-recursive olarak tasarlamıştık. Şimdi bu right-recursive yapıyı _REST isimli yardımcı nonterminal'lerle ifade edelim. Anlaşılırlığı artırmak için gramerimizi sadece çıkarma (-), çarpma (*) ve sayılardan (INT) oluşacak şekilde sadeleştirelim:

⟨S⟩ → ⟨Expr⟩ ;
 
⟨Expr⟩ → ⟨Term⟩ ⟨ExprRest⟩
 
⟨ExprRest⟩ → - ⟨Term⟩ ⟨ExprRest⟩ | ε
 
⟨Term⟩ → ⟨Atom⟩ ⟨TermRest⟩
 
⟨TermRest⟩ → * ⟨Atom⟩ ⟨TermRest⟩ | ε
 
⟨Atom⟩ → int | ( ⟨Expr⟩ )

Önceki gramer yapımızı librdesc ile kullanmanın önünde bir engel yoktu, ancak librdesc'in bazı özelliklerini kullanabilmek için şimdiden bu değişikliği yaptık. Bir sonraki bölümde bu tercihi yapma nedenimizi detaylandıracağız.

Gramer için gerekli declaration'ları header'da yapalım:

#include <rdesc/grammar.h>
 
/* toplam nonterminal sayısı */
#define NT_COUNT 6
/* bir nonterminal'deki maksimum alternatif sayısı */
#define MAX_ALT_COUNT 2
/* bir alternatifdeki maksimum sembol sayısı */
#define MAX_ALT_SIZE 3
 
enum tk_id {
        TK_MINUS,
        TK_STAR,
        TK_SEMI,
        TK_LPAREN, TK_RPAREN,
        /* TK_INT'i tokenizer tanımlıyor. */
};
 
enum nt_id {
        NT_STMT,
        NT_EXPR, NT_EXPR_REST,
        NT_TERM, NT_TERM_REST,
        NT_ATOM,
};
 
/* Gramer tanımını tutacak struct'ı declare ediyoruz.*/
extern struct rdesc_grammar_symbol production_rules
        [NT_COUNT][MAX_ALT_COUNT + 1][MAX_ALT_SIZE + 1];

Grameri, formal gösterimine neredeyse birebir benzeyen bir tabloya dönüştürmek için, librdesc'in sağladığı makroları kullanacağız. Spagetti gibi birbirini çağıran fonksiyonlar yok!

• r(...): Production rule'ı başlatır.
• alt: Production rule alternatiflerini (|) ayırır.
• EPSILON: Production rule'ın boş (ε) geçilebileceğini belirtir.

#include <rdesc/rule_macros.h>
#include <string.h>
 
#include "../include/tokenizer.h" // IWYU pragma: keep, TK_INT için
 
 
struct rdesc_grammar_symbol
production_rules[NT_COUNT][MAX_ALT_COUNT + 1][MAX_ALT_SIZE + 1] = {
        /* ⟨S⟩ → ⟨Expr⟩ ; */ r(
                NT(EXPR), TK(SEMI)
        ),
 
        /* ⟨Expr⟩ → ⟨Term⟩ ⟨ExprRest⟩ */ r(
                NT(TERM), NT(EXPR_REST)
        ),
 
        /* ⟨ExprRest⟩ → - ⟨Term⟩ ⟨ExprRest⟩ | ε */ r(
                TK(MINUS), NT(TERM), NT(EXPR_REST)
        alt     EPSILON
        ),
 
        /* ⟨Term⟩ → ⟨Atom⟩ ⟨TermRest⟩ */ r(
                NT(ATOM), NT(TERM_REST)
        ),
 
        /* ⟨TermRest⟩ → * ⟨Atom⟩ ⟨TermRest⟩ | ε */ r(
                TK(STAR), NT(ATOM), NT(TERM_REST)
        alt     EPSILON
        ),
 
        /* ⟨Atom⟩ → num | ( ⟨EXPR⟩ ) */ r(
                TK(INT)
        alt     TK(LPAREN), NT(EXPR), TK(RPAREN)
        )
};

Sonrasında, bu tabloyu kullanarak struct rdesc oluşturuyoruz:

struct rdesc_grammar grammar;
struct rdesc parser;
 
assert(rdesc_grammar_init_checked(&grammar,
        NT_COUNT, MAX_ALT_COUNT, MAX_ALT_SIZE, production_rules) == 0);
 
assert(rdesc_init(&parser, &grammar, sizeof(union seminfo), NULL) == 0);

Bu kadar! Tokenizer ile (token_id, seminfo) ikilisini üretiyorduk, şimdilik hard-coded birkaç tokeni rdesc'e gönderip test edelim:

assert(rdesc_start(&parser, NT_STMT) == 0);
 
union seminfo s;
 
s.num_int = 10;
assert(rdesc_pump(&parser, TK_INT, &s) == RDESC_CONTINUE);
 
assert(rdesc_pump(&parser, TK_MINUS, NULL) == RDESC_CONTINUE);
 
s.num_int = 2;
assert(rdesc_pump(&parser, TK_INT, &s) == RDESC_CONTINUE);
 
assert(rdesc_pump(&parser, TK_MINUS, NULL) == RDESC_CONTINUE);
 
s.num_int = 3;
assert(rdesc_pump(&parser, TK_INT, &s) == RDESC_CONTINUE);
 
assert(rdesc_pump(&parser, TK_SEMI, NULL) == RDESC_READY);

rdesc_pump(), pompalama sonrasında kuralın tamamlanıp tamamlanmamasına göre RDESC_CONTINUE ve RDESC_READY döner. rdesc, kuralı match ettikten sonra ekrana yazdıralım:

rdesc_dump_cst(stdout, rdesc_get_root(&parser), node_printer);

Bu CST'yi, left-associative çıkarma işlemine sahip olacak şekilde döndürmek için rdesc_flip_left() çağırmamız yeterli:

rdesc_flip_left(rdesc_get_root(&parser), 0);
 
rdesc_dump_cst(stdout, rdesc_get_root(&parser), node_printer);

rdesc_flip_left() sonrası elimizde Left-Associative, matematiksel olarak doğru bir CST var. Sıradaki adım bu ağacı traverse etmek ve değerleri hesaplamak. Artık parsing ile evaluation'ı birbirinden tam olarak ayırmış olacağız.

Ayrıca, rdesc_dump_cst() fonksiyonuna verdiğimiz node_printer()'ın tanımını tek bir node'ı traverse etme örneği olarak verebiliriz, bir sonraki aşama olan Tree-Walk Interpreter'da bu tarz şeyler yapacağız:

#include <rdesc/cst_macros.h>
 
 
const char *tk_names[] = {
        "-", "*", ";", "(", ")"
};
 
const char *nt_names[] = {
        "stmt",
        "expr", "expr_rest",
        "term", "term_rest",
        "atom",
};
 
void node_printer(FILE *out, struct rdesc_node node)
{
        if (rtype(node) == RDESC_TOKEN) {
                if (rid(node) == TK_INT) {
                        union seminfo s;
 
                        memcpy(&s, rseminfo(node), sizeof(union seminfo));
 
                        fprintf(out, "[shape=box,label=<%lld>]", (long long int) s.num_int);
                } else {
                        fprintf(out, "[shape=box,label=<%s>]", tk_names[rid(node)]);
                }
        } else {
                fprintf(out, "[label=\"%s\"]", nt_names[rid(node)]);
        }
}

Biraz librdesc'in derinliklerine inelim: librdesc Detayları.