Kanonik LR ayrıştırıcı - Canonical LR parser

İçinde bilgisayar Bilimi, bir standart LR ayrıştırıcı veya LR (1) ayrıştırıcı bir LR (k) ayrıştırıcı için k = 1, yani tek bir ileri bakmak terminal. Bu ayrıştırıcının özel özelliği, herhangi bir LR (k) dilbilgisinin k> 1 bir LR (1) dilbilgisine dönüştürülebilir.^[1] Bununla birlikte, k'yi azaltmak için geri ikameler gereklidir ve geri ikameler arttıkça, dilbilgisi hızla büyüyebilir, tekrarlanabilir ve anlaşılması zor olabilir. LR (k) hepsini işleyebilir belirleyici bağlamdan bağımsız diller.^[1] Geçmişte, bu LR (k) ayrıştırıcıdan, daha az güçlü alternatiflerin lehine olan büyük bellek gereksinimleri nedeniyle kaçınılmıştır. LALR ve LL (1) ayrıştırıcı. Ancak son zamanlarda, alan gereksinimleri LALR ayrıştırıcılarına yakın olan bir "minimum LR (1) ayrıştırıcı"^{[kaynak belirtilmeli ]}, birkaç ayrıştırıcı oluşturucu tarafından sunulmaktadır.

Çoğu ayrıştırıcı gibi, LR (1) ayrıştırıcısı otomatik olarak derleyici derleyiciler sevmek GNU Bizonu, MSTA, Menhir,^[2] HYACC,^[3].

Tarih

1965'te Donald Knuth LR (k) ayrıştırıcısını icat etti (Lsağa eft, Ren sağdaki türev ayrıştırıcı) bir tür shift-azaltma ayrıştırıcısı, var olanın bir genellemesi olarak öncelik ayrıştırıcıları. Bu ayrıştırıcı, tüm belirleyici bağlamdan bağımsız dilleri tanıma potansiyeline sahiptir ve girdi dosyasında karşılaşılan ifadelerin hem sol hem de sağ türevlerini üretebilir. Knuth, k = 1 için maksimum dil tanıma gücüne ulaştığını kanıtladı ve LR (k), k> 1 gramerlerini LR (1) gramerlerine dönüştürmek için bir yöntem sağladı.^[1]

Kanonik LR (1) ayrıştırıcıları, dahili ayrıştırıcı tablosu gösterimleri için muazzam bellek gereksinimlerine sahip olma pratik dezavantajına sahiptir. 1969'da Frank DeRemer, LR ayrıştırıcısının iki basitleştirilmiş sürümünü önerdi: LALR ve SLR. Bu ayrıştırıcılar, Canonical LR (1) ayrıştırıcılardan çok daha az bellek gerektirir, ancak biraz daha az dil tanıma gücüne sahiptir.^[4] LALR (1) ayrıştırıcıları, LR Ayrıştırıcının en yaygın uygulamaları olmuştur.

Ancak, yeni bir LR (1) ayrıştırıcı türü, bazıları "Minimal LR (1) ayrıştırıcı" olarak adlandırılır, 1977'de David Pager tarafından tanıtıldı^[5] bellek gereksinimleri LALR (1) ayrıştırıcılarınınkilerle rekabet eden LR (1) ayrıştırıcılarının oluşturulabileceğini gösteren kim. Son günlerde^{[ne zaman? ]}, bazı ayrıştırıcı üreteçleri, yalnızca bellek gereksinimi sorununu değil, aynı zamanda LALR (1) ayrıştırıcı üreteçlerinin doğasında bulunan gizemli çatışma sorununu da çözen Minimal LR (1) ayrıştırıcıları sunar.^{[kaynak belirtilmeli ]} Ek olarak, Minimal LR (1) ayrıştırıcıları vardiya-azaltma eylemlerini kullanabilir, bu da onları Canonical LR (1) ayrıştırıcılardan daha hızlı yapar.

Genel Bakış

LR (1) ayrıştırıcısı bir deterministik otomat ve bu nedenle operasyonu statik dayanmaktadır durum geçiş tabloları. Bunlar, tanıdığı dilin gramerini kodlar ve tipik olarak "ayrıştırma tabloları" olarak adlandırılır.

LR (1) ayrıştırıcısının ayrıştırma tabloları, bir önden okuma terminali ile parametrelendirilir. Tarafından kullanılanlar gibi basit ayrıştırma tabloları LR (0) ayrıştırıcı, formun gramer kurallarını temsil eder

A1 → A, B

bu demektir ki eyaletten gidersek Bir belirtmek B sonra eyalete gideceğiz A1^{[anlaşılmaz ]}. Böyle bir kuralı ileriye dönük parametrelendirdikten sonra elimizde:

A1 → A, B, a

bu, geçişin artık yalnızca önden okuma terminali a. Bu, basit bir kuralın ileri görme bağlamına bağlı olarak farklı anlamlara sahip olabileceği daha zengin dillere izin verir. Örneğin, bir LR (1) dilbilgisinde, aşağıdaki kuralların tümü, aynı durum dizisine dayanmasına rağmen farklı bir duruma geçiş yapar.

A1 → A, B, a

A2 → A, B, b

A3 → A, B, c

A4 → A, B, d

Bir ileri-geri terminali hesaba katılmasaydı aynı şey doğru olmazdı. Ayrıştırma hataları, bazı kuralları hata olarak bildirerek ayrıştırıcının tüm girdiyi okumasına gerek kalmadan belirlenebilir. Örneğin,

E1 → B, C, d

ayrıştırıcının durmasına neden olan bir hata ilan edilebilir. Bu, önden okuma bilgisinin aşağıdaki örnekte olduğu gibi hataları yakalamak için de kullanılabileceği anlamına gelir:

A1 → A, B, a

A1 → A, B, b

A1 → A, B, c

E1 → A, B, d

Bu durumda A, B, önden ilerleme a, b veya c olduğunda A1'e indirgenecek ve önden ilerleme d olduğunda bir hata rapor edilecektir.

Bakış açısı, bir kuralın ne zaman azaltılacağına karar vermede de yardımcı olabilir. Önden okuma, önden okuma geçerli değilse belirli bir kuralı azaltmaktan kaçınmaya yardımcı olabilir, bu da muhtemelen mevcut durumun önceki durum yerine aşağıdaki ile birleştirilmesi gerektiği anlamına gelir. Bu, aşağıdaki örnekte olduğu anlamına gelir

• Durum dizisi: A, B, C
• Kurallar:

A1 → A, B

A2 → B, C

durum dizisi,

A, A2

onun yerine

A1, C

ayrıştırıcı B durumuna geçtikten sonraki bakış kabul edilebilir değildi, yani hiçbir geçiş kuralı mevcut değildi. Durumlar doğrudan bir terminalden üretilebilir.

X → y

durum dizilerinin görünmesine izin verir.

LR (1) ayrıştırıcıları, her bir kuralın tam bir LR (1) şeklinde ifade edilmesi gerekliliğine sahiptir, yani belirli bir önden okuma ile iki durum dizisi. Bu gibi basit kurallar yapar

X → y

Tüm olası durumların kombinasyonlarını ve takip edebilecek ileri-geri uçlu terminalleri esasen numaralandıran çok sayıda yapay kural gerektirir. Benzer bir sorun, önceden olmayan kuralları uygulamak için ortaya çıkıyor.

A1 → A, B

tüm olası bakış açılarının numaralandırılması gereken yer. LR (1) ayrıştırıcılarının önemli bellek optimizasyonları olmadan pratik olarak uygulanamamasının nedeni budur.^[5]

LR (1) ayrıştırma tablolarının oluşturulması

LR (1) ayrıştırma tabloları şu şekilde oluşturulur: LR (0) ayrıştırma tabloları her birinin yaptığı değişiklik ile Öğe bir bakış içerir terminal. Bu, LR (0) ayrıştırıcılarının tersine, işlenecek öğenin ardından farklı bir uçbirim gelirse farklı bir eylemin yürütülebileceği anlamına gelir.

Ayrıştırıcı öğeler

İtibaren üretim kuralları bir dil için ilk önce bu dil için öğe kümeleri belirlenmelidir. Basit bir ifadeyle, bir ürün seti, şu anda işlenen sembolün parçası olabileceği üretim kuralları listesidir. Bir öğe kümesi, bir ayrıştırıcı durumuna bire bir karşılık gelirken, kümedeki öğeler, sonraki sembolle birlikte, hangi durum geçişlerinin ve ayrıştırıcı eyleminin uygulanacağına karar vermek için kullanılır. Her öğe, o anda işlenen sembolün, öğenin temsil ettiği kuralda hangi noktada göründüğünü not etmek için bir işaret içerir. LR (1) ayrıştırıcıları için, her öğe bir önden okuma terminaline özgüdür, bu nedenle önden okuma terminali de her öğenin içinde not edilmiştir.

Örneğin, 'n', '+', '(', ')' terminal sembolleri, 'E', 'T' terminal sembolleri, 'S' başlangıç ​​kuralı ve aşağıdaki üretim kurallarından oluşan bir dil varsayalım:

S → E

E → T

E → (E)

T → n

T → + T

T → T + n

Öğe kümeleri, LR (0) ayrıştırıcıları için prosedüre analog olarak üretilecektir. Başlangıç ​​durumunu temsil eden 0 öğe kümesi, başlangıç ​​kuralından oluşturulacaktır:

[S → • E, $]

Nokta '•', bu kural dahilinde mevcut ayrıştırma konumunun işaretini gösterir. Bu kuralı uygulamak için beklenen önden okuma terminali virgülden sonra belirtilir. "$" İşareti, başlangıç ​​kuralında olduğu gibi "girdi sonu" beklendiğini belirtmek için kullanılır.

Yine de bu, 0 öğesinin tamamı değildir. Her bir madde seti 'kapalı' olmalıdır, yani bir '•' sonrasındaki her bir non-terminal için tüm üretim kuralları, bu son olmayanların tümü ele alınana kadar, madde setine tekrar tekrar dahil edilmelidir. Ortaya çıkan öğe setine, başladığımız öğe setinin kapanışı denir.

Her bir üretim kuralı için LR (1) için, kuralı izleyen her olası önden okuma terminali için bir kalem dahil edilmelidir. Daha karmaşık diller için bu genellikle çok büyük öğe kümeleri ile sonuçlanır, bu da LR (1) ayrıştırıcılarının büyük bellek gereksinimlerinin nedenidir.

Örneğimizde, başlangıç ​​sembolü, terminal olmayan 'E'yi gerektirir ve bu da' T 'gerektirir, bu nedenle tüm üretim kuralları, öğe setinde 0 görünecektir. İlk başta, ön yüzleri bulma sorununu görmezden geliriz ve sadece durumuna bakarız. öğeleri ileri yönlü terminaller içermeyen bir LR (0). Yani 0 öğe kümesi (önden görünüm olmadan) şöyle görünecektir:

[S → • E]

[E → • T]

[E → • (E)]

[T → • n]

[T → • + T]

[T → • T + n]

İLK ve TAKİP setleri

İleriye dönük terminalleri belirlemek için, İLK ve İZLEME setleri kullanılır. İLK (A), bir Öğe I [A'nın terminal olmayan A ile eşleşen herhangi bir kural zincirinin ilk öğesi olarak görünebilen terminaller kümesidir [A → α • B β, x], hemen ardından görünebilen terminaller dizisidir. terminal olmayan B, burada α, β keyfi sembol dizeleridir ve x, gelişigüzel bir önden okuma terminalidir. İZLEME (k, B) bir öğe kümesi k ve bir terminal olmayan B, k içindeki tüm öğelerin aşağıdaki kümelerinin birleşimidir; burada '•' ve ardından B gelir. İLK kümeler, doğrudan tüm son olmayanların kapanışlarından belirlenebilir. İZLEME setleri ise İLK setlerin kullanım altındaki maddelerden belirlenir.

Örneğimizde, aşağıdaki öğe setlerinin tam listesinden doğrulanabileceği gibi, ilk setler şunlardır:

İLK (LER) = {n, '+', '('}

İLK (E) = {n, '+', '('}

İLK (T) = {n, '+'}

Önden okuma terminallerini belirleme

Öğe seti 0 içinde aşağıdaki setler bulunabilir:

TAKİP (0, S) = {$}

TAKİP ET (0, E) = {$, ')'}

TAKİP ET (0, T) = {$, '+', ')'}

Bundan, bir LR (1) ayrıştırıcısı için tam öğe kümesi 0, LR (0) öğesindeki her öğe için LHS olmayan terminalin takip eden setindeki her terminal için bir kopya oluşturarak oluşturulabilir. Aşağıdaki kümenin her bir öğesi, geçerli bir ileri yönlü terminal olabilir:

[S → • E, $]

[E → • T, $]

[E → • T,)]

[E → • (E), $]

[E → • (E),)]

[T → • n, $]

[T → • n, +]

[T → • n,)]

[T → • + T, $]

[T → • + T, +]

[T → • + T,)]

[T → • T + n, $]

[T → • T + n, +]

[T → • T + n,)]

Yeni eşya setleri oluşturma

Öğe setlerinin geri kalanı aşağıdaki algoritma ile oluşturulabilir

1. Halihazırda var olan her öğe setinde bir '•' den sonra görünen her bir terminal ve terminal olmayan sembol A için, m'ye tüm k kurallarını ekleyerek yeni bir öğe kümesi oluşturun, burada '•' A ile gelir, ancak yalnızca m, 3. adımdan sonra zaten var olan bir öğe setiyle aynı olmayacaktır.

2. yeni öğedeki her kural için tüm '•' leri kaydırın sağa bir simge ayarlayın

3. yeni öğe setinin kapanışını oluşturun

4. Yeni setler görünmeyene kadar tüm yeni oluşturulan öğe setleri için 1. adımdan itibaren tekrarlayın.

Örnekte, 0 numaralı öğe setinden, terminal dışı E için öğe seti 1'den, terminal n terminali için öğe seti 3'ten, '+' terminali için öğe seti 4'ten ve '(' .

Öğe seti 1 (E):

[S → E •, $]

Öğe seti 2 (T):

[E → T •, $]

[T → T • + n, $]

[T → T • + n, +]

·

·

·

Öğe seti 3 (n):

[T → n •, $]

[T → n •, +]

[T → n •,)]

Öğe grubu 4 ('+'):

[T → + • T, $]

[T → + • T, +]

[T → • n, $]

[T → • n, +]

[T → • + T, $]

[T → • + T, +]

[T → • T + n, $]

[T → • T + n, +]

·

·

·

Öğe grubu 5 ('('):

[E → (• E), $]

[E → • T,)]

[E → • (E),)]

[T → • n,)]

[T → • n, +]

[T → • + T,)]

[T → • + T, +]

[T → • T + n,)]

[T → • T + n, +]

·

·

·

Eşya setleri 2, 4 ve 5'ten birkaç eşya seti daha üretilecek. Tam liste oldukça uzundur ve bu nedenle burada belirtilmeyecektir. Bu dilbilgisinin ayrıntılı LR (k) işlemi, ör. içinde bulunmak [1].

Git

Bir LR (1) öğesinin önden görünüşü, yalnızca azaltma eylemleri düşünüldüğünde doğrudan kullanılır (yani, işaretçi sağ uçta olduğunda).

çekirdek LR (1) öğesinin [S → a A • B e, c] LR (0) öğesidir S → a A • B e. Farklı LR (1) öğeleri aynı çekirdeği paylaşabilir.

Örneğin, 2. öğe setinde

[E → T •, $]

[T → T • + n, $]

[T → T • + n, +]

ayrıştırıcı, bir sonraki simge '$' ise indirgeme [E → T] gerçekleştirmek, ancak sonraki simge '+' ise kaydırma yapmak gerekir. Bir LR (0) ayrıştırıcısının, yalnızca öğelerin özünü dikkate aldığından ve bu nedenle bir kayma / çatışmayı azaltma rapor edeceğinden bu kararı veremeyeceğini unutmayın.

[A → α • X β, a] içeren bir durum, X etiketli [A → α X • β, a] içeren bir duruma geçecektir.

Goto'ya göre her durumun geçişleri vardır.

Eylemleri değiştir

[A → α • b β, a] I durumunda ise_k ve ben_k I durumuna geçer_m b etiketiyle, sonra eylemi ekleriz

eylem [I_k, b] = "üst karakter m"

Eylemleri azaltın

[A → α •, a] I durumunda ise_ksonra eylemi ekliyoruz

eylem [I_k, a] = "A → α'yı azalt"

Referanslar

Dış bağlantılar

• Pratik LR (k) Ayrıştırıcı Yapı HTML sayfası, David Tribble
• Python'da (Narayana Chikkam) İlk ve Takip Setleri Yapımı