Basit LR ayrıştırıcı - Simple LR parser
 | Bu makale değil anmak hiç kaynaklar. (Aralık 2012) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin) |
İçinde bilgisayar Bilimi, bir Basit LR veya SLR ayrıştırıcı bir tür LR ayrıştırıcı küçük ile tabloları ayrıştır ve nispeten basit bir ayrıştırıcı üretici algoritması. Diğer LR (1) ayrıştırıcı türlerinde olduğu gibi, bir SLR ayrıştırıcısı, tek doğru olanı bulmada oldukça etkilidir. aşağıdan yukarıya ayrıştırma giriş akışı üzerinden tek bir soldan sağa taramada, varsayım veya geriye dönük izleme olmaksızın. Ayrıştırıcı, dil için biçimsel bir gramerden mekanik olarak oluşturulur.
SLR ve daha genel yöntemler LALR ayrıştırıcı ve Kanonik LR ayrıştırıcı ayrıştırma zamanında aynı yöntemlere ve benzer tablolara sahip olmak; bunlar yalnızca ayrıştırıcı oluşturma aracı tarafından kullanılan matematiksel gramer analizi algoritmalarında farklılık gösterir. SLR ve LALR üreteçleri, aynı boyutta ve özdeş ayrıştırıcı durumlarında tablolar oluşturur. SLR üreteçleri, LALR üreteçlerinden daha az gramer kabul eder. yacc ve Bizon. Birçok bilgisayar dili, SLR'nin kısıtlamalarına olduğu gibi hemen uymuyor. Dilin doğal gramerini SLR dilbilgisi form daha fazla uzlaşma ve gramer korsanlığı gerektirir. Bu nedenle, LALR jeneratörleri, biraz daha karmaşık araçlar olmalarına rağmen, SLR üreticilerinden çok daha yaygın bir şekilde kullanılmaktadır. SLR yöntemleri, derleyici teorisindeki üniversite derslerinde yararlı bir öğrenme adımı olmaya devam etmektedir.
SLR ve LALR, Frank DeRemer ilk pratik kullanımları olarak Donald Knuth LR ayrıştırıcı teorisi.[kaynak belirtilmeli ] Tam LR yöntemleriyle gerçek gramerler için oluşturulan tablolar, SLR ve LALR yöntemlerinden 100 kat veya daha fazla ayrıştırıcı durumuyla, o on yılın çoğu bilgisayar belleğinden daha büyük, pratik olmayan bir şekilde büyüktü.[kaynak belirtilmeli ].
Önden Görünüm setleri
SLR ve LALR arasındaki farkları anlamak için, birçok benzerliklerini ve her ikisinin de vardiya azaltma kararlarını nasıl aldıklarını anlamak önemlidir. (Makaleye bakın LR ayrıştırıcı şimdi o arka plan için, indirimlerle ilgili bölüme bakın ' ileri görüşlü setler.)
SLR ve LALR arasındaki tek fark, jeneratörlerin, ne zaman tamamlandığında, daha sonra görünmesi gereken ileri doğru giriş sembollerini nasıl hesapladıklarıdır. üretim kuralı bulunur ve azaltılır.
SLR üreteçleri, tek tek ayrıştırıcı durumlarının ve geçişlerinin ayrıntılarını görmezden gelerek, doğrudan dilbilgisine dayalı kolay bir yaklaşım yöntemiyle bu bakışı hesaplar. Bu, mevcut ayrıştırıcı durumunun belirli bağlamını göz ardı eder. Bazı terminal olmayan semboller S Dilbilgisinin birçok yerinde kullanıldığı için, SLR bu yerleri ayrı ayrı ele almak yerine aynı tek şekilde ele alır. SLR üreteci çalışıyor Takip et (S), bazı oluşumlarını hemen takip edebilen tüm terminal sembollerinin kümesi S. Ayrıştırma tablosunda, her indirgeme S Follow (S) 'yi LR (1) önden okuma seti olarak kullanır. Bu tür takip kümeleri ayrıca LL yukarıdan aşağı ayrıştırıcılar için üreteçler tarafından kullanılır. Aşağıdaki kümeleri kullanırken çatışmaları değiştirmeyen / azaltmayan veya azaltan / azaltan bir dilbilgisine SLR dilbilgisi.
LALR üreteçleri, önden okuma kümelerini ayrıştırıcı durumlarının grafiğini ve geçişlerini keşfetmeye dayalı daha kesin bir yöntemle hesaplar. Bu yöntem, mevcut ayrıştırıcı durumunun belirli bağlamını dikkate alır. Bazı terminal dışı S'lerin her gramer oluşumunun işlenmesini özelleştirir. Makaleye bakın. LALR ayrıştırıcı bu hesaplamanın diğer ayrıntıları için. LALR oluşturucuları tarafından hesaplanan önden okuma kümeleri, SLR üreteçleri tarafından hesaplanan yaklaşık kümelerin bir alt kümesidir (ve dolayısıyla onlardan daha iyidir). Bir dilbilgisinin SLR izleme kümelerini kullanırken tablo çakışmaları varsa, ancak LALR izleme kümelerini kullanırken çelişki içermiyorsa, buna LALR dilbilgisi denir.
Misal
Bir SLR ayrıştırıcısı tarafından ayrıştırılabilen ancak bir LR (0) ayrıştırıcısı tarafından ayrıştırılamayan bir dilbilgisi aşağıdaki gibidir:
- (0) S → E
- (1) E → 1 E
- (2) E → 1
Eylem ve goto tablosunun LR (0) ayrıştırıcıları için yapıldığı gibi yapılandırılması, aşağıdaki öğe kümelerini ve tablolarını verecektir:
- Öğe seti 0
- S → • E
- + E → • 1 E
- + E → • 1
- Öğe seti 1
- E → 1 • E
- E → 1 •
- + E → • 1 E
- + E → • 1
- Öğe seti 2
- S → E •
- Öğe seti 3
- E → 1 E •
Eylem ve tablolara git:
| aksiyon | git | ||
|---|---|---|---|
| durum | 1 | $ | E |
| 0 | s1 | 2 | |
| 1 | s1 / r2 | r2 | 3 |
| 2 | acc | ||
| 3 | r1 | r1 | |
Görülebileceği gibi, durum 1 ve terminal '1' için bir kaydırma-azaltma çakışması vardır. Bunun nedeni, bir LR (0) ayrıştırıcısı için eylem tablosu oluşturulduğunda, azaltma eylemlerinin her satıra göre eklenmesidir. Ancak, bir takip kümesi kullanılarak azaltma eylemleri daha ince ayrıntıyla eklenebilir. Bu dilbilgisi için aşağıdaki set:
| sembol | S | E | 1 |
|---|---|---|---|
| takip etme | $ | $ | 1,$ |
Bir azaltmanın yalnızca belirli bir eylem sütununa eklenmesi gerekir, eğer söz konusu eylem bu azaltmayla ilişkili takip kümesindeyse. Bu algoritma, bir eylem sütununa bir azaltma eyleminin eklenmesi gerekip gerekmediğini açıklar:
function mustBeAdded (lessAction, action) {ruleNumber = lessAction.value; ruleSymbol = kurallar [kuralNumarası] .leftHandSide; return (followSet (kuralSimbol) içindeki eylem)}Örneğin, mustBe added (r2; "1") yanlıştır, çünkü 2. kuralın sol tarafı "E" dir ve 1, E'nin takip kümesinde değildir. mustBe added (r2, "$") doğrudur, çünkü "$" E'nin follow setindedir.
Eylem tablosundaki her bir azaltma eyleminde mustBe Added'i kullanarak, sonuç, çatışmasız bir eylem tablosudur:
| aksiyon | git | ||
|---|---|---|---|
| durum | 1 | $ | E |
| 0 | s1 | 2 | |
| 1 | s1 | r2 | 3 |
| 2 | acc | ||
| 3 | r1 | ||