Quando utilizzare un albero di sintassi astratto o concreto?

Question

Ho fatto ricerche sui compilatori. Il lexer sembra essere molto semplice: prendi una "frase" e suddividila in parole (o token). Per garantire la grammatica corretta è necessario un parser. Generalmente il parser prende i token e costruisce un albero che risulta in un nodo radice (parole in frasi, paragrafi, pagine, ecc ...).

Da this question sembrerebbe che un parser creerebbe un AST. L'AST contiene solo ciò che è necessario per eseguire il codice, quindi elementi come parentesi non sarebbero necessari poiché la precedenza degli operatori è incorporata in un AST. Un AST è probabilmente tutto un bisogno di compilatore.

Ma per quanto riguarda la conversione del codice da una lingua all'altra? Prendere una lingua preparata (grammatica) o una grammatica esistente e convertirla in un'altra in cui le regole di precedenza degli operatori possono o meno essere diverse? La precedenza dell'operatore è "incorporata" anche nel CST?

Ad esempio, diciamo che ho inventato una lingua e volevo tradurla in codice PHP. L'operatore ternario nella maggior parte delle lingue ha associatività da destra a sinistra. PHP utilizza erroneamente associatività da sinistra a destra (see more about this here). Voglio che la "mia lingua" utilizzi da destra a sinistra, ma il codice PHP risultante deve applicare la parentesi per ottenere il risultato corretto in PHP (con lo link to Wikipedia, il risultato deve essere "treno" anziché "cavallo").

Quindi per la traduzione linguistica un CST sarebbe migliore? La precedenza dell'operatore è solitamente incorporata in un CST? C'è qualcosa in mezzo? Esistono esempi che confrontino entrambi gli alberi con una semplice equazione algebrica? Qualche esempio che illustra un operatore ternario?

(Is "transcodifica" il termine corretto per "traduzione linguaggio di programmazione" Una ricerca su Google porta in primo piano la conversione dei media?).

Quello che sto cercando di capire è: quando è più opportuno utilizzare uno sull'altro?

Answer 1

Un AST che modella tutti i dettagli semantici della lingua di partenza è tutto ciò che serve. Per definizione, se modella correttamente la semantica e il linguaggio include un operatore ternario, modellerà correttamente l'ordine specifico in cui vengono applicati gli operatori (ad esempio, i risultati delle sovrascrizioni del modulo di predecence come parentesi).

Quindi il tuo problema non è nell'AST. Sta generando in un'altra lingua usando operatori simili (ternari) la cui precedenza è diversa.

Questo è un problema secolare nella generazione del codice: gli operatori del target non corrispondono esattamente agli operatori della sorgente e quindi l'output non può essere uno a uno. Nel tuo caso, dovresti essere in grado di risolvere il problema generando operatori ternari di PHP con parentesi intorno a loro per controllare l'ordine per ottenere ciò che è la semantica originale, quindi questo non è un grosso problema.

In generale, generare sequenze di codice che raggiungono un risultato desiderato può essere piuttosto complicato e ci sono molti modi per farlo. Ecco perché i libri del compilatore sono spessi piuttosto che sottili. Sembra che tu abbia implicitamente deciso "get AST, walk AST, spit code"; questo è quasi un generatore di codice on-the-fly. E questo funziona in modo adeguato se non ti interessa se il codice generato è particolarmente buono, e la lingua di destinazione è molto vicina alla lingua di partenza.

Se il problema di generazione del codice è più complesso, ciò che normalmente accade è che l'AST viene utilizzato per generare ciò che equivale a un modello di flusso di dati del calcolo, costituito da operatori che producono risultati e consumano i risultati degli operatori precedenti in "operatori" che recuperano valori e costanti variabili.Quindi la rappresentazione del flusso di dati viene attraversata per generare il codice; questo ha il vantaggio di poter scegliere un operatore nella rappresentazione del flusso di dati, trovare una sequenza di codice corrispondente nella lingua di destinazione, generarla e quindi preoccuparsi di come vengono raccolti gli operandi. Gli schemi migliori corrispondono ai sottografi del flusso di dati (che rappresentano costrutti equivalenti del linguaggio di destinazione composto) al grafico del flusso di dati prodotto; questo può produrre codice significativamente migliore. Spesso, è possibile applicare ottimizzazioni specifiche del linguaggio di destinazione dopo la generazione di codice non elaborato per produrre codice ancora migliore. In entrambi i casi, devi preoccuparti di gestire i risultati dell'operatore; possono essere inviati direttamente al successivo operatore di lingua di destinazione, oppure devono entrare in una sorta di memoria temporanea (per il codice macchina, questo può essere un altro registro o una posizione di memoria). Fare tutto questo non è facile; di nuovo, è per questo che i libri del compilatore non sono sottili.

Una variazione su questa idea è rappresentata dalle trasformazioni del programma sorgente-sorgente. Questa mappa costruisce nel codice sorgente "direttamente" i costrutti nel codice di destinazione, anche se questo viene solitamente fatto dietro le quinte operando su AST perché il testo del linguaggio di programmazione non analizzato è difficile da eguagliare. Il nostro DMS Software Reengineering Toolkit è un esempio di questo tipo di sistema. Con tale strumento, si scrivono i pattern nella lingua di origine (che corrispondono implicitamente a un albero di analisi) e i corrispondenti pattern nella lingua di destinazione (implicitamente producendo AST del linguaggio di destinazione). È possibile scrivere complessi costrutti di origine o di destinazione dando gran parte dell'effetto del grafico del flusso di dati corrispondente sopra. L'ottimizzazione post-generazione consiste in più regole di riscrittura che trasformano il codice di destinazione in codice di destinazione.

Bottom line: Avere un AST non è veramente sufficiente a meno che la traduzione non sia veramente banale. Puoi leggere di più su ciò che ti serve in questa risposta SO: https://stackoverflow.com/a/3460977/120163

ATTENZIONE: l'opinione forte segue.

Re "Transcoder": preferisco di gran lunga il termine compilatore "compilation", "translation" o "source-to-source". Ho costruito strumenti di analisi e manipolazione del programma per quasi 40 anni. Non avevo mai sentito il termine "transcoder" fino a quando non ho incontrato questa domanda SO: Experience migrating legacy Cobol/PL1 to Java e una risposta che descrive IMHO uno schema di traduzione del codice veramente terribile chiamato NACA. Ho sentito da quando questo termine sta guadagnando trazione; Non vedo perché abbiamo dovuto inventare un altro termine quando ne abbiamo di perfettamente adeguati. Di solito questo è un segno di qualcuno che ha inventato un alto sacerdozio; "inventiamo un nuovo termine brillante in modo che le persone non capiscano davvero cosa stiamo facendo". Sono felice di lasciare questo termine a traduzioni veramente terribili.