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 rdesc 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

Ö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.

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_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 */
    r(
        TK(INT)
    )
};

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! Sonrasında rdesc'e token göndermeye başlayabiliriz:

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);

Bu CST'yi traverse edip evaluate etmenin detaylarına ineceğiz. rdesc_dump_cst() fonksiyonuna verdiğimiz node_printer()'ın tanımını tek bir node'ı traverse etme örneği olarak verebiliriz:

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)]);
        }
}

Artık tam-teşekküllü bir dil kodlamaya başlayabiliriz: Tree-Walk Interpreter