Yantra, yerleşik lexer ve yukarıdan aşağı AST gezinme özellikleriyle C++'a LALR(1) ayrıştırmayı getiriyor

Yantra nedir

MIT lisansıyla yayınlanan, C++ ile yazılmış yeni bir parser üreteci olan Yantra, Hacker News'te paylaşıldı. LALR(1) ailesinden bir compiler-compiler olan proje, bir dil geliştiricisinin genellikle ayrı ayrı bir araya getirdiği üç parçayı tek pakette sunuyor: entegre bir lexer, parser'ın kendisi ve yerleşik tree walker'larla AST üretimi. Projenin yazarı Renji Panicker.

Projenin repository'sine göre Yantra, C++ standart kütüphanesi dışında hiçbir bağımlılığa ihtiyaç duymuyor. Düz bir CMake build'i üreteci çalıştırılabilir dosyayı, ycc'yi üretiyor; üretilen parser'lar clang, gcc ve MSVC dahil herhangi bir C++23 derleyicisiyle derlenebiliyor. Adı Sanskritçe "makine" anlamına geliyor; bu da tekniğin kalbindeki durum makinelerine bir gönderme.

Tek dilbilgisi, lexer dahil

Lexer UNICODE ve UTF-8 girdiyi destekliyor ve çok modlu; proje, bunun iç içe çok satırlı yorumlar gibi yapılar için yararlı olduğunu belirtiyor. Ayrıştırma ayrıca push tabanlı, lexer yönlendirmeli bir modda da çalışabiliyor: girdi bir seferde bir karakter okunuyor ve token'lar tamamlandıkça parser'a teslim ediliyor; bu da örneğin bir socket'ten gelen bir akışı geldiği anda işlemeye uygun.

Çıktı iki biçimde geliyor. İsteğe bağlı amalgamated modda tüm parser, çalışan bir main() fonksiyonuyla birlikte tek bir .cpp dosyası olarak üretiliyor; amalgamated olmayan moddaysa mevcut bir projeye eklenmeye uygun ayrı .hpp ve .cpp dosyaları üretiyor.

Aşağıdan yukarı ayrıştır, yukarıdan aşağı gez

Yantra'yı klasik araçlardan ayıran tasarım kararı, semantik eylemlerin ne zaman çalıştığı. Bison, Yacc ve Lemon — Yantra'nın beyan edilen ilham kaynağı SQLite'taki Lemon — eylemleri ayrıştırma sırasında, her kural indirgendiğinde aşağıdan yukarı çalıştırıyor. Yantra ise önce her zaman tam AST'yi oluşturuyor, ardından ayrı bir geçişte ağacı yukarıdan aşağı gezerek eylemlerinizi çağırıyor; böylece bir üst kuralın eylemi, alt kuralları ziyaret edilmeden önce çalışıyor.

Repository bunu bir hesap makinesi dilbilgisiyle örneklendiriyor: "1 + 2 + 3" için, (1 + 2) + 3 olarak sola birleşimli ayrıştırıldığında, önce kök düğümün eylemi tetikleniyor, sonra sol çocuğu, sonra da sağ alt ağaç. Elle yazılmış bir recursive-descent ya da aşağıdan yukarı parser, bu sıralamayı elde etmek için ek AST sınıflarına ve ayrı bir gezinme geçişine ihtiyaç duyardı; burada ise, projenin dediğine göre, bu doğrudan dilbilgisinden çıkıyor. Tek bir dilbilgisi ayrıca birden fazla walker tanımlayabiliyor; örneğin aynı ayrıştırma sonucundan biri C++, diğeri Java üreten iki walker. Bison ailesinden bu davranışlardan birini elde etmek, AST'yi ve walker'ı elle üstüne inşa etmek anlamına geliyor.

ANTLR ve tree-sitter ile karşılaştırma

Projenin dokümantasyonundaki karşılaştırma bölümü alışılmadık derecede dürüst. ANTLR da tamamen inşa edilmiş bir parse tree'yi geziyor, ama bu onun LL(*) algoritmasından doğal olarak geliyor. Yantra ise aynı yukarıdan aşağı gezinmeyi LALR(1) üzerinde sunuyor; LALR(1), ayrıştırma sırasında ağacın bütününün var olduğu bir anın bulunmadığı aşağıdan yukarı bir algoritma — üstelik projenin iddiasına göre LALR(1)'in zaman ve alan verimliliğini koruyarak. Yalnızca C++'ı hedefliyor ve üreteci yerel bir çalıştırılabilir dosya; ANTLR'ın üreteci ise bir Java programı, yani C++ projesi üreteci çalıştırmak için build araç zincirine bir JVM katmak zorunda kalıyor. Dokümantasyon, ANTLR'ın çok daha olgun ve yaygın kullanıldığını, Yantra'nın ise çok daha küçük, daha yeni, tek geliştiricili bir çaba olduğu konusunda açık sözlü. tree-sitter ise tamamen farklı bir sorun olarak bir kenara bırakılmış: editörler ve IDE'ler için artımlı, hataya toleranslı ayrıştırma; Yantra bunu denemiyor bile.

Ekosistem ve olgunluk

Çekirdek aracın çevresinde bağımsız bir örnek proje olan lingo ve Raj Chaudhuri tarafından yazılmış, Yantra sözdizimi vurgulamasını VS Code, Qt Creator ve Language Server Protocol'ü destekleyen diğer tüm IDE'lere getiren üçüncü taraf bir language server var. Repository ayrıca aracın henüz yapmadığı şeyleri kapsayan bir Known Limitations sayfasına bağlantı veriyor.

Neden önemli

C++'ta compiler ve DSL çalışması için mevcut yolların her biri bir sürtünme noktası taşıyor: Bison ailesi AST inşasını ve gezinmeyi size bırakıyor, ANTLR ise bir JVM bağımlılığı ve daha büyük bir runtime getiriyor. Yantra'nın vaadi şu: tek bir dilbilgisi, bağımlılıksız yerel bir araç tarafından üretilen lexer, parser, AST ve yukarıdan aşağı walker'lar veriyor. Bu, küçük dil projeleri için gerçek bir kolaylık. Tek bir geliştiricinin yazdığı erken dönem bir yazılım; dolayısıyla üzerine bir üretim compiler'ı bahse girecek olan herkes sınırlamalar listesini okumalı ve bus factor'ü tartmalı. Ama temel fikir — LALR(1) ayrıştırmanın üzerine katmanlanmış yukarıdan aşağı gezinme — C++ geliştiricileri için gerçek bir boşluğu dolduruyor.