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 yazmayı denedim.
tokens.l

%{
#define OPERATOR 101
#define OPERAND 102

        struct eleman {
                int tip;
                int sayi;
                struct eleman* onceki;
        };

        int sayi;
        enum{
                TOPLA = 0,
                CIKART,
                CARP,
                BOL
        };

        void eleman_ekle(int tip, int sayi);
        void yazdir_stack();
%}


%%

[ \t]   /* ignore */
[0-9]+  { eleman_ekle(OPERAND, atoi(yytext)); }
\n      { printf("İslem yapilacak: %s\n", yytext); yazdir_stack();}
\+      { eleman_ekle(OPERATOR, TOPLA);printf("Toplama: %s\n", yytext); }
-       { eleman_ekle(OPERATOR, CIKART);printf("Cikarma: %s\n", yytext); }
\*      { eleman_ekle(OPERATOR, CARP); printf("Carpma: %s\n", yytext);}
\/      { eleman_ekle(OPERATOR, BOL); printf("Bolme: %s\n", yytext);}


.  /*ignore*/

%%

struct eleman* bas;


int main(int argc, char* argv[])
{
        yylex();
}

void eleman_ekle(int tip, int sayi){
        if(!bas){
                bas = (struct eleman*)malloc(sizeof(struct eleman));
                bas->tip = tip;
                bas->sayi = sayi;
                bas->onceki = NULL;
        }else{
                struct eleman* yeni = (struct eleman*)malloc(sizeof(struct eleman));
                yeni->tip = tip;
                yeni->sayi = sayi;
                yeni->onceki = bas;
                bas = yeni;
        }
}

void yazdir_stack(){
        while(bas != NULL){
                if(bas->tip == OPERAND)
                        printf("%d\n", bas->sayi);
                else
                        switch(bas->sayi){
                                case TOPLA: printf("toplama\n"); break;
                                case CIKART: printf("cikarma\n"); break;
                                case CARP: printf("carpma\n"); break;
                                case BOL: printf("bolme\n"); break;
                                default: break;
                        }
                struct eleman* temp = bas;
                bas = bas->onceki;
                free(temp);

        }
}

Bir aritmatik işlem operand ve operatorlerden oluşur. Buradaki dizgecikleri(tokens) TOPLA, CIKART, CARP, BOL ve sayi olarak tanımladım.
Lex ve Yacc mantığından biraz uzaklaşarak ve bilmemenin katkılarıyla, ayırdığım tokenları bir stackte toplamak mantıklı gelmişti. Sadece yazdığım Lex programı çalışması gerektiği gibi çalışıyordu. Ama bu dizgecikleri(tokens) ve onların değerlerini(token bir SAYI ise onun kaç olduğunu), yacc'a nasıl atacağım konusunda bir fikrim yoktu.
Bu deneme en azından tokenlara ayırabildiğim için yarı başarılı bir deneme olarak kaldı. Yacc tarafını hiç yazmadım.

Hazır Örnek

[Calculator example][http://epaperpress.com/lexandyacc/pry2.html]
Yukarıdaki linkte bulduğum kodu yazdım. Çalıştırdım. Okudum. Eksiklerime baktım.
Dikkatimi çeken ilk şey. Lex tarafındaki şu kod parçası oldu.
[-+()=/*\n] { return *yytext; }
Bu kısımda örneği yazan kişi bu aritmatik operatorleri açıkca token olarak tanımlamamış. Sadece bunları olduğu gibi Yacc'a döndermiş. Ben onları açıkca token olarak tanımlayarak işi uzatmışım. Sonrasında bu dizgecikleri alıp yacc'da şuna benzer şekillerde kullanmış.

expr:
        INTEGER
        | VARIABLE                { $$ = sym[$1]; }
        | expr '+' expr           { $$ = $1 + $3; }
        | expr '-' expr           { $$ = $1 - $3; }
        | expr '*' expr           { $$ = $1 * $3; }
        | expr '/' expr           { $$ = $1 / $3; }
        | '(' expr ')'            { $$ = $2; }
        ;

Burada gelen ifadeyi(expression) çözümleme kuralı yer alıyor. expr '+' expr buradaki '+' yukarıda return *yytext; den gelen '+'. Bu kısmı kaçırmıştım.
Bunların dışında Yacc adına öğrendiğim bir diğer şey: Yacc'ın değerler(values) ve dizgecikler(tokens) için iki ayrı stack'e sahip olmasıydı. Benim ilk denememde yazdığım gibi bir stack'e ihtiyaç yoktu. Yacc zaten kendisi böyle bir stack barındıyordu.
Ama bu stacklere nasıl veri yazılıyor, ya da veri bu stacklerden nasıl okunuyordu?
İşte bu soru tam cevaplayabildiğim bir soru değil şimdilik. Adam bu hesap makinesi örneğinde açıklamış. Ama tam olarak anladığım söylenemez.
Parser kuralları işlerken shift/reduce dedikleri olayı yapıyor. Bottom-up parserlar (alttan üste çözümleyen çözümleyici) için böyle bir şey var. Shift(öteleme) dediği gelen token'a göre ya bir sonraki tokeni istiyor (shift) ya da bir kuralı üste çıkıyor, bir kural tamamlıyor(reduce). [Şurada][http://epaperpress.com/lexandyacc/thy.html] bu durumla alakalı bir örneği var.

Sonuç

Bu bahsettiğim sitedeki hemen hemen tüm örneklere baktım. Yazdım çizdim. Biraz daha Lex ve yacc konusunda biraz daha teorik bilgiye ihtiyacım olduğunu farkettim.
İlerleyen günlerde Lex ve Yacc'ın oluşturan teorik bilgilere yönelik çalışmalar yapacağım. Context-free languages, parsing tecniques ve Backus Naur Form ilk başta gelen konular arasında. Belki bu konular daha başka konulara ön ayak olabilir. Yapıp göreceğiz.