İç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 etmek için büyük harfli semboller devamlıları (nonterminal) ve küçük harfli semboller sonucuları (terminal) ifade etmekte, -> ok işareti ise, işaretin solundaki devamlının (nonterminal), sağındaki sembolle gösterilebileceğini ifade etmektedir.

Bir dili içerikten bağımsız (context-free) yapan, o dilin bir belirsiz aşağı sürüklememli otomat (non deterministic pushdown automata) tarafından üretilebilir olmasıdır.

İçerikten bağımsız diller, programlama dilleri olarak sıklıkla kullanılmaktadır, bilinen çoğu programlama dili aslında birer içerikten bağımsız dil özelliğindedir ve bu dillerin kurallarının tanımlandığı gramerlerde içerikten bağımsız gramerlerdir (context free grammer).

Bu anlamda, YACC gibi programlama ortamlarında, bir dil tasarlamak ve içerikten bağımsız kurallar yazark dili tanımlamak mümkündür.

CFG gösterimi ne yazık ki doğal diller (natural languages) için kullanılamaz. Ya da kullanılsa bile bir doğal dilin tamamını kapsayacak bir CFG gösterimi çıkarılamaz. Örneğin doğal dillerde kelimebiliminin (lexicology) bir parçası olarak sıkça kullanılan uyum (agreement) veya atıf (reference) kullanımları CFG ile gösterilemeyen özelliklerdir. Yani daha net bir ifadeyle CFG gösterimi için dildeki anlamların belirli olması gerekir. Çeşitli durumlarda belirsizlik içeren doğal diller için ise bu durum imkansızdır.

CFG tanımı

Temel olarak bir içerik bağımsız gramer dört özellik içermelidir. Bunlar sonlular (terminals), devamlılar (nonterminals), bağlantılar (relation) ve başlangıç sembolu (starting symbol) olarak sıralanabilir. Bir gramerin tanımı sırasında kullanılan bu kümeler aşağıdaki şekilde yazılabilir:

G = ( V , ∑ , R , S)

Bu gösterimdeki grammer (G) , V devamlıları, ∑ sonluları, R bağlantıları, S ise başlangıç sembolünü göstermektedir.

Örneğin

S -> aSb | ab

şeklinde tanımlanan bir dilde:

G= ( {S} , {a,b} , {S -> aSb | ab} , S )

gösterimi kullanılabilir.

Gelen soru üzerine, basit örnekleri içeren bir videoyu aşağıdaki şekilde paylaştım: