Yazan : Şadi Evren ŞEKER

YACC, bilgisayara bilimlerinin önemli dallarından birisi olan dil tasarımı ve dil geliştirilmesi sırasında (compiler teory) sıkça kullanılan bir kod üretici programdır. YACC basitçe dildeki sözdizim (syntax) tasarımı için kullanılır ve tasarladığımız dildeki kelimelerin sıralamasının istediğimiz şekilde girilip girilmediğini kontrol eder. Aynı zamanda sıralamadaki her kelimenin anlamını da yacc marifetiyle belirleyebiliriz.

YACC temel olarak BNF (Backus Normal Form) kullanarak cümle dizimini belirtmektedir.

LEX ile birlikte kullanıldığıdan bir dil tasarımının neredeyse yarısı olan lexical (kelime) ve syntax (cümle) analizi tamamlanmış olur. Bundan sonra dildeki her kelime ve cümle diziliminin anlamını (semantic) kodlamak kalır.

YACC neredeyse tamamen aynı olan açık kaynak kodlu bison isimli paket ile de kurulabilir.

Aşağıda örnek bir yacc dosyası verilmiştir. Bu dosyayı inceleyerek yacc’ın kullanımını anlamaya çalışalım:

%{ // tanımlamam yapılan ilk bölüm
    #include <stdio.h>
    int yylex(void);
    void yyerror(char *);
%}

%token INTEGER

%% // BNF yapısındaki ikinci bölüm

program:
        program expr 'n'         { printf("%dn", $2); }
        | 
        ;

expr:
        INTEGER
        | expr '+' expr           { $$ = $1 + $3; }
        | expr '-' expr           { $$ = $1 - $3; }
        ;

%%
// fonksiyon içeriklerinin bulunduğu son bölüm
void yyerror(char *s) {
    fprintf(stderr, "%sn", s);
}

int main(void) {
    yyparse();
    return 0;
}

Dosyamız LEX’e benzer şekilde 3 bölümden oluşmaktadır. İlk bölümde kodumuza dahil edilecek kütüphaneleri ve fonksiyon prototiplerini tanımlıyoruz.

ikinci bölümde BNF yapısı benzeri bir şekilde dilimizdeki sözdizim tanımlanıyor.

üçüncü ve son bölümde fonksiyon tanımları ve main fonksiyonu bulunmaktadır.

Yukarıdaki dosyada yapılan işlemleri aşağıda anlatalım:

YACC dosyasında %token ve %type olarak iki farklı tanım yapılabilmektedir. %token tanımı lex’den gelen bir sabit bilgiyi taşımak için kullanılır. %type ise yacc içerisinde tanımlanan devamlıları (nonterminal) ifade etmek için kullanılır.

Genelde bir kural olmamasına karşılık BNF yapısındaki sonlular (terminal) büyük harfle ve devamlılar (nonterminal) küçük harf ile yazılırlar. (dosyamızın C kodu üreteceğini ve gerek yacc gerek lex gerek se C dilinin büyükküçük harfe duyarlı (case sensitive) olduğunu unutmayınız)

yyerror fonksiyonu yacc tarafından girilen değeri kontrol ederken bir dizilim hatası bulunması (syntax error) çağrılan fonksiyondur.

main fonksiyonu aynen üretilen koda kopyalanmakta ve ilk çalışan C fonksiyonumuzdur.

BNF yapısının yanında bulunan ve küme parantezleri arasında (curved brackets) bulunan kodda ise aşağıdaki terimler kullanılabilir:

$$ -> bu devamlıdan (nonterminal) dönecek olan değerdir.

$1 -> BNF yapımızdaki ilk parametredir. Örneğin aşağıdaki satırı ele alalım:

 | expr '+' expr           { $$ = $1 + $3; }

Bu satırda ilk sembol veya anlamında | sembolüdür. Bu sembolün amacı bir expr tanımlanırken ihtimallerden birisi olmasıdır. Ardından expr sembolü ilk sembol ‘+’ ikinci sembol ve ikinci expr sembolü ise 3. semboldür. Dolayısıyla sırasıyla :

$1= expr

$2= ‘+’

$3 = expr

anlamına gelmektedir.

Bu satırın bulunması durumunda yapılacak işlem ilk expr karşılık gelen değer ile ikinci expr karşılık gelen değerin sayısal olarak toplanması ve sonuç olarak $$ marifeti ile döndürülmesidir.

Yorumlar

  1. b_iZec

    süper bi paylaşımm.. paylaşımların hepsi harikaa!! !!! süper çok saolunn!! benje herkese yararlı olujak bilgiler bunlarr!!! bence yorum yazmadan geçmemek gerekiRR: süpeR!!!

  2. Meltem

    Merhaba hocam,öncelikle gerçekten inanılmaz açıklayıcı ve aydınlatıcı olmuş.Emeginize sağlık ve cok teşekkürler.
    Mümkünse aşagıdaki alanı da daha ayrıntılı acıklar mısınız,kafamdaki soru işaretlerinin tamamen kalkması için cok iyi olacaktır.

    program:
    program expr ‘n’ { printf(“%dn”, $2); }
    |
    ;

    Simdiden cok tesekkür ediyorum
    İyi çalışmalar..

  3. Şadi Evren ŞEKER Article Author

    Yacc dosyamızın ilk kuralından bahsediyorsunuz sanırım. Burada bir “program” tanımı yapılmış ve bir programın aşağıdaki BNF (CFG) yapısında olduğu anlatılmış:

    program : program expr ‘n’ | ;

    bunun anlamı, bir programın yine bir program, bir expr (ki tanımı sonraki satırda yapılmış) ve bir satır sonu karakterinden oluşabileceği veya (| işareti ile ayrılmış) boş olabileceği (lambda veya bazı kaynaklarda epsilon ile gösterilen değer) yani hiçbir bilgi olmaması hali.

    programın, bu ihtimallerden ilki olması için de ekrana ikinci parametre ($2 ile gösterildiği için dizilimdeki ikinci eleman demek oluyor) olan expr değerini basması istenmiş (kuralın tanımında yanda küme parantezleri içerisinde C kodu yazılabilir, burada kullanılan $2 açıkladığım üzere özel bir semboldür, diğerleri nomral C komutlarıdır)

    başarılar

  4. Meltem

    İlginiz için çok teşekkürler hocam,anlatımınız gerçekten çok aydınlatıcı.Çok teşekkürler.Tekrar emeğinize sağlık.

  5. ali

    Hocam bison da işlem önceliği bilidirimlerinin nasıl yapıldığı hakkında biraz bilgi verebilir misiniz?
    Bison dosyayapısında bildirimin nerede yapılması gerektiğini biliyorum ama nasıl yapılması gerekiyor bilmiyorum. Yardımcı olursanız sevinirim.

  6. Şadi Evren ŞEKER Article Author

    Sorunuzun bison ile doğrudan ilgisi yok. Yani aslında sorunuzun bison içerisinde yazılan BNF (veya CFG (Context Free Grammer, İçerikten Bağımsız Dil) ) ile ilgisi var. İşlem önceliğini ancak doğru bir CFG tasarımı yaparak bisona anlatabilirsiniz.

    Örneğin aşağıdaki CFG yapısını ele alalım:

    S-> num * S | A | num
    A-> num + S

    Yukarıdaki yazılıma göre çarpma işlemi, toplamadan önceliklidir. Bunun sebebini aşağıdaki dizgiyi (string) parse ederek anlatalım:

    3 + 4 * 5

    Yukarıdaki yapıyı öncelikle doğru şekilde parçalayalım (parse) ve aşağıdaki parçalama ağacını (parse tree) çizelim:

        S
        |
        A
      /   
    num  + S
     |    /  
     3  num * S
         |    |
         4   num
              |
              5
    

    Yukarıdaki açılımda görüldüğü üzere, işlemde önce çarpma (daha yakın olan) ve ardından toplama yapılmalıdır. Yani önce 4*5 daha sonra + 3 işlemi yapılır.
    Aynı CFG için hatalı açılımı deneyelim:

        S
      /  
    num * S
     |    |
     3   HATA
    

    Görüldüğü üzere önce çarpma işlemi açılsa daha sonra toplamanın açılmasına ve dolayısıyla toplamanın, çarpmadan önce yapılmasına imkan yoktur.

    Kısacası sorunuzun cevabı işlem önceliği için doğru CFG tasarımı ile işe başlamanızda yatıyor.

    Başarılar

  7. Hasan Fatih KAVİ

    Şadi hocam mükemmel bir paylaşım gerçekten. İnternette bu konu ile ilgili Türkçe kaynak sitesi yok denecek kadar az.

Hasan Fatih KAVİ için bir cevap yazın Cevabı iptal et

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir