Algoritmo di ordinamento delle dipendenze di un compilatore

Question

Algoritmo di ordinamento delle dipendenze di un compilatore

#1 da (4 voti)

3

Diciamo, ipoteticamente, che sto scrivendo un compilatore Java. E supponiamo che nel mio caso una classe non possa essere compilata fino a quando non saranno note tutte le firme delle dipendenze (importazioni e altre classi utilizzate). Poiché non desidero mantenere contemporaneamente il codice sorgente e AST di tutte le classi in memoria, ho bisogno di un algoritmo per gestire tali dipendenze e elaborarle tutte nell'ordine corretto.

Quale sarebbe un buon algoritmo per ordinare tutte le dipendenze? Quella:

non è ricorsivo
non conserva tutti i codici sorgente e / o gli ast nodi in memoria
è lineare sia nello spazio che nel tempo
può gestire le dipendenze cicliche

O forse più generale, come si fa normalmente?

Il mio approccio è il seguente:

abstract class Compiler {

    TypeSystem ts;


    Type compile(String className) {

        if (ts.containsType(className)) {
            return ts.getType(className);
        }

        // Create skeleton type for this class:
        Type type = ts.createType(className);

        // Parse the class file:
        Node ast = parse(className);

        // Create signature:
        for (Node attribute : ast.findAll("AttributeDeclaration")) {

            // Get the text value of the name of the attribute:
            String attributeName = attribute.find("Identifier").text();

            // Get the text value of the type of the attribute:
            String attributeTypeName = attribute.find("Type").text();

            // Call compile recursive!
            Type attributeType = compile(attributeTypeName);

            type.createAttribute(attributeName, attributeType);
        }

        return type;
    }

    abstract Node parse(String className); // This method can find the file by class name.
}

Per semplicità, questo codice elabora solo attributi e semplici strutture. Nota che questo algoritmo è ricorsivo!

java algorithms dependencies compiler graph

posta Tim 21.09.2015 - 21:20

fonte

1 risposta

Leggi altre domande sui tag java algorithms dependencies compiler graph

Perché aggiornare il modello client prima del modello sever? Come memorizzare correttamente i messaggi in un servizio web?

score 4 · Accepted Answer

Per compilare un file sorgente, non è necessario aver compilato tutte le dipendenze prima di esso. Tuttavia, hai bisogno di qualcosa a cui collegarti: una sorta di interfaccia o intestazione. In linguaggi come Java, questo è abbastanza semplice poiché tutti i tipi definiti dall'utente hanno una semantica di riferimento. La struttura e l'implementazione di un tipo non hanno importanza, ma solo il nome. Pertanto, puoi issare tutti i nomi di tipi che si verificano in una unità di compilazione e le sue dipendenze nella "top".

es. supponiamo di avere due classi in due file separati:

Foo :

class Foo {
  public void frobnicate(Bar b) {
    if (rand) b.frobnicate(this);
  }
}

Bar :

class Bar {
  public void frobnicate(Foo f) {
    if (rand) f.frobnicate(this);
  }
}

Il tipo e la definizione di frobnicate sono reciprocamente ricorsivi. Questo può essere compilato facendo un passaggio iniziale che estrae l'interfaccia di queste classi. L'interfaccia viene quindi referenziata durante la compilazione delle implementazioni effettive in un secondo passaggio. Sebbene questa strategia abbia più passaggi, è ancora lineare e non è necessario conservare l'intero AST in memoria, ma solo le firme del tipo.

Intestazione :

// predeclare type names
class Foo;
class Bar;

// predeclare available operations
class Foo {
  public void frobnicate(Bar); // type Bar is known
}
class Bar {
  public void frobnicate(Foo); // type Foo is known
}

Foo :

#include Header
// implement the pre-declared function
void Foo::frobnicate(Bar b) {
  if (rand) b.frobnicate(this); // method Bar::frobnicate(Foo) is known
}

Bar :

#include Header
void Bar::frobnicate(Foo f) {
  if (rand) f.frobnicate(this);  // method Foo::frobnicate(Bar) is known
}

In lingue come C o C ++, queste dipendenze devono essere risolte manualmente usando tali predeclarazioni. C è stato progettato specificamente per la compilazione a passaggio singolo efficiente in termini di spazio, sebbene questo si traduca in velocità di compilazione poiché tutte le dipendenze dell'intestazione verranno nuovamente analizzate nuovamente per ciascuna unità di compilazione.

Questa strategia di pre-dichiarazione funziona solo per i tipi definiti dall'utente che hanno semantica di riferimento. Se un tipo ha semantica del valore, deve essere completamente definito prima di poter essere utilizzato. Passando a C ++, questo tipo pre-dichiarato Incomplete può essere utilizzato in un tipo Complete poiché la dimensione di un puntatore è nota:

struct Incomplete;

struct Complete {
  Incomplete* thing;
};

Tuttavia, l'incorporamento di un tipo incompleto senza un puntatore non funzionerebbe; il tipo incorporato dovrebbe essere completamente definito per primo.