Rimozione di ricorsione sinistra da Context-Free Grammatiche - Ordinazione di nonterminali

Question

Ho recentemente implementato l'algoritmo di Paull per la rimozione di sinistra-ricorsione da grammatiche context-free:

Assegnare un ordinamento $ A_1, \ dots, a_n $ ai nonterminals della grammatica.

for $ i: = 1 $ a $ n $ do begin
$ \ Quad $ a $ j: = 1 $ a $ i-1 $ Non comincio
$ \ Quad \ quad $ per ogni produzione della forma $ A_i \ a A_j \ alpha $ do begin
$ \ Quad \ quad \ quad $ rimuovere $ A_i \ a A_j \ alpha $ dalla grammatica
$ \ Quad \ quad \ quad $ per ogni produzione della forma $ A_j \ a \ beta $ do begin
$ \ Quad \ quad \ quad \ quad $ aggiungere $ A_i \ a \ beta \ alpha $ alla grammatica
$ \ Quad \ quad \ quad $ end
$ \ Quad \ quad $ end
$ \ Quad $ end
$ \ Quad $ trasformare il $ A_i $ -productions per eliminare diretta sinistra ricorsione
end

questo documento , l'efficienza dell'algoritmo dipende essenzialmente l'ordinamento dei non-terminali scelti in principio; il documento analizza la questione in dettaglio e suggeriscono ottimizzazioni.

Qualche notazione:

Si dirà che il simbolo $ X $ è un nell'angolo sinistro diretta di un non terminale $ A $, se c'è un $ A $ -Produzione con $ X $ come il più a sinistra il simbolo sul lato destro. Definiamo il rapporto sinistra-angolo di essere la chiusura transitiva riflessiva della relazione-angolo diretta-sinistra, e definiamo il relazione corretta-sinistra-angolo di essere il transitiva chiusura di il rapporto-angolo diretta-sinistra. Un non terminale è ricorsiva sinistra se si tratta di un angolo corretta sinistro della stessa; un non terminale è direttamente a sinistra ricorsiva se si tratta di un angolo diretta sinistro della stessa; e un non terminale è indirettamente sinistra ricorsiva se è ricorsiva sinistra, ma non ricorsivo direttamente sinistra.

Ecco quello che gli autori propongono:

Nel ciclo interno dell'algoritmo di Paull, per non-terminali $ A_i $ e $ A_j $, in modo tale che $ i> j $ e $ A_j $ è un angolo diretta sinistro di $ A_i $, sostituiamo tutte le occorrenze di $ A_j $ come un angolo a sinistra diretta di $ A_i $ con tutte le possibili espansioni di $ A_j $.

Questo solo contribuisce alla eliminazione della ricorsione sinistra dalla grammatica se $ A_i $ è a sinistra-ricorsiva non terminale, e $ $ A_j si trova su un percorso che rende $ A_i $ rimasto ricorsiva; cioè, se $ A_i $ è un angolo a sinistra di $ A_j $ (in aggiunta a $ A_j $ essendo un angolo a sinistra di $ A_i $).

Si potrebbe eliminare le sostituzioni che sono inutili nella rimozione di ricorsione sinistra se potevamo ordinare le nonterminals della grammatica in modo che, se $ i> j $ e $ A_j $ è un angolo diretta sinistro di $ A_i $, allora $ A_i $ è anche un angolo a sinistra di $ A_j $.

può raggiungere questo ordinando i nonterminals in ordine di numero di angoli distinti sinistra hanno decrescente.

Poiché la relazione sinistra-angolo è transitivo, se C è un angolo diretto sinistro di B, ogni angolo sinistro C è anche un angolo sinistro B.

Inoltre, poiché abbiamo definito il rapporto sinistro corner per essere riflessiva, B è un angolo sinistro della stessa.

Quindi, se C è un angolo diretto sinistro di B, B deve seguire in ordine di numero di angoli distinti sinistra decrescente, a meno che B è un angolo di sinistra C.

Tutto quello che voglio è sapere come ordinare i nonterminals in principio, ma non farlo dalla carta. Qualcuno può spiegare in un modo più semplice? Pseudocodice avrebbe aiutato a capire meglio.

Answer 1

Questo è in realtà non è molto complicato. Darò per scontato che epsilon produzioni sono già stati eliminati dal linguaggio, perché che oscurare solo il concetto chiave di "sinistra".

Formare un grafo G in cui i vertici sono tutti i non-terminali della grammatica. Ora disegnare un arco orientato da A a B se non v'è alcuna regola di produzione che si presenta come "A -> B [...]". Le chiamate carta B un "angolo sinistro diretta" di A. Più in generale, un altro C-terminale non è chiamato "sinistra" di A se c'è qualche percorso da A a C lungo i bordi di questo grafico. Questo può essere fatto calcolando la transitiva chiusura di G, H chiamano.

Il documento suggerisce di ordinare i vertici contando il numero di curve a sinistra ogni vertice A è (cioè quante altre non-terminali si può raggiungere da A, o il grado uscente di A nel grafico H), quindi smistamento in ordine decrescente da questo numero.

Una motivazione handwavy per questa politica è che se c'è un importante non terminale (diciamo il simbolo a partire S) con collegamenti per molti altri simboli), allora ha senso di spurgo sinistra-ricorsione da S presto, perché se si lascia a più tardi ci saranno più copie di S che è necessario espandere fuori. Credo che la spiegazione nella carta è più convincente, ma forse meno evidente.