Sulla complessità dei parser di discesa ricorsivi

Question

È noto che i parser di discendenza ricorsiva possono richiedere tempi esponenziali in alcuni casi; qualcuno potrebbe indicarmi i campioni, dove questo accade? Particolarmente interessato ai casi di PEG (cioè con scelte prioritarie).

Answer 1

È perché è possibile finire per analizzare le stesse cose (controllare la stessa regola nella stessa posizione) molte volte in diversi rami di ricorsione. È un po 'come calcolare il n-esimo numero di Fibonacci usando la ricorsione.

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 * 
     ... 

* - dove analizziamo una regola nella stessa posizione in cui abbiamo già analizzato in un ramo diverso. Se avessimo salvato i risultati - quali regole falliscono in quali posizioni - sapremmo che xA (xyxyy) fallisce la seconda volta e non verificheremo di nuovo l'intera sottostruttura. Non volevo scrivere tutto, ma puoi vedere che ripeterà gli stessi sottoalberi molte volte.

Quando accadrà, quando ci sono molte trasformazioni sovrapposte. La scelta prioritaria non cambia le cose - se la regola della priorità più bassa finisce per essere l'unica corretta (o nessuna è corretta), devi comunque controllare tutte le regole.

Answer 2

Qualsiasi parser dall'alto verso il basso, inclusa la discesa ricorsiva, può teoricamente diventare esponenziale se la combinazione di input e grammatica è tale da rendere necessario un numero elevato di backtrack. Questo succede se la grammatica è tale che le scelte determinative sono poste alla fine di lunghe sequenze. Ad esempio, se hai un simbolo come & che significa "tutti gli altri precedenti sono effettivamente positivi" e poi hai dati come "((((a - b) - c) - d) - e &" allora il parser deve andare all'indietro e cambia tutti i minimi rispetto ai negativi. Se inizi a creare espressioni nidificate lungo queste linee, puoi creare un insieme di input efficacemente non terminante.

Devi capire che stai entrando in una questione politica qui, perché la realtà è che la maggior parte delle grammatiche e dei set di dati normali non sono così, tuttavia, ci sono MOLTE persone che sistematicamente biforcano la discendenza ricorsiva perché non è facile da rendere automaticamente RD. Tutti i parser iniziali sono LALR perché sono MOLTO più facili da eseguire automaticamente rispetto a RD. Quindi, quello che è successo è che tutti hanno appena scritto LRD e RD a bocca aperta, perché nei vecchi tempi l'unico modo per creare un RD era codificarlo a mano. Ad esempio, se leggi il libro del drago troverai che Aho & Ullman scrive solo un paragrafo su RD, ed è fondamentalmente solo un takedown ideologico che dice "RD è cattivo, non farlo".

Ovviamente, se si avvia RD a mano (come ho fatto), si scoprirà che sono molto meglio dei LALR per una serie di motivi. Ai vecchi tempi si poteva sempre dire a un compilatore che aveva un RD codificato a mano, poiché aveva messaggi di errore significativi con precisione di localizzazione, mentre i compilatori con LALR mostravano l'errore che si verificava a 50 linee di distanza da dove realmente si trovava. Le cose sono cambiate molto dai tempi antichi, ma dovresti rendertene conto quando inizi a leggere il FUD su RD, che proviene da una lunga tradizione di "trascrizione verbale" in "determinati cerchi".