Come si confrontano i parser Pratt con altri tipi di parser e perché vengono utilizzati così poco?

Question

Recentemente ho appreso i parser di Pratt dall'articolo eccellente this e ho trovato i parser di Pratt molto più semplici e molto più eleganti dei parser di discesa ricorsivi. Ho provato a trovare un po 'più di informazioni su come si confrontano con altri tipi di parser, ma ho scoperto che l'articolo di Wikipedia è a malapena uno stub e la quantità di progetti più grandi che lo uso che potrei trovare è uguale a due.

Perché i parser Pratt sono così poco utilizzati? Hanno delle limitazioni o degli svantaggi severi di cui non sono a conoscenza? In che modo si confrontano esattamente con altri tipi di parser? Quando dovrei e quando non dovrei usarli?

Answer 1

C'è pochissima differenza tra un parser di Pratt e il cosiddetto parser "shunting yard" (che ha un articolo di Wikipedia molto più lungo allegato); la differenza principale è che Pratt usa la ricorsione e quindi lo stack, mentre Djikstra (il "shunting yard") mantiene uno stack esplicito. A parte questo, fanno esattamente la stessa sequenza di operazioni. Suppongo che l'espressione dell'algoritmo di Djikstra sia più comune a causa della recursofobia.

Ci sono alcuni vantaggi nell'utilizzo dello stack di programma; uno di questi è che è più semplice mantenere la sicurezza del tipo, poiché l'intero stack non deve essere un tipo. D'altra parte, molti parser di espressioni hanno un solo tipo.

Il libro del drago include un algorthm che genererà una tabella di precedenza degli operatori da una grammatica. Come indicato, il fatto che l'algoritmo abbia esito positivo non implica necessariamente che il parser di precedenza dell'operatore analizzerà esattamente la stessa lingua. Ci sono informazioni più interessanti là che ho certamente dimenticato; se sei interessato all'algoritmo, quello è uno dei posti che potresti guardare. Comprende l'interessante intuizione che gli operatori di relazioni di precarietà <e> possono essere generati osservando una derivazione, se si circonda il risultato di una produzione con <e> in modo ovvio. Nel complesso, la mia esperienza è che la maggior parte delle volte quando trovi un post sul blog che dice "Mio Dio, mi sono appena imbattuto in X ed è fantastico e perché non lo sanno più persone ??? ? ", la risposta è" Per favore non dare per scontato che la tua ignoranza sia universale ". Ma forse oggi sono solo di umore cinico.

A proposito, il parser Lua è un parser di discesa ricorsivo costruito a mano che utilizza l'analisi di stile Pratt per analizzare le espressioni; questa è una tecnica abbastanza comune, penso, e probabilmente la troverai in altri posti, anche se potresti dover analizzare il codice per vedere il modello.