Pompalama Önsavı (Pumping Lemma)

Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde dil tasarımı (language design, compiler design) konusunda önemli araçlardan birisidir. Bu önsava (lemma) göre şayet bir dil, bir herhangi bir gruba ( içerik bağımsız dil (context free language) veya düzenli ifadeler (Regular expression) yada farklı bir dil grubu ) dahil olarak kabul ediliyorsa, bu dil ne kadar pompalanırsa […]

Devam

İçerikten Bağımsız Gramer (context free grammer, CFG)

Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde, dil tasarımı sırasında kullanılan bir gramer tipidir. Basitçe bir dilin kurallarını (dilbilgisini, grammer) tanımlamak için kullanılır. Örneğin: S -> a Yukarıdaki dil tanımında bir büyük harfle gösterilen (S) bir de küçük harfle gösterilen (a) sembolleri bulunmaktadır. Bu satır, S devamlısının(nonterminal) a sonuncusuna(terminal) dönüştüğünü göstermektedir. Kısaca dildeki kuralları ifade […]

Devam

İçerikten bağımsız dil (Context Free Language, CFL)

Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde bir dilin tasarımı sırasında, içerik bağımsız bir gramer ile oluşturulması durumudur. Basitçe bir aşağı sürüklemeli otomat (push down automata) tarafından kabul edilen dil çeşididir. Bazı kaynaklarda bağlamdan bağımsız dil olarak da geçmektedir. Örneğin çok meşhur L= {anbn , n>0} dilini ele alalım. Bu dil örneğinin bu kadar meşhur […]

Devam

EBNF (Uzatılmış BNF, Extended Backus Normal Form)

Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde dil tasarımı konusunda kullanılan backus normal şeklinin (backus normal form) özel bir halidir. Basitçe standart BNF’te yazılan kuralların birleştirilerek daha sade yazılmasını hedefler. Bu durumu aşağıdaki örnek üzerinden görebiliriz: Örneğin BNF olarak yazılan dilimize göre: <EGER> ::= if( <KOSUL>) | if( <KOSUL>) else şeklinde bir satırımız bulunsun. Bu […]

Devam

SableCC

Yazan : Şadi Evren ŞEKER SableCC 1998 yılında Étienne Gagnon tarafından bir yüksek lisans tezi olarak hazırlanmış ve dil geliştirmekte kullanılan, JAVA üzerinde çalışan, nesne yönelimli bir geliştirme ortamıdır. Temel olarak SableCC üzerinde bir dil geliştirmek için aşağıdaki adımların takip edilmesi gerekir: Dilde bulunacak olan kelimeler (lexicons) için bir kelime tanımı (lexical definition) yapılmalıdır. Tanım […]

Devam

Backus Normal Form (BNF)

Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerilnde genellikle bir dil tanımlamada ve bu dilin gramerini (Dil bilgisini) belirlemekte kullanılan gösterim biçimidir. Basitçe dil bir dil tanımında başlayarak Terminal (sonuncu) ve Non-Terminal (Devamlı) terimler kullanarak tanılmanmaktadır. Örneğin aşağıda basit bir örneği verilmiştir: <dil> ::= <harf>|<imla> <harf> ::= a|b|…|z <imla> ::= .| |,|? Yukarıda bir dil tanımı […]

Devam

Tek Geçişli Çevirici (One Pass Assembler)

Yazan : Şadi Evren ŞEKER Tek geçişli bir çeviricinin (assembler) karşılaştığı en büyük problem çeviricinin kaynak koddaki (Assembly dilindeki koddaki)  değişken ve etiketlerin kodun ilerleyen kısımlarında tanımlanma ihtimalidir. Bu durumda kodun geri dönerek daha sonradan tanımlanan bilgilerin önceki adreslere yazılması mümkün olmaz. Tek geçişli çeviricilerde bu problemi çözmek için iki farklı yöntem kulllanılabilir: 1. İleride […]

Devam

Çevirici (Assembler)

Yazan : Şadi Evren ŞEKER Bilgisayar bilimlerinde iki farklı kavram için assembler kelimesi kullanılmaktadır. Birincisi Assembly dili adı verilen ve makine diline (machine language) çok yakın düşük seviyeli (low level language) için kullanılan ve nesne kodunu (object code) makine koduna (machine code) çeviren dildir. İkincisi ise birleştirmek, monte etmek anlamında örneğin nesne yönelimli dillerde nesnelerin […]

Devam

NFA'den DFA'e çevirim (Converting NFA to DFA)

Yazan : Şadi Evren ŞEKER Bu yazıda belirsiz sonlu otomattan(NFA) Belirli sonlu otomata (gerekirci sonlu otomat, nedensel sonlu otomat, deterministic finite automata) dönüştürmenin nasıl yapıldığı anlatılmaktadır. Basitçe bir iki adımlık işlemler izlenerek bu dönüşüm gerçekleştirilebilir: Öncelikle gerekircilik (determinism) açısından birbiri ile özdeş olan kümler çıkarılmalıdır (subset construction) Bu kümelerin diğer kümler ile olan ilişkisi çıkarılmalıdır. […]

Devam

Belirsiz Sonlu Otomat (Nondeterministic Finite Automat, NFA)

Yazan : Şadi Evren ŞEKER DFA (deterministic finite automat) belirli sonlu otomatların (özdevinirlerin) tersine her durumdan gidişin karışık olduğu ve her durum için bir sonraki kelimede nereye gidileceğinin belirli olmadığı otomatlardır. Basitçe DFA kurallarına uymayan bütün otomatlar NFA olarak adlandırılabilir. Aşağıda bir örnek üzerinde durumu incleyelim: yukarıdaki örnekte belirsiz durumlar bulunmaktadır. Örneğin b durumunda iken […]

Devam