Lex ve Yacc

Özet

Lex & Yacc ile ilgili kaynak aradım. Örnekleri yazdım, çizdim. Regex bilgimi tazeledim. Ortalama 6-7 saat çalıştım.

Lex: A Lexical Analyzer Generator (Sözcüksel çözümleyici üretici)

[Lex][http://dinosaur.compilertools.net/lex/] karakter bazındaki girdileri dizgecikler (tokens) haline getiren bir bilgisayar programı. Derleme evlerinde gösterilen ilk evreyi bu program rahatlıkla gerçekleştiriyor.

Yacc: Yet Another Compiler-Compiler (Bir başka derleyici-derleyici)

[Yacc][http://dinosaur.compilertools.net/yacc/index.html] gramer (sözdizilim) ayrıştırıcı. Girdiğimiz gramer kurallarına göre dizgecikleri çözümlüyor. Anlatması biraz zor. Yani adı bile "compiler-compiler". Çok tatlı durmuyor. Ama ne yaptığını görünce anlaması biraz kolay oluyor. Şöyle ki;

Ömer yakışıklı bir insandır.

Bu cümledeki kelimeleri çıkaran onların isim mi fiil mi sıfat mı olduğunu bulan kısım Lex (Tabi bizim yazdığımız kurallara göre). Yacc ise bu cümlenin doğru bir cümle olup olmadığına bakıyor.
Biz Lex'e diyoruz ki:

isimler: Ömer, insan
sıfatlar: yakışıklı, bir
Yacc ' a da bu kuralları yazıyoruz:
cümle -> isim isimyüklem
cümle -> isim fiilyüklem
isim -> sıfat isim

Sonrasında Lex girilen dizgenin geçerli bir dizge olup olmadığını buluyor. Lexical(sözcüksel) analiz yapıyor. Yacc is girilen cümlenin geçerli bir cümle olup olmadığına bakıyor. Yani Syntactic(sözdizimsel) analiz yapıyor.

Aslında bunlara şöyle demek daha doğru: Lex, size sözcüksel bir analizci üretiyor. Yacc size sözdizimsel bir analizci üretiyor.

Biraz daha açıklıyayım. Bunlar kıyma çeken makine değil, o makineyi üreten makineler. (Bayramüstü ondan esti sanırım.)

Flex ve Bison

Flex ve Bison, Lex ve Yacc'la aynı işi yapan programlar. Cygwin'e yüklemesi kolay oldu. Lex ve Yacc'ın orjinalini bulamadım zaten. Bulsamda direk çalıştırabilirini bulamam, öbür türlü alıp bir da onu build et, hem windows kullanıyorsun o bu şu derken zehir olurdu. Böylesi iyi oldu.
Şimdi [şöyle][http://epaperpress.com/lexandyacc/] bir kaynak buldum. Biraz da flex ve bison'un documentasyonlarına baktım. Bir kaç örneği kopyaladım. Örnekleri anlamam biraz zor oldu. Çünkü baya çirkin bir şey yazıyoruz. Yani insanlar yazıyorlarmış. Ama bu lex ve yacc olayı bir programlama dili yazma işini çok kolaylaştırıyor. Yani öğrenmeye değer. Şimdi kalkıp ben bir lexer yazsam, bir ton iş. Ama bu yöntemle olay kolay gibi olursa deneyebilirim.

Flex

Karakter sayma programı


%{
 unsigned karakter_sayisi = 0; 
%}

%% 
.  { karakter_sayisi++; }

%% 
int main(int argc, char* argv[]){
    yylex();
   printf("Karakter sayisi: %d\n", karakter_sayisi);
}
Bu flex'le yapılabilecek basit bir program. Girdide kaç tane karakter olduğunu bastırıyor.
Nasıl derlenir
Flex programı .l uzantısıyla kaydediliyor. flex karakter.l şeklinde derleniyor. Çıktı olarak bir .c dosyası üretiyor. Bu dosyayı sonra gcc ile gcc cikti.c -lfl seklinde flex kütüphanesiyle bağlayı çalıştırınca bizim program ortaya çıkmış oluyor.
Programın Yapısı
Flex programı anladığım kadarıyla üç bölümden oluşuyor. Bölümler %% ile ayrılmış durumda. İlk bölümde %{ %} bunların arasına yazdıklarınız. Bildiğimiz C kodu ve oluşturduğu C dosyasının içine direk atıyor. İlk bölümde bunların dışına yazdığımız şeyler genellikle bir 'regular expression' tanımlaması oluyor.

İkinci bölümde bir kural ve o kuralın sonunda gerçekleşecek eylem belirtiliyor. Örneğin yukarıdaki örnekte bir tane 'nokta' var. '.' bu nokta regex te bütün karakterler olabilir demek. Doğal olarak o satır her türlü karakterte karakter_sayisini bir artır diyoruz.

Üçüncü bölüm, anladığım kadarıyla tamamen C kısmı. Buraya C fonksiyonları yazabiliyoruz. Eğer yacc kullanmayacak main fonksiyonunu da buraya yazabiliriz. Ya da gerekirse başka fonksiyonlar tanımlayabiliriz.

Bison

Basit Cümle Dogrulayici

Bu örnekte isim, sıfat,zarf,fiil seklindeki girdiler alıyorum. Sonra cümleler alıyorum kullanıcıdan. Yazdığım kurala uyan cümlelere 'Geçerli cümle.\n" bastırıyorum.

gramer.y

%{
  #include<stdio.h>
%}
%token ISIM SIFAT FIIL ZARF
%%

cumle: ozne yuklem {printf("Gecerli cümle.\n");}


ozne : ISIM
     | SIFAT ozne
     ;


yuklem: FIIL
        | ZARF yuklem
        ;


%%
extern FILE *yyin;

int main()
{
    do{
        yyparse();
    }while(!feof(yyin));
}

void yyerror(char *s)
{
    fprintf(stderr, "Hata: %s\n", s);
}
kelimeler.l

%{
 #include "y.tab.h"
 #define YOK 0
 int durum;
%}
%%
\n {durum = YOK;} /* Satır sonu */
\.\n { durum = YOK;
        return 0;
     }

^fiil { durum = FIIL;}
^zarf { durum = ZARF;}
^sifat { durum= SIFAT;}
^isim {durum = ISIM;}

[a-zA_Z]+ {
    if(durum != YOK){
        sozluge_ekle(durum, yytext);
    }else {
        switch(kelimeye_bak(yytext)){
          case FIIL: return(FIIL);
          case ZARF: return(ZARF);
          case SIFAT: return(SIFAT);
          case ISIM: return(ISIM);
          default:
            printf("%s: boyle bir kelime yok!", yytext);
            break;
        }
    }
}

.     /* geri herseyi yoksay */

%%

struct kelime{
    char* kelime_adi;
        int kelime_tipi;
        struct kelime* sonraki;
};

struct kelime *kelime_listesi; /* Liste basi */
extern void *malloc();

int sozluge_ekle(int tip, char *kelime){
    struct kelime *k;
    if(kelimeye_bak(kelime) != YOK){
        printf("!! Kelime %s zaten tanımlanmış.", kelime);
        return 0;
    }
    /* Kelime listesine  yeni eleman ekle */
        k = (struct kelime *)malloc(sizeof(struct kelime));
        k->sonraki = kelime_listesi;

        /* Yeni elemana kelimeyi ekle */

        k->kelime_adi = (char *)malloc(sizeof(kelime) + 1);

        strcpy(k->kelime_adi, kelime);
        k->kelime_tipi = tip;
        kelime_listesi = k; /* Listenin basini eski haline getir */

        return 1;
}

int kelimeye_bak(char *kelime){
    struct kelime *k = kelime_listesi;
        /* Kelimeyi listede ara */

        for(;k; k = k->sonraki){
        if(strcmp(k->kelime_adi, kelime) == 0){
            return k->kelime_tipi;
        }
    }
        return YOK; // BULAMADIK;
}
Derleniş 

yacc -d gramer.y
flex kelime.l
gcc y.tab.c lex.yy.c -lfl
yacc dosyasını -d seçeneği le derleyince, size bir y.tab.h adında bir başlık dosyası oluşturuyor. Bu başlık dosyasında %token şeklinde tanımlananlar (ISIM, FIIL vs.) #define şeklinde tanımlanıyor. Böylece Lex ile yacc arasında bir köprü oluşturuluyor. İkiside birbirinin hangi dizgelere (token) baktıklarından haberdar oluyorlar.

gramer.y dosyası bir yacc dosyası. Yacc dosyası da flex dosyasına bayağı benziyor. O da aynı şekildeki üç bölümden oluşuyor.

1- Tanımlar
2- Kurallar
3- Kod kismi

Programın Çalışması

REGEX

Lexin dizgecik(token) oluşturulması için yazılan kalıpları(patterns) regex kullanarak yapılması gerekiyor. Benim de regex bilgim üniversitedeki Computing Theory dersi ile kısıtlıydı. Bir iki kere web sitesi hazırlarken url oluşturmak için kullandığım olmuştu. Ama onlar daha basit yapılardı.
Bu yüzden biraz regex bilgimi tazeledim. Hangi işaret neyi temsil ediyor. Lexin kullandığı patternlarla genel olarak kullanılan patternlar aynı mı falan diye. Örneğin bash'ta [:digit:] herhangi bir sayi ile eşleşir. Bunu [\d] şekline gösteren regex yorumlayıcıları da var vs.

Sonuç olarak

Flex ve Bison derleme evrelerinin iki önemli kısmını halleden iki önemli programdır. Bunlar; dizgecik(token) oluşturma ve sözdizimi kontrol etme. Flex ve Bison benim yazabileceğim herhangi lexer ve parser'dan daha iyi. Ama gerek duyarsam el ile bir lexer yazabilir. Ama şimdili böyle bir ihtiyaç yok. Bunların üzerine çalışmaya devam edeceğim.

EK

[linkedlist][https://en.wikipedia.org/wiki/Linked_list]
[bash][https://en.wikipedia.org/wiki/Bash_(Unix_shell)]
[regex][https://en.wikipedia.org/wiki/Regular_expression]

Yorumlar

Yorum Gönder

Bu blogdaki popüler yayınlar

NFA, DFA, Regex, CFG, PDA

Resim
Özet Hesaplama kuramında öğrenip unuttuğum bazı teorik bilgileri yeniledim. Unuttuğum ve en önemli olan kısım: Regex: NFA , CFG: PDA ikililerinin birbirleriyle bu kadar içli dışlı olduklarıydı. İyi oldu. Güzel oldu. NFA, DFA, Regex, CFG, PDA Finite Automata (Sonlu Otomat) Sonlu otomatlar, düzenli dilleri kabul eden ya da fark eden basit bilgisayarlar/hesaplama sistemleridir. Sonlu otomat, bir alfabeden, bir durumlar kümesinden, bir geçiş fonksiyonundan, bir başlangıç ve bir ya da birden fazla kabul durumundan oluşur. Şöyle gösterilir. M = (Q, E, &, q0, F) Q: Durumlar kümesi E: Alfabe &: Q x E -> Q şeklinde geçiş fonksiyonu F: Kabul durumlar kümesi Deterministic Finite Automata (Belirli Sonlu Otomat) Belirli bir otomattır. Aynı anda makina aynı anda sadece bir durumda bulunabilir. Non-Deterministic Finite Automata (Belirsiz Sonlu Otomat) Epsilonun, yani boş karakteri girdi olarak kabul eden. Aynı anda birden çok durumda bulunabilen makinelerdir. Regular ...
Devamı

Lex ve Yacc-2

ÖZET Lex ve yacc ile alakalı örnekler yapmaya çalıştım ve hazır örnekler üzerine çalıştım. Onlarla alakalı bir kaç yazı okudum. Kısmi anlamda arkalarındaki teoriye baktım. Ortalama 3-4 saat çalıştım. Giriş Lex ve yacc bir derleyici ya da yorumlayıcı oluşturmak için çok gerekli olan iki araç. Bu araçları iyi kullanabilmek bir programlama dili oluşturma yolunda önemli bir yere sahip. Bu düşünceyle Lex ve yaccın biraz daha üstüne düştüm. Tabiki bunların yerine kendir lexer ve parserımı da yazabilirim. Ama böyle iki iyi araç varken böyle bir şeyin peşine düşmek pek mantıklı değil, heleki bu araçları da tam anlamıyla kullanamıyor ve bilmiyorken. Şimdiki kısa süreli amacım lex ve yaccı iyi kullanabilmek. Başından sonuna herşeyini anlamak. Hesap Makinesi Benim Denemem Hesap makinesi örneğini [Tom Nieman][ http://epaperpress.com/ ]'ın sitesinde görmüştüm. Bundan cesaret alarak, ne de olsa yanlışımı kontrol edebileceğim bir yer var, şu anki lex ve yacc bilgimle bir hesap makinesi...
Devamı