Sözcüksel ve Sözdizimsel Analiz
Sözcüksel ve sözdizimsel analiz, bir derleyicinin ön ucunu oluşturarak kaynak metni belirteçlere (token) ayırmakta ve dilbilgisel yapısını bir ayrıştırma veya sözdizimi ağacı olarak tanımaktadır.
Tanım
Sözcüksel analiz, girdi karakterlerini belirteçler halinde gruplandıran aşamadır; sözdizimsel analiz (ayrıştırma) ise bu belirteçlerin bir dilbilgisine göre geçerli bir program oluşturup oluşturmadığını ve nasıl oluşturduğunu belirleyen, bir sözdizimi ağacı üreten aşamadır.
Kapsam
Bu konu, karakter akışlarını düzenli diller ve sonlu otomatlar kullanarak belirteçlere dönüştüren sözcüksel analizi ve bir programın cümle yapısını bağlamdan bağımsız bir dilbilgisine göre tanıyan sözdizimsel analizi (ayrıştırma) kapsamaktadır. Üstten aşağı (LL) ve alttan yukarı (LR) ayrıştırma, ayrıştırıcı üreteçleri, belirsizlik ve hata kurtarma ile soyut sözdizimi ağaçlarının oluşturulmasını içermektedir.
Temel sorular
- Düzenli ve bağlamdan bağımsız diller, program yapısını tanımlamak için nasıl kullanılmaktadır?
- LL ve LR ayrıştırma arasındaki avantaj ve dezavantajlar nelerdir?
- Belirsizlik ve ayrıştırma hataları nasıl tespit edilmekte ve ele alınmaktadır?
- Bir belirteç akışından soyut bir sözdizimi ağacı nasıl oluşturulmaktadır?
Temel kuramlar
- LR ayrıştırma
- Knuth, birçok ayrıştırıcı üretecinin temelini oluşturan, geniş LR dilbilgisi sınıfını doğrusal zamanda deterministik olarak ayrıştıran alttan yukarı bir teknik olan LR ayrıştırmayı tanıtmıştır.
- Genel bağlamdan bağımsız ayrıştırma
- Earley'nin algoritması, kısıtlı deterministik ayrıştırıcıların yetersiz kaldığı durumlarda genel bir yöntem sunarak, belirsiz olanlar da dahil olmak üzere keyfi bağlamdan bağımsız dilbilgilerini ayrıştırmaktadır.
- Ön ucun düzenli ve bağlamdan bağımsız temelleri
- Dragon Kitabı, tarama için düzenli ifadelerin ve sonlu otomatların, ayrıştırma için ise bağlamdan bağımsız dilbilgilerinin kullanımını, standart LL ve LR oluşturma algoritmaları da dahil olmak üzere sistematize etmektedir.
Klinik önem
Sözcüksel analiz (lexing) ve ayrıştırma (parsing), yalnızca derleyiciler için değil, aynı zamanda yorumlayıcılar, kod denetleyicileri (linters), biçimlendiriciler (formatters), entegre geliştirme ortamları (IDEs) ve veri formatı işlemcileri için de temel niteliktedir. İyi hata kurtarma özelliğine sahip sağlam bir ayrıştırma, herhangi bir dil aracının geliştirici deneyimi için kritik öneme sahiptir.
Tarihçe
Chomsky'nin 1950'lerin sonlarındaki biçimsel dil hiyerarşisi, düzenli ve bağlamdan bağımsız dillerin kuramını sağlamıştır. Knuth, 1965'te LR ayrıştırmayı biçimselleştirmiş ve Earley, 1970'te genel bir bağlamdan bağımsız algoritma sunmuştur. yacc gibi ayrıştırıcı üreteçleri, LR ayrıştırmayı pratik hale getirirken, sonraki çalışmalar ayrıştırma ifade dilbilgilerini (parsing expression grammars) ve kombinatör tabanlı ayrıştırıcıları araştırmıştır.
Tartışmalar
- Üretilmiş ayrıştırıcılar ile el yazımı ayrıştırıcılar
- Uygulayıcılar, özlü ve doğrulanabilir olan biçimsel dilbilgilerinden ayrıştırıcı üreteçleri kullanmayı, daha fazla kod maliyetiyle genellikle daha iyi hata mesajları ve kontrol sağlayan el yazımı özyinelemeli iniş ayrıştırıcılarına karşı tartışmaktadır.
Öne çıkan isimler
- Donald Knuth
- Jay Earley
- Alfred Aho
- Noam Chomsky
İlgili konular
Temel eserler
- knuth1965
- earley1970
- aho2006
Sıkça sorulan sorular
- Sözcüksel analizci (lexer) ile ayrıştırıcı (parser) arasındaki fark nedir?
- Bir sözcüksel analizci, ham karakterleri tanımlayıcılar ve operatörler gibi belirteçler halinde gruplandırırken, bir ayrıştırıcı bu belirteçleri dilin dilbilgisine göre hiyerarşik bir sözdizimi ağacında düzenlemektedir.
- LL ve LR ayrıştırma arasındaki fark nedir?
- LL ayrıştırıcılar üstten aşağı çalışarak girdi önekinden üretimleri tahmin ederken, LR ayrıştırıcılar alttan yukarı çalışarak tanınan alt dizgileri indirgemektedir; LR, kesinlikle daha geniş bir dilbilgisi sınıfını ele almaktadır ancak yapımı daha karmaşıktır.