Earley ayrıştırıcı - Earley parser

Gelen bilgisayar bilimleri , Earley ayrıştırıcı bir olan algoritma için ayrıştırma dizeleri belirli bir aittir bağlam serbest dili olsa da, bazı null grammars ile ilgili sorunlar ortaya çıkabilir (tipe bağlı olarak). Adını mucidi Jay Earley'den alan algoritma, dinamik programlamayı kullanan bir grafik ayrıştırıcıdır ; esas olarak hesaplamalı dilbilimde ayrıştırma için kullanılır . İlk olarak 1968'deki tezinde tanıtıldı (ve daha sonra bir dergide kısaltılmış, daha okunaklı bir biçimde ortaya çıktı).

Earley ayrıştırıcıları, derleyicilerde daha tipik olarak kullanılan ancak yalnızca sınırlı dil sınıflarını işleyebilen LR ayrıştırıcıları ve LL ayrıştırıcılarının aksine, bağlamdan bağımsız tüm dilleri ayrıştırabildikleri için çekicidir . Earley ayrıştırıcısı , n'nin ayrıştırılan dizenin uzunluğu, belirsiz olmayan dilbilgileri için ikinci dereceden zaman ve tüm deterministik bağlamdan bağımsız dilbilgisi için doğrusal zaman olduğu genel durumda kübik zamanda yürütülür . Kurallar sola özyinelemeli olarak yazıldığında özellikle iyi performans gösterir . ${\görüntüleme stili {O}(n^{3})}$ ${\ Displaystyle {O}(n^{2})}$

Earley tanıyıcı

Aşağıdaki algoritma Earley tanıyıcıyı açıklar. Tanıyıcı, tanıdığı gibi bir ayrıştırma ağacı oluşturmak için kolayca değiştirilebilir ve bu şekilde bir ayrıştırıcıya dönüştürülebilir.

algoritma

Aşağıdaki tariflerde, α, β, ve herhangi birini temsil y dize ve terminallerine / nonterminallerdir (dahil boş dizge ), X ve Y, bir tek nonterminallerin temsil eder ve bir terminal sembolü temsil eder.

Earley'in algoritması yukarıdan aşağıya bir dinamik programlama algoritmasıdır. Aşağıda, Earley'nin nokta gösterimini kullanıyoruz: bir X → αβ üretimi verildiğinde, X → α • β gösterimi, α'nın zaten ayrıştırıldığı ve β'nın beklendiği bir durumu temsil eder.

Giriş konumu 0, girişten önceki konumdur. Giriş konumu N kabul ettikten sonra pozisyondur n inci belirteç. (Gayrı resmi olarak, giriş konumları belirteç sınırlarındaki konumlar olarak düşünülebilir .) Her giriş konumu için ayrıştırıcı bir durum kümesi oluşturur . Her durum, aşağıdakilerden oluşan bir tanımlama grubudur (X → α • β, i ).

• şu anda eşleşen üretim (X → α β)
• o üretimdeki mevcut konum (nokta ile gösterilir)
• bu üretimin eşleşmesinin başladığı girdideki i konumu : başlangıç ​​konumu

(Earley'nin orijinal algoritması, duruma ileriye dönük bir bakış içeriyordu; daha sonraki araştırmalar bunun ayrıştırma verimliliği üzerinde çok az pratik etkisi olduğunu gösterdi ve daha sonra çoğu uygulamadan çıkarıldı.)

k giriş konumunda ayarlanan duruma S( k ) adı verilir . Ayrıştırıcı, yalnızca üst düzey kuraldan oluşan S(0) ile tohumlanır. Ayrıştırıcı daha sonra art arda üç işlemi yürütür: tahmin , tarama ve tamamlama .

• Tahmin : (X → α • Y β, j ) formunun S( k ) içindeki her durumu için (burada j yukarıdaki gibi başlangıç ​​konumudur), her biri için S( k )' ye (Y → • γ, k ) ekleyin. sol tarafta Y ile dilbilgisinde üretim (Y → γ).
• Tarama : Eğer bir giriş akışı bir sonraki sembol S (her durum için, bir K formu) (X → α • bir β, j ), eklenti (X → α bir • β, j S) ( k +1).
• Tamamlama : (Y → γ •, j ) formunun S( k ) içindeki her durumu için (X → α • Y β, i ) formunun S( j ) içindeki tüm durumları bulun ve (X → α Y) ekleyin • β, i ) ila S( k ).

Durum kümesine yinelenen durumlar eklenmez, yalnızca yenileri eklenir. Bu üç işlem, kümeye yeni durum eklenemeyecek duruma gelene kadar tekrarlanır. Küme genellikle, ne tür bir durum olduğuna bağlı olarak gerçekleştirilecek işlemle birlikte işlenecek bir durum sırası olarak uygulanır.

Algoritma, (X → γ •, 0) S( n ) ile biterse kabul eder , burada (X → γ) üst düzey kural ve n giriş uzunluğudur, aksi halde reddeder.

sözde kod

Daniel Jurafsky ve James H. Martin tarafından Speech and Language Processing'den uyarlanmıştır ,

DECLARE ARRAY S;

function INIT(words)
    S ← CREATE_ARRAY(LENGTH(words) + 1)
    for k ← from 0 to LENGTH(words) do
        S[k] ← EMPTY_ORDERED_SET

function EARLEY_PARSE(words, grammar)
    INIT(words)
    ADD_TO_SET((γ → •S, 0), S[0])
    for k ← from 0 to LENGTH(words) do
        for each state in S[k] do  // S[k] can expand during this loop
            if not FINISHED(state) then
                if NEXT_ELEMENT_OF(state) is a nonterminal then
                    PREDICTOR(state, k, grammar)         // non_terminal
                else do
                    SCANNER(state, k, words)             // terminal
            else do
                COMPLETER(state, k)
        end
    end
    return chart

procedure PREDICTOR((A → α•Bβ, j), k, grammar)
    for each (B → γ) in GRAMMAR_RULES_FOR(B, grammar) do
        ADD_TO_SET((B → •γ, k), S[k])
    end

procedure SCANNER((A → α•aβ, j), k, words)
    if a ⊂ PARTS_OF_SPEECH(words[k]) then
        ADD_TO_SET((A → αa•β, j), S[k+1])
    end

procedure COMPLETER((B → γ•, x), k)
    for each (A → α•Bβ, j) in S[x] do
        ADD_TO_SET((A → αB•β, j), S[k])
    end

Örnek

Aritmetik ifadeler için aşağıdaki basit dilbilgisini göz önünde bulundurun:

<P> ::= <S>      # the start rule
<S> ::= <S> "+" <M> | <M>
<M> ::= <M> "*" <T> | <T>
<T> ::= "1" | "2" | "3" | "4"

Giriş ile:

2 + 3 * 4

Bu durum kümelerinin sırasıdır:

Durum (P → S •, 0) tamamlanmış bir ayrıştırmayı temsil eder. Bu durum, tam cümleler olan S(3) ve S(1)'de de görülür.

Ayrıştırma ormanı oluşturma

Earley'in tezi, bir Earley öğesindeki her bir terminal olmayandan, tanınmasına neden olan öğelere bir dizi işaretçi ekleyerek ayrıştırma ağaçları oluşturmaya yönelik bir algoritmayı kısaca açıklar. Ancak Tomita , bunun semboller arasındaki ilişkileri hesaba katmadığını fark etti, bu yüzden dilbilgisini düşünürsek S → SS | b ve bbb dizesi, yalnızca her S'nin bir veya iki b ile eşleşebileceğini ve böylece bb ve bbbb için sahte türevler ve bbb için iki doğru türev ürettiğini not eder.

Diğer bir yöntem, her Earley öğesini, üçlü (s, i, j) ile etiketlenmiş bir paylaşılan paketlenmiş ayrıştırma ormanı (SPPF) düğümüne bir işaretçi ile artırarak, ilerledikçe ayrıştırma ormanı oluşturmaktır; burada s bir sembol veya bir LR(0'dır). ) öğe (noktalı üretim kuralı) ve i ve j, bu düğüm tarafından türetilen girdi dizesinin bölümünü verir. Bir düğümün içeriği ya tek bir türetme veren bir çift alt işaretçi ya da her biri bir türetmeyi temsil eden bir çift işaretçi içeren "paketlenmiş" düğümlerin bir listesidir. SPPF düğümleri benzersizdir (belirli bir etikete sahip yalnızca bir tane vardır), ancak belirsiz ayrıştırmalar için birden fazla türetme içerebilir . Bu nedenle, bir işlem bir Earley öğesi eklemese bile (çünkü zaten var), öğenin ayrıştırma ormanına yine de bir türetme ekleyebilir.

• Öngörülen öğelerin boş bir SPPF işaretçisi var.
• Tarayıcı, taradığı terminal olmayanı temsil eden bir SPPF düğümü oluşturur.
• Ardından, tarayıcı veya tamamlayıcı bir öğeyi ilerlettiğinde, çocukları noktası ilerletilen öğeden düğüm olan bir türetme ve üzerinde ilerletilen yeni sembolün (terminal olmayan veya tamamlanmış öğe) türevini eklerler.

SPPF düğümleri hiçbir zaman tamamlanmış bir LR(0) öğesiyle etiketlenmezler: bunun yerine üretilen sembolle etiketlenirler, böylece hangi alternatif üretimden geldiklerine bakılmaksızın tüm türevler tek bir düğüm altında birleştirilir.

Optimizasyonlar

Philippe McLean ve R. Nigel Horspool, "A Faster Earley Ayrıştırıcı" adlı makalelerinde, Earley ayrıştırmayı LR ayrıştırma ile birleştirir ve büyüklük sırasına göre bir gelişme sağlar.

Ayrıca bakınız

• CYK algoritması
• Bağlamdan bağımsız dilbilgisi
• Ayrıştırma algoritmaları

alıntılar

Diğer referans malzemeleri

• Aycock, John; Horspool, R. Nigel (2002). "Pratik Earley Ayrıştırma". Bilgisayar Dergisi . 45 (6): 620–630. CiteSeerX  10.1.1.12.4254 . doi : 10.1093/comjnl/45.6.620 .
• Leo, Joop MIM (1991), "Her LR( k ) gramerinde ileriye bakmadan doğrusal zamanda çalışan genel bağlamdan bağımsız bir ayrıştırma algoritması ", Theoretical Computer Science , 82 (1): 165–176, doi : 10.1016/0304 -3975(91)90180-A , MR  1112117

• Tomita, Masaru (1984). "Doğal diller için LR ayrıştırıcıları" (PDF) . SOĞUTMA . 10. Uluslararası Hesaplamalı Dilbilim Konferansı. s. 354–357.

Uygulamalar

C, C++

• 'Yine Başka Earley Ayrıştırıcı (YAEP)' – C / C++ kitaplıkları
• 'C Earley Ayrıştırıcı' - bir Earley ayrıştırıcı C

Haskell

• 'Earley' - Bir Earley ayrıştırıcı DSL içinde Haskell

Java

• [1] – Earley algoritmasının bir Java uygulaması
• PEN – Earley algoritmasını uygulayan bir Java kitaplığı
• Pep – Earley algoritmasını uygulayan ve ayrıştırma yapıları olarak tablolar ve ayrıştırma ağaçları sağlayan bir Java kitaplığı
• digitalheir/java-probabilistic-earley-parser - belirsiz bir cümleden en olası ayrıştırma ağacını belirlemek için yararlı olan olasılıksal Earley algoritmasını uygulayan bir Java kitaplığı

C#

• coonsta/earley - C# dilinde bir Earley ayrıştırıcısı
• patrickhuber/pliant - Marpa tarafından benimsenen iyileştirmeleri birleştiren ve Elizabeth Scott'ın ağaç oluşturma algoritmasını gösteren bir Earley ayrıştırıcısı.
• ellisonch/CFGLib - C# için Olasılıksal Bağlamdan Bağımsız Dilbilgisi (PCFG) Kitaplığı (Earley + SPPF, CYK)

JavaScript

• Nearley – Marpa'nın benimsediği iyileştirmeleri entegre etmeye başlayan bir Earley ayrıştırıcısı
• Bir Pint büyüklüğünde Earley Ayrıştırıcı - Elizabeth Scott'ın paylaşılan paketlenmiş ayrıştırma ormanı oluşturma tekniğini göstermek için bir oyuncak ayrıştırıcı (açıklamalı sözde kodlu)
• lagodiuk/earley-parser-js – Earley ayrıştırıcısının küçük bir JavaScript uygulaması (ayrıştırma ormanının oluşturulması dahil)
• digitalheir/probabilistic-earley-parser-javascript - olasılıksal Earley ayrıştırıcısının JavaScript uygulaması

OCaml

• Simple Earley - Belgelerle birlikte basit bir Earley benzeri ayrıştırma algoritmasının uygulanması.

Perl

• Marpa::R2 – bir Perl modülü. Marpa , Joop Leo, Aycock ve Horspool tarafından yapılan iyileştirmeleri içeren bir Earley algoritmasıdır.
• Parse::Earley – Jay Earley'in orijinal algoritmasını uygulayan bir Perl modülü

piton

• Lark – bir SPPF çıktısı veren bir Earley ayrıştırıcısının nesne yönelimli, prosedürel uygulaması.
• NLTK – Earley ayrıştırıcılı bir Python araç takımı
• Spark – Earley ayrıştırıcısını uygulayan Python için nesne yönelimli küçük bir dil çerçevesi
• spark_parser - yukarıdaki Spark ayrıştırıcısının hem Python 3 hem de Python 2'de çalışan güncellenmiş ve paketlenmiş sürümü
• earley3.py – ayrıştırma ormanı ve örneklerin oluşturulması da dahil olmak üzere 150 satırdan daha az kodda algoritmanın bağımsız bir uygulaması
• tjr_python_earley_parser - Python'da minimal bir Earley ayrıştırıcısı

Ortak Lisp

• CL-Earley-parser - bir Earley ayrıştırıcı uygulayan bir Common Lisp kitaplığı

Şema, Raket

• Charty-Racket – Bir Şema – Bir Earley ayrıştırıcısının Raket uygulaması

Wolfram

• uygunEarleyParser - Bazı temel test durumları ile Wolfram programlama dilinde bir Earley ayrıştırıcısının temel bir minimal uygulaması .

Kaynaklar

• Accent derleyici-derleyici