O złożoności parserów rekurencyjnych

Question

Wiadomo, że parser rekursywny może wymagać czasu wykładniczego w niektórych przypadkach; Czy ktokolwiek może wskazać mi próbki, gdzie to się dzieje? Szczególnie interesuje się przypadkami dla PEG (to jest z priorytetowymi wyborami).

Answer 1

To dlatego, że możesz skończyć analizując te same rzeczy (sprawdź tę samą regułę w tej samej pozycji) wiele razy w różnych gałęziach rekursji. To trochę tak, jakby obliczać n-tą liczbę Fibonacciego przy użyciu rekurencji.

Grammar: 

A -> xA | xB | x 
B -> yA | xA | y | A 
S -> A 

Input: 
xxyxyy 

Parsing: 
xA(xxyxyy) 
    xA(xyxyy) 
     xA(yxyy) fail 
     xB(yxyy) fail 
     x(yxyy) fail 
    xB(xyxyy) 
     yA(yxyy) 
      xA(xyy) 
       xA(yy) fail 
       xB(yy) fail 
       x(yy) fail 
      xB(xyy) 
       yA(yy) 
        xA(y) fail 
        xB(y) fail 
        x(y) fail 
       xA(yy) fail * 
      x(xyy) fail 
     xA(yxyy) fail * 
     y(yxyy) fail 
     A(yxyy) 
      xA(yxyy) fail * 
      xB(yxyy) fail * 
      x(yxyy) fail * 
    x(xyxyy) fail 
xB(xxyxyy) 
    yA(xyxyy) fail 
    xA(xyxyy) * 
     xA(yxyy) fail * 
     xB(yxyy) fail * 
     ... 

* - gdzie możemy analizować regułę w tym samym miejscu, w którym mamy już analizowany go w innej branży. Gdybyśmy zapisali wyniki - które reguły zawiodłyby przy których pozycjach - dowiedzielibyśmy się, że xA (xyxyy) zawodzi za drugim razem i nie przejdziemy ponownie przez całe poddrzewo. Nie chciałem napisać wszystkiego, ale widać, że wielokrotnie będzie powtarzać te same poddrzewa.

Kiedy to się stanie - gdy masz wiele nakładających się transformacji. Priorytetowy wybór nie zmienia rzeczy - jeśli reguła najniższego priorytetu kończy się jako jedyna poprawna (lub żadna nie jest poprawna), musisz sprawdzić wszystkie reguły.

Answer 2

Każdy analizator składający się z góry w dół, włącznie z rekurencyjnym zejściem, może teoretycznie stać się wykładniczy, jeśli kombinacja danych wejściowych i gramatyki jest taka, że ​​wymagana jest duża liczba ścieżek wstecz. Dzieje się tak, jeśli gramatyka jest taka, że ​​wybory determinujące są umieszczane na końcu długich sekwencji. Na przykład, jeśli masz symbol taki jak &, co oznacza "wszystkie poprzednie minusy są w rzeczywistości plusses", a następnie mają dane takie jak "(((((a - b) - c) - d) - e &)" następnie parser musi przejść do tyłu i zmień wszystkie plusy na minusy. Jeśli zaczniesz tworzyć wyrazy zagnieżdżone wzdłuż tych linii, możesz utworzyć efektywny, nie kończący się zestaw danych wejściowych.

Musisz zdać sobie sprawę z tego, że wkraczasz tutaj w kwestię polityczną, ponieważ w rzeczywistości większość normalnych gramatyk i zestawów danych nie jest taka, jednak istnieje wiele osób, które systematycznie odradzają rekursywne zejście, ponieważ nie jest ono łatwe do zrobienia RD automatycznie. Wszystkie wczesne parsery to LALR, ponieważ są DUŻO łatwiejsze do zrobienia automatycznie niż RD. Stało się tak dlatego, że wszyscy po prostu napisali LALR i zepsutą RD, ponieważ w dawnych czasach jedynym sposobem na stworzenie RD było ręczne kodowanie. Na przykład, jeśli czytasz smoczą książkę, zobaczysz, że Aho & Ullman pisze tylko jeden akapit na RD, i jest to w zasadzie tylko ideologiczne zdanie: "RD jest złe, nie rób tego".

Oczywiście, jeśli zaczniesz ręczne kodowanie RD (tak jak ja), przekonasz się, że są one dużo lepsze niż LALR z różnych powodów. W dawnych czasach zawsze można było powiedzieć kompilatorowi, który miał ręcznie zakodowane RD, ponieważ miał znaczące komunikaty o błędach z dokładnością lokalizacji, podczas gdy kompilatory z LALR-em pokazywałyby błąd występujący jak 50 linii od miejsca, w którym faktycznie był. Wiele się zmieniło od dawnych czasów, ale powinieneś zdać sobie sprawę, że kiedy zaczynasz czytać FUD na RD, to pochodzi z długiej, długiej tradycji werbalnej niszczenia RD w "pewnych kręgach".