Kanonik LR (1) ayrıştırıcı kapanışlarını belirlemek için geçiş kapanması için Warshall algoritması nasıl kullanılır?

Question

LR (1) kapanışlarını hızlı bir şekilde hesaplamak için Warshall algoritmasını uygulamaya çalışıyorum. Grafiğin

• düğümleri, LR items olan A → B • C
• gibi kenarları A → B • C den C → • D
başlayan "geçişler" şunlardır:

Ben I (0) o LR nasıl çalıştığını anlamak düşünmek

Sorun şu ki, LR (1) lookah hesaplarının hesaplanmasını gerektirir ve bunları algori'ye nasıl dahil edeceğimi anlayamıyorum thm.
'u bildiğim halde, herhangi bir LR öğesinin hala geçişinin geçici olarak kapatılması, sadece her bir öğe için hangi görünümün ayarlandığını bulmak için aynı hesaplamadan geçmesi gerekir.

Kanonik LR (1) kapaklarını hesaplamak için Warshall algoritmasını kullanmak mümkün mü, yoksa daha kısıtlı durumlarda (LR (0), SLR (1), vb.) Mümkün mü?

Answer 1

Bunun için Warshall algoritmasını kullanabileceğinizi düşünmüyorum, çünkü yeni bir öğe eklediğinizde, başka öğeler eklemeniz gerekebilir. Bu yinelenen bir süreç. Yönlendirilmiş grafik veya bağlantı matrisi değişmeye devam edecektir. Bu konuda yanlış olabilirim. LR (1) kalem setinin kapanmasını yinelemeli bir işlemle hesapladım ve bu sayede kapama setine zaten dahil olan bir dizi ürün tutuldu. Benim LRSTAR Parser Generator'u indirebilir ve isterseniz kaynak koduna bakabilirsiniz. Kendi çözümleyici üretecinizi yazmanıza ve LRSTAR kullanmanıza gerek olmayacağına karar verebilirsiniz. Not: İleriye dönük setlerin hesaplanması için Warshall algoritmaları yerine DeRemer'in kağıdındaki Digraph algoritmasını kullandım. list of papers implemented in LRSTAR on the website'a bakın.