Compiler-Konstruktion: Explizite Parsebäume

Question

Wie kann ein Compiler ohne den Aufbau eines expliziten Syntaxbaums auskommen? Was sind die Vor- und Nachteile der expliziten Syntaxanalysebaumkonstruktion?

Ich weiß, dass Compiler kann Konstruktion ohne explizite Parse-Struktur mithilfe von SDT und Ausführen der Semantik während des Parsing ausgeführt werden. Aber ich möchte die Vorteile und Nachteile der expliziten Syntaxanalysebaumkonstruktion kennen.

Answer 1

Im ein bisschen ein Noob so wenden Sie sich bitte mit mir paitient werden ... thx ...

Aber um Ihre Frage zu beantworten, eine rekursive-anständige Sammlung (ohne Parsing-Baum) nur in die getan werden einfachste Fälle, in denen es keine Vorwärtsreferenzen und ein Symbol gibt, sind nur von dem Punkt ihrer Deklaration und nicht von ihrem gesamten Gültigkeitsbereich gültig.

Offensichtlich wird es nicht mit einer Sprache wie Java arbeiten. Wenn es Referenzen vorwärts gibt, dann sind mindestens zwei Durchgänge erforderlich, und drei Durchgänge werden benötigt, wenn überladene Funktionen darüber hinaus sind, wie es in Java ist (oder wenn du weißt, wie es in weniger als drei ist, dann erleuchte uns bitte) . Zu diesem Zweck erstellen wir einen Syntaxbaum.

Der einfachste Parse Tree-Knoten könnte in etwa so aussehen (Disclaimer: das ist kein echter Code).

package compiler; 
import java.util.ArrayList; 
import scanner.Token; 
import scanner.TokenSet; 

class Production 
{ 
    Token leading;  // the first token in the production 
    int productionID; // a unique integer that identifies the production 
    ArrayList<Production> childNodes; // duh 
    Production mother; // mother node (may be null) 

    public Production (Token leading, int productionID) 
    { 
     this.leading  = leading; 
     this.productionID = productionID; 
     childNodes  = new ArrayList<Production>(); 
    } 

    public void append (Production child) // add a new child node 
    { 
     child nodes.add(child); 
     child.mother = this; 
    } 

    public abstract void build1 (TokenSet follow, TokenSet anchor); // implements pass 1 
    public abstract void build2 .... 

}

aber ein viel stärkerer Ansatz ist es, eine neue Unterklasse auf jeder Produktion abzuleiten und die untergeordneten Knoten als Feldvariablen deklarieren. Wir können dann die productionID eliminieren und stattdessen instanceof checks verwenden. Sie können sogar eine Symbolschnittstelle für eine bestimmte Unterklasse von Knoten implementieren, die ein Symbol definiert und den Knoten direkt in die Symboltabelle einfügt. und eine Produktion, die einen verschachtelten Geltungsbereich definiert, kann auch eine eigene Symboltabelle haben (ich werde das hier nicht tun). Der Punkt ist, dass auf diese Weise sowohl die syntaktische als auch die semantische Analyse in die Parse-Baumstruktur und sogar die endgültige Übersetzung integriert werden können. Der einzige Nachteil ist, diese schrecklichen Java-Schnittstellen: lol:

wir zum Beispiel einen Modula-2-Header-Datei erklären könnte wie:

// i wont bother with imports since this isnt real code 

class DefinitionModule extends Production 
{ 
    Identifier name; 

    ArrayList<ImportClause> importClauses; 
    ArrayList<ExportClause> exportClauses; 
    ArrayList<Production> itemList; // CONST-,TYPE-, & VAR- declarators & function headers 

    public DefinitionModule() // no more productionID 
    { 
     super(lastTokenRead()); // always sits on DEFINITION 
     importClauses = new ArrayList<ImportClause>; 

    } 


    // build() 
    // 
    // DefinitionModule ::= DEFINITION MODULE Identifier ";" {ImportClause}{ExportClause}{HeaderItem} END Identifier 
    // 
    // where HeaderItem ::= ConstDeclarator | TypeDeclarator | VarDeclator | ProcedureHeader. 
    // Identifier, ImportClause, & ExportClause below are all derived from 
    // Production, above 



    public void build (TokenSet follow, TokenSet anchor) 
    { 
     Scanner.getToken(); // skip the DEFINITION 
     Scanner.expectToken(Token.ID_MODULE); // make sure MODULE is there & then skip it 
     name = name.build(new TokenSet(Token.ID_SEMICOLON)); 
     expectToken(Token.ID_SEMICOLON); 
     while (lastTokenRead()==Token.ID_IMPORT || lastTokenRead()==Token.ID_FROM) 
     { 
     ImportClause IC = new ImportClause(lastTokenRead()); 
     importClauses.add(IC.build(new TokenSet(Token.ID_SEMICOLON)); 
     Scanner.expectToken(Token.ID_SEMICOLON); 
     } 

     while (lastTokenRead()==Token.ID_EXPORT) 
     { 
     ExportClause XC = new ExportClause(lastTokenRead()); 
     exportClauses.add(XC.build(new TokenSet(Token.ID_SEMICOLON)); 
     Scanner.expectToken(Token.ID_SEMICOLON); 
     } 

     // etc, etc, etc 
    } 
} 

wenn man es so tun, wird der Compiler selbst bauen um die Merkmale der Sprache und nicht die traditionellen Pässe eines Compilers.

viel glück ...