Büyük Dil Modelleri için Verimli Kılavuzlu Oluşturma: Yinelemeli Ayrıştırmanın Uzantıları

Bağlantı Tablosu

• Özet ve Giriş
• LLM Örnekleme ve Kılavuzlu Üretim
• Yinelemeli FSM İşleme ve İndeksleme
• Yinelemeli Ayrıştırma Uzantıları
• Tartışma, Referanslar ve Teşekkür

4. Yinelemeli Ayrıştırmanın Uzantıları

Bu bölümde, odak noktamızı genel ayrıştırıcı kılavuzlu nesile kaydırıyoruz ve CFG olarak sağlanan Python benzeri bir dilbilgisi için basit bir gözden geçirme ile başlıyoruz.

Örtülü bir CFG'ye göre Python benzeri sözdizimi üretmek için birleştirilebilecek "d" ve "ef" gibi dizelerden oluşan bir kelime dağarcığını düşünün ve bu dizelerin Algoritma 1 gibi bir sürece göre sıralı olarak örneklendiğini ve birleştirildiğini varsayalım.

Ayrıca, CFG'de "def" dizisine karşılık gelen ve önemsiz düzenli def ifadesi tarafından verilen bir terminal sembolü DEF'yi düşünün. Ayrıca, [^\W\d]\w* normal ifadesi (örn. Python tanımlayıcıları) tarafından verilen bir İSİM sembolünü düşünün. Yukarıda belirtilen sözcük dağarcığından örneklenen dizeleri Python sözdizimine uyacak şekilde sırayla ayrıştırmak istiyoruz.

Örneğin, aşağıdakiler böyle bir dizi olabilir: ["d", "ef", " f", "oo(", "):", " ", "pass"]. Dizinin tüm unsurları tanım gereği kelime dağarcığının unsurlarıdır. Dizinin birleştirilmesi, bir işlevi tanımlayan geçerli bir belirteç dizisi olan "def foo(): pass" değerini üretir. Düşündüğümüz durumda, belli bir noktaya kadar tüm tokenleri gözlemlemiş olacağız ve o noktadan sonra olanlar hakkında hiçbir şey bilmiyoruz.

Örneğin, örnek dizideki üçüncü gözlemde, birleştirilmiş "def f" dizesine sahibiz. Bu dizeyi lex/ayrıştıracak olsaydık, geleneksel bir yaklaşım, "f"yi tam bir NAME belirteci olarak yanlış tanımlayan DEF NAME sembol dizisini döndürürdü. Sıranın geri kalanından da görebileceğimiz gibi doğru NAME belirteci "foo" olacaktır.

Genel olarak, sözcük dağarcığından örneklenebilecek bir sonraki geçerli dizeler,

1. şu anda "f" ile başlayan İSİM'i genişletmeye/ilerletmeye devam edin (örneğimizdeki tam dizide olduğu gibi) ve/veya

   
   

2. "(" ile başlayan herhangi bir şey –yani normal ifadeye sahip bir LPAR sembolü (–ve geçerli bir argüman imzası belirtmeye devam eder.

İlk durumda, "f" Python'da kısmen eşleşen bir İSİM sembolü olarak görülebilir ve düzenli ifadesinin [^\W\d]\w* olduğunu hatırlayarak her iki alt kalıpla da eşleştiğini söyleyebiliriz. (yani [^\W\d] ve \w*) normal ifadede. FSM'leri kullanmamız, FSM'nin durumları aracılığıyla alt modeller kavramını resmileştirir. Bu durumda, NAME için normal ifade, üç duruma sahip bir FSM, M ile temsil edilebilir: 0 (yani başlangıç durumu q0), 1 (yani [^\W\d]) ve 2 (yani \w*) , burada 1, 2 ∈ F.

Algoritma 3'ü kullanarak, "f" için FSM durum dizilerini (0, 1), (1, 2), (2, 2) ve İSİM sembolüne karşılık gelen FSM, M'yi elde ederiz. "F" için olan bu FSM dizileri bize, bu kelime dizisi için eşleştirmenin 0, 1 veya 2 durumlarında başlayabileceğini ve 1 veya 2 durumlarında bitebileceğini söyler.

Yukarıdaki durum 1.'e göre, ayrıştırma, İSİM sembolü için, önceden durum 1 veya 2'de sonlandıktan sonra devam ettirilebilir. Durum 2.'ye göre, bir sonraki dize aynı zamanda bir LPAR ile başlayabilir veya bir LPAR içerebilir; bu da M'nin sona ereceğini ima eder. 1 ve 2'nin, "f" okunduktan sonra ayrıştırmanın duracağı M'deki son durumlar olduğu verilebilir. M'nin sonlandırılması aynı zamanda bir NAME sembolünün tamamlandığını ve dilbilgisi tarafından LPAR'ı kabul eden bir duruma geçişe izin verildiğini de gösterir.

Bu çizimde, bir sonraki geçerli sözcük dizeleri en azından "d", "ef", "pass", " ", "oo("'dur, çünkü bu dizelerin tümü kısmen eşleşen NAME'i genişletecektir ve sonuncusu da aynı zamanda ayrıştırma durumunu LPAR okuyan bir dizeye ilerletin. Düşündüğümüz sözcük dağarcığının alt kümesinden kalan "):" dizesi, geçersiz sözdizimine sahip bir diziyle sonuçlanacaktır.

FSM indeksleme yaklaşımıyla ilgili olarak bu, Algoritma 4'ün FSM durumlarını 0, 1 ve 2'yi NAME sembolü için "d", "ef", "pass", " ", "oo(" alt kümesiyle eşleyeceği anlamına gelir ve FSM, M.

Bu çizimde hangi dilbilgisi simgelerine ve geçişlere izin verildiğini belirleyen temel ayrıştırıcı durumları atlanmıştır. FSM yaklaşımını genişletmek ve kalan ayrıntıları ele almak için aşağı açılan otomatları (PDA) kullanıyoruz.

4.1 Aşağı Açılan Otomata Formülasyonu

Aşağı açılan otomatları aşağıdaki 6'lı demet gösterimini kullanarak tanımlarız [Sipser, 1996, Tanım 2.13]:

PDA güdümlü bir ayrıştırıcı için bir indeksleme yaklaşımı oluşturmak amacıyla, bir CFG'nin sembolleri arasındaki bağlantıyı (karşılık gelen bir PDA'nın alfabesi aracılığıyla) ve bir PDA tarafından okunan sembolleri üreten sözcük oluşturma ve tarama adımları arasındaki bağlantıyı kullanmamız gerekir.

Daha spesifik olarak, Bölüm 4'te dolaylı olarak gösterdiğimiz gibi ayrıştırıcılar, bir dizi karakter girişinden sembolleri tanımlayan sözcük oluşturucular ve tarayıcılar tarafından desteklenir. İzin verilen sembol ve yığın geçişlerine dayalı olarak her ayrıştırma/PDA durumu için terminal simgelerinin sıralı listeleri oluşturulabilir. her durumdaki δ haritasına göre. Bu, durum tarafından okunan terminal sembollerine karşılık gelen her FSM'nin birleşimi olan her ayrıştırma durumu için bir FSM oluşturabileceğimiz anlamına gelir.

Daha sonra bir tarama adımı, ayrıştırma işleminde tam olarak tanımlanan son sembolden bu yana okunan karakterler için bir dizi olası terminal sembolü V ⊂ Σ tanımlayacaktır. Örneğin, Bölüm 4'teki Python benzeri CFG için bir PDA'nın başlangıç durumu q0'da, "de" dizgesinin taranması ve sözlüklenmesi V = {DEF, NAME} ile sonuçlanacaktır: yani "def" dizgesini tamamlayan herhangi bir sözcük dizgesi için DEF –ardından aynı zamanda NAME FSM tarafından okunmayan bir dize gelir (ör. "def")– ve FSM'si tarafından okunan diğer dizeler için NAME (ör. "varsayılan"). Tarayıcının adımlarının ve LLM'nin örnekleme adımlarının, tek bir terminal sembolü v ∈ V belirlenene kadar sonunda V setini azaltacağını unutmayın.

Her ayrıştırma durumu için birleştirilmiş FSM'leri kullanarak V'deki her diziye Algoritma 3'ü uygulayarak, PDA durumlarından, karşılık gelen FSM durumlarından ve potansiyel terminal sembollerinden oluşan ayrıştırıcı konfigürasyonlarını belirleyebiliriz.

Algoritma 3'teki adımlara benzer şekilde, PDA'nın geçiş haritasının ön görüntüsünü, bir ayrıştırıcı konfigürasyonunun PDA durumlarını q ∈ Q ve terminal sembol kümelerini V okuyacak PDA yığın değerlerini belirlemek için kullanabiliriz:

Bu harita tarafından sağlanan yığın değerleri, olası ayrıştırıcı yapılandırmalarından başlayarak V'deki her dizenin başarılı ve eksiksiz ayrıştırılmasına olanak tanıyan PDA boyunca (varsa) yolları bulmak için gereklidir. Bir LALR(1) ayrıştırıcısının REDUCE işlemlerine karşılık gelen ayrıştırıcı durumu ve terminal birleşimleri için, bu ayrıştırıcı konfigürasyonları Γ'deki yığının tepe değerlerinden daha fazlasını içerecektir; bir kelime dizisinin gerektirdiği REDUCE işlemleri için tüm geçerli öneklere karşılık gelen alt yığınlardan oluşacaktır. Sonuçta, bir sözcük dizisinin tam olarak ayrıştırılmasına izin veren her ayrıştırıcı konfigürasyonu, PDA'nın indeksine bir giriş olarak eklenir ve bu durumda, ayrıştırıcının veri yapısına karşı sorgulara izin vermek için indeksin bir trie veri yapısı olması gerekecektir. yığın değerleri.