Bir Kod Parçasının Lexical Analizi (1)

Lexical kelime anlamı olarak sözcükle ilgili olan anlamına gelmekedir. Tarama (scanning) olarak da bilinir. Programlama dilleri açısından sözcük veya kelime değişken ismi, sayılar, anahtar kelimeler ve benzerleridir. Bu sözcükler token olarak isimlendirilir.Lexical analizcisi bir stringin karakterlerini alır ve token’lara dönüştürür. Bunu yaparken boşluk gibi karekterleri atar.

Örneğin:

[code]

int a;

a = a + 2;

[/code]

analiz edilecek olursa:

int token_int

a token_identifier

; token_special

a token_identifier

= token_assign

a token_identifier

+ token_operator

2 token_int_constant

; token_special

şeklinde analiz edilir.

Lexical Analizi Yapılacak Kod Parçası

Lexical analiz işlemi düzenli ifadeler kullanılarak kolaylıkla yapılabilirler. Fakat Deterministik Sonlu Durum Otomatları(DFA) kullanılarak da kodlanabilirler.

Burada DFA’lar kullanılarak nasıl kodlama yapılacağı gösterilecektir. Bir dilde tanımlanacak anahtar kelimeler ve durumlar çok fazladır. Fakat belirli bir örnek üzerinde yapılacak çalışma konunun anlaşılmasını kolaylaştıracaktır. Bir dile ait diğer tüm anahtar kelimeler de gösterilecek yolla analiz edilebilirler. Yazılacak lexer en az aşağıdaki kod parçasıda geçen token’ları tanıyacaktır.

[code]

while (y < z) {

int x = a+b;

y+=x;

}

[/code]

Buradaki token’ları sırasıyla yazarsak:

while token_while

( token_paren

y token_id

< token_less

z token_id

) token_paren

{ token_open_brace

int token_int

x token_id

= token_assign

a token_id

+ token_plus

b token_id

; token_comma

y token_id

+ token_plus

= token_assign

x token_id

; token_comma

} token_close_brace

Lexer için Sonlu Durum Otomatı Hazırlamak

Tasarım aşamasında deterministik olmayan sonlu durum otomatlarını kullanmak daha kolaydır. Fakat deterministik olmayan otomatları kodlanması mümkün değildir. Bu nedenle bu şekilde hazırlanan otomatlar mutlaka deterministik sonlu durum otomatına çevrilmelidir. Yapılabiliyorsa tasarım deterministik olarak yapılmalıdır. Tasarlanan otomat bu sayede ikinci kez işleme girmekten kurtulur.

Otomat tasarımında Jflap programı kullanılacaktır. Jflap, tasarlanan otomat üzerinde dönüştürme işlemleri yapılmasını kolaylaştırmasının yanı sıra, test işlemlerini de ek çaba harcamadan yapar. Ayrıca otomatın deterministik olmasını sağlamak için nondeterministik geçişleri gösteren araçlara da sahiptir.

Jflap’ta Sonlu Durum Otomatını Tasarlamak

Programlama dilindeki her bir karakter bir geçişi temsil etmelidir. Ayrıca herbir geçiş sonunda dilin özelliğine göre token olup olmadığına göre bir son durum belirlemesi yapılmalıdır. Örneğin:

lexer1

Başlangıç durumu q0’da iken ( sembolü geldiği zaman lexer bir final durumuna ulaşır. Bu final durumunun adı dilin özelliğine göre tanınmak istenen token olmalıdır.

Başka bir örneğe bakılacak olursa:

lexer2

Başlangıç durumuna gelen i karakteri otomatı q1 durumuna taşımıştır. Daha sonra gelecek olan belirli geçiş sembolleri yeni durumlara taşıyacaktır. Eğer i,n,t sembolleri ardı ardına gelirse o zaman int token’ı tanınacaktır. Arada boşluk olmadan başka bir karakter gelirse o zaman bu yeni bir tanımlayıcı olabileceği için otomat yine durum değiştirmelidir. Örneğin int_sayi şeklinde bir değişken ismi olabilir. Buradaki int dilin anahtar kelimelerinden değildir. In isminde de bir değişken olabilir fakat otomatta son durum olmadığı için tanınmayacaktır.

Deterministik sonlu durum otomatı örnekteki koda ek olarak tanımlanması kolay başka semboller de içerecektir.

Otomat bahsedilen temel mantıkta açağıdaki gibi tasarlanmıştır, burada her durum tanındıktan sonra tekrar ilk duruma dönmektedir. Karışık bir görüntü oluşturacağı için gösterilmemiştir:

lexer3

Bu otomatı tasarladıktan sonra Jflap’ın test araçlarını kullanarak tasarımın nondeterministik olup olmadığını kontrol edebiliriz. Deterministik olmayan bir otomatın kodlanması imkansızdır. Çünkü aynı işaretle iki farklı duruma geçiş söz konusu olduğunda bunu temsil edecek kod parçası yoktur. Dönüşüm yapılması gerekir.

lexer4

Daha fazla token’ın tanınması isteniyorsa, DFA aşağıdaki gibi tasarlanabilir:

lexer5

“Bir Kod Parçasının Lexical Analizi (1)” için 4 yanıt

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir

This site uses Akismet to reduce spam. Learn how your comment data is processed.