Basit LR ayrıştırıcı - Simple LR parser

Gelen bilgisayar bilimleri , bir Basit LR veya SLR ayrıştırıcı türüdür LR ayrıştırıcı küçük olan ayrıştırma tablolar ve nispeten basit bir ayrıştırıcı jeneratör algoritması. LR diğer türleri ile de (1) ayrıştırıcı, bir SLR ayrıştırıcı tek bir doğru bulmak oldukça etkilidir aşağıdan yukarı ayrıştırma varsayımları veya Backtracking olmadan giriş akışı üzerinde tek bir sol-sağ tarama. Ayrıştırıcı mekanik olarak dil için resmi bir dilbilgisi oluşturulur.

SLR ve daha genel yöntemler LALR ayrıştırıcı ve Kanonik LR ayrıştırıcı aynı yöntem ve ayrıştırma zamanda içindeki tablolar; onlar sadece ayrıştırıcı jeneratör aracı tarafından kullanılan matematiksel gramer analizi algoritmaları farklıdır. SLR ve LALR jeneratörler özdeş boyutu ve aynı ayrıştırıcı durumlarının tablolar oluşturun. SLR jeneratörleri gibi LALR jeneratörleri göre daha az sayıda dilbilgisi kabul yacc ve Bison . Olduğu gibi birçok bilgisayar dilleri kolayca, SLR kısıtlamalar uymaz. İçine dilin doğal dilbilgisi Bükme SLR dilbilgisibir şekilde daha fazla taviz ve gramer hackery gerektirir. Yani LALR jeneratörler çok daha yaygın hale biraz daha karmaşıktır araçları olmasına rağmen SLR jeneratörlere göre kullandık. SLR yöntemleri derleyici teorisi üzerine üniversite sınıflarında yararlı bir öğrenme aşaması kalır.

SLR ve LALR ikisi tarafından geliştirilmiştir Frank DeRemer ilk pratik kullanımları olarak Donald Knuth 'ın LR ayrıştırıcı teorisi. Tam LR yöntemlerle gerçek grammars için oluşturulan tablolar SLR ve LALR yöntemlerine göre daha 100 kat veya daha fazla ayrıştırıcı devletlerle, bu on yılın en çok bilgisayar anıları daha büyük, mümkün olamayacak kadar büyük olduğunu ..

lookahead setleri

SLR ve LALR arasındaki farkları anlamak için, onların birçok benzerlik anlamak önemlidir ve her ikisi yapmak nasıl karar vardiya-azaltır. (Makale Bkz LR ayrıştırıcı kadar azalmalara bölümünde yoluyla, o arka üzere hemen lookahead setleri .)

Bazı tamamlanan her onların jeneratörler sonraki görünmelidir girdi sembollerinin, bir ileri yönlü setleri hesaplamak nasıl SLR ve LALR arasındaki tek fark, üretim kuralı bulundu ve azalır.

SLR jeneratörleri bireysel ayrıştırıcı ve geçişler ayrıntılarını görmezden, gramer doğrudan esaslı kolay bir yaklaşım yöntemi ile bu lookahead hesaplayın. Bu, mevcut ayrıştırıcı durumunun özel bağlamını göz ardı eder. Bazı nonterminal sembol ise S dilbilgisi içinde çeşitli yerlerde kullanılır, SLR bunları tek tek ele ziyade aynı tek şekilde o yerleri davranır. SLR jeneratör dışarı çalışır Follow(S), hemen bazı oluşumunu takip edebilirsiniz tüm terminal semboller kümesini S . Ayrıştırma tablosunda, her bir indirgeme S (1) ileri yönlü ayarlanmış LR olarak Takip (S) kullanır. Böyle takip setleri de LL yukarıdan aşağıya ayrıştırıcıları için jeneratörler tarafından kullanılmaktadır. Hiçbir kayma / takip setleri kullanırken çatışmaları azaltmak / azaltmak veya azaltmak olan bir gramer bir denir SLR dilbilgisi .

LALR jeneratör ayrıştırıcı durumları ve geçişler grafik keşfetmek göre daha kesin bir yöntem ile ileriye dönük setleri hesaplar. Bu yöntem, mevcut ayrıştırıcı durumunun özel bağlamını dikkate alır. Bazı nonterminal S. bakınız makale her dilbilgisi oluşum işlenmesini özelleştirir LALR ayrıştırıcı bu hesaplamanın daha detaylı bilgi için. LALR jeneratörler ile hesaplanan lookahead setleri SLR jeneratörler ile hesaplanan yaklaşık setleri (ve dolayısıyla daha iyi) bir alt kümesidir. Bir gramer SLR setleri izleyin kullanırken tablo uyuşmazlığı olan fakat LALR setleri izleyin kullanırken çatışmasız ise, bir LALR dilbilgisi denir.

Örnek

SLR ayrıştırıcı tarafından değil, LR (0) çözümleyici ile çözümlenen -Gramer aşağıdaki gibidir:

(0) S → E
(1) e → 1 e
(2) E 1 →

LR için yapıldığı gibi eylem ve git tablo oluşturma (0) ayrıştırıcıları Aşağıdaki öğe setleri ve tablolar verecekti:

Ürün seti 0
S → • E
+ E → • 1 D
+ E → • 1
Ürün set 1
E → 1 • E
E → 1 •
+ E → • 1 D
+ E → • 1
Ürün set 2
S → E •
Ürün set 3
E → 1 e •

eylem ve git tablolar:

aksiyon git
belirtmek, bildirmek 1 $ E
0 s1 2
1 s1 / r2 r2 3
2 acc
3 r1 r1

Görüldüğü gibi 1 durumuna ve terminal için bir vites-azaltmak çakışma olup '1'. LR (0) çözümleyici için eylem tablosu oluşturulduğunda, eylemler satır başına bazında sokulur azaltmak için oluşur. Ancak, bir izleme seti kullanarak, azaltmak eylemleri daha hassas eklenebilir. Bu dilbilgisi için takip seti:

sembol S E 1
takip etme $ $ 1 $,

Bir o eylem olduğunu azaltmak ilişkili takip sette ise sadece belirli bir eylem sütuna eklenmesi gerekiyor azaltır. Bu algoritma, bir küçültme işlemi bir eylem kolonuna eklenmelidir olmadığını açıklar: 

function mustBeAdded(reduceAction, action) {
 ruleNumber = reduceAction.value;
 ruleSymbol = rules[ruleNumber].leftHandSide;
 return (action in followSet(ruleSymbol))
}

örneğin, mustBeAdded(r2, "1")kural 2 sol taraftaki "E" dir ve 1 E'nin takip kümesinde olmadığı için, yanlıştır. Tam tersine, mustBeAdded(r2, "$")"$" E'nin takip sette olduğu için, doğrudur.

her biri üzerinde mustBeAdded kullanarak eylem tablosundaki etkisini azalttığı olarak, sonuç çatışmasız bir eylem tablosu:

aksiyon git
belirtmek, bildirmek 1 $ E
0 s1 2
1 s1 r2 3
2 acc
3 r1

Ayrıca bakınız