Un Abstract Syntax Tree è una struttura dati che utilizza la struttura per eliminare la parentesi e altri dettagli della rappresentazione testuale.
La precedenza degli operatori , una caratteristica significativa della rappresentazione testuale, è, nell'AST, codificata nella struttura dell'albero: mentre in forma testuale la precedenza degli operatori è codificata utilizzando le regole di priorità dell'operatore insieme alla parentesi per sovrascrivere (o anche per enfatizzare) le regole standard.
Tradurre da AST di nuovo alla rappresentazione testuale è una forma di generazione di codice, o, alcuni potrebbero chiamarlo piuttosto stampa.
Ingenuamente, dovresti generare tutte queste operazioni binarie racchiuse testualmente all'interno di () se non disponevi dell'ottimizzazione corretta per eliminarle o della comprensione della precedenza degli operatori della grammatica testuale.
Quindi, il tuo primo esempio di albero, genererebbe in modo ingenuo:
( ( a + ( b / c ) ) + d )
che, quando ottimizzato per la precedenza degli operatori comuni, consentirebbe la rimozione di tutte le parentesi.
Il più interessante del mazzo è in basso a sinistra, perché richiede () nella rappresentazione testuale che non può essere eliminata. Tuttavia, nella forma ad albero AST, come al solito, non sono richiesti () ; la precedenza sovrascrive di () nella rappresentazione testuale per far sì che l'addizione avvenga prima che la moltiplicazione sia ora inerente e implicita nella struttura dell'albero e quindi non è richiesto esplicitamente () nel modulo AST.
Dai un'occhiata a (E) BNF , che è un modo comune di codificare un grammatica (come testo). Vedi anche ANTLR , che è uno strumento generatore di parser in grado di analizzare LL (*) grammatiche (che sono più potenti di LALR (1) e LL (k) grammatiche.
Una grammatica dell'ETF è un'espressione della grammatica un po 'ristretta in cui ci sono livelli limitati di precedenza degli operatori, e in particolare solo sufficienti livelli di precedenza per consentire all'addizione di avere precedenza più bassa rispetto alla moltiplicazione insieme a () permesso di sovrascrivere (o enfatizzare ) la precedenza. ETF, espressione, termine, fattore , sono effettivamente i tre livelli. Nota che F ammette ( E ) , ovvero F (precedenza alta) consente e qualsiasi E (bassa precedenza) circondato da () , che consente a () di sovrascrivere (es. precedenza dell'espressione contenuta relativa all'espressione di contenimento.
Facciamo anche una distinzione tra alberi di analisi e alberi di sintassi astratti. Parse Trees (ovvero gli alberi di sintassi del calcestruzzo) manifestano più nodi corrispondenti alla sintassi di input, ovvero le produzioni effettivamente riconosciute nella grammatica per un dato testo di input nel languge. Quindi per l'espressione in basso a sinistra, avresti un nodo () nell'albero immediatamente sopra l'operatore + (per non parlare di molte altre cose). Al contrario, nella forma AST, questi dettagli testuali sono soppressi.
