Değişkenlerin Tutulması Sorunsalı

Giriş

Bisondaki yystype değişkeni anladım. Bir kaç örnektede kullanabildim. Gramer dosyasındaki kurallarda  $$ = $1 + $2; gibi action ifadelerindeki değişken tipinin neleri nasıl etkilediği de anladım. (Biraz geç oldu ama) Değişkenleri tutmak için bir yer bulmaya çalıştım ve orada kaldım.

Değişkenlerin Tutulması

Yazdığım her hesap makinesinde tanımlanan değişkenler ya tek harf ve dizide ya da çok harfli bir listede tutuyordum. Yani yaptığım örneklerde öyleydi.
Tek harf kullanılan durumlarda, kullanıcı sadece a = 5 b = 6 gibi değişkenler tanımlayabiliyordu. Bunları bir dizide (genelde 26'lık) tam sayıya çevirerek tutuyordum.

int table[26];
Ve lex dosyasında da onu Bisonun değer stackine şöyle gönderiyordum.

[a-z]  {yylval = yytext[0]-'a'; return NAME;}

Ya da bir linked list oluşturup, değişkenleri onun içinde saklıyordum. Listedeki değişkene bakmam gerektiğinde algoritma O(n) de çalışıyordu. Programdaki değişken sayısı arttıkça bu algoritma ve veri yapısıyla daha çok yürümezdi.

Devam

Sonrasında aklıma Trie kullanmak geldi. Biraz fanteziye kaçmak gibi bir şey. Bu Trie aslında bir ağaç. Şöyle;

 .
 |
 s-------a----- .
 |       |
 e       k
 |       |
 l       ı
 |       |   
 a---m   l---n
 |   |   |   |
 m   a   l   .
 |   |   |
 .   .   ı
         |
         .
 // (.) Nokta NULL yerine kullanılmıştır.

Bir Trie'a selam, selma, akın, akıllı sözcükleri ekleyince yukarıda gibi bir görüntü de olmaları gerekiyor. Sonrasında belki o kelimelere karşılık gelen bir veri eklenebilir.
Şöyle C de şöyle tanımlanabilir.

struct _trie_node{
  char key;
  void* data;
  struct _trie_node* next;
  struct _trie_node* child;
};
Bunu implement etmek için bir kaç denemede bulundum. Bayağı uğraştım. Teoride herşey çok tatlıydı. Ama iş implement etmeye gelince, bir de ben "ben yazacağım" diye inat edince uzadıkça uzadı. Oralarda biraz kayboldum. Zaten C'de bir şey yazmak zor. Neyse, biraz zamanım bunlarda gitti. Bir Trie yazmak için bayağı bir zamanım gitti. Konu dışına da çok çıktım. Sonunda hertarafı bug dolu bir Trie yazdım sayılır.
En son bugün hash tableda tamamım, oluşturacağım bir hash table, bulacağım tatlı bir hash fonksiyonu.. Sonrası biraz sıkıntı.

Sonuç

Bu değişkenleri güzel bir yerde saklama sorununu çözdükten sonra işler biraz zorlaşacak gibi duruyor. Anladığım kadarıyla anlamsal analiz yapabilmem için bir expression tree oluşturmam gerekiyor. Böylece yazacağım programlama dilinde 5 + 'omer' gibi anlamsal hataları yakalayabileyim.( Tabi 5 + 'omer' böyle bir ifadeye yazacağım dil izin de verebilir. 5 i de bir karakter kabul eder, '5omer' döndürebilir. Ama elbet bir yerde tipleri uymayan değişkenler için yazılmaması gereken operasyonlar olacak. ) Bisondaki şöyle bir gramer bu sıkıntıya yol açacaktır.

ifade: ifade '+' ifade
  | DEGISKEN
  ;
Sonrasında sanırım kod üretme, optimizasyon gibi seviyeler var. Şu kod üretme aşamasında bir fonksiyonu ya da bir for/while döngüsünü nasıl yorumlayacağım kısmını çok merak ediyorum. Bakalım nasıl olacak. Oraya gelebilecek miyim ?

Yorumlar

Bu blogdaki popüler yayınlar

NFA, DFA, Regex, CFG, PDA

Lex ve Yacc-2

3. Hafta