Bölüm 3
Sentaks ve
semantik tarifi
ISBN 0-321-49362-1
Bölüm 3 Konuları
•
•
•
•
•
Giriş
Genel olarak sentaks tarifi
Sentaks tarifinin matematiksel yöntemleri
Özellik gramerleri (Attribute Grammars)
Programların anlamını tarif etme: Dinamik
Semantik
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-2
Giriş
• Sentaks: program ünitelerinin ve
ifadelerinin şekli/yapısı
• Semantik: program ünitelerinin ve
ifadelerinin anlamı
• Bir dilin tanımı sentaks ve semantiği ile
yapılır
• Dil tanımını kullananlar:
• Diğer dil tasarımcıları
• Dil implementasyonu yapanlar (derleyici-tercüman
yazanlar)
• Programcılar (dilin kullanıcıları)
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-3
Sentaks tarifi: terimler
• Cümle: bir alfabeden gelen karakterler
dizisi
• Dil: Cümleler kümesi
• Sözcük (lexeme): dilin en alt seviyeli
parçalara ayrılamayan ünitesi (örnek: *,
sum, begin, if, while, =)
• Jeton (token): sözcükler kategorisi (örnek:
değişken, if, sayı)
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-4
Dillerin matematiksel tanımı
• Tanıyıcılar
– Tanıyıcı alfabeden oluşturulan dizileri okur ve dile ait olup
olmadığına karar verir.
– Örnek: derleyicinin sentaks analiz kısmı
• Üreticiler
– Dile ait cümleleri sistematik olarak üretebilen “cihazlar”
– Örnek “gramerler”
– Tanıyıcıdan üretici (veya tersi) elde etmek mümkündür.
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-5
BNŞ ve Ortam-Bağımsız gramerler
• Ortam-bağımsız gramerler
– 1950 ortalarında Noam Chomsky tarafından
geliştirildi
– Dil üreticisi; amacı doğal dillerin sentaksını tarif
etmek
– Ortam-bağımsız diller sınıfını tanımlar
• Backus-Naur Şekli (BNŞ) (Backus-Naur
Form) (1959)
– John Backus tarafından Algol 58 dilini tarif
etmek için tasarlandı
– Ortam-bağımsız gramere eşdeğer
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-6
BNŞ Temelleri
•
Nonterminal semboller – sentaks yapı sınıflarını gösteren değişkenler
•
Terminaller – jetonlar (‘=’ ‘{’ gibi tek karakterler de jeton sayılıyor)
•
Kuralların solunda bir nonterminal, sağında ise terminal ve/veya nonterminallerden
oluşan bir dizi olur.
•
Nonterminaller çoğunlukla köşeli parantez içinde yazılırlar
–
Örnek BNŞ kuralları:
<ident_list> → identifier | identifier, <ident_list>
<if_stmt> → if <logic_expr> then <stmt>
•
Gramer: sonlu, boş olmayan kurallar kümesi
•
Başlangıç sembolü: nonterminallerin özel bir üyesi. Türeme her zaman başlangıç
sembolü ile başlar.
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-7
BNŞ Kuralları
• Bir nonterminali tanımlayan kuralın
birden çok sağ tarafı olabilir.
<stmt>  <single_stmt>
| begin <stmt_list> end
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-8
Liste tarifi
• Listeler özyineleme ile gösterilir
<ident_list>  ident
| ident, <ident_list>
• Türeme başlangıç sembolünden
başlayarak her seferınde bir kural
uygulanarak cümle (terminallerden
oluşan dizi) elde edilmesidir. Kural
uygulanması bir nonterminalin onu
tanımlayan kuralın sağ tarafı ile
değiştirilmesi ile yapılır.
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-9
Örnek Gramer
<program>  <stmts>
<stmts>  <stmt> | <stmt> ; <stmts>
<stmt>  <var> = <expr>
<var>  a | b | c | d
<expr>  <term> + <term> | <term> - <term>
<term>  <var> | const
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-10
Örnek Türeme
<program> => <stmts> => <stmt>
=> <var> = <expr>
=> a = <expr>
=> a = <term> + <term>
=> a = <var> + <term>
=> a = b + <term>
=> a = b + const
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-11
Türemeler
• Bir türemedeki her dizi bir cümlesel şekil
dir (sentential form)
• Cümle sadece terminallerden oluşan bir
cümlesel şekildir.
• Soldan (sağdan) türeme türemenin her
adımında cümlesel şekildeki en soldaki
(sağdaki) nonterminali seçmekle
değiştirmekle olur.
• Ne soldan, ne de sağdan olan türemeler
mümkündür.
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-12
Ayrıştırma ağacı (“gramer ağacı”)
• Türemenin hiyerarşik temsiliyeti
<program>
<stmts>
<stmt>
<var>
=
<expr>
a <term> +
<term>
<var>
const
b
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-13
Gramerlerde belirsizlik
• Bir gramer ayni cümle için iki tane farklı
ağaç üretebiliyorsa, bu gramer
belirsizdir.
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-14
Belirsiz bir ifade grameri
<expr>  <expr> <op> <expr>
<op>  / | -
|
const
<expr>
<expr>
<expr>
<op> <expr>
<expr> <op>
<expr> <op> <expr>
const
-
const
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
<expr>
<expr> <op> <expr>
/
const
const
-
const /
const
1-15
Belirsiz olmayan bir ifade grameri
<expr>  <expr> - <term> | <term>
<term>  <term> / const| const
<expr>
<expr>
-
<term>
<term>
<term> /
const
const
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
const
1-16
Operatör birleşebilirliği
(associativity)
• Sol özyineleme, sola birleşebilirlik
• Sağ özyineleme, sağa birleşebilirlik
<expr> -> <expr> + <expr> | const
<expr> -> <expr> + const | const
<expr>
<expr>
<expr>
<expr>
+
+
(ambiguous)
(unambiguous)
const
const
const
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-17
Genişletilmiş BNŞ (GBNŞ)
• Opsiyonel kısımlar köşeli parantez içine[ ]
<proc_call> -> ident [(<expr_list>)]
• Sağ tarafın alternatif kısımları parantez
içinde | ile ayrılır
<term> → <term> (+|-) const
• Sıfır veya daha çok defa tekrar için {}
kullanılır.
•
<ident> → letter {letter|digit}
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-18
BNŞ ve GBNŞ
• BNF
<expr>  <expr> + <term>
| <expr> - <term>
| <term>
<term>  <term> * <factor>
| <term> / <factor>
| <factor>
• GBNŞ
<expr>  <term> {(+ | -) <term>}
<term>  <factor> {(* | /) <factor>}
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-19
Statik Semantik
• Anlamla ilgisi yok
• Ortam-bağımsız gramerler programlama
dillerinin bütün yapılarını tarif edemezler
veya tarif edilmeleri pratik değildir.
• Örnek sorunlu yapılar:
- Ifadelerin tipleri
- Değişkenlerin kullanım öncesi
tanımlanmaları
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-20
Özellik (attribute) gramerleri (ÖG)
• Özellik gramerlerinin ortam-bağımsız
gramerlere göre ayrıştırma ağaçlarının
düğümlerinde (nodes) fazladan bilgi
saklama yetenekleri vardır.
• ÖG’lerin kullanım yerleri:
– Statik semantik belirlemesi
– Derleyiçi tasarımı (kod üretimi, statik
semantik kontrolü)
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-21
Özellik Gramerleri: Tanım
• Özellik grameri, ortam bağımsız gramer G
= (S, N, T, P) e aşağıdaki eklemelerle
oluşur.
– Her gramer sembolü x için bir özellik kümesi
A(x) vardır
– Her kuralda, bazı/tüm özelliklerin nasıl
hesaplandıklarını gösteren fonksiyonlar vardır.
– Her kuralda özelliklerinin tutarlılığını kontrol
eden sıfır veya daha çok yüklem (predicate)
vardır.
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-22
Özellik Gramerleri: Tanım
• X0  X1 ... Xn bir kural olsun
• A(X0)’in herhangi bir elemanı  kendi
değeri için sadece X1 ... Xn özelliklerinin
değerlerine bağlı ise,  sentezlenmiş
(synthesized) bir özelliktir.
• Aksi halde  miras kalmış (inherited) bir
özelliktir.
• İlk başta, yapraklarda gerçek özellikler
(hesaplanması gerekmeyen) ve değerleri
bulunur.
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-23
Özellik Gramerleri : Örnek
• Sentaks
<assign> -> id = <expr>
<expr> -> <expr> + id
<expr> -> id
• gerçek_tip: <expr> için
sentezlenmiş
• beklenen_tip: <expr> için miras
kalmış
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-24
Özellik Gramerleri (devam)
Sentaks kuralı: <assign> -> id = <expr>
Semantik kurallar:
<expr>.beklenen_tip  lookupType(id.index)
Yüklem:
<expr>. beklenen_tip == <expr>. gerçek_tip
• lookupType: sembol tablosundan bir değişkenin vs.
tipini bakan fonksiyon
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-25
Özellik Gramerleri (devam)
Sentaks kuralı: <expr>  <expr> + id
Semantik kurallar:
<expr>1.gerçek_tip  <expr>2.gerçek_tip
<expr>2.beklenen_tip 
<expr>1.beklenen_tip
Yüklemler:
<expr>2.gerçek_tip == <expr>2.beklenen_tip
<expr>2.gerçek_tip == lookupType(id.index)
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-26
Özellik Gramerleri (devam)
Sentaks kuralı: <expr> -> id
Semantik kurallar:
<expr>.gerçek_tip 
lookupType(id.index)
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-27
Özellik Gramerleri (devam)
• Özellik değerleri nasıl hesaplanır?
– Bütün özellikler miras kalmış ise, ağaç
yukarıdan aşağı doğru “süslenebilir”
– Bütün özellikler sentezlenmiş ise, ağaç
aşağıdan yukarı doğru “süslenebilir”
– Çoğu zaman her iki tür özellik olduğundan,
ağacın hem yukarıdan aşağı, hem de aşağıdan
yukarı “süslenmesi” gerekir.
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-28
Semantik
• Semantiği anlatmak için kabul gören tek bir
yöntem yoktur.
• Üç ana yaklaşım
– Operasyonel semantik
– Aksiyomatik semantik
– Gösterimsel semantik
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-29
Operasyonel Semantik
• Bir programın anlamı program ifadelerinin
gerçek veya benzetimi yapılan bir
makinenin üzerinde çalıştırılması ile elde
edilir. Makinenin durumundaki değişiklik
ifadelerin anlamını tanımlar.
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-30
Operasyonel Semantik (devam)
• Yöntem:
– İdeal özelliklerde bir bilgisayar tasarla
– Bu ideal bilgisayar için bir simülatör yaz
– Kaynak dilden ideal makine koduna bir
derleyicinin kurallarını ver
– Bu kuralları gerçekleştiren derleyici yaz
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-31
Operasyonel Semantik (devam)
• Değerlendirme:
– Çok detaya girmeden kullanılırsa iyi
– Matematiksel kullanım karmaşık olabilir
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-32
Aksiyomatik Semantik
• Matematiksel mantığa dayalı
• İlk amacı: matematiksel program doğruluğu
• Dildeki her ifade türü için bir aksiyom
(çıkarım kuralı) var
• Aksiyomların parçası olan mantık
ifadelerine iddia denir.
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-33
Aksiyomatik Semantik (devam)
• İfade öncesi bir iddia (öncekişart)
değişkenler arasında o anda var olan
ilişkileri belirtir
• İfade sonrası iddialara sonrakişart denir.
• En zayıf öncekişart en az sınırlaması olup
da sonrakişartı garantileyen iddiadır.
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-34
Aksiyomatik semantik şekli
• {P} ifade {Q}
• Örnek
– a = b + 1 {a > 1}
– Olası bir öncekişart:
{b > 10}
– En zayıf öncekişart :
{b > 0}
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-35
Program doğruluğunun ispatı
• Tüm programın sonrakişartı istenilen
neticedir
– Sondan başlayıp geriye doğru gidin. Programın
önşartına erişebilirseniz o zaman program
doğrudur.
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-36
Aksiyomatik Semantik: Aksiyomlar
• Atama ifadeleri için aksiyom: {Qx->E} x = E {Q}
• Sonuç kuralı:
{P} S {Q}, P'  P, Q  Q'
{P' } S {Q'}
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-37
Aksiyomatik Semantik: Aksiyomlar
• S1; S2 şeklinde sıralı ifadeler için çıkarım kuralı
{P1} S1 {P2}
{P2} S2 {P3}
{P1} S1 {P2}, {P2} S2 {P3}
{P1} S1; S2 {P3}
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-38
Aksiyomatik Semantik: Aksiyomlar
• Ön testli döngüler için çıkarım kuralı
{P} while B do S end {Q}
(I and B) S {I}
{I} while B do S {I and (not B)}
I döngü değişmezi dir
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-39
Aksiyomatik Semantik: Aksiyomlar
• Döngü değişmezinin özellikleri: I aşağıdaki
şartları sağlamalı:
–
–
–
–
P => I -- ilk başta doğru olmalı
{I} B {I} -- Bnin çalışması I’yı değiştirmemeli
{I and B} S {I} -- I dongü tarafından değiştirilmemeli
-- I doğru ise ve B yanlış ise Q doğru
(I and (not B)) => Q
olmalı
– Döngü son bulur
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
-- ispatı zor olabilir
1-40
Döngü değişmezi
• Döngü değişmezi hem bir önşarttır, hem de
döngü sonrakişartının zayıflatılmış şeklidir
• Döngüye girmeden önce doğru olmak için
yeterince zayıf olmalı, ama dongü bitiş şartı
ile birleştiğinde sonrakişartın doğruluğunu
garanti etmeli
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-41
Aksiyomatik semantik
değerlendirmesi
• Dilin her ifadesi için çıkarım kuralı üretmek
zordur.
• Program doğruluğu ispatları ve programlar
hakkında mantık neticelerine varmak için iyi
bir araçtır
• Programlama dilinin anlamını vermede
kullanıcıIara ve derleyici yazanlara çok
yararlı değildir
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-42
Gösterimsel Semantik
• Özyinelemeli fonksiyon kuramına dayalı
• En soyut semantik anlatım yöntemi
• Scott ve Strachey tarafından geliştirildi
(1970)
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-43
Gösterimsel Semantik (devam)
• Bir dil için göserimsel sematik tanımlama
yöntemi:
- Her dil varlığı için matematiksel bir nesne
tanımla
• Dil varlıklarını matematiksel nesnelere
eşleştiren bir fonksiyon tanımla.
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-44
Gösterimsel Semantik Değerlendirmesi
• Programların doğruluğunu ispat için
kullanılabilir
• Programlar hakkında matematiksel
kesinlikle düşünme yoludur
• Dil tasarımına yardımcı olabilir
• Derleyici üretim sistemlerinde kullanıldı
• Karmaşıklığından dolayı, dil kullanıcılarına
faydası sınırlı
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-45
Özet
• BNŞ ve ortab bağımsız gramerler birbiri ile
eşdeğer
• Programlama dillerinin sentaksını
tanımlamaya uygun
• Özellik gramerleri dilin sentaksını ve statik
semantiğini anlatmaya uygun
• Dinamik semantik tanımı için üç ana
yöntem: operasyonel, aksiyomatik ve
gösterimsel
Tercüme edip geliştiren: Doç. Dr. Zeki Bayram, DAÜ
1-46
Download

Sentaks ve semantik