Klasik örnektir, defalarca derslerde denk gelmişsinizdir: Matematiksel ifadeleri expression tree olarak göstermek ve o gösterimi evaluate etmek: 1 + 3 / ((2 + 1) * 4³)

Bu expression tree yapısını in-order traverse ederek sonucu bulabiliriz. Her seferinde karşımıza bu kadar basit gramer yapıları çıkacak değil. Yazılım dillerinde matematiksel ifadelerden başka yapılar da mevcut, örneğin aşağıdaki kod parçasını ağaca oturtmak istersek,

if (x == -1)

y = 2 + func();

Aslında epey kolay! Metin formundaki kodu bir şekilde ağaç yapısına dönüştürdüğümüzde değer hesaplamak için tree traversal yeterli oluyor! Peki, bu ağacı nasıl oluşturacağız? Asıl soruna geliyoruz: lexing ve sonrasında parsing.

Lexical Analysis

String üzerinde çalışmak genel olarak zor. Ağaca oturtma sürecinde bir sayının değeri, değişkenin ya da fonksiyonun ismi bizi ilgilendirmiyor. Tokenizer ile metin işleme sürecinde lexeme denilen syntax parçalarının anlamını çıkarırız. Mesela, if (x == -1) y = 2;i ele alalım.

lexeme	token ID	seminfo
if	IF
(	LPAREN
x	IDENT	"x"
==	EQEQ
-1	NUM	-1
)	RPAREN
y	IDENT	"y"
=	EQ
2	NUM	2
;	SEMI

Genelde, bütün metni tutmak yerine gereksiz detayları atlayarak ham token bilgisini tutmayı tercih ederiz. token_id isminde bir enum ve seminfo isminde bir union tanımlayarak gramer yapılarını daha özlü bir şekilde temsil etmek mümkündür:

enum token_id {
    TK_IF,
    TK_TY_INT,
    // ...
};
 
union seminfo {
    char *id;
    size_t num;
};

Sadece if keyword'üne, sayılara ve isimlere odaklanacak olursak, aşağıdaki görseldeki state machine'ler metinden token üretme kurallarını uygulamaya yeterli olacaktır:

Her bir token için 3 ayrı state machine başlatmak uygulanabilir değil. Tek bir state machine olacak şekilde yeniden düzenleme yapmamız gerekiyor. Bunu, yeni starting state ekleyip onu eski starting statelere epsilon transition ile bağlayarak yapabiliriz:

Ancak şu anda lexerimiz nondeterministic finite state machine (NFA) oldu. Bunun implementasyonunu (en azından doğrudan) yapmamız mümkün değil, deterministic finite state macine (DFA) oluşturmamız gerekiyor. DFA-NFA dönüşümleri bu dersin konusu değil, sadece örnek olsun diye veriyorum:

Tabii bugün elle bu kadar optimize edilmiş bir state macine kodlamayacağız. Sayı, identifier ve punctuation'ları metinden tokenize edecek bir lexer kodlamaya başlayalım: Lexer

Alt sayfalar