Perché non archiviamo l'albero della sintassi invece del codice sorgente?

108

Abbiamo molti linguaggi di programmazione. Ogni lingua viene analizzata e la sintassi viene controllata prima di essere convertita in codice, quindi viene creato un albero sintattico astratto (AST).

Abbiamo questo albero sintassi astratto, perché non archiviamo questo albero di sintassi invece del codice sorgente (o vicino al codice sorgente)?

Usando un AST invece del codice sorgente. Ogni programmatore di un team può serializzare questo albero in qualsiasi lingua desideri (con la corretta grammatica contestuale) e tornare ad AST quando sono finiti. Questo eliminerebbe il dibattito sulle domande sullo stile di codifica (dove inserire {e}, dove inserire spazi, rientri, ecc.)

Quali sono i pro e i contro di questo approccio?

    
posta Calmarius 10.11.2011 - 23:04
fonte

13 risposte

70

Spazio bianco e commenti

Generalmente un AST non include spazi bianchi, terminatori di riga e commenti.

Formattazione significativa

Hai ragione che nella maggior parte dei casi questo è un positivo (elimina la formattazione di guerre sante), ci sono molti casi in cui la formattazione del codice originale trasmette un significato, come in letterali stringa multi-linea e "paragrafi di codice" ( separare i blocchi di istruzioni con una linea vuota).

Codice che non può essere compilato

Mentre molti parser sono molto resistenti alla sintassi mancante, il codice con errori spesso si traduce in un albero di sintassi molto bizzarro, che va bene e dandy fino al punto in cui l'utente ricarica il file. Hai mai commesso un errore nel tuo IDE e poi all'improvviso l'intero file ha "squigglie"? Immagina come sarebbe ricaricato in un'altra lingua.

Forse gli utenti non eseguono il commit di codice non analizzabile, ma sicuramente hanno bisogno di salvare localmente.

Non ci sono due lingue perfette per le coppie

Come altri hanno sottolineato, non ci sono quasi due lingue che abbiano la parità perfetta delle funzionalità. Il più vicino che riesco a pensare è VB e C #, o JavaScript e CoffeeScript, ma anche in questo caso VB ha caratteristiche come XML Literals che non hanno equivalenti in C # e la conversione da JavaScript a CoffeeScript potrebbe generare molti valori letterali JavaScript. / p> Esperienza personale:

In un'applicazione software che scrivo, abbiamo effettivamente bisogno di farlo, poiché ci si aspetta che gli utenti inseriscano espressioni "plain English" convertite in JS in background. Abbiamo preso in considerazione solo la memorizzazione della versione JS, ma ho trovato quasi nessun modo accettabile per fare in modo affidabile carico e scarico, quindi abbiamo finito per memorizzare sempre sia il testo dell'utente che la versione JS, oltre a una bandiera che indicava se "plain english "versione analizzata perfettamente o meno.

    
risposta data 10.11.2011 - 23:27
fonte
42

Why don't we store this syntax tree instead of the source code? Every programmer in a team can serialize this tree to any language, they want and parse back to AST when they finished.

In effetti, questa è un'idea ragionevole. Microsoft aveva un progetto di ricerca negli anni '90 per fare quasi esattamente quello .

Mi vengono in mente diversi scenari.

Il primo è piuttosto banale; come dici tu, potresti rendere il rendering AST in viste diverse a seconda delle preferenze dei diversi programmatori per cose come la spaziatura e così via. Ma la memorizzazione di un AST è eccessivo per quello scenario; scriviti una bella stampante. Quando carichi un file nel tuo editor, avvia la graziosa stampante per inserirlo nel formato preferito e torna al formato originale quando lo salvi.

Il secondo è più interessante. Se è possibile memorizzare l'albero di sintassi astratto, la modifica del codice diventa non testuale ma piuttosto sintattica. I refactoring in cui il codice viene spostato diventano molto più facili da capire. Il lato negativo è ovviamente che la scrittura degli algoritmi di albero-diff non è esattamente banale e spesso deve essere fatto su una base per lingua. La differenza di testo funziona praticamente per qualsiasi lingua.

Il terzo è più simile a quello che Simonyi ha previsto per la Programmazione Intentional: che i concetti fondamentali comuni ai linguaggi di programmazione sono quelli che sono serializzati, e quindi avete diverse visioni di quei concetti resi in diverse lingue. Anche se una bella idea, il fatto brutto è che le lingue sono sufficientemente diverse nei loro dettagli che un approccio al minimo comune denominatore non funziona davvero.

Quindi, in breve, è un'idea carina ma è un'enorme quantità di lavoro extra per un vantaggio relativamente piccolo. Ecco perché quasi nessuno lo fa.

    
risposta data 11.11.2011 - 18:45
fonte
19

Si potrebbe sostenere che questo è esattamente ciò che il codice byte è in .NET. Infatti, il programma Reflector di redgate traduce il codice byte in una gamma di linguaggi di programmazione .NET.

Tuttavia, ci sono problemi. La sintassi è specifica della lingua in quanto ci sono cose che puoi rappresentare in una lingua che non ha alcuna rappresentazione in altre lingue. Ciò si verifica in .NET con C ++ che è l'unico linguaggio .NET che ha accesso a tutti i 7 livelli di accesso.

Al di fuori dell'ambiente .NET diventa molto più complicato. Ogni lingua quindi inizia ad avere il proprio set di librerie associate. Non sarebbe possibile riflettere una sintassi generica in C e Java che riflette la stessa esecuzione di istruzioni mentre risolvono problemi similari in modi molto diversi.

    
risposta data 10.11.2011 - 23:17
fonte
12

Mi piace un po 'della tua idea, ma tu stai sovrastimando notevolmente la facilità con cui tradurre la lingua in lingua. Se fosse così facile, non avresti nemmeno bisogno di memorizzare l'AST, dal momento che puoi sempre analizzare la lingua X nell'AST, quindi passare da AST alla lingua Y.

Tuttavia, mi auguro che le specifiche del compilatore riflettano un po 'di più sull'esposizione di alcuni AST attraverso una sorta di API. Cose come la programmazione orientata agli aspetti, il refactoring e l'analisi statica del programma potrebbero essere implementate attraverso tale API, senza che l'implementatore di quelle funzionalità debba rifare così tanto del lavoro già implementato dagli scrittori di compilatori.

È strano quanto spesso la struttura dei dati del programmatore per rappresentare un programma sia un insieme di file contenenti stringhe.

    
risposta data 10.11.2011 - 23:45
fonte
11

Penso che i punti salienti siano quelli:

  • Non ci sono benefici. Hai detto che significherebbe che tutti potrebbero usare la loro lingua preferita. Ma non è vero - l'uso di una rappresentazione ad albero della sintassi eliderebbe solo le differenze sintattiche, ma non quelle semantiche. Funziona in una certa misura per linguaggi molto simili - come VB e C #, o Java e Scala. Ma nemmeno lì completamente.

  • È problematico. Hai guadagnato la libertà di linguaggio, ma hai perso la libertà degli strumenti. Non puoi più leggere e modificare il codice in un editor di testo, o anche in un IDE - tu dipendere su uno strumento specifico che parla la tua rappresentazione AST sia per leggere che per modificare il codice. Non c'è niente guadagnato qui.

    Per illustrare questo ultimo punto, dai un'occhiata a RealBasic, che è un'implementazione proprietaria di un potente dialetto BASIC. Per un certo periodo, sembrava quasi che la lingua potesse decollare, ma era completamente dipendente dal fornitore, al punto che si poteva solo visualizzare il codice nel proprio IDE dal momento che era stato salvato in un formato proprietario non di testo. Grande errore .

risposta data 11.11.2011 - 13:26
fonte
6

Penso che, se memorizzi sia il testo che l'AST, non hai davvero aggiunto nulla di utile, poiché il testo è già presente in una lingua e l'AST può essere rapidamente ricostruito dal testo.

D'altra parte, se si archivia solo l'AST, si perdono elementi come i commenti che non possono essere ripristinati.

    
risposta data 10.11.2011 - 23:16
fonte
4

Credo che l'idea sia interessante in teoria ma non molto pratica in quanto i diversi linguaggi di programmazione supportano costrutti diversi, alcuni dei quali non hanno equivalenti in altre lingue.

Ad esempio, X ++ ha un'istruzione 'while select' che non può essere scritta in C # senza molto codice extra (classi extra, logica aggiuntiva, ecc.). link

Quello che sto dicendo qui è che molte lingue hanno zuccheri sintattici che traducono in grandi blocchi di codice della stessa lingua o persino elementi che non esistono affatto negli altri. Ecco un esempio del perché l'approccio AST non funziona:

Lingua X ha una parola chiave K che è tradotta, in AST in 4 istruzioni: S1, S2, S3 e S4. L'AST è ora tradotto in lingua Y e un programmatore cambia S2. Ora cosa succede con la traduzione su X? Il codice è tradotto come 4 affermazioni anziché una singola parola chiave ...

L'ultimo argomento contro l'approccio AST sono le funzioni della piattaforma: cosa succede quando una funzione è incorporata nella piattaforma? Come .NET's Environment.GetEnvironmentVariable. Come lo traduci?

    
risposta data 11.11.2011 - 01:07
fonte
4

C'è un sistema costruito attorno a questa idea: JetBrains MPS . Un editor è un po 'strano, o solo diverso, ma in generale non è un grosso problema. Il problema più grande è, beh, che non è più un testo, quindi non puoi usare nessuno dei normali strumenti basati sul testo - altri editor, grep , sed , strumenti di unione e diff, ecc.

    
risposta data 11.11.2011 - 14:00
fonte
4

Esistono in realtà diversi prodotti, generalmente noti come "banchi di lavoro linguistici" che memorizzano gli AST e presentano, nei loro editor, una "proiezione" dell'AST in una lingua particolare. Come ha detto @ sk-logic, MPS di JetBrains è uno di questi sistemi. Un altro è Intentional Workbench del software intenzionale.

Il potenziale per i banchi di lavoro della lingua sembra molto alto, in particolare nell'area dei linguaggi specifici del dominio, dal momento che è possibile creare una proiezione specifica del dominio. Ad esempio, Intenzionale demos un DSL relativo all'elettricità che proietta come schema circuitale - molto più facile e più accurato per un esperto di domini di discutere e criticare rispetto a un circuito descritto in un linguaggio di programmazione basato su testo.

In pratica, i banchi di lavoro della lingua sono stati lenti a prendere piede perché, a parte il lavoro DSL, gli sviluppatori preferirebbero probabilmente lavorare in un linguaggio di programmazione generale familiare. Se confrontati testa a testa con un editor di testo o IDE di programmazione, i banchi di lavoro della lingua hanno tonnellate di spese generali ei loro vantaggi non sono così chiari. Nessuno dei banchi di lavoro linguistici che ho visto sono stati attaccati al punto di poter estendere facilmente i propri IDE, ovvero se i banchi di lavoro della lingua sono ottimi per la produttività, perché gli strumenti del banco di lavoro linguistico non sono migliorati -e meglio a tassi sempre più veloci?

    
risposta data 11.11.2011 - 20:13
fonte
3

Mi hai letto nel pensiero.

Quando ho frequentato un corso di compilatore, alcuni anni fa, ho scoperto che se prendi un AST e lo serializzi, con notazione di prefisso invece della solita notazione infissa, e usi parentesi per delimitare le intere istruzioni, ottieni Lisp. Mentre avevo imparato a conoscere Scheme (un dialetto di Lisp) nei miei studi universitari, non avevo mai ottenuto un apprezzamento per questo. Ho sicuramente guadagnato un apprezzamento per Lisp e i suoi dialetti, come risultato di quel corso.

Problemi con ciò che proponi:

  1. è difficile / lento comporre un AST in un ambiente grafico. Dopo tutto, molti di noi possono digitare più velocemente di quanto possiamo spostare un mouse. Eppure, una domanda emergente è "come si scrive codice del programma con un tablet?" La digitazione su un tablet è lenta / ingombrante, rispetto a una tastiera / laptop con una tastiera hardware. Se potessi creare un AST trascinando e rilasciando componenti da una tavolozza su un canvas su un dispositivo touchscreen di grandi dimensioni, la programmazione su un tablet potrebbe diventare una cosa reale.

  2. pochi / nessuno dei nostri strumenti esistenti lo supporta. Abbiamo decenni di sviluppo coinvolti nella creazione di IDE sempre più complessi e di editor sempre più intelligenti. Abbiamo tutti questi strumenti per riformattare il testo, confrontare il testo, cercare il testo. Dove sono gli strumenti che possono fare l'equivalente di una ricerca di espressioni regolari su un albero? O un diff di due alberi? Tutte queste cose sono fatte facilmente con il testo. Ma possono solo confrontare le parole. Cambia un nome di variabile, in modo tale che le parole siano diverse ma il significato semantico è lo stesso, e quegli strumenti di diff sono nei guai. Tali strumenti, sviluppati per operare su AST anziché testo, consentirebbero di avvicinarsi al confronto del significato semantico. Questa sarebbe una buona cosa.

  3. mentre si trasforma il codice sorgente del programma in un AST è relativamente ben compreso (abbiamo compilatori e interpreti, no?), trasformare un codice AST in codice di programma non è così ben compreso. Moltiplicare due numeri primi per ottenere un grande numero composito è relativamente semplice, ma è molto più difficile ricondurre un numero grande e composito a numeri primi; è qui che ci troviamo con AST parsing vs decompiling. Ecco dove le differenze tra le lingue diventano un problema. Anche all'interno di una particolare lingua, ci sono molti modi per decompilare un AST. Iterare attraverso una collezione di oggetti e ottenere un qualche tipo di risultato, per esempio. Utilizzare un ciclo for, iterando attraverso un array? Sarebbe compatto e veloce, ma ci sono dei limiti. Utilizzare un Iterator di qualche tipo, operando su una collezione? Quella Collezione potrebbe essere di dimensioni variabili, il che aggiunge flessibilità al (possibile) costo della velocità. Riduci mappa? Più complesso, ma implicitamente parallelizzabile. E questo è solo per Java, a seconda delle tue preferenze.

Col tempo, lo sforzo di sviluppo sarà esaurito e svilupperemo utilizzando touchscreen e AST. La digitazione diventerà meno necessaria. Lo vedo come una progressione logica da dove siamo, guardando a come usiamo i computer, oggi, che risolverò il # 1.

Stiamo già lavorando con gli alberi. Lisp è semplicemente AST serializzati. XML (e HTML, per estensione) è solo un albero serializzato. Per fare ricerca, abbiamo già un paio di prototipi: XPath e CSS (per XML e HTML, rispettivamente). Quando vengono creati strumenti grafici che ci consentono di creare selettori e modificatori in stile CSS, avremo risolto parte del # 2. Quando questi selettori possono essere estesi per supportare regex, saremo più vicini. Sto ancora cercando un buon strumento grafico per confrontare due documenti XML o HTML. Man mano che le persone sviluppano questi strumenti, # 2 può essere risolto. Le persone stanno già lavorando su queste cose; non sono ancora lì, ancora.

L'unico modo in cui posso vedere per poter decompilare quegli AST al testo del linguaggio di programmazione sarebbe una ricerca di obiettivi. Se sto modificando il codice esistente, l'obiettivo potrebbe essere raggiunto da un algoritmo che rende il mio codice modificato il più simile possibile al codice di partenza (diff minimo testuale). Se sto scrivendo codice da zero, l'obiettivo potrebbe essere il codice più piccolo e più stretto (probabilmente un ciclo for). Oppure potrebbe essere un codice che si parallelizza nel modo più efficiente possibile (probabilmente una mappa / riduzione o qualcosa che coinvolge CSP). Pertanto, lo stesso AST potrebbe comportare un codice significativamente diverso, anche nella stessa lingua, in base al modo in cui sono stati impostati gli obiettivi. Lo sviluppo di un tale sistema risolverebbe # 3. Sarebbe complesso dal punto di vista computazionale, il che significa che probabilmente avremmo bisogno di un qualche tipo di disposizione client-server, che consenta al tablet del tuo palmare di scaricare molti carichi pesanti su alcuni server basati su cloud.

    
risposta data 19.06.2014 - 16:27
fonte
1

Se la tua intenzione è eliminare il dibattito sugli stili di formattazione, allora forse quello che vuoi è un editor che legge in un file sorgente, lo formatta in base alle tue preferenze personali per la visualizzazione e la modifica, ma al momento del salvataggio, riformatta il file scelto stile usato dal team.

È abbastanza facile se usi un editor come Emacs . La modifica dello stile di formattazione di un intero file è un lavoro a tre comandi.

Dovresti anche essere in grado di creare i ganci per trasformare automaticamente un file nel tuo stile al momento del caricamento e trasformarlo nello stile di squadra durante il salvataggio.

    
risposta data 11.11.2011 - 15:23
fonte
1

È difficile leggere e modificare un AST, invece del codice sorgente.

Tuttavia, alcuni strumenti relativi al compilatore consentono di utilizzare l'AST. Bytecode Java e codice .NET Intermediate funzionano come un AST.

    
risposta data 11.11.2011 - 00:39
fonte
0

è una bella idea; ma AST di ogni lingua è diversa da ogni altra.

l'unica eccezione che conosco è VB.NET e C #, dove microsoft sostiene che sono "la stessa lingua esatta con sintassi diversa". Anche altri linguaggi .NET (IronPython, F #, qualsiasi cosa) sono diversi a livello di AST.

Stessa cosa con i linguaggi JVM, hanno tutti lo stesso target bytecode, ma i costrutti del linguaggio sono diversi, rendendoli linguaggi diversi e diversi AST.

Anche i linguaggi 'thin layer', come CoffeScript e Xtend condividono molto la teoria dei linguaggi sottostanti (JavaScript e Java, rispettivamente); ma introduce concetti di livello superiore che sono (o dovrebbero essere) mantenuti a livello di AST.

se Xtend potesse essere ricostruito da un AST Java, penso che sarebbe stato definito come un uncompiler Java-to-Xtend che crea magicamente astrazioni di livello superiore dal codice Java esistente, non credi?

    
risposta data 11.11.2011 - 15:05
fonte

Leggi altre domande sui tag