Come modificare le azioni semantiche quando si rimuove sinistra-ricorsione da una grammatica

Question

Esiste un algoritmo che ci dice come modificare le azioni semantiche associate a una grammatica left-recursive? Per esempio, abbiamo la seguente grammatica, e le sue azioni semantiche associate:

$ S \ rightarrow id = expr $ {S.s = expr.size}

S $ \ rightarrow $ se expr allora $ S_1 $ altro $ S_2 $ {$ S_1.t = S.t + 2; $ $ S_2.t = S.t + 2; $ $ S.s = expr.size + S_1.size + S_2.size + 2; $}

S $ \ rightarrow $ mentre expr do $ S_1 $ {$ S_1.t = S.t + 4; $ $ S.s = expr.size + S_1.s + 1; $}

S $ \ rightarrow $ $ S_1 $; $ S_2 $ {$ S_1.t = S_2.t = S.t; $ $ S.s = S_1.s + S_2.s; $}

Chiaramente la versione non ricorsiva della grammatica è:

S $ \ rightarrow $ id = expr T

S $ \ rightarrow $ se expr allora $ S_1 $ altro $ S_2 $ T

S $ \ rightarrow $ mentre expr do $ S_1 $ T

T $ \ rightarrow $; $ S_2 $ T

T $ \ rightarrow $ $ \ epsilon $

Ma abbiamo anche bisogno di cambiare le azioni semantiche di conseguenza. come questo può essere fatto qualche idea?

Answer 1

Da quello che ho scoperto, non esiste una tecnica generale per modificare le azioni semantiche durante la rimozione sinistra-ricorsione. Al contrario, il metodo migliore è quello di prendere un esempio rappresentativo, disegnare il suo albero sintattico, e poi controllando quali azioni semantiche ci danno lo stesso risultato che la grammatica precedente.

Answer 2

Ho una soluzione parziale (io sto cercando uno generale). Se la grammatica NON ha produzioni epsilon, quindi non nonterminals sono annullabili. Questo significa che l'algoritmo per rimuovere la ricorsione sinistra passa attraverso (anche se introduce produzioni epsilon).

Se si aggiungono le azioni semantiche della forma d'azione (etichetta, conteggio) che riconoscono la stringa vuota, e utilizzare uno spostamento / ridurre parser, ed esaminare tutte le alternative **, non c'è affatto bisogno di riorganizzare l'albero sintattico. Durante l'analisi, se un terminale è riconosciuto spinge un attributo nello stack parser, questa è un'azione di trasferimento. Quando viene rilevato un azione, si apre N valori dallo stack, e spinge un nodo con l'etichetta specificata ei valori estratto dallo stack, in senso inverso, come i bambini. Questo è il ridurre l'azione.

Il parser deve propagare la posizione attuale e la pila parser, e le operazioni di spostamento e di ridurre dovrebbe essere fatto con non aggiornamenti funzionali mutazioni. E 'quindi evidente che refactoring la grammatica non cambia la sequenza di spostamento e di ridurre le azioni, così l'albero di analisi che ne risulta è invariante per il refactoring.

Questo significa che se si genera un AST, piuttosto che un albero di analisi si deve fare riferimento agli attributi in base al numero. La macchina funziona perché lo stack parser e pila di controllo sono disaccoppiati e refactoring cambia solo la pila di controllo. La difficoltà è che la grammatica deve essere epsilon libera inizialmente perché i termini Ridurre azione sono essi stessi annullabili.

** L'assunzione tutte le alternative vengono esaminate è fatto in modo che l'ordine di considerazione è irrilevante. Sebbene rifattorizzazione producono grammatiche equivalenti, non v'è alcuna garanzia automatica degli alberi di analisi risultanti saranno le stesse se non tutte le possibilità sono esaminati. In tal caso i resti ordinazione indeterminata, ma l'insieme di risultati saranno uguali.