Gramerlerde bağlam bağımsızlık ve indentation-based gramerlerin çözümlenmesi

June 12, 2012 - Tagged as: haskell, tr.

(Yazıda terimleri Türkçe kullanmaya çalıştım, bağlam bağımsız = context-free, çözümleme = parsing, indentation-based ve lexing/lexer için güzel bir Türkçe karşılık bulamadım, önerilere açığım.)

Indentation-based gramerlerin çözümlenmesi her zamankinden biraz daha zor. Sebebi bunların aslında bağlam bağımsız(bu kelime grubu bana çok anlamsız geliyor, context-free yani) olmaması. Birazdan bunun ne anlama geldiğinden bahsedeceğim. lex programının Haskell karşılığı olan Alex için kod örnekleri vereceğim. Şu anda elimde çalışan bir derleyici olsa da, kaynak kodunu açmam için epey bir vakit var sanırım.

Çoğu ayrıştırıcı kütüphane/programlar aslında bağlam bağımsız gramerlerin bazı alt kümelerini ayrıştırabiliyor(yeterince esnek olanlarıyla bağlam bağımsız olmayan bazı örnekleri de çözümleyebiliyorsunuz, örneğin çözümleme aşamasında bazı durum değişkenleri tutarak). Örneğin aşağıdan yukarı(bottom-up) veya yukarıdan aşağı(top-down) bir yol izlemelerine göre, LL(n), LR(n), LALR, SLR, PEG(packrat çözümleyiciler) gibi. Genel olarak tüm bağlam bağımsız gramerleri(BNF şeklinde gösterilebildikleri sürece, ve tüm bağlam bağımsız gramerler BNF formunda gösterilebiliyorlar) çözümleyebilen algoritmalar olsa da(örneğin CYK, Unger algoritmaları), bu yöntemler zaman ve bazen bellek kullanımı açısından verimsiz olduklarındaın ve aslında programlama dilleri gramerlerinde çoğu zaman bağlam bağımsız gramerlerin bazı özelliklere sahip olabilen alt kümelerini kullandığımızdan, çözümleyiciler de bağlam-bağımsız gramerlerin çeşitli alt kümeleri üzerinde çalışıyorlar.

Bir dilin bağlam bağımsız olduğunu bağlam bağımsız bir gramerle ifade edilip edilemeyeceğinden anlıyoruz. Bağlam bağımsız gramerde şu anlama geliyor: tüm dönüşümler, A bir değişken ve a değişkenler ve terminaller dizisi olmak üzere, A -> a şeklinde olmalı. Dönüşümün sol tarafında sadece bir değişken oluyor yani. Bu aslında şu anlama geliyor: A gördüğümüz her yerde, herhangi bir başka duruma(yani _context_e) bakmaksızın dönüşümü yapabiliyorz. Bağlam bağımlı olma durumda ise örneğin şöyle oluyor: xAb -> xab. Burda Ayı dönüştürebilmek için, etrafını da kontrol etmemiz, yani durum/içerikten haberdar olmamız gerekiyor.

Peki indentation-based gramerlerle ne alakası var? Bu tip gramerleri kullanan bir dil düşünelim, Python veya YAML mesela. Bu dillerde bir blokun bittiğini anlamamız için, önceki satır hakkında bilgi sahibi olmamız gerekiyor. Örneğin bir önceki satırın kaç birim girintilenmiş olduğunu bilmemiz lazım. Eğer şu anda incelemdiğimiz satır ondan çok girintilenmişse, yeni bir blok başlangıcı, az girintilenmişse bir veya birde fazla blok bitişi anlamına geliyor.

Bu da indentation-based gramerleri bağlam bağımlı yapıyor. Yani şu anda kullanılan neredeyse hiçbir çözümleyici kütüphane/programla bunu ayrıştıramazsınız¹ Çoğu zaten tüm bağlam bağımsız gramerleri bile çözümleyemiyor.

İşin sırrı lexing aşamasında, satır satır girintilemeleri takip edip, satır başlarında ne kadar değişiklik olduğuna göre gerekli indent ve dedent tokenlarını oluşturmak. Çözümleme aşamasında yapamayıp, daha güçsüz olmasına rağmen(bkz. düzenli diller, DFA) lexing aşamasında bunu yapabilmemizin sebebi şu, çözümleme aşaması daha kompleks olduğundan, kütüphaneler kullanıcıya daha az imkan veriyor. Çoğunda BNF formuna yakın bir formda(dilin izin verdiği ölçüde, veya kimisi farklı bir formattan programlama diline derleme yapıyor, mesela Bison, ANTLR, bu yazıda bahsettiğim Happy) ifade edilmiş bağlam bağımlı gramerlerden direkt olarak parse tree oluşturuyor ve bu sürece çok fazla müdahele edemiyoruz. Lexing aşamasında bunu çözdüğümüzde çözümleme aşamasına bağlam bağımsız bir gramer ile çözümleyebileceğimiz bir dil sunmuş oluyoruz.

Algoritma şu: Tamamen boşluk karakterlerinden oluşmayan her satır için, eğer bir önceki satırdaki girintileme daha azsa, bir tane indent tokenı oluştur, eğer daha azsa, ne kadar daha az olduğuna göre, bir veya birkaç tane dedent tokenı oluştur. Bu tokenlar aslında { ve } kullanan dillerdeki bu karakterlerle tamamen aynı anlama geliyor yani(veya Pascal tarzı syntax kullanılıyorsa, begin/do ve end kelimeleri).

Alex’de bu işi şöyle yapıyorum(kodun sadece alakalı kısımlarını koyuyorum):

...
$whitespace = [\ \t\b]
...
\n $whitespace* \n { skip }
\n $whitespace*    { setIndent }
$whitespace+       { skip }
...

İkinci satır tamamen boşluklardan oluşan satırı hiç hesaba katmıyor. Üçüncü satır eğer satırda boşluklardan başka karakter varsa, girintilemeyi hesap ediyor ve gerekli işlemleri yapıyor(birazdan geleceğiz). 3. satır da satır içindeki normal boşluk karakterleri.

Bir önceki satırın girintileme sayısını tutmak istediğimizden, wrapper olarak monadUserState kullanmamız gerekiyor. Bu durumda Alex bir veri tipi ve veri tipi için bir başlangıç durumu istiyor:

data AlexUserState = AlexUserState { indent :: Int }
alexInitUserState :: AlexUserState
alexInitUserState = AlexUserState 0

Artık burda başka ne gibi durumlara ihtiyacınız varsa eklersiniz. Bu durum(state) üzerinde çalışmak için 2 tane yardımcı fonksiyon tanımlayacağım:

getLexerIndentLevel :: Alex Int
getLexerIndentLevel = Alex $ \s@AlexState{alex_ust=ust} -> Right (s, indent ust)
setLexerIndentLevel :: Int -> Alex ()
setLexerIndentLevel i = Alex $ \s@AlexState{alex_ust=ust} -> Right (s{alex_ust=(AlexUserState i)}, ())

Ne yaptıkları sanırım barizdir. Bu aşamadan sonra asıl işi setIndent fonksiyonu yapıyor. Bu fonksiyon İlk verdiğim kod parçasındaki regex ne zaman bir eşleşse, eşlesen karakter dizisi ile çağırılacak:

...
data LexemeClass
    ...
    | LTIndent Int
    | LTDedent Int
    | LIndent
    | LDedent
    ...
    deriving (Show, Eq)
...
setIndent :: AlexInput -> Int -> Alex Lexeme
setIndent input@(p, _, _, str) i = do
    --let !x = unsafePerformIO $ putStrLn str
    lastIndent <- getLexerIndentLevel
    currIndent <- countIndent (drop 1 str) 0 -- first char is always \n
    if (lastIndent < currIndent) then
        do setLexerIndentLevel currIndent
           mkL (LTIndent (currIndent - lastIndent)) input i
    else if (lastIndent > currIndent) then
        do setLexerIndentLevel currIndent
           mkL (LTDedent (lastIndent - currIndent)) input i
    else alexMonadScan
  where
    countIndent str total
        | take 1 str == "\t" = do skip input 1
                                  countIndent (drop 1 str) (total+1)
        | take 4 str == "    " = do skip input 4
                                    countIndent (drop 4 str) (total+1)
        | otherwise = return total

Burda bir problem, aslında bir eşleşmede birden fazla token oluşturamadığımızdan(Alex’in bir kısıtlaması, belki de bir yolu vardır ama ben bulamamışımdır), ben LTDedent adlı bir lexeme oluşturuyorum, burdaki T temporary, yani geçici anlamına geliyor. Çünkü daha sonra token listesinden bu elemanları silip başka tokenlar ekleyeceğim. Bu tokenların her biri ne kadar indent veya dedent olduğunu tutuyor. Yani örneğin bir önceki satıra göre 2 birim dışarı çıkmışsa, LTIndent 2 ile bir LexemeClass oluşturuyorum. Daha sonra bunu 2 ayrı LIndente dönüştürmeliyim ki, dilimin { ve } gibi karakterler kullanan dillerden hiçbir farkı kalmasın(bu arada şimdi farkettim, LTIndent diye bir sınıfa ihtiyacım yok, çünkü zaten bir önceki satırdan daha fazla girintilenmişse kesin olarak bir yeni blok oluşmuştur, bir ara düzeltirim artık :).

runAlex fonksiyonu yardımıyla Lexeme listesini elde ettikten sonra şu şekilde bu tokenları ayrı ayrı girintileme tokenları ile değiştiriyorum(kod tekrarı için kusura bakmayın :P )

addIndentations :: [Lexeme] -> [Lexeme]
-- ML style pattern matching for patterns with same cases or maybe view patterns
-- could be useful here
addIndentations (lex@(Lexeme pos (LTIndent c) _):ls) =
    concat [iter lex c, addIndentations ls]
  where iter lex c = if c == 0 then []
                     else (Lexeme pos LIndent Nothing):(iter lex (c-1))
addIndentations (lex@(Lexeme pos (LTDedent c) _):ls) =
    concat [iter lex c, addIndentations ls]
  where iter lex c = if c == 0 then []
                     else (Lexeme pos LDedent Nothing):(iter lex (c-1))
addIndentations (l:ls) = l:(addIndentations ls)
addIndentations [] = []

Ve böylece bağlam bağımlı bir grameri, lexing aşamasında basit bir hileyle bağlam bağımsız hale getirmiş oluyoruz. Indentation-based gramerlerde yapılabilecek en mantıklı iş bu gibi. Bağlam bağımlı gramerleri çözümlemek için bilinen çok iyi algoritmalar/kütüphaneler/programlar var ve bu iş lexing aşamasında çok kolay yapılabiliyor.

Değişik olduğunu düşündüğüm bir programlama dili üzerinde çalışıyorum, beklemede kalın :P .