Gramer Yapısı ve Diller PDF

Gramer Yapısı ve Diller Dr. Öğr. Üyesi Şengül Bayrak 1. Her biçimsel dil belirli bir alfabe üzerinde tanımlanır. 2. Alfabe sonlu sayıda simgelerden oluşan bir kümedir. 3. Alfabedeki simgelerin arka arkaya getirilmesi ile dizgiler (string) oluşturulur. 4. Biçimsel dil, bir alfabedeki simgelerden oluş...

Gramer Yapısı ve Diller Dr. Öğr. Üyesi Şengül Bayrak 1. Her biçimsel dil belirli bir alfabe üzerinde tanımlanır. 2. Alfabe sonlu sayıda simgelerden oluşan bir kümedir. 3. Alfabedeki simgelerin arka arkaya getirilmesi ile dizgiler (string) oluşturulur. 4. Biçimsel dil, bir alfabedeki simgelerden oluşturulan dizgilerin bir kümesidir. Bu kümeyi E ile gösterirsek, bu alfabe üzerinde tanımlanan her dil E’nin bir alt kümesidir. E deki her dizgi dilin tümcelerini (sentence) oluşturur. 5. Bir alfabe üzerinde tanımlanan biçimsel bir dil, bu alfabedeki simgelerden oluşan dizgileri geçerli ve geçersiz diye ikiye ayırır. Dilde yer alan ve tümceleri oluşturan dizgiler geçerli tersi ise geçersiz’dir. Slide 1 6. Biçimsel dil açısından dizgi, tümce ve sözcük terimleri birbirlerinin yerine kullanılabilir. Tümce dilde yer alan dizgi veya sözcükleri anlatmak için kullanılır. Buna göre, bir alfabe ve bu alfabe üzerinde tanımlı bir dil düşünüldüğünde, alfabedeki simgelerden oluşturulan ve dilde yer alan geçerli dizgiler dilin tümcelerini oluşturmaktadır. 7. Dilin hangi tümcelerden oluştuğunu gösteren kurallar bütünü ise dilbilgisi (grammar) olarak adlandırılır. Slide 2 Biçimsel dilbilgisi ve dillerin incelenmesinde, değişik harf grupları değişik alanlarda kullanılır. Harf Grubu Örnekler Kullanım alanları Latin alfabesinin başındaki büyük harfler A,B,C,... Sözdizim değişkenleri Latin alfabesinin başındaki küçük harfler ve rakamlar a,b,c,...,0,1,2 Uç simgeler Latin alfabesinin sonundaki büyük harfler U,V,W,Y,... Sözdizim değişkeni ya da uç simgeler Latin alfabesinin sonundaki küçük harfler u,v,w,y,... Uç simge dizgileri (sözcükler) Yunan alfabesinin başındaki küçük harfler , , ,... Tümcesel yapılar Slide 3 Karmaşıklık Chomsky Hiyerarşisi Özyinelemeli Sayılabilir Diller (Recursively Enumerable) Bağlama Bağımlı Diller (Context - Sensitive) Bağlamdan Bağımsız Diller (Context-Free) 0 1 2 3 Düzenli Diller (Regular) Slide 4 Sırasıyla; Dilbilgisi ve Dilin Biçimsel Tanımı Dilbilgisi ve Dillerin Sınıflandırılması tür-0, tür-1, tür-2, tür-3 Sağ-doğrusal ve Sol-doğrusal Dilbilgisi Türetme/Ayrıştırma Ağacı Chomsky Normal Biçimi Yukarıdan-aşağıya Ayrıştırma (Top-down parsing) Aşağıdan-yukarıya Ayrıştırma (Bottom-up parsing) Slide 5 Dilbilgisi ve Dilin Tanımı Slide 7 Slide 8 Dilbilgisi ve Dillerin Sınıflandırılması Slide 9 Slide 10 Slide 11 Slide 12 Programlama dilleri Bağlamdan-Bağımsız dilbilgisidir Slide 13 Slide 14 Slide 15 İçerisinde en az bir tane 0 bulunan dizgeler ∪ Slide 16 Sağ Doğrusal – Sol Doğrusal Dilbilgisi Slide 17 Slide 18 Türetme Ağacı Slide 19 Slide 20 Türetme ve Ayrıştırma Ağacının Tanımı Slide 21 Slide 22 Slide 23 Slide 24 Slide 25 Yukarıdan Aşağıya Ayrıştırma (Top-Down Parsing) Slide 28 Slide 29 Yukarıdan-Aşağıya Ayrıştırma (Top-Down Parsing, Left-to-Right, Depth-First) Slide 30 Slide 31 Slide 32 Slide 33 Slide 34 Noun meal Slide 35 Aşağıdan-Yukarı Ayrıştırma (Bottom-Up Parsing) S VP fl fl fl fl fl fl fl Slide 36 S -> Aux NPVP S -> NP VP NP -> Det Nominal NP -> NP PP A flight from Indianapolis to Houston on TWA Slide 37 S -> Aux NP VP S -> NPVP NP -> Det Nominal NP -> NP PP A flight from Indianapolis to Houston on TWA flight Slide 38 S -> Aux NP VP S -> NPVP NP -> Det Nominal NP -> NP PP PP -> Prep NP A flight from Indianapolis to Houston on TWA flight flight Slide 39 S -> Aux NP VP S -> NPVP NP -> Det Nominal NP -> NP PP A flight from Indianapolis to Houston on TWA fl fl fl Slide 40 S -> Aux NP VP S -> NPVP NP -> Det Nominal NP -> NP PP A flight from Indianapolis to Houston on TWA fl fl fl fl Slide 41 Örnek “Bir cümle isim veya fiil grubundan oluşur.”, “isim grubu isim ve/veya sıfat, fiil grubu da isim grubu ve/veya fiil den oluşur”. Bu gramerde “Küçük çocuk kırmızı top aldı” cümlesinin çözümü C İG FG : (cümle isim ve fiil grubundan oluşur) İG S İ : (isim grubu sıfat+isim) FG İG F : (fiil grubu isim grubu + fiil) S küçük|kırmızı İ çocuk|top F aldı Slide 42 C İG S FG İ küçük çocuk İG F kırmızı top aldı Slide 43 Genişletilmiş Geçiş Ağları – GGA Augmented Network Transition Grammer- ATN Biçimsel dillerin, doğal dilleri tam olarak ifade edemediği durumlarda Genişletilmiş Geçiş Ağları tercih edilir. GGA, cümlelerin sözdizimsel analizinde kullanılır. GGA sonlu makinelere benzeyen durum ve bu durumlar arası geçiş kurallarından oluşmaktadır. Üç bileşenden oluşur: En az bir başlangıç ve son durumu olan sonlu sayıdaki durumlar kümesi Belli bir metindeki mümkün olan harflerden oluşan küme Sonlu sayıdaki bir durumdan diğer bir duruma geçişi sağlayan geçişler kümesi Slide 44 Geçiş ağlarında bir durumdan diğer bir duruma geçmek için gerekli harf okunur ve bu harf geçilecek olan duruma geçmek için gereken harfle karşılaştırılır. Uygun olması durumunda geçilir. Geçiş ağlarında doğru bir yol, bir başlangıç durumundan başlayıp, son duruma ulaşan geçişler sağlandığında tamamlanır. Geçişlerdeki harflerin birbirine eklenmesiyle oluşan metin, ağın kabul etmesi için verilen metinle aynı ise, bu metin ağ tarafından kabul edilmiş demektir. Slide 45 Genişletilmiş Geçiş Ağı örneği q1 abb aa q2  q3 a q4/s b Bu ağda tanınabilecek birkaç metin örneği: abba, abbaaabba, abbaab, b Fakat abbab, baab yi tanıyamaz. Slide 46 Dilin grameri, durumlara karşı düşen yönlü graflar şeklinde ifade edilir. Bağlarda ise, çoğalmakta olan durumlar arasındaki geçişleri tanımlayan etiket sınıfları bulunmaktadır. Bu etiketler özel kelimeler, kelime kategorileri veya cümlenin önemli parçalarını tanıyan diğer ağlara yönlendirme gibi değerler almaktadır. GGA, dil tanımında belirtilen cümle birimlerini, hiyerarşik yapı içerisinde yukarıdan aşağıya doğru çözümlemeye çalışır. Slide 47 Basit bir Türkçe sözdizimi kural kümesinin GGA yapısı “Ali camı kırdı” cümlesi morfolojik analiz sonucunda “Ali cam + ı kır + dı” Q4/s cümle özne nesne yüklem özne isim isim fiil Q1 nesne yüklem Q2 Q3/s Q5/s Q6 Q8 nesne_eki Q7/s zaman_eki Q 9/s Slide 48 Bir sözdizimi kural kümesinin GGA biçiminde ifade edilmesin yararı, cümle birimlerinin bir kez tanımlandıktan sonra sonsuz kez kullanılıyor olmasıdır. Bir sıfat tamlaması bir kez tanımlanıp birçok yerde kullanılabilir. GGA’da döngüler bulunabilir. Bu özellik ile dilin kabul ettiği cümle yapıları sayısı sonsuza kadar artırabilir. “yırtık kırmızı büyük top” sıfat S isim Q Slide 49 Referans 1- https://avesis.yildiz.edu.tr/diri Slide 49