Clean Abstract Syntax Tree

Question

Clean Abstract Syntax Tree

#1 da (2 voti)
#2 da (0 voti)
#3 da (0 voti)
#4 da (-1 voti)

2

Sto scrivendo un compilatore di giocattoli per divertimento.

Fondamentalmente, il mio problema è che non voglio ingombrare l'AST con cose come le informazioni di debug (token simbolici, posizioni dei token, ecc.) così come i dati che l'analizzatore semantico calcola.

Ad esempio, l'analizzatore semantico esegue qualche inferenza di tipo e il tipo di risultato è memorizzato nel tipo di nodo. Sembra qualcosa del genere:

/// A variable declaration in my language looks like this:
/// var x = 10
struct VarDec: Statement {
    var varKeyword: Keyword
    var varName: Id
    var assignment: Symbol
    var initializer: Expr
    var type: Optional<Type>
}

Il problema principale qui è che ora il tipo di nodo ha uno stato, l'inferenza di tipo è stata fatta o meno. Questo rende difficile ragionare. L'altra cosa è che l'intero AST si ingombra di quei token che sono veramente necessari per i messaggi di errore.

È stato suggerito di creare un'altra rappresentazione dell'AST solo per l'analisi semantica che ricollega all'AST ma sembra un sacco di lavoro e codice ridondante ...

Qualcuno ha un'idea di come posso pulire questo codice senza dover creare più alberi?

programming-languages data-structures compiler parsing trees

posta NSAddict 21.07.2015 - 16:00

fonte

4 risposte

Leggi altre domande sui tag programming-languages data-structures compiler parsing trees

Best practice per l'ambito dei dati restituiti per stored procedure Quale stile usare per le funzionalità che non sono guidate direttamente dagli esseri umani quando si utilizza il linguaggio BDD Gherkin?

score 2 · Answer 1

It has been suggested that I could create another representation of the AST just for semantic analysis that links back to the AST but that seems like a lot of work and redundant code...

Non penso che significhi molto lavoro e molto codice ridondante.

L'AST digitato potrebbe contenere principalmente le informazioni sul tipo e un riferimento (ad esempio un puntatore) all'AST sintattico.

Non avrai molto lavoro extra: dovrai comunque calcolare le informazioni sul tipo.

Probabilmente non avrai molti codici ridondanti: ogni nodo AST (quindi ogni tipo di nodo) deve essere elaborato.

FWIW, il compilatore Ocaml e il compilatore GCC hanno diverse rappresentazioni interne (spesso simili ad alberi) del codice sorgente compilato.

Un'alternativa potrebbe essere quella di avere diverse tabelle associative abbastanza grandi che mappano AST sintattico agli attributi calcolati (inclusi i tipi) e li sviluppano progressivamente. Non sono sicuro che sarebbe meglio (e non conosco i compilatori che lo usano, tranne forse alcune implementazioni di Prolog).

score 0 · Answer 2

Il mio consiglio è di mantenere i token come token e, se possibile, eseguire una fase di inferenza di tipo in cui si avvolge ogni nodo in un'altra classe o struttura che ha ha stato.

// Token type struct - immutable
struct VarDec: Statement {
    var varKeyword: Keyword
    var varName: Id
    var assignment: Symbol
    var initializer: Expr
}

// Type-checked token /w state
struct StatementTyped {
    var statement: Statement
    var type: Optional<Type>
}

In questo modo ottieni il meglio da entrambi i mondi.

score 0 · Answer 3

The main problem here is that now the node type has a state, type inference has either been done or not. This makes it hard to reason about.

Solo a una persona il cui cervello è stato danneggiato da un'overdose di Kool Aid, rigorosamente immutabile. Il ragionamento è in realtà abbastanza semplice: se il valore è nullo, si può chiaramente dedurre che l'inferenza di tipo non è ancora stata eseguita. Se il valore non è nullo, si può facilmente dedurre che l'inferenza di tipo ha già eseguita. Dov'è la parte difficile?

Inoltre, a meno che tu non stia eseguendo un rigoroso compilatore a passaggio unico, l'intero AST sarà una massa enorme di stato mutabile, con ogni passaggio perfezionato e semplificando le cose finché non sarai pronto per la generazione del codice.

The other thing is that the whole AST gets cluttered with those tokens that are only really needed for error messages.

I messaggi di errore sono molto importanti per un compilatore. A parte la compilazione del codice funzionante , produrre feedback utili su ciò che il codice sicuramente (errori) o probabilmente (avvertenze) ha sbagliato è la singola cosa più importante che un compilatore può fare e se si fornisce inutile o fuorviante messaggi di errore, i tuoi utenti ti odieranno per questo.

Se si desidera mantenere pulita l'interfaccia delle classi del nodo, tuttavia, una cosa che si potrebbe fare è creare una classe separata per tutti i dati del token. Chiamalo LexicalInfo e memorizzalo come il nome del file, il punto di partenza (riga e colonna) e il punto finale (riga e colonna e le linee potrebbero essere diverse se supporti le stringhe multilinea) di ciascun token.

score -1 · Answer 4

The main problem here is that now the node type has a state, type inference has either been done or not. This makes it hard to reason about.

Lo stato non è così difficile da ragionare sullo stato - mutevole è difficile ragionare.

E non è necessario lo stato mutabile per rappresentare una pre-inferenza e post-inferenza dell'albero di sintassi, è sufficiente un tipo di segnaposto che rappresenta e un'istanza di "un tipo ancora sconosciuto". Quando si esegue l'inferenza, il compilatore restituisce nuovi nodi con le inferenze sostituite con tipi reali.

Questo ti dà il vantaggio di avere più alberi senza il codice che ha più alberi e senza i problemi generali che derivano dallo stato mutabile.