Bölüm 3 Konuları
• Giriş
• Sözdizim(Syntax) tanımlamanın genel
problemi
• Sözdizim(Syntax) tanımlamada resmi
metotlar
• Özellik Gramerleri
• Programların anlamlarını tanımlama:
Dinamik Anlamlar(Dynamic Semantics)
Giriş
• Sözdizimi(Syntax): Deyimlerin, ifadelerin ve
program birimlerinin biçimi ya da yapısı
• Anlamsal(Semantics): Deyimlerin, ifadelerin
ve program birimlerinin anlamı
• Sözdizimi(Syntax) ve anlamsallar(semantics)
bir dilin tanımını sağlarlar
– Bir dil tanımının kullanıcıları
• Diğer dil tasarımcıları
• Gerçekleştiriciler
• Programcılar (dilin kullanıcıları)
Sözdizim(Syntax) tanımlamanın genel problemi: Terminoloji(Terminology)
• Bir cümle(sentence) bir karakter dizisidir.
Kullanılan karakterler bir alfabeden alınır.
• Bir dil(language) cümleler(sentences)
kümesidir.
• Bir lexeme dilin en düşük seviyeli
sözdizimsel birimidir(örn., *
, sum, begin)
• Bir simge(token) lexeme ların
kategorisidir(örn., tanıtıcı(identifier))
Dillerin resmi tanımı
• Dil Tanıyıcıları(Recognizers)
– Bir tanıyıcı aygıt dilden bir karakter dizisi okur
ve bu karakter dizisinin bu dile ait olup
olmadığına karar verir.
– Örnek: bir derleyicinin söz dizimanalizcisi
– Bölüm 4 de ayrıntılandırılacaktır.
• Dil Üreticileri(Generators)
– Bir dile ait cümle üreten aygıtlart
– Belirli bir cümlenin söz diziminin doğru olup
olamdığı o dili üreten üretici incelenerek tespit
edilebilir.
Söz Diziminin Tanımında Kullanılan Resmi Metotlar
• Backus-Naur Form and Serbest- İçerik
Gramerleri(Context-Free Grammars)
– Programlama dillerinin söz dizimlerini
tanımlamada kullanılan en yaygın metottur.
• Genişletilmiş BNF(Extended BNF)
– BNF nin okunabilirliğini ve yazılabilirliğini
arttırır.
• Gramerler ve Dil Tanıyıcıları
F ve Serbest-İçerik Gramlerleri(ContextFree Grammars)
• Serbest İçerik Gramerleri
– Noam Chomsky tarafından 1950 lerin ortasında
geliştirildir
– Dil üreticileri doğal dillerin söz dizimlerini
tanımlama anlamına gelir
– Serbest-İçerik dilleri adlanılan bir diller sınıfını
tanımlar.
Backus-Naur Form (BNF)
• Backus-Naur Form (1959)
– John Backus tarafından Algol 58 i tanımlamak
için keşfedildi.
– BNF serbest içerik gramerlerinin(context-free
grammars) eşleniğidir.
– BNF bir metalanguage dir be başka bir dil
anımlar
– BNF de, soyutlamalar söz dizimsel yapıların
sınıflarını temsil etmek için kullanılır. Söz
disimsel değişkenler gibi davranırlar
(sonolmayan semboller:nonterminal symbols
adlanırlar.)
BNF Temelleri
• Son Olmayan semboller(Non-terminals): BNF soyutlamaları(abstractions) • Son semboller(Terminals): lexeme lar ve token lar • Gramer: bir kurallar koleksiyonudur. – Örnek BNF kuralları: → identifier | identifier, → if then
BNF Kurallar
• Bir kuralda sol taraf(LHS-left hand side) ve sağ taraf(RHS-right hand side) vardır ve son olan(terminal) ve son olmayan (nonterminal) sembollerden oluşur. • Bir gramer sonlu boş olmayan kurallar kümesidir. • Bir soyutlamanın(abstraction) (ve ya son olmayan sembol) birden fazla sağ tarafı olabilir. → | begin end
Tanımlama Listeleri
• Söz dizimsel listeler yineleme(recursion) kullanılarak tanımlanır. → ident | ident, • Bir türetme(derivation) kuralların tekrarlı bir şekilde uygulanmasıdır.Bir başlangıç sembolünden başlanır ve tüm elemanları son olan sembol(terminal)den oluşan bir cümle de biter.
Bir örnek gramer
Bir örnek türetme
Türetme
• Türetmelerde sembollerin her dizisi bir
cümlesel biçimdedir.
• Bir cümle sadece son olan sembollerden oluşan
bir cümlesel biçimdir(sentential form).
• En sol türetme(leftmost derivation) her
cümlesel biçimde en soldaki son olamayan
terimin açıldığı türetmedir.
• Bir türetme en sol ya da en sağ(right most)
olabilir.
Ayrıştırma Ağacı(Parse Tree)
Gramerlerin belirsizliği(Ambiguity)
• Bir gramerdeki bir cümlesel biçim iki veya
daha fazla ayrıştırma ağacı(parse tree)
oluşturuyorsa bu gramer
belirsiz(ambiguous) adlanır.
Bir belirsiz deyim(expression) grameri
Bir belirsiz deyim(expression) grameri
• Eğer ayrıştırma ağacında
işleçlerin(operators) öncelik seviyeleri
gösterilirse belirsizlik olmaz.
İşleçlerin Birleşikliği(Associativity of Operators)
• İşleç birleşikliği de bir gramerde gösterilebilir.
Genişletilmiş BNF(Extended BNF)
• Seçimli olan parçalar [ ] içinde tanımlanır. -> ident [()] • Sağ tarafın(RHS) alernatif seçenekli kısımları parantez içinde dikey çubuklar ile ayrılarak gösterilir. → (+|-) const • (0 ya da daha fazla) tekrarlamalar { } içinde yazılır. → letter {letter|digit}
Özellik Gramerleri(Attribute Grammars)
• Serbest içerik gramerleri programlama
dillerinin tüm söz dizimini tanımlamazlar
• Serbest içerikli gramerlere ayrıştırma
ağaçları ile birlikte bazı anlamsal bilgiler
içeren eklentiler katılır.
• Özellik gramerlerinin birinci değeri
– Statik anlamsal belirtimler(Static semantics
specification)
– Derleyici tasarımı (static semantics checking)
Özellik Gramerleri : Tanımlama(Definition)
• Bir özellik grameri aşağıdaki eklentilere
sahip bir serbest içerik G = (S, N, T, P)
grameridir.
– Her x gramer kuralı için bir A(x) özellik
değerleri kümesi vardır.
– Her kural fonksiyonlar kümesine sahiptir. Bu
fonksiyonlar kuraldaki son olmayan semboller
için belirli özellikler tanımlar
– Her kural (boş olabilir) özelliklerin tutarlılığını
kontrol eden yüklemseller(predicates) kümesine
sahiptir.
• X0 → X1 … Xn bir kural olsun
• S(X0) = f(A(X1), … , A(Xn)) biçimindeki
fonsiyonlar sentezlenmiş özellikleri
(synthesized attributes) tanımlar.
• I(Xj) = f(A(X0), … , A(Xn)), for i <= j <= n,
biçimindeki fonksiyonlar kalıtılmış
özellikleri(inherited attributes) tanımlar.
• Başlangıçta, yapraklarda içsel özellikler
(intrinsic attributes) bulunur.
Özellik Gramerleri
• Özellik değerleri nasıl hesaplanır?
– Eğer tüm özellikler kalıtılmışsa, ağaç yukarıdan
aşağıya sırada(top-down order) dekore
edilebilmelidir.
– Eğer tüm özellikler sentezlenmişse, ağaç
aşağıdan yukarıya sırada(bottom-up order)
dekore edilebilmelidir.
– Birçok durumda, her iki çeşit özellik de
kullanılır, ve yukarıdan aşağıya ; aşağıdan
yukarıya dekorasyon kullanılır.
Anlamsallar(Semantics)
• Anlamsalları tanımlamak için geçiş çapta
kabul edilen tek bir rotasyon yoktur.
• İşlemsel Anlamlar(Operational Semantics)
– Bir programın ifadelerini bir makinede
çalıştırarak anlamlarını tanımlar; ya simüle eder
ya da gerçekten çalıştırır. Makinenin
durumundaki(bellek-memory, yazmaçlar, registers) değişiklik ifadenin anlamını tanımlar.
İşlemsel Anlamlar(Operational Semantics)
• Bir yüksek seviye dil için işlemsel anlamaları
kullanmak için bir sanal makineye ihtiyaç vardır.
• Bir donanımsal saf yorumlayıcı çok pahalı
olacaktır.
• Bir yazılımsal saf yorumlayıcının da bazı
problemleri vardır
– Belirli bilgisayarın detaylı karakteristikleri
eylemleri anlamayı zorlaştıracaktır.
– Bu tip bir anlamsal tanımlama makine-bağımlı
olacaktır.
• Daha iyi bir alternatif: Tam bir bilgisayar simulasyonu
• süreç:
– Bir dönüştürücü oluştur( kaynak kodu idealleştirilmiş
bilgisayar için makine koduna dönüştür)
– İdealleştirilmiş bilgisayar için bir simulatör oluştur.
• İşlemsel anlamların değerlendirilmesi:
– Resmi olmayan şekilde kullanılacaksa iyidir(Dil ek
kitabı gibi)
– Resmi kullanılırsa oldukça karmaşık(örn., VDL), PL/I
nın anlamsallarını tanımlamak içişn kullanılmıştır.
Aksiyomatik Anlamlar(Axiomatic Semantics)
• biçimsel mantık temellidir.
• Orijinal amaç: biçimsel program doğrulama
• Aksiyonlar veya girişim(inference) kuralları
dildeki her ifade için tanımlanır(bu
deyimlerden başka deyimlere
dönüştürmeye izin verir)
• Deyimler iddialar(assertions) olarak
adlandırılır.
• Bir ifadeden önceki iddia (a precondition)
değişkenler arasındaki ilişkileri ve kısıtları
tanımlar
• Bir ifadeden sonraki iddia postcondition dır.
• En zayıf ön koşul (weakest precondition) en
az kısıtlayıcı önkoşuldur ve bu koşul post
condition ı garanti eder
Program kanıt süreci(Program Proof Process)
• Tüm program için önkoşul istenilen
sonuçtur.
– Programın ilk ifadesine doğru geriye doğru
çalışılır. Eğer ilk ifadenin önündeki ön koşul
program belirtimi ile aynıysa, program
doğrudur.
Aksiyomsal Anlamsal: Aksiyomlar(Axioms)
• Döngü değişkeninin karakteristikleri: I
aşağıdaki koşulları sağlamalıdır:
– P => I — ilk başta döngü değişmezi doğru olmalıdır.
– {I} B {I} — Mantıksalın hesaplanması I yı değiştirmemelidir.
– {I and B} S {I} — I döngü gövdesinin çalıştırılmasıyla değiştirilmez
– (I and (not B)) => Q — Eğer I doğruysa ve B yanlış ise,
anlamındadır
– Döngüğ sonlanır.
Döngü Değişmezi(Loop Invariant)
• I döngü değişkeni döngü postcondition nın
zayıflatılmış versiyonudur.ve ayrıca bir ön
koşuldur.
• I döngü başlamadan öncede doğru olacak
şekilde yeteri kadar zayıf olmalıdır, fakat
döngü sonlanma şartı ile birleştirildiğinde
post condition ı doğrulayacak kadar da
kuvvetli olmalıdır.
Aksiyomsal Anlamsalların hesaplanması
• Dildeki tüm ifadeler için aksiyonlar ve
girişim kuralları tanımlamak zordur.
• Doğruluk kontrolü için iyi bir araçtır ve
programlardan sonuç çıkarmada
kullanılır.Kafat dil kullanıcılarıo ve derleyici
tasarımcıları için iyi değildir.
• Bir programlama dilinin anlamını
anlamadaki kullanılışlığı dil kullanıcıları ve
derleyici tasarımcıları için iyi değildir.
Gösterimsel Anlamsallar (Denotational Semantics)
• Özyinelemeli fonksiyon temellidir.
• En soyut anlamsal tanımlama metodudur.
• Scott and Strachey (1970) tarafından
geliştirilmiştir.
• Bir dil için gösterimsel anlamsalların
üretilmesi sürecinde her dil varlığı için bir
matematiksel nesne tanımlanır.
– Dilin varlıklarının uygun gelen matematiksel
nesne örneklerine eşleyen bir fonksiyon
tanımlanır.
• Dil yapılarının anlamı sadece program
değişkenlerinin değerleri ile tanımlanır.
Gösterimsel Anlamsallar -İşlemsel Anlamsallarda
• İşlemsel anlamsallarda,durum değişiklikleri
kodlarla tanımlanır
• Gösterimsel anlamsallarda, durum
değişiklikleri katı matematiksel fonksiyonlar
ile tanımlanır.
Döngü Anlamı(Loop Meaning)
• Döngünün anlamı; program
değişkenlerinin, döngü içindeki ifadeler
belirlenen sayıda işlendikten sonraki
değerleridir.
• Öz olarak, döngü iterasyondan
özyinelemeye dönüştürülür, burada
özyinelemi kontrol başka bir özyinelemli
durum eşleme fonksiyonu ile tanımlanır.
• özyineleme(recursion), iterasyona göre
matematiksel olarak daha kolay tanımlanır.
Özet
• BNF ve serbest içerik gramerleri(contextfree grammars) eş meta dillerdir.
– Programlama dillerinin söz dizimini
tanımlamada kullanılırlar.
• Bir özellik grameri(attribute grammar) hem
sözdizimi hemde anlamsal tanımlama
yapabilir. Anlamsal tanımlamada üç temel
yöntem vardır.
– İşlemsel(Operation),aksiyomatik( axiomatic),
gösterimsel(denotational)