- 7 Şub 2012
- 5,018
- 21
Merhabalar, http://www.turkhackteam.org/off-top...cilar-belli-olacak-teknik-yarisma-ihan3t.html konusunda sorduğum sorunun cevabının bir kısmını yazmaya karar verdim.
Sorduğum soruda istediğim şey bir tokenizer (lexer) ve bir adet parser yazılmasıydı, fakat birçoğu soruyu anlamadı/çarpıttı ve istenilen cevap ortaya maalesef çıkmadı.
Bir programlama dilini kullanarak yazdığımız kod aslında belirli kurallara uyarak bir araya getirdiğimiz karakterler kümesidir.
Tokenizer, bu karakterler kümesini dilin kurallarını kullanarak interpreterın anlayacağı hale getirir.
Şimdi basit matematiksel ifadelerimizi tokenize etme işlemini yapacağız.
Yapacağımız iş,
(9*3)-1+8*5+(1-3)
şeklinde verilen bir ifadeyi tokenlara ayırmak olacak.
Tokenizer adında bir classımız olsun. Tokenlara ayırmak için verilen expression ımızı teker teker okuyup belirli bir kurala göre tokenize edeceğiz. Kuralımız ise şu, eğer matematiksel bir ifadeye rastlarsa (dört işlem sembolü veya parantez) token olarak ekle, eğer bir sayıya rastlarsa sayı devam ettiği sürece alıp bunu token olarak ekle.
Classımızın 3 adet fieldı var. Birincisi tokenize edeceğimiz expression, diğeri şuanda okuduğumuz char diğeri expressiondaki mevcut pozisyonumuz (kaçıncı karakteri okuduğumuz) sonuncusu ise operation tiplerimizi tutan dictionary tipindeki değişkenimiz. (bu değişken yerine TokenTypes gibi bir enum da tutulabilirdi, farklı şekillerde yapılabilirdi, token tiplerimiz az olduğu için ve kod yazarken kolaylık olsun diye ben dictionary seçtim)
Tokenlarımızı temsil eden classımız :
Tokenize etme işlemi sırasında bir char ın operation olup olmadığına karar vereceğimiz ve eğer operation ise hangi operation olduğunu söyleyen metodu ekleyelim :
Şimdi gelelim tokenize metodumuza. Asıl işi burada yapıyor olacağız.
- Burada expressionımızdan bir karakter okuyoruz
- Başlangıçta "default" adında bir durumdayız
- Durumumuz default ise okuduğumuz karakterin operation mı yoksa sayı tipinde mi olduğuna bakıyoruz
- Eğer operation tipindeyse, hangi operation olduğunu bulup token listemize ekliyoruz
- Eğer sayı tipindeyse sayıyı token değişkenimize ekleyip, state değişkenini "number" yapıyoruz ve sayının sonuna kadar okumaya devam ediyoruz
- Sayı bitip tekrar bir operation geldiğinde state imizi tekrar değiştiriyoruz ve token oluşturma işlemine devam ediyoruz
Programı bir bütün haline getirelim :
Kodumuzu çalıştırdığımızda bize şöyle bir çıktı veriyor :
Tokenize edilmiş sonucumuz. Bu çok simple bir tokenizer. Bir expressionı tokenize ettikten sonra, mantığı anlayıp daha derin bilgiler edindiğinizde aslında bir programlama dili syntaxı oluşturmaya başlıyorsunuz.
Parse etme sürecini de öğrenince aslında çalışan bir programlama diliniz oluyor.
Tabii ki bu tasarlamayı yapmak için context free grammer kavramını, terminal ve non terminal değişkenleri bilmek gerekiyor.
Verdiğim örneklerden yola çıkıp kendinizi geliştirerek programlama dili keywordlerini tokenize eden bir tokenizer yazabilirsiniz artık.
Tokenize etme aşamasında çok farklı teknikler kullanılabilir, matematik dilini baz aldığımız için bu şekilde karakter bazında okuma işlemi bizim için yeterli.
Yeterli ilgi olursa parse etme işlemini ileriki zamanlarda fırsat bulursam anlatabilirim.
Herkese iyi forumlar, ihan3t.
Sorduğum soruda istediğim şey bir tokenizer (lexer) ve bir adet parser yazılmasıydı, fakat birçoğu soruyu anlamadı/çarpıttı ve istenilen cevap ortaya maalesef çıkmadı.
Bir programlama dilini kullanarak yazdığımız kod aslında belirli kurallara uyarak bir araya getirdiğimiz karakterler kümesidir.
Tokenizer, bu karakterler kümesini dilin kurallarını kullanarak interpreterın anlayacağı hale getirir.
Şimdi basit matematiksel ifadelerimizi tokenize etme işlemini yapacağız.
Yapacağımız iş,
(9*3)-1+8*5+(1-3)
şeklinde verilen bir ifadeyi tokenlara ayırmak olacak.
Tokenizer adında bir classımız olsun. Tokenlara ayırmak için verilen expression ımızı teker teker okuyup belirli bir kurala göre tokenize edeceğiz. Kuralımız ise şu, eğer matematiksel bir ifadeye rastlarsa (dört işlem sembolü veya parantez) token olarak ekle, eğer bir sayıya rastlarsa sayı devam ettiği sürece alıp bunu token olarak ekle.
Classımızın 3 adet fieldı var. Birincisi tokenize edeceğimiz expression, diğeri şuanda okuduğumuz char diğeri expressiondaki mevcut pozisyonumuz (kaçıncı karakteri okuduğumuz) sonuncusu ise operation tiplerimizi tutan dictionary tipindeki değişkenimiz. (bu değişken yerine TokenTypes gibi bir enum da tutulabilirdi, farklı şekillerde yapılabilirdi, token tiplerimiz az olduğu için ve kod yazarken kolaylık olsun diye ben dictionary seçtim)
Tokenlarımızı temsil eden classımız :
Kod:
class Token():
type = ''
text = ''
def __init__(self, text, type):
self.type = type
self.text = text
Kod:
class Tokenizer():
expression = ''
currentChar = ''
currentCharPosition = 0Tokenize etme işlemi sırasında bir char ın operation olup olmadığına karar vereceğimiz ve eğer operation ise hangi operation olduğunu söyleyen metodu ekleyelim :
Kod:
class Tokenizer():
expression = ''
currentChar = ''
currentCharPosition = 0
opTypes = {
'+' : 'ADD',
'-' : 'SUBTRACT',
'*' : 'MULTIPLY',
'/' : 'DIVIDE',
'(' : 'LEFT_PAREN',
')' : 'RIGHT_PAREN'
}
def isOp(self, chr):
opList = ['+', '-', '*', '/', '(', ')']
return True if chr in opList else False
def findOpType(self, chr):
return self.opTypes[chr]Şimdi gelelim tokenize metodumuza. Asıl işi burada yapıyor olacağız.
Kod:
def tokenize(self, resource):
tokens = []
token = ''
state = 'DEFAULT'
index = 0
while index < len(resource):
chr = resource[index]
index += 1
if state == 'DEFAULT':
if self.isOp(chr):
opType = self.findOpType(chr)
tokens.append(Token(chr, opType))
elif chr.isdigit():
token += chr
state = 'NUMBER'
continue
if state == 'NUMBER':
if chr.isdigit():
token += chr
else:
tokens.append(Token(token, 'NUMBER'))
token = ''
state = 'DEFAULT'
index -= 1
continue
return tokens- Burada expressionımızdan bir karakter okuyoruz
- Başlangıçta "default" adında bir durumdayız
- Durumumuz default ise okuduğumuz karakterin operation mı yoksa sayı tipinde mi olduğuna bakıyoruz
- Eğer operation tipindeyse, hangi operation olduğunu bulup token listemize ekliyoruz
- Eğer sayı tipindeyse sayıyı token değişkenimize ekleyip, state değişkenini "number" yapıyoruz ve sayının sonuna kadar okumaya devam ediyoruz
- Sayı bitip tekrar bir operation geldiğinde state imizi tekrar değiştiriyoruz ve token oluşturma işlemine devam ediyoruz
Programı bir bütün haline getirelim :
Kod:
class Tokenizer():
expression = ''
currentChar = ''
currentCharPosition = 0
opTypes = {
'+' : 'ADD',
'-' : 'SUBTRACT',
'*' : 'MULTIPLY',
'/' : 'DIVIDE',
'(' : 'LEFT_PAREN',
')' : 'RIGHT_PAREN'
}
def isOp(self, chr):
opList = ['+', '-', '*', '/', '(', ')']
return True if chr in opList else False
def findOpType(self, chr):
return self.opTypes[chr]
def tokenize(self, resource):
tokens = []
token = ''
state = 'DEFAULT'
index = 0
while index < len(resource):
chr = resource[index]
index += 1
if state == 'DEFAULT':
if self.isOp(chr):
opType = self.findOpType(chr)
tokens.append(Token(chr, opType))
elif chr.isdigit():
token += chr
state = 'NUMBER'
continue
if state == 'NUMBER':
if chr.isdigit():
token += chr
else:
tokens.append(Token(token, 'NUMBER'))
token = ''
state = 'DEFAULT'
index -= 1
continue
return tokens
def main():
tokenizer = Tokenizer()
expression = "( 9 *3 )-1+8*5+(1-3)"
tokens = tokenizer.tokenize(expression)
for token in tokens:
if token.type == 'NUMBER':
print '{} ({})'.format(token.type, token.text)
else:
print token.typeKodumuzu çalıştırdığımızda bize şöyle bir çıktı veriyor :
Kod:
LEFT_PAREN
NUMBER (9)
MULTIPLY
NUMBER (3)
RIGHT_PAREN
SUBTRACT
NUMBER (1)
ADD
NUMBER (8)
MULTIPLY
NUMBER (5)
ADD
LEFT_PAREN
NUMBER (1)
SUBTRACT
NUMBER (3)
RIGHT_PARENTokenize edilmiş sonucumuz. Bu çok simple bir tokenizer. Bir expressionı tokenize ettikten sonra, mantığı anlayıp daha derin bilgiler edindiğinizde aslında bir programlama dili syntaxı oluşturmaya başlıyorsunuz.
Parse etme sürecini de öğrenince aslında çalışan bir programlama diliniz oluyor.
Tabii ki bu tasarlamayı yapmak için context free grammer kavramını, terminal ve non terminal değişkenleri bilmek gerekiyor.
Verdiğim örneklerden yola çıkıp kendinizi geliştirerek programlama dili keywordlerini tokenize eden bir tokenizer yazabilirsiniz artık.
Tokenize etme aşamasında çok farklı teknikler kullanılabilir, matematik dilini baz aldığımız için bu şekilde karakter bazında okuma işlemi bizim için yeterli.
Yeterli ilgi olursa parse etme işlemini ileriki zamanlarda fırsat bulursam anlatabilirim.
Herkese iyi forumlar, ihan3t.
