Otomatlar Kuramı ve Biçimsel Diller

Düzenli ifadeler, sonlu otomatlar, bağlamdan bağımsız gramerler, yığıtlı otomatlar, Turing makineleri ve hesaplanabilirlik ilişkisini izleyen biçimsel diller ders notları.

Otomatlar kuramı ve biçimsel diller notlarını model, dil ve ifade gücü arasındaki ilişkiyi tek çizgide görebilmek için tutmuştum. Bu nedenle tanımları mümkün olduğunca kısa, dönüşümleri ise adım adım bıraktım. Düzenli dillerden Turing makinelerine ilerleyen ders yapısını değiştirmeden yalnız belirsiz veya fazla ezbere dayalı ifadeleri düzelttim.

Otomatlar kuramı ve biçimsel diller, hesaplamanın hangi soyut makinelerle ifade edilebildiğini, hangi dizgi kümelerinin hangi makine sınıflarınca tanınabildiğini ve programlama dillerinin sözdizimsel yapılarının nasıl modellenebildiğini inceler. Sonlu otomatlardan Turing makinelerine doğru ilerledikçe makinenin belleği ve ifade gücü artar. Buna karşılık karar verme ve çözümleme problemleri de daha karmaşık hale gelir.

Bu notlarda terimler günümüzde yerleşmiş kullanımla dengelenmiştir. "Özdevinir" yerine otomat, "düzgün dil" yerine düzenli dil, "düzgün deyim" yerine düzenli ifade, "uç durum" yerine kabul durumu, "geçiş çizeneği" yerine durum geçiş diyagramı kullanılır. Türkçe bilgisayar bilimi terminolojisinde yerleşmiş olan dizgi, dilbilgisi, yığıt, türetme, ayrıştırma, ardıl ve özyineleme gibi terimler korunur. İngilizce karşılıklar ilk geçtiği yerde verilir.

Ünite 1: Sonlu Otomatlar

Sonlu otomat modeli

Sonlu otomat, sonlu sayıda duruma sahip matematiksel bir hesaplama modelidir. Giriş bir simgeler dizisi olarak işlenir. Otomat her giriş simgesinde bulunduğu durumdan başka bir duruma geçer.

Sonlu otomatlar özellikle:

sözcüksel çözümleme,
metin arama,
protokol durumlarının modellenmesi,
denetim sistemleri,
dijital devreler,
basit örüntü tanıma

gibi alanlarda kullanılır.

Bir tanıyıcı sonlu otomatın temel sorusu şudur:

Verilen dizgi tanımlanan dile ait mi?

Sonlu otomatların belleği yalnızca içinde bulundukları durumdan oluşur. Sınırsız sayıcı veya yığıt kullanamazlar. Bu sınırlama, tanıyabilecekleri dil sınıfını belirler.

Alfabe, simge ve dizgi

Alfabe, sonlu bir simgeler kümesidir ve genellikle Σ ile gösterilir.

Örnek:

Σ = {0, 1}

Bu alfabe üzerinde:

birer dizgidir.

Boş dizgi ε ile gösterilir. Bazı kaynaklarda λ kullanımı da görülür.

Bir dizginin uzunluğu:

|w|

ile gösterilir.

Örneğin:

w = 01011
|w| = 5

Bir alfabe üzerindeki bütün sonlu dizgilerin kümesi:

Σ*

ile gösterilir.

Boş dizgi dışındaki bütün sonlu dizgiler:

Σ+

kümesini oluşturur.

Temel ilişki:

Σ+ = Σ* - {ε}

Dil

Bir alfabe üzerinde tanımlanan herhangi bir dizgi kümesine biçimsel dil denir.

L ⊆ Σ*

Örneğin:

L = { w ∈ {0,1}* | w içinde 11 alt dizgisi bulunur }

bir dildir.

Bir otomatın tanıdığı dil, başlangıç durumundan başlayıp girişin tümünü işledikten sonra bir kabul durumuna götüren dizgilerin kümesidir.

Deterministik sonlu otomat

DFA - Deterministic Finite Automaton, her durum ve giriş simgesi için tam olarak bir sonraki durumun bulunduğu sonlu otomattır.

Bir DFA beşli olarak tanımlanır:

M = (Q, Σ, δ, q0, F)

Burada:

Q: sonlu durumlar kümesi,
Σ: giriş alfabesi,
δ: geçiş fonksiyonu,
q0: başlangıç durumu,
F: kabul durumları kümesidir.

Geçiş fonksiyonu:

δ : Q x Σ -> Q

biçimindedir.

Bu tanım determinizmi açıklar. Her (durum, giriş simgesi) çifti için yalnız bir sonraki durum vardır.

DFA örneği

{0,1} alfabesinde içinde 11 alt dizgisi bulunan bütün dizgileri tanıyan bir DFA düşünülsün.

Durumlar:

q0 = henüz ardışık 11 görülmedi
q1 = son okunan simge 1
q2 = 11 görüldü

q2 kabul durumudur.

Geçiş tablosu:

| Durum | 0 | 1 | | --- | --- | --- | | q0 | q0 | q1 | | q1 | q0 | q2 | | q2 | q2 | q2 |

Örneğin:

w = 01011

için:

q0 --0--> q0
q0 --1--> q1
q1 --0--> q0
q0 --1--> q1
q1 --1--> q2

son durum q2 olduğundan dizgi kabul edilir.

Durum geçiş diyagramı

DFA'nın geçiş fonksiyonu yönlü çizge olarak gösterilebilir.

Her durum bir düğümdür.
Her geçiş yönlü bir kenardır.
Kenarın üzerinde geçişi oluşturan giriş simgesi bulunur.
Başlangıç durumu dışarıdan gelen bir okla işaretlenir.
Kabul durumları çift çemberle gösterilir.

Geçiş diyagramı ile geçiş tablosu aynı bilgiyi farklı biçimde gösterir.

Genişletilmiş geçiş fonksiyonu

DFA'nın tek simge yerine bütün bir dizgiyi işlemesini göstermek için geçiş fonksiyonu genişletilir.

δ* : Q x Σ* -> Q

Temel tanım:

δ*(q, ε) = q
δ*(q, wa) = δ(δ*(q, w), a)

Bir DFA'nın tanıdığı dil:

L(M) = { w ∈ Σ* | δ*(q0, w) ∈ F }

olarak tanımlanır.

Şeritli soyut makine görünümü

DFA bir şerit üzerinde yazılı giriş dizgisini soldan sağa tek geçişte okuyan soyut makine olarak düşünülebilir.

Model:

yalnız okunabilir giriş şeridi,
okuma kafası,
sonlu denetim birimi

bileşenlerinden oluşur.

Her adımda:

mevcut hücredeki simge okunur,
geçiş fonksiyonu uygulanır,
yeni duruma geçilir,
kafa bir hücre sağa gider.

DFA giriş üzerinde geriye dönmez ve ek çalışma belleği kullanmaz.

Deterministik olmayan sonlu otomat

NFA - Nondeterministic Finite Automaton, aynı durum ve giriş simgesi için sıfır, bir veya birden fazla sonraki durumun bulunmasına izin verir.

Geçiş fonksiyonu:

δ : Q x Σ -> P(Q)

biçimindedir.

Burada P(Q), Q kümesinin kuvvet kümesidir.

Örneğin:

δ(q0, 1) = {q0, q1}

ise q0 durumunda 1 okunduğunda iki olası yol vardır.

Bir NFA, giriş için oluşabilecek yollardan en az biri kabul durumunda bitiyorsa dizgiyi kabul eder.

Bu modelin fiziksel olarak aynı anda birden çok evrende çalışması gerekmez. Determinizm dışılık matematiksel bir tanımlama kolaylığıdır.

NFA'nın kabul koşulu

Bir dizgi için başlangıç durumundan kabul durumuna ulaşan en az bir yol varsa dizgi kabul edilir.

Örneğin bir NFA:

L = { w ∈ {0,1}* | w içinde 00 veya 11 bulunur }

dilini, birden fazla olasılığı aynı anda temsil eden geçişlerle DFA'dan daha sade biçimde ifade edebilir.

NFA'nın durum sayısının küçük olması daha güçlü olduğu anlamına gelmez. DFA ve NFA aynı dil sınıfını tanır.

Epsilon geçişi

NFA, girişten herhangi bir simge tüketmeden durum değiştiren geçişlerle genişletilebilir.

Bu geçiş:

ε

ile gösterilir. Bazı eski notasyonlarda λ kullanılır.

Örneğin:

q0 --ε--> q1

geçişi, otomatın hiçbir giriş simgesi okumadan q0 durumundan q1 durumuna geçebileceğini ifade eder.

Bir durumdan yalnız epsilon geçişleri kullanılarak ulaşılabilen durumların kümesine epsilon kapanışı, yani ε-closure denir.

ε-closure(q)

her zaman q durumunun kendisini de içerir.

Epsilon geçişlerinin ifade gücü

Epsilon geçişleri NFA modelinin ifade gücünü artırmaz.

Her epsilon-NFA için aynı dili tanıyan:

epsilon geçişsiz bir NFA,
ardından eşdeğer bir DFA

oluşturulabilir.

Epsilon geçişlerinin yararı modelleme kolaylığıdır.

NFA'dan DFA'ya dönüşüm

Her NFA'ya eşdeğer bir DFA vardır.

Temel yöntem alt küme yapımı, yani subset construction yöntemidir.

NFA'nın aynı anda bulunabileceği durumlar kümesi DFA'da tek bir durum olarak ele alınır.

NFA:

Q = {q0, q1, q2}

durumlarına sahipse eşdeğer DFA'nın olası durumları:

∅
{q0}
{q1}
{q2}
{q0,q1}
{q0,q2}
{q1,q2}
{q0,q1,q2}

alt kümelerinden oluşabilir.

En kötü durumda n durumlu bir NFA için DFA'nın:

2^n

duruma kadar büyümesi mümkündür.

Pratik dönüşümde yalnız başlangıç durumundan erişilebilir alt kümeler oluşturulur.

Epsilon-NFA'dan DFA'ya dönüşüm

Epsilon geçişleri varsa her adımda epsilon kapanışları hesaba katılır.

Başlangıç DFA durumu:

ε-closure({q0})

olur.

Bir DFA durumu S ve giriş simgesi a için:

move(S, a)

hesaplanır ve ardından:

ε-closure(move(S, a))

alınır.

Bu küme yeni DFA durumudur.

DFA ve NFA eşdeğerliği

Her DFA zaten özel bir NFA'dır.

Ayrıca her NFA eşdeğer DFA'ya dönüştürülebilir.

Dolayısıyla:

DFA tarafından tanınan diller
=
NFA tarafından tanınan diller
=
düzenli diller

eşitliği vardır.

NFA çoğu problemi daha az durumla ve daha doğal biçimde ifade eder. DFA ise bir dizginin çalıştırılması sırasında tek aktif duruma sahip olduğu için doğrudan gerçeklemeye daha uygundur.

İki yönlü sonlu otomat

Klasik DFA giriş üzerinde yalnız soldan sağa ilerler.

2DFA - Two-Way Deterministic Finite Automaton modelinde okuma kafası giriş üzerinde hem sağa hem sola hareket edebilir.

Geçiş fonksiyonunda sonraki durumla birlikte hareket yönü de belirlenir:

δ : Q x Σ -> Q x {L, R}

İki yönlü hareket modelin çalışma biçimini değiştirir ancak tanınabilen dil sınıfını büyütmez.

Tek yönlü DFA ile 2DFA aynı ifade gücüne sahiptir ve yalnız düzenli dilleri tanır.

Anlık tanım

Bir soyut makinenin belirli andaki tüm hesaplama durumunu ifade eden gösterime anlık tanım, yani instantaneous description denir.

İki yönlü bir otomat için anlık tanım:

mevcut durum,
okuma kafasının konumu,
girişin okunmuş ve okunmamış bölümleri

ile ifade edilebilir.

Anlık tanım kavramı daha sonra yığıtlı otomat ve Turing makinesinde daha önemli hale gelir.

Çıkış üreten sonlu otomatlar

Tanıyıcı otomat yalnız kabul veya ret sonucu üretir.

Bazı uygulamalarda ise her giriş dizgisine karşı bir çıkış dizgisi üretilmesi gerekir.

Bu sınıfta iki temel model vardır:

Moore makinesi,
Mealy makinesi.

Moore makinesi

Moore makinesinde çıkış yalnız mevcut duruma bağlıdır.

Model:

M = (Q, Σ, Δ, δ, λ, q0)

Burada:

Q: durumlar,
Σ: giriş alfabesi,
Δ: çıkış alfabesi,
δ: durum geçiş fonksiyonu,
λ: çıkış fonksiyonu,
q0: başlangıç durumudur.

Çıkış fonksiyonu:

λ : Q -> Δ

biçimindedir.

Bir duruma girildiğinde o durumun çıkışı üretilir.

Mealy makinesi

Mealy makinesinde çıkış mevcut durum ve giriş simgesine bağlıdır.

Çıkış fonksiyonu:

λ : Q x Σ -> Δ

biçimindedir.

Durum diyagramında geçişler çoğu zaman:

giriş / çıkış

biçiminde etiketlenir.

Moore ve Mealy farkı

| Özellik | Moore | Mealy | | --- | --- | --- | | Çıkış | Duruma bağlı | Durum ve girişe bağlı | | Çıkış etiketi | Durum üzerinde | Geçiş üzerinde | | Tepki | Durum değişimiyle | Giriş geçişinde | | Durum sayısı | Bazı dönüşümlerde daha fazla olabilir | Bazı durumlarda daha az olabilir |

Aynı giriş-çıkış davranışını sağlayan Moore ve Mealy makineleri karşılıklı olarak dönüştürülebilir.

Çıkış zamanlamasına ilişkin başlangıç ayrıntıları nedeniyle üretilen dizgilerin uzunlukları yorumlanırken model tanımı açık tutulmalıdır.

Moore'dan Mealy'ye dönüşüm

Moore makinesinde q durumundan a girişiyle p durumuna geçiliyorsa Mealy karşılığında geçişin çıkışı p durumunun Moore çıkışı olarak atanabilir.

Kavramsal olarak:

Moore:
q --a--> p
λ(p) = x

Mealy:

q --a/x--> p

Mealy'den Moore'a dönüşüm

Bir Mealy durumuna farklı geçişlerden farklı çıkışlarla giriliyorsa Moore dönüşümünde bu durumun birden fazla kopyasının oluşturulması gerekebilir.

Bu nedenle Mealy'den Moore'a dönüşüm durum sayısını artırabilir.

Otomat minimizasyonu

Aynı dili veya aynı giriş-çıkış davranışını tanımlayan birden fazla eşdeğer otomat bulunabilir.

Minimizasyon, gereksiz durumları kaldırarak aynı davranışı daha az durumla ifade etmeyi amaçlar.

Önce:

erişilemeyen durumlar kaldırılır,
birbirinden ayırt edilemeyen durumlar bulunur.

Eşdeğer ve ayırt edilebilir durumlar

İki DFA durumu p ve q, bundan sonra uygulanabilecek her w dizgisi için aynı kabul veya ret sonucunu veriyorsa eşdeğerdir.

p ≡ q

Eğer en az bir w dizgisi iki durumu farklı sonuçlara götürüyorsa durumlar ayırt edilebilirdir.

Başka bir deyişle bir ayırt edici dizgi varsa:

δ*(p,w) ∈ F

iken:

δ*(q,w) ∉ F

veya tersi olur.

DFA minimizasyonu

Pratik yöntemlerden biri bölümleme yaklaşımıdır.

İlk bölümleme:

P0 = { F, Q-F }

yani kabul ve kabul olmayan durumlar ayrılır.

Ardından her grup, giriş simgeleri altında farklı gruplara geçiş yapan durumlar ayrılacak biçimde tekrar bölünür.

Bölümleme artık değişmediğinde aynı bloktaki durumlar eşdeğerdir.

Her blok minimal DFA'da tek durum olur.

Minimal DFA, durum adlarının yeniden adlandırılması dışında tektir.

Ünite 2: Düzenli Diller ve Düzenli İfadeler

Düzenli dil

Sonlu otomatların tanıyabildiği dillere düzenli dil, yani regular language denir.

Aynı dil sınıfı üç eşdeğer gösterimle tanımlanabilir:

DFA
NFA / ε-NFA
Düzenli ifade

Ayrıca sağ veya sol doğrusal düzenli dilbilgileri de aynı dil sınıfını üretir.

Bu eşdeğerlik otomat kuramının temel sonuçlarından biridir.

Düzenli kümeler

Bir alfabe üzerinde düzenli kümeler özyinelemeli olarak tanımlanabilir.

Temel düzenli kümeler:

∅
{ε}
{a}  her a ∈ Σ için

Düzenli kümeler şu işlemlere göre kapalıdır:

birleşim,
ardışık birleştirme,
Kleene yıldızı.

Eğer A ve B düzenli ise:

A ∪ B
AB
A*

de düzenlidir.

Düzenli ifade

Düzenli dil tanımlamak için kullanılan sözdizimsel gösterime düzenli ifade, yani regular expression denir.

Temel düzenli ifadeler:

∅
ε
a

ve bileşik işlemler:

r | s      birleşim
rs         ardışık birleştirme
r*         sıfır veya daha fazla tekrar

biçimindedir.

Uygulama araçlarında:

+
?
{m,n}
[]
.

gibi ek regex işleçleri bulunabilir. Bunların bir bölümü temel düzenli işlemlerin kısa gösterimidir. Bazı modern regex motorları backreference gibi düzenli dillerin ötesine geçen özellikler de sağlar. Kuramsal "regular expression" ile belirli bir yazılım kütüphanesinin regex dili bu nedenle birebir aynı değildir.

İşlem önceliği

Yaygın öncelik:

yıldız *,
ardışık birleştirme,
birleşim |.

Örneğin:

ab*|c

ifadesi:

(a(b*)) | c

olarak yorumlanır.

Temel örnekler

{0,1} alfabesinde bütün dizgiler:

(0|1)*

01 ile biten dizgiler:

(0|1)*01

en az bir 1 içeren dizgiler:

(0|1)*1(0|1)*

yalnız çift sayıda 0 içeren bir dil için doğrudan ifade daha dikkatli kurulmalıdır. Düzenli ifadelerde amaç yalnız örnek dizgileri üretmek değil, istenmeyen dizgileri de dışarıda bırakmaktır.

Kleene yıldızı

Bir dilin Kleene yıldızı:

L* = ⋃ L^i, i >= 0

olarak tanımlanır.

Burada:

L^0 = {ε}

olduğundan L* her zaman boş dizgiyi içerir.

Pozitif kapanış:

L+ = ⋃ L^i, i >= 1

ve:

L+ = LL*

ilişkisi vardır.

Düzenli ifadeden sonlu otomata dönüşüm

Her düzenli ifade için aynı dili tanıyan bir sonlu otomat oluşturulabilir.

Klasik yapım yönteminde önce epsilon-NFA üretilir.

Temel parçalar:

Tek simge

a için:

q0 --a--> q1

Birleşim

r|s için yeni başlangıç ve kabul durumları eklenerek epsilon geçişleriyle iki alt otomat bağlanır.

Ardışık birleştirme

rs için r otomatının kabul durumları epsilon geçişiyle s otomatının başlangıcına bağlanır.

Kleene yıldızı

r* için:

boş dizginin kabulü,
r otomatına giriş,
tekrar başa dönüş,
çıkış

epsilon geçişleriyle sağlanır.

Bu yöntem Thompson yapımı olarak bilinir.

Sonlu otomattan düzenli ifadeye dönüşüm

Her DFA veya NFA'nın tanıdığı dil bir düzenli ifadeyle gösterilebilir.

Klasik yöntemlerden biri durum eleme yöntemidir.

Diyagramdaki durumlar sırayla kaldırılırken kalan kenar etiketleri düzenli ifadelerle güncellenir.

Bir durum k kaldırılırken i durumundan j durumuna yeni ifade:

Rij | Rik(Rkk)*Rkj

mantığıyla oluşturulur.

Böylece başlangıçtan kabule kalan tek ifade dilin düzenli ifadesini verir.

Farklı durum eleme sıraları farklı fakat eşdeğer düzenli ifadeler üretebilir.

Arden yaklaşımı

Otomat geçişlerinden düzenli dil denklemleri oluşturulabilir.

Arden önermesinin temel biçimi:

X = AX ∪ B

ve ε ∉ A ise:

X = A*B

çözümüdür.

Bu yöntem sonlu otomattan düzenli ifadeye sistematik dönüşüm için kullanılabilir.

Düzenli dillerin kapalılık özellikleri

Düzenli diller şu işlemler altında kapalıdır:

birleşim,
kesişim,
tümleme,
fark,
ardışık birleştirme,
Kleene yıldızı,
ters çevirme,
homomorfizma,
ters homomorfizma.

Örneğin L1 ve L2 düzenliyse:

L1 ∩ L2

de düzenlidir.

Kesişim için iki DFA'nın durum çiftlerinden ürün otomatı kurulabilir.

Q = Q1 x Q2

Tümleme

Tam bir DFA'nın tanıdığı dilin tümleyeni, kabul ve ret durumları yer değiştirilerek elde edilir.

F' = Q - F

Bu yöntem NFA üzerinde doğrudan yalnız kabul durumlarını ters çevirmek biçiminde uygulanamaz. Önce deterministik ve tam DFA elde edilmelidir.

Ürün otomatı

İki DFA'nın:

kesişim,
birleşim,
simetrik fark

gibi işlemleri için ürün otomatı kullanılabilir.

Durum:

(q1, q2)

çiftidir.

Geçiş:

δ((q1,q2), a)
=
(δ1(q1,a), δ2(q2,a))

biçimindedir.

Kabul kümesi yapılmak istenen işleme göre belirlenir.

Pumping Lemma

Düzenli diller için pumping lemma, yeterince uzun her kabul edilen dizginin belirli bir parçasının tekrar edilerek yine dil içinde kalacağını söyler.

Bir L dili düzenliyse bir p pumping uzunluğu vardır. Her:

w ∈ L
|w| >= p

için:

w = xyz

şeklinde bir ayrım bulunur ve:

|xy| <= p
|y| > 0

koşulları altında her i >= 0 için:

xy^i z ∈ L

olur.

Pumping lemma nasıl kullanılır?

Pumping lemma çoğunlukla bir dilin düzenli olmadığını göstermek için kullanılır.

Tipik ispat:

L düzenli varsayılır.
Pumping uzunluğu p alınır.
|w| >= p olan uygun bir w ∈ L seçilir.
Kurala uyan her w=xyz ayrımı düşünülür.
Bir i değeri seçilerek xy^i z dil dışına çıkarılır.
Çelişki elde edilir.

Klasik örnek:

L = { 0^n 1^n | n >= 0 }

düzenli değildir.

w = 0^p 1^p seçildiğinde |xy| <= p nedeniyle y yalnız 0lardan oluşur. y pompalanınca 0 ve 1 sayılarının eşitliği bozulur.

Pumping lemma bir dilin düzenli olduğunu kanıtlamak için yeterli bir yöntem değildir.

Myhill-Nerode bakışı

Bir dilin düzenli olması için ve ancak sonlu sayıda ayırt edilebilir sağ bağlam sınıfına sahip olması gerekir.

Dizgiler:

x ~L y

ilişkisiyle:

her z için xz ∈ L ancak ve ancak yz ∈ L

ise eşdeğer kabul edilir.

Myhill-Nerode teoremi:

düzenlilik,
DFA durumlarının anlamı,
minimal DFA

arasında doğrudan bağ kurar.

Ünite 3: Dilbilgileri ve Diller

Dilbilgisi

Biçimsel dilbilgisi, bir dildeki dizgilerin hangi kurallarla üretilebildiğini tanımlar.

Bir dilbilgisi dört bileşenden oluşur:

G = (V, Σ, P, S)

Burada:

V: değişkenler veya terminal olmayan simgeler,
Σ: terminal simgeler,
P: üretim kuralları,
S: başlangıç simgesidir.

V ve Σ ayrık kümelerdir.

Terminal ve terminal olmayan simgeler

Terminal simge, türetme sonunda üretilen dilin parçası olarak kalan simgedir.

Terminal olmayan simge, üretim sürecindeki yapısal değişkendir.

Örneğin:

S -> aSb
S -> ε

dilbilgisinde:

V = {S}
Σ = {a,b}

olur.

Dil:

L(G) = { a^n b^n | n >= 0 }

şeklindedir.

Türetme

Bir üretim kuralının uygulanmasına türetme adımı denir.

α => β

α dizgisinden tek adımda β dizgisinin türetilebildiğini gösterir.

Sıfır veya daha fazla adım:

α =>* β

ile gösterilir.

Bir dilbilgisinin ürettiği dil:

L(G) = { w ∈ Σ* | S =>* w }

olarak tanımlanır.

Chomsky hiyerarşisi

Dilbilgileri üretim kurallarının biçimine göre dört ana sınıfa ayrılır.

| Tür | Dilbilgisi | Dil sınıfı | Makine modeli | | --- | --- | --- | --- | | Tür 3 | Düzenli | Düzenli diller | Sonlu otomat | | Tür 2 | Bağlamdan bağımsız | CFL | Yığıtlı otomat | | Tür 1 | Bağlama duyarlı | CSL | Doğrusal sınırlı otomat | | Tür 0 | Kısıtlanmamış | Özyinelemeli numaralanabilir | Turing makinesi |

Kapsama ilişkisi:

Düzenli
  ⊂
Bağlamdan bağımsız
  ⊂
Bağlama duyarlı
  ⊂
Turing tarafından tanınabilir

Her üst sınıf alt sınıfın dillerini kapsar.

Tür 0 dilbilgisi

En genel üretim kurallarına sahiptir.

Genel biçim:

α -> β

Burada α en az bir terminal olmayan simge içermelidir.

Tür 0 dilbilgileri Turing makinelerinin tanıyabildiği dillerle ilişkilidir.

Tür 1 dilbilgisi

Bağlama duyarlı dilbilgisinde üretim kuralları genel olarak dizgi uzunluğunu azaltmaz.

Tipik biçim:

αAβ -> αγβ

şeklinde ifade edilebilir.

Burada A, çevresindeki bağlama göre γ dizgisine dönüşür.

Bu diller doğrusal sınırlı otomatlarla ilişkilidir.

Tür 2 dilbilgisi

Bağlamdan bağımsız dilbilgisinde her üretim kuralının sol tarafında tek terminal olmayan simge bulunur.

A -> α

Bu sınıf programlama dillerinin sözdizimi açısından çok önemlidir.

Yığıtlı otomatlar bağlamdan bağımsız dilleri tanır.

Tür 3 dilbilgisi

Düzenli dilbilgisi en kısıtlı sınıftır.

Sağ doğrusal biçim:

A -> aB
A -> a
A -> ε

Sol doğrusal biçim:

A -> Ba
A -> a
A -> ε

uygun koşullarla düzenli dilleri üretir.

Sağ ve sol doğrusal üretim biçimleri aynı dilbilgisinde gelişigüzel karıştırılmamalıdır.

Düzenli dilbilgisi ve sonlu otomat

Düzenli dilbilgisi ile sonlu otomatlar ifade gücü bakımından eşdeğerdir.

Düzenli dilbilgisi
        ⇄
Sonlu otomat

Her düzenli dilbilgisinin ürettiği dili tanıyan bir sonlu otomat vardır.

Her sonlu otomatın tanıdığı dili üreten düzenli dilbilgisi de oluşturulabilir.

Sağ doğrusal dilbilgisinden otomata

Her terminal olmayan simge bir otomat durumuna dönüştürülebilir.

Kural:

A -> aB

için:

A --a--> B

geçişi oluşturulur.

Kural:

A -> a

için bir kabul durumuna a geçişi eklenebilir.

S -> ε varsa başlangıç durumunun kabul durumu olması gerekir.

Sonlu otomattan düzenli dilbilgisine

Her durum bir terminal olmayan simgeyle eşleştirilir.

Geçiş:

qi --a--> qj

için:

Qi -> aQj

kuralı oluşturulur.

qj kabul durumundaysa uygun biçimde:

Qi -> a

veya kabul durumu için epsilon üretimi eklenebilir.

Düzenli dillerin sınırı

Sonlu otomatın yalnız sonlu sayıda durumu vardır. Bu nedenle keyfi büyüklükte iki sayacı karşılaştırma gibi gereksinimleri doğrudan yerine getiremez.

Örneğin:

L = { a^n b^n | n >= 0 }

düzenli değildir.

Bu dili tanımak için a sayısını hatırlayıp aynı sayıda b geldiğini denetlemek gerekir. Sınırsız n için sonlu durum belleği yeterli değildir.

Bu noktada bağlamdan bağımsız dilbilgileri ve yığıtlı otomatlar devreye girer.

Ünite 4: Bağlamdan Bağımsız Dilbilgileri

Bağlamdan bağımsız dilbilgisi

CFG - Context-Free Grammar, üretim kurallarının sol tarafında tek terminal olmayan simge bulunan dilbilgisidir.

A -> α

Burada:

A ∈ V
α ∈ (V ∪ Σ)*

olur.

CFG'ler:

programlama dili sözdizimi,
iç içe parantezler,
blok yapıları,
aritmetik ifadeler

gibi özyinelemeli yapılara uygundur.

Temel örnek

S -> aSb | ε

dilbilgisi:

L = { a^n b^n | n >= 0 }

dilini üretir.

Türetme:

S
=> aSb
=> aaSbb
=> aaaSbbb
=> aaabbb

olabilir.

Ayrıştırma ağacı

Bir dizginin dilbilgisi kurallarından nasıl türetildiğini ağaç biçiminde gösteren yapıya ayrıştırma ağacı, yani parse tree denir. Türetme ağacı terimi de kullanılır.

Kök başlangıç simgesidir.

İç düğümler terminal olmayan simgelerdir.

Yapraklar soldan sağa okunduğunda üretilen dizgiyi verir.

Örneğin:

S -> aSb | ε

ile aabb:

biçiminde düşünülebilir.

Soldan türetme

Her adımda en soldaki terminal olmayan simge genişletilir.

=>lm

notasyonu kullanılabilir.

Sağdan türetme

Her adımda en sağdaki terminal olmayan simge genişletilir.

=>rm

notasyonu kullanılabilir.

Aynı ayrıştırma ağacı farklı türetme sıralarıyla ifade edilebilir.

Belirsiz dilbilgisi

Aynı dizgi için birden fazla farklı ayrıştırma ağacı varsa dilbilgisi belirsiz, yani ambiguous kabul edilir.

Klasik örnek:

E -> E + E
E -> E * E
E -> id

id + id * id için:

(id + id) * id

ve:

id + (id * id)

biçiminde iki farklı ağaç oluşabilir.

Bu durum operatör önceliği ve birleşme yönü açıkça tanımlanarak giderilebilir.

Öncelik ve birleşme yönü

Aritmetik ifadeler için:

E -> E + T | T
T -> T * F | F
F -> (E) | id

biçimindeki yapı * işlemini + işleminden daha yüksek öncelikli yapar.

Sol özyineleme:

E -> E + T

+ işleminin sola birleşmesini doğal biçimde ifade eder.

Özyineleme

Bir terminal olmayan simge doğrudan veya dolaylı olarak kendisini üretiyorsa özyineleme vardır.

Doğrudan sol özyineleme:

A -> Aα | β

biçimindedir.

Bazı top-down ayrıştırıcılar doğrudan sol özyinelemeyi işleyemez.

Standart dönüşüm:

A  -> βA'
A' -> αA' | ε

biçimindedir.

Yok edilebilir değişken

Bir terminal olmayan simge:

A =>* ε

üretebiliyorsa nullable, yani boş dizgi türetebilen değişkendir.

CFG sadeleştirmede epsilon kuralları kaldırılırken bu değişkenler sistematik biçimde bulunur.

Başlangıç simgesinin epsilon üretmesi özel olarak korunabilir.

Birim üretim

Şu biçimdeki kurala birim üretim denir:

A -> B

Burada sağ taraf yalnız tek terminal olmayan simgedir.

Dil değişmeden birim üretimler uygun dönüşümle kaldırılabilir.

Yararsız simgeler

Bir terminal olmayan simge iki nedenle yararsız olabilir:

başlangıç simgesinden erişilemiyordur,
hiçbir terminal dizgisi üretemiyordur.

Sadeleştirme sırasında her iki sınıf da kaldırılır.

Sıra önemlidir. Önce üretken simgeler, sonra erişilebilir simgeler bulunması yaygın yöntemdir.

CFG sadeleştirme

Bir CFG'nin dilini koruyarak:

epsilon üretimleri,
birim üretimler,
yararsız simgeler

kaldırılabilir.

Bu işlemler normal biçime dönüştürme ve ayrıştırıcı üretme açısından önemlidir.

Chomsky normal biçimi

Bir CFG, uygun istisnalar dışında bütün üretimleri şu biçimlerden oluşuyorsa Chomsky Normal Form, CNF biçimindedir:

A -> BC
A -> a

Eğer dil ε içeriyorsa başlangıç simgesi için:

S -> ε

özel durumu bulunabilir.

CNF'ye dönüşüm genel olarak:

yeni başlangıç simgesi oluşturma,
epsilon üretimlerini kaldırma,
birim üretimleri kaldırma,
yararsız simgeleri kaldırma,
uzun sağ tarafları ikili hale getirme,
terminal ve terminal olmayan simgelerin karıştığı kuralları ayırma

adımlarını kullanır.

CNF örneği

Kural:

A -> aBCD

doğrudan CNF değildir.

Önce terminal için yeni değişken:

Ta -> a

oluşturulur:

A -> Ta B C D

sonra sağ taraf ikili parçalara ayrılır:

A  -> Ta X1
X1 -> B X2
X2 -> C D

Greibach normal biçimi

Bir CFG'nin üretimleri:

A -> aα

biçimindeyse Greibach Normal Form, GNF yaklaşımındadır.

Burada:

a terminal,
α sıfır veya daha fazla terminal olmayan simgeden oluşur.

Her üretim bir terminal simgeyle başlar.

Uygun koşullar altında her epsilon içermeyen bağlamdan bağımsız dil için GNF biçiminde bir dilbilgisi vardır.

CNF ve GNF'nin amacı

Normal biçimler dilin ifade gücünü artırmaz.

Ama:

ispatları standartlaştırır,
ayrıştırma algoritmalarını kolaylaştırır,
dilbilgisi yapısını sınırlar.

CNF, CYK algoritmasının temelidir.

GNF ise türetmenin her adımında bir terminal tüketmesi nedeniyle belirli kuramsal analizlerde kullanışlıdır.

CYK algoritması

CNF biçimindeki bir CFG için bir dizginin dile ait olup olmadığı dinamik programlamayla belirlenebilir.

Dizginin alt parçalarını üretebilen değişkenler tabloya yazılır.

Yaklaşık zaman karmaşıklığı:

O(n^3 |G|)

olarak ifade edilir.

Bu algoritma genel CFG üyelik probleminin sistematik çözüm yollarından biridir.

Bağlamdan bağımsız dillerin Pumping Lemması

CFL'ler için ayrı pumping lemma vardır.

Yeterince uzun z ∈ L dizgisi:

z = uvwxy

biçiminde ayrılabilir ve:

|vwx| <= p
|vx| > 0

koşulları altında her i >= 0 için:

uv^i wx^i y ∈ L

olur.

Bu lemma bazı dillerin bağlamdan bağımsız olmadığını göstermek için kullanılabilir.

Örneğin:

{ a^n b^n c^n | n >= 0 }

bağlamdan bağımsız değildir.

Ünite 5: Yığıtlı Otomatlar

Yığıtlı otomat modeli

PDA - Pushdown Automaton, sonlu denetim birimine ek olarak bir yığıta sahip otomat modelidir.

Sonlu otomatın belleği yalnız durumundan oluşurken PDA:

yığıta simge ekleyebilir,
yığının tepesindeki simgeyi okuyabilir,
tepedeki simgeyi çıkarabilir.

Bu ek bellek bağlamdan bağımsız dilleri tanımaya yeterlidir.

Temel eşdeğerlik:

Bağlamdan bağımsız dilbilgisi
             ⇄
Yığıtlı otomat

PDA'nın biçimsel tanımı

Yaygın tanım:

M = (Q, Σ, Γ, δ, q0, Z0, F)

Burada:

Q: durumlar,
Σ: giriş alfabesi,
Γ: yığıt alfabesi,
δ: geçiş fonksiyonu,
q0: başlangıç durumu,
Z0: başlangıç yığıt simgesi,
F: kabul durumlarıdır.

Nondeterministik PDA için geçiş fonksiyonu genel olarak:

δ : Q x (Σ ∪ {ε}) x Γ
    -> P(Q x Γ*)

biçimindedir.

Bir geçiş:

girişten bir simge tüketebilir veya tüketmeyebilir,
yığının tepesine göre karar verir,
tepedeki simgeyi başka bir dizgiyle değiştirebilir.

PDA soyut makinesi

PDA üç ana yapıdan oluşur:

Giriş şeridi
     ↓
Sonlu denetim
     ↕
    Yığıt

Yığıt LIFO çalışır:

push
pop
top

işlemlerine sahiptir.

PDA yığının yalnız tepesine doğrudan erişebilir.

Anlık tanım

PDA'nın anlık tanımı:

(q, w, γ)

şeklinde gösterilebilir.

Burada:

q: mevcut durum,
w: henüz okunmamış giriş,
γ: yığıt içeriğidir.

Tek adımlı geçiş:

⊢

çok adımlı geçiş:

⊢*

ile gösterilebilir.

Final durumla kabul

Girişin tümü tüketildiğinde otomat bir kabul durumundaysa dizgi kabul edilir.

(q0, w, Z0)
⊢*
(qf, ε, γ)

ve:

qf ∈ F

olmalıdır.

Yığının tamamen boş olması gerekmez.

Boş yığıtla kabul

Giriş tamamen tüketildiğinde yığıt boşsa dizgi kabul edilir.

(q0, w, Z0)
⊢*
(q, ε, ε)

Burada son durumun kabul durumu olması şart değildir.

Nondeterministik PDA'larda final durumla kabul ve boş yığıtla kabul aynı bağlamdan bağımsız dil sınıfını verir.

Palindrom benzeri dil örneği

Dil:

L = { wcw^R | w ∈ {0,1}* }

olsun.

PDA:

c simgesine kadar gelen w bölümünü yığıta iter.
c okunduğunda ikinci faza geçer.
Sonraki her simgeyi yığın tepesindeki simgeyle karşılaştırır.
Eşleşmede simgeyi yığından çıkarır.
Giriş bittiğinde başlangıç yığıt simgesine ulaşılmışsa kabul eder.

Örnek:

w = 010
wcw^R = 010c010

Yığıt ilk yarının tersini doğal olarak sakladığı için bu dil PDA için uygundur.

Orta simgesiz palindrom

Dil:

L = { ww^R | w ∈ {0,1}* }

için orta nokta giriş üzerinde açıkça belirtilmez.

Nondeterministik PDA, hangi anda push fazından pop fazına geçeceğini nondeterministik olarak tahmin edebilir.

Bu örnek nondeterminizmin PDA'daki rolünü gösterir.

Deterministik PDA

DPDA - Deterministic Pushdown Automaton, her konfigürasyonda en fazla bir geçerli hareket bulunan yığıtlı otomattır.

DPDA'ların tanıdığı deterministik bağlamdan bağımsız diller, bütün bağlamdan bağımsız dillerin gerçek bir alt kümesidir.

Bu durum sonlu otomatlardan farklıdır:

DFA = NFA ifade gücü

iken:

DPDA < NPDA ifade gücü

olur.

CFG'den PDA'ya dönüşüm

Bir CFG'nin türetimini yığıtta taklit eden nondeterministik PDA kurulabilir.

Temel yaklaşım:

Yığıta başlangıç simgesi S konur.
Yığın tepesinde terminal olmayan A varsa herhangi bir:

   A -> α

üretimi nondeterministik seçilir ve A, α ile değiştirilir.

Yığın tepesindeki terminal girişin sıradaki terminaliyle aynıysa ikisi birlikte tüketilir.
Giriş ve yığıt uygun biçimde bittiğinde kabul edilir.

Bu yöntem soldan türetmenin yığıt üzerinde simülasyonu olarak düşünülebilir.

PDA'dan CFG'ye dönüşüm

Her PDA için aynı dili üreten bir CFG oluşturulabilir.

Yapım DFA dönüşümünden daha karmaşıktır.

Değişkenler, bir durumdan başka duruma geçerken yığının belirli bölümünü dengeli biçimde tüketen hesaplamaları temsil eder.

Bu dönüşüm:

PDA tarafından tanınan diller
=
CFG tarafından üretilen diller

eşdeğerliğinin diğer yönünü kanıtlar.

Sonlu otomat ile PDA farkı

Sonlu otomat:

durum

belleğine sahiptir.

PDA:

durum + sınırsız yığıt

kullanır.

Bu nedenle:

{ a^n b^n | n >= 0 }

PDA ile tanınabilir.

İlk bölümde her a için yığıta simge eklenir. b bölümünde her b için bir simge çıkarılır.

Sonlu otomat ise sınırsız n değerini hatırlayamaz.

Ünite 6: Turing Makineleri

Turing makinesi

Turing makinesi genel hesaplama kavramını modelleyen temel soyut makinedir.

Bir Turing makinesi:

sonlu denetim birimi,
teorik olarak sınırsız şerit,
okuma-yazma kafası

kullanır.

Sonlu otomat yalnız giriş okur.

PDA giriş okuyup yığıt kullanır.

Turing makinesi şeritte:

okuyabilir,
yazabilir,
sağa veya sola hareket edebilir.

Bu nedenle hesaplama gücü çok daha yüksektir.

Temel model

Yaygın biçimsel tanım:

M = (Q, Σ, Γ, δ, q0, qaccept, qreject)

Burada:

Q: durumlar,
Σ: giriş alfabesi,
Γ: şerit alfabesi,
δ: geçiş fonksiyonu,
q0: başlangıç durumu,
qaccept: kabul durumu,
qreject: ret durumudur.

Giriş alfabesi şerit alfabesinin alt kümesidir.

Şerit alfabesi ayrıca boş hücre simgesini içerir.

Geçiş fonksiyonu

Bir temel deterministik Turing makinesinde:

δ : Q x Γ
    -> Q x Γ x {L,R}

veya model tanımına göre {L,R,S} yönleri kullanılabilir.

Geçiş:

mevcut durum ve okunan simgeye bakar,
yeni durum belirler,
şeride yeni simge yazar,
kafayı sola veya sağa hareket ettirir.

Örnek:

δ(q1, 0) = (q2, X, R)

şu anlama gelir:

q1 durumunda 0 okunursa,
X yaz,
q2 durumuna geç,
sağa hareket et.

Anlık tanım

Turing makinesinin bir andaki hesaplama durumu:

şerit içeriği,
kafa konumu,
mevcut durum

ile belirlenir.

Yaygın gösterim:

α q β

biçimindedir.

Makine q durumundadır ve kafa β bölümünün ilk simgesini okumaktadır.

Dil tanıma

Bir Turing makinesi w girdisinde kabul durumuna ulaşırsa w kabul edilir.

Makine:

kabul edebilir,
reddedebilir,
sonsuza kadar çalışabilir.

Bu ayrım hesaplanabilirlik kuramı açısından kritiktir.

Tanınabilir ve karar verilebilir dil

Bir dil için Turing makinesi:

dildeki her girdiyi kabul ediyor,
dil dışında bazı girdilerde sonsuza kadar çalışabiliyorsa

dil Turing-tanınabilir olarak adlandırılır.

Makine her girdi için sonlu sürede durup kabul veya ret veriyorsa dil karar verilebilir, yani decidable dildir.

Karar verilebilir diller tanınabilir dillerin alt kümesidir.

Turing makinesi örneği

Dil:

L = { 0^n 1^n | n >= 1 }

Turing makinesi şu stratejiyi kullanabilir:

soldaki işaretlenmemiş ilk 0ı X yap,
sağa gidip ilk işaretlenmemiş 1i Y yap,
sola dön,
işlemi tekrarla,
işaretlenmemiş 0 veya 1 kalmadığında kabul et,
eşleşme bozulursa reddet.

Turing makinesinin şeride yazabilmesi iki bölgedeki sayıları eşleştirmesini sağlar.

`a^n b^n c^n` dili

Dil:

L = { a^n b^n c^n | n >= 1 }

CFG ve tek yığıtlı PDA ile tanınamaz.

Turing makinesi her turda:

bir a,
bir b,
bir c

işaretleyerek üç grubun sayısını eşleştirebilir.

Bu örnek Chomsky hiyerarşisindeki ifade gücü artışını gösterir.

Turing makinesinin varyantları

Temel Turing makinesi farklı biçimlerde genişletilebilir:

iki yönde sonsuz şerit,
çok şeritli makine,
çok izli makine,
birden fazla kafa,
çok boyutlu şerit,
ayrı giriş şeritli makine,
nondeterministik Turing makinesi.

Bu varyantlar klasik hesaplanabilirlik anlamında temel Turing makinesinden daha güçlü değildir.

Aynı hesaplanabilir fonksiyonları ifade ederler.

Fark çoğunlukla hesaplama kolaylığı ve verimliliğidir.

Çok şeritli Turing makinesi

Birden fazla şerit ve her şerit için ayrı kafa bulunur.

Bir adımda tüm kafalar okunur, simgeler yazılır ve hareketler yapılır.

Çok şeritli model algoritma tasarımını kolaylaştırabilir.

Her çok şeritli Turing makinesi tek şeritli makineyle simüle edilebilir.

Nondeterministik Turing makinesi

Bir konfigürasyonda birden fazla geçiş mümkün olabilir.

Girdi, olası hesaplama dallarından en az biri kabul ederse kabul edilir.

Hesaplanabilirlik açısından deterministik ve nondeterministik Turing makineleri eşdeğerdir.

Karmaşıklık açısından nondeterminizm çok daha derin sonuçlar doğurur. P ve NP ayrımı bu bağlamda ortaya çıkar, ancak bu konu otomatların temel dil sınıflandırmasından ayrıdır.

Evrensel Turing makinesi

Bir Turing makinesinin tanımı veri olarak kodlanabilir.

Evrensel Turing makinesi, başka bir Turing makinesinin kodunu ve girdisini alıp onun çalışmasını simüle edebilir.

Kavramsal olarak:

U(<M>, w)

ifadesi M makinesinin w girdisindeki çalışmasını simüle eder.

Bu fikir programların veri olarak temsil edilmesi ve genel amaçlı bilgisayar kavramının kuramsal temelidir.

Church-Turing tezi

Church-Turing tezi, etkin biçimde hesaplanabilir her fonksiyonun Turing makinesiyle hesaplanabileceğini ileri sürer.

Bu matematiksel olarak kanıtlanmış bir teorem değildir. "Etkin hesaplama" sezgisel bir kavram olduğu için bir tezdir.

Lambda calculus, recursive functions, register machines ve modern programlama modelleri gibi birçok bağımsız hesaplama formalizminin aynı hesaplanabilirlik sınıfına ulaşması tezin güçlü dayanağıdır.

Durma problemi

Genel bir programın belirli girdide durup durmayacağını her durumda doğru belirleyen bir algoritma yoktur.

Halting Problem karar verilemezdir.

Varsayımsal:

HALT(P, x)

algoritmasının her program ve girdi için doğru cevap verdiği kabul edilirse kendi davranışını tersine çeviren bir program kurularak çelişki elde edilir.

Bu sonuç bilgisayar biliminin temel sınırlarından biridir:

Her iyi tanımlı problem için algoritmik karar yöntemi bulunmaz.

Chomsky hiyerarşisi ve makine gücü

Dil sınıfları makine belleğiyle birlikte genişler:

Düzenli dil
    ↓
Sonlu otomat
    ↓
yalnız sonlu durum belleği

Bağlamdan bağımsız dil
    ↓
Yığıtlı otomat
    ↓
bir yığıt

Bağlama duyarlı dil
    ↓
Doğrusal sınırlı otomat
    ↓
girdi uzunluğuyla sınırlı şerit

Turing-tanınabilir dil
    ↓
Turing makinesi
    ↓
sınırsız çalışma şeridi

Bellek arttıkça tanınabilen dil sınıfı genişler.

Düzenli, CFG ve Turing düzeylerinin karşılaştırılması

Örnek diller:

(0|1)*01

düzenlidir.

{ a^n b^n | n >= 0 }

bağlamdan bağımsızdır fakat düzenli değildir.

{ a^n b^n c^n | n >= 0 }

bağlamdan bağımsız değildir ancak daha güçlü modellerle tanınabilir.

Bu örnekler makine belleğinin ifade gücündeki etkisini açık biçimde gösterir.

Ünite 7: Ayrıştırma

Ayrıştırma kavramı

Ayrıştırma, parsing, bir simge dizisinin belirli bir dilbilgisine göre yapısal olarak geçerli olup olmadığını ve geçerliyse hangi sözdizimsel yapıya sahip olduğunu belirleme işlemidir.

Derleyicide genel akış:

Kaynak metin
    ↓
Sözcüksel çözümleyici
    ↓ tokenlar
Ayrıştırıcı
    ↓
Sözdizim ağacı
    ↓
Anlamsal çözümleme
    ↓
Ara gösterim / kod üretimi

Sözcüksel çözümleme çoğunlukla düzenli diller ve sonlu otomatlarla ilişkilidir.

Sözdizimsel ayrıştırma çoğunlukla bağlamdan bağımsız dilbilgileri ve yığıt yapılarıyla ilişkilidir.

Sözcüksel ve sözdizimsel çözümleme

Sözcüksel çözümleyici:

total = price + tax;

girdisini:

IDENTIFIER
ASSIGN
IDENTIFIER
PLUS
IDENTIFIER
SEMICOLON

token dizisine dönüştürebilir.

Parser bu tokenların dilbilgisine uygun yapıda olup olmadığını denetler.

Ayrıştırma ağacı ve soyut sözdizim ağacı

Parse tree dilbilgisinin bütün yapısal ayrıntılarını gösterir.

AST - Abstract Syntax Tree ise gereksiz sözdizimsel düğümleri çıkarıp programın anlam açısından önemli yapısını korur.

Örneğin:

a + b * c

AST:

    +
   / \
  a   *
     / \
    b   c

şeklinde olabilir.

Yukarıdan aşağı ayrıştırma

Top-down parsing başlangıç simgesinden başlar ve giriş dizgisine doğru türetme yapar.

Amaç soldan türetmeye karşılık gelen ağacı kökten yapraklara doğru kurmaktır.

Başlıca teknikler:

recursive descent,
predictive parsing,
LL(k).

Recursive descent

Her terminal olmayan simge için bir yordam yazılabilir.

Örneğin:

Expr()
Term()
Factor()

Yordamlar birbirini dilbilgisi yapısına göre çağırır.

Backtracking kullanılabilir ancak deterministik predictive parser gereksiz geri dönüşten kaçınır.

Sol özyineleme problemi

Dilbilgisi:

E -> E + T | T

recursive descent için doğrudan kullanılırsa:

E()
 -> E()
 -> E()
 ...

sonsuz özyinelemeye yol açabilir.

Sol özyineleme kaldırılır:

E  -> T E'
E' -> + T E' | ε

Sol ortak çarpanlama

Dilbilgisi:

S -> if E then S else S
S -> if E then S

ilk ortak bölüm nedeniyle tek lookahead ile karar vermeyi zorlaştırır.

Left factoring:

S  -> if E then S S'
S' -> else S | ε

biçiminde ortak önek ayrıştırılır.

FIRST kümesi

FIRST(α), α dizgisinden türetilen dizgilerin başlayabileceği terminal simgeler kümesidir.

Eğer α =>* ε ise ε de FIRST(α) içinde bulunur.

Örnek:

A -> aB | ε

ise:

FIRST(A) = {a, ε}

FOLLOW kümesi

FOLLOW(A), herhangi bir türetmede A terminal olmayanından hemen sonra gelebilecek terminal simgelerin kümesidir.

Başlangıç simgesi için giriş sonu işareti:

FOLLOW(S) içine alınır.

FIRST ve FOLLOW kümeleri LL(1) ayrıştırma tablosunun oluşturulmasında kullanılır.

LL(k)

LL(k):

girdiyi Left-to-right okur,
Leftmost derivation üretir,
karar için k token lookahead kullanır.

Pratik derslerde en yaygın özel durum LL(1)dir.

LL(1) parser:

deterministiktir,
geri dönüş gerektirmez,
her tablo hücresinde en fazla bir üretim olmasını gerektirir.

LL(1) tablosu

Her üretim:

A -> α

için:

a ∈ FIRST(α) ise M[A,a] hücresine üretim yazılır.
ε ∈ FIRST(α) ise her:

   b ∈ FOLLOW(A)

için M[A,b] hücresine üretim yazılır.

Aynı hücreye birden fazla üretim düşerse dilbilgisi bu biçimiyle LL(1) değildir.

LL(1) ayrıştırma

Parser bir yığın kullanır.

Başlangıçta:

yığın: $ S
girdi: w $

Her adımda:

yığın tepesi terminalse girişle eşleştirilir,
terminal olmayan ise tabloya bakılarak üretim seçilir,
$ ile $ eşleşirse kabul edilir.

Aşağıdan yukarı ayrıştırma

Bottom-up parsing giriş tokenlarından başlayıp başlangıç simgesine ulaşmaya çalışır.

Ters sağdan türetme olarak düşünülebilir.

Temel işlemler:

shift: girişten tokenı yığıta al,
reduce: yığının tepesindeki sağ tarafı ilgili sol tarafla değiştir,
accept: ayrıştırma başarılı,
error: geçerli hareket yok.

Shift-reduce ayrıştırma

Örnek üretim:

E -> E + T

Yığının tepesinde:

E + T

bulunursa:

E + T

yerine:

konabilir. Bu işlem reduce'dur.

Handle

Sağdan türetmenin ters adımında azaltılması gereken alt dizgiye handle denir.

Bottom-up parser'ın temel problemi doğru handle'ı ve doğru zamanda hangi üretime göre reduce yapılacağını belirlemektir.

LR ailesi bunu durum makineleri ve ayrıştırma tablolarıyla sistematik hale getirir.

LR(k)

LR(k):

girdiyi Left-to-right okur,
Rightmost derivation in reverse üretir,
k lookahead simgesi kullanır.

LR ayrıştırıcılar LL ayrıştırıcılardan daha geniş CFG sınıflarını işleyebilir.

LR öğeleri

Üretim üzerinde ne kadar ilerlediğimizi göstermek için noktalı öğe kullanılır.

Üretim:

A -> XYZ

için olası LR(0) öğeleri:

A -> .XYZ
A -> X.YZ
A -> XY.Z
A -> XYZ.

Noktanın solu tanınmış, sağı henüz beklenen bölümdür.

Closure

Bir LR öğe kümesinde:

A -> α . B β

öğesi varsa ve B için:

B -> γ

üretimi bulunuyorsa:

B -> .γ

öğesi kapanışa eklenir.

Bu işlem yeni öğe eklenmeyene kadar sürdürülür.

GOTO

Bir öğe kümesi I ve gramer simgesi X için:

GOTO(I, X)

noktanın X üzerinden ilerletilmesiyle elde edilen öğelerin closure'ıdır.

Closure ve GOTO, LR durum otomatını oluşturur.

LR(0) durum otomatiği

Her LR öğe kümesi bir durum olarak ele alınır.

Geçişler:

I --X--> GOTO(I,X)

biçimindedir.

Bu deterministik sonlu otomat parser'ın geçerli ön ekleri izlemesini sağlar.

Burada sonlu otomat teorisinin derleyici tasarımına doğrudan bağlandığı görülür.

LR(1) öğesi

LR(1) öğesi:

[A -> α . β, a]

biçimindedir.

a lookahead terminalidir.

Reduce kararı yalnız üretim tamamlandığı için değil uygun lookahead bulunduğu zaman verilir.

Bu ek bağlam LR(0)'a göre daha güçlü karar verme sağlar.

LR ayrıştırma tablosu

Tablo iki ana bölümden oluşur:

ACTION,
GOTO.

ACTION[state, terminal]:

shift,
reduce,
accept,
error

kararını verir.

GOTO[state, nonterminal] ise reduce işleminden sonra geçilecek durumu belirler.

LR ayrıştırma döngüsü

Yığında durumlar ve gramer simgeleri bulunur.

Tipik akış:

yığının tepesindeki durum s alınır,
sıradaki giriş tokenı a alınır,
ACTION[s,a] okunur,
shift ise token ve yeni durum yığıta itilir,
reduce ise üretimin sağ tarafı yığından çıkarılır,
sol taraf eklenir ve GOTO ile yeni durum bulunur,
accept veya error oluşana kadar sürer.

Shift-reduce çatışması

Bir tablo hücresinde hem:

shift,
reduce

mümkünse shift-reduce conflict vardır.

Bu durum:

belirsiz dilbilgisi,
yetersiz ayrıştırıcı sınıfı,
eksik öncelik bilgisi

gibi nedenlerle ortaya çıkabilir.

İfade dilbilgilerinde operatör önceliği ve birleşme yönü çatışmanın çözümünde kullanılabilir.

Reduce-reduce çatışması

Aynı durumda iki farklı üretime göre reduce mümkünse reduce-reduce conflict vardır.

Bu genellikle dilbilgisinin parser açısından yeterince ayırt edilebilir olmadığını gösterir.

LR ailesi

Yaygın LR teknikleri:

LR(0),
SLR(1),
LALR(1),
canonical LR(1).

Genel olarak ifade gücü:

LR(0)
   ⊂
SLR(1)
   ⊆
LALR(1)
   ⊂
LR(1)

biçiminde düşünülebilir.

LALR(1), canonical LR(1)'e göre daha küçük tablo üretmesi nedeniyle uzun süre parser generator araçlarında yaygın kullanılmıştır.

LL ve LR karşılaştırması

| Özellik | LL | LR | | --- | --- | --- | | Yön | Soldan sağa giriş | Soldan sağa giriş | | Türetme | Soldan türetme | Sağdan türetmenin tersi | | Temel yaklaşım | Top-down | Bottom-up | | Uygulama | Daha sade | Daha karmaşık | | Dilbilgisi sınıfı | Daha sınırlı | Daha geniş | | Sol özyineleme | Sorun oluşturur | Doğal olarak işlenebilir |

Parser seçimi yalnız teorik güçle yapılmaz. Dilin yapısı, hata mesajları, araç desteği ve bakım gereksinimleri de önemlidir.

Derleyiciyle ilişki

Otomatlar kuramındaki sınıflar derleyici yapısında doğrudan görülür:

Kaynak karakterleri
      ↓
Düzenli ifadeler
      ↓
Sonlu otomat
      ↓
Lexer
      ↓
Token dizisi
      ↓
CFG
      ↓
PDA / LL / LR
      ↓
Parser
      ↓
AST

Bu ilişki dersin farklı ünitelerini tek bir uygulama zincirinde birleştirir.

Konular Arasındaki Temel Eşdeğerlikler

Otomatlar kuramında en önemli sonuçlardan biri farklı gösterimlerin aynı dil sınıflarını tanımlamasıdır.

Düzenli diller

Düzenli ifade
      ⇅
Düzenli dilbilgisi
      ⇅
NFA / ε-NFA
      ⇅
DFA

Bu yapıların tümü aynı dil sınıfını ifade eder.

Bağlamdan bağımsız diller

Bağlamdan bağımsız dilbilgisi
              ⇅
Nondeterministik yığıtlı otomat

Aynı dil sınıfını ifade eder.

Genel hesaplanabilirlik

Tür 0 dilbilgisi
       ⇅
Turing makinesi

Turing-tanınabilir dilleri ifade eder.

Makine belleği ve dil gücü

Sonlu otomat
    yalnız durum
        ↓
Düzenli diller

PDA
durum + yığıt
        ↓
Bağlamdan bağımsız diller

Turing makinesi
durum + okunabilir/yazılabilir sınırsız şerit
        ↓
Turing-tanınabilir diller

Makine belleğindeki artış dil sınıfının ifade gücünü artırır.