AST aufstellen und ausgeben

jkallup

Erfahrenes Mitglied
Hallo,
ich erhalte immer einen segfault bei printAST.
Ziel ist es, einen AST aufstellen, und diesen durchsuchen.
Hier den aktuellen Code:

Danke für Hilfe

Code:
enum enumStaticType {
    CHAR,
    SHORT,
    INT,
    LONG,
    stFLOAT,
    DOUBLE,
    ARRAY
};
class dBaseClass;
class Statement;

class StaticType {
public:
    StaticType() {}
    ~StaticType() {}
   
    enumStaticType staticType;
    QVariant value;
};
class Expression: public StaticType {
public:
    Expression() { }
    ~Expression() { }
    Expression * left;
    Expression * right;
   
    dBaseClass * nextStmt;
};
class Assignment {
public:
    Assignment() { }
    ~Assignment() { }
    QString variableName;
    Expression * rvalue;
};
class Statement {
public:
    Statement() { }
    ~Statement() { }
    Assignment * op_assign;
};
class dBaseClass {
public:
    dBaseClass() { }
    dBaseClass * next;
   
    Assignment * op_assign;
};


void printAST(dBaseClass * head)
{
    dBaseClass * current = head;
    while (current != nullptr) {
        current = current->next;
        qDebug() << current->op_assign->variableName;
       
        if (current == nullptr)
        break;
    }
}
void pushAST(
    dBaseClass * head,
    enumClassType type,
    QString vname,
    float vfloat)
{
    dBaseClass * current = head;
    while (current->next != nullptr) {
        current = current->next;
    }

    current->next = new dBaseClass;
   
    if (type == enumClassType::ctAssign) {
        auto *ptr = current->next->op_assign = new Assignment;
        ptr->variableName = vname;
        auto *num = ptr->rvalue = new Expression;
        num->staticType = enumStaticType::stFLOAT;
        num->value = vfloat;
        num->left = nullptr;
    }
   
    current->next->next = nullptr;
}

void testAST()
{
    // -----------------------------------
    // init rootAST ...
    // -----------------------------------
    dBaseClass * rootASTstmt = nullptr;
    rootASTstmt = new dBaseClass;
    rootASTstmt->next = new dBaseClass;
    rootASTstmt->next->next = nullptr;

    pushAST(rootASTstmt,ctAssign,"Test1", 21.44);
//    pushAST(rootASTstmt,ctAssign,"22Test22", 121.144);

    printAST(rootASTstmt);
}
 
ich erhalte immer einen segfault bei printAST.
void printAST(dBaseClass * head)
{
dBaseClass * current = head;
while (current != nullptr) {
current = current->next;
qDebug() << current->op_assign->variableName;

if (current == nullptr)
break;
}
}
current != nullptr garantiert dir, dass current->next erreichbar ist. Aber danach greifst du auf current->next->op_assign zu. Und current-> next kann ja nullptr sein.

Davon abgesehen: Du solltest den Konstruktor erweitern, nicht nach Konstruktion noch manuell next auf 0 setzen...

Ein Parser ist übrigens ein ziemlich ambitioniertes Projekt. Machst du es zu Trainingszwecken? Ansonsten würde es sich lohnen, die Lexer/Parser-Kombination Flex/Bison zu nutzen.

Gruss
cwriter
 
Hallo cwriter,

ich teste gerade Parser, ja. Wobei ich daran gedacht habe, selbst eine Template Lib zu basteln, die aber nicht so gewaltig ist wie BOOST. Flex/Bison habe ich schon getestet. diese sind zwar gut - aber wie heißt es: "Respekt, wer's selber macht" :)

Danke für Deine Tipps.
 
So, habe ich jetzt abgeändert.
Aber es gibt immer noch einen Crash, wenn ich das zweite Element pushe.

Code:
void printAST(dBaseClass * head)
{
    dBaseClass * current = head;
    while (current != nullptr) {
        if (current->next == nullptr)
        break;
       
        current = current->next;
        qDebug() << current->op_assign->variableName;
    }
}
 
So, ferdsch, habe eine Lösung gefunden.
Ok, man kann das natürlichet weise auch anders machen, aber zum lernen reicht dies hier:
obwohl, wenn ich's mir näher anschaue - die Sache mit dem "current" Array - dort können doch dann im späteren Verlauf Labels bzw. Sprungmarken sein, an denen man mit JMP ode so hinhüpfen kann.
Mal überlegen ...

Code:
void printAST(dBaseClass * head)
{
    dBaseClass * current = head;
    while (current != nullptr) {
        if (current->next == nullptr)
        break;
       
        current = current->next;
        qDebug() << current->op_assign->variableName;
    }
}
dBaseClass * pushAST(
    dBaseClass * head,
    enumClassType type,
    QString vname,
    float vfloat)
{
    dBaseClass * current = head;
    while (current->next != nullptr) {
        current = current->next;
    }

    current->next = new dBaseClass;
   
    if (type == enumClassType::ctAssign) {
        auto *ptr = current->next->op_assign = new Assignment;
        ptr->variableName = vname;
        auto *num = ptr->rvalue = new Expression;
        num->staticType = enumStaticType::stFLOAT;
        num->value = vfloat;
        num->left = nullptr;
    }
   
    current->next->next = nullptr;
    return current->next;
}

void testAST()
{
    // -----------------------------------
    // init rootAST ...
    // -----------------------------------
    dBaseClass * rootASTstmt = nullptr;
    dBaseClass * current[4];
   
    rootASTstmt = new dBaseClass;
    rootASTstmt->next = new dBaseClass;
    rootASTstmt->next->next = nullptr;

    current[0] = pushAST(rootASTstmt,ctAssign,"Test1", 21.44);
    current[1] = pushAST(current[0],ctAssign,"AATestCC", 121.144);
    current[2] = pushAST(current[1],ctAssign,"22Test22", 121.144);

    printAST(current[0]);
}
 
gerade festgestellt - neues Problem - wie macht man das nochmal mit links und rechts?
links die kleinen, rechts die großen Expressionen ?
wie verdrated man das vernüftig?

Code:
enum enumMathCommand {
    ncMUL
};
enum enumClassType {
    ctAssign,
    ctAssignADD,
    ctAssignSUB,
    ctAssignMUL,
    ctAssignDIV
};


enum enumStaticType {
    CHAR,
    SHORT,
    INT,
    LONG,
    stFLOAT,
    DOUBLE,
    ARRAY
};
class dBaseClass;
class Statement;

class StaticType {
public:
    StaticType() {}
    ~StaticType() {}
   
    enumStaticType staticType;
    QVariant value;
};
class Expression: public StaticType {
public:
    Expression() { }
    ~Expression() { }
   
    Expression * left;
    Expression * right;
   
    enumMathCommand command;
    dBaseClass * nextStmt;
};
class Assignment {
public:
    Assignment() { }
    ~Assignment() { }
   
    enumClassType command;
    QString variableName;
    Expression * rvalue;
};
class Statement {
public:
    Statement() { }
    ~Statement() { }
    Assignment * op_assign;
};
class dBaseClass {
public:
    dBaseClass() { }
    dBaseClass * next;
   
    Assignment * op_assign;
};


void printAST(dBaseClass * head)
{
    dBaseClass * current = head;
    while (current != nullptr) {
        if (current->next == nullptr)
        break;
       
        current = current->next;
        qDebug() << current->op_assign->variableName;
    }
}
dBaseClass * pushAST(
    dBaseClass * head,
    enumClassType type,
    QString vname,
    QVariant prop1,
    QVariant prop2)
{
    dBaseClass * current = head;
    while (current->next != nullptr) {
        current = current->next;
    }

    current->next = new dBaseClass;
   
    if (type == enumClassType::ctAssign) {
        auto *ptr = current->next->op_assign = new Assignment;
        ptr->variableName = vname;
        auto *num = ptr->rvalue = new Expression;
        num->staticType = enumStaticType::stFLOAT;
        num->right = new Expression;
        num->right->value = prop1;
        num->left = nullptr;
    }   else
    if (type == enumClassType::ctAssignMUL) {
        auto *ptr = current->next->op_assign = new Assignment;
        auto *num = ptr->rvalue = new Expression;
        num->command = ncMUL;

        if (prop1.canConvert<float>())
        {
            if (prop2.canConvert<float>()) {
               
                float p1 = prop1.toFloat();
                float p2 = prop2.toFloat();
               
                qDebug() << p1;
                qDebug() << p2;
               
                num->left  = new Expression;
                num->right = new Expression;
               
                if (p1 < p2) {
                    num->left ->value = p1;
                    num->right->value = p2;
                }   else {
                    num->left ->value = p2;
                    num->right->value = p1;
                }
            }
        }
    }
   
    current->next->next = nullptr;
    return current->next;
}

void testAST()
{
    // -----------------------------------
    // init rootAST ...
    // -----------------------------------
    dBaseClass * rootASTstmt = nullptr;
    dBaseClass * current[10];
   
    rootASTstmt = new dBaseClass;
    rootASTstmt->next = new dBaseClass;
    rootASTstmt->next->next = nullptr;

    current[0] = pushAST(rootASTstmt,ctAssign,"Test1", 21.44,0);
    current[1] = pushAST(current[0],ctAssignMUL,"kk",2.2,2);
    current[2] = pushAST(current[0],ctAssignMUL,"kk",0.3,1);
    current[3] = pushAST(current[1],ctAssign,"AATestCC", 121.144,0);
    current[4] = pushAST(current[2],ctAssign,"22Test22", 121.144,0);

    printAST(current[0]);
}
 
links die kleinen, rechts die großen Expressionen ?
Bitte was?

Falls du das Problem ansprichst, wie man eine Expression am besten auflöst, also am wenigsten Register braucht, dann gilt die Formel für die Anzahl benötigter Register ab jeder Node:

depth(left) == depth(right) => depth(left) + 1
depth(left) != depth(right) => max(depth(left), depth(right))

(Oder zusammengefasst: max(depth(left), depth(right)) + (depth(left) == depth(right) ? 1 : 0)

D.h. man sollte immer die grössere Seite zuerst rechnen, sonst brauchst du im schlimmsten Fall für jede Expression ein Register. Dafür musst du aber naturlich zuerst alle Nodes besucht haben (siehe Visitor Pattern).

Falls du die Operator Precedence von * / vor + - meinst: Das sollte der Parser eigentlich schon gelöst haben und sollte nicht auf AST-Ebene behandelt werden. Da ich bei dir keinen Parser sehe, nehme ich an, dass du direkt den AST baust, der dann halt den Regeln eines fiktiven Parsers folgen muss.

Ach, ich zeige mich einfach mal wieder sozial inkompetent:
Einen Compiler zu bauen ist keine leichte Aufgabe, selbst wenn man das klare Konzept von Lexer -> Parser -> AST -> bereinigter AST -> Symbol Table -> IR -> Compiler einhält.

Wenn du den Parser selbst machen willst, dann musst du Konzepte wie Grammatiken verstehen, den Unterschied der verschiedenen Parserfamilien (LR(n) / LALR / ...) kennen und dich für einen entscheiden. Dann den Parser selbst bauen (das alleine ist keine ganz so leichte Aufgabe - es gibt einen Grund, weshalb es ausser Flex/Bison und ANTLR fast keine Parser gibt).

Und was du machst, sieht eher nach ein bisschen Durchprobieren aus. Das kann so nicht funktionieren jedenfalls nicht auf lange Sicht.

Warum nutzt du nicht erstmal Flex/Bison und bekommst damit einen schönen AST, den du dann weiterbearbeiten kannst? Wenn du unbedingt alles selber gemacht haben willst, kannst du den Parser ja später ersetzen, aber um Himmels Willen, mach dir ein Konzept. Und mach keine if-Unterscheidungen, sondern ein Visitor Pattern, ich garantiere dir, dass du sonst kein Land sehen wirst.

Gruss
cwriter
 
Hallo cwriter,

ich habe mal so auf die Schnelle eine kleine visitor Klasse(n) erstellt.
Es funktioniert sehr einfach, Danke für den Hinweis auf "Visitor Pattern".
Mal angenommen, ich habe eine Schleife oder eine IF ELSE ENDIF Anweisung,
wie schreibt man das dann?
Rechts - Links? oder
Links - Rechts?

Letzteres (ohne es gestetet zu haben) läuft alles scheinpaar Zeilenweise, da ich das Ganze in einen Vector untergebracht habem, um so besser die Anzahl Kommandos zu Zählen.

Im Anhang der Code.
Danke für weirere Hilfe.

Update: Irgendwie geht das Datei-Hochladen niicht, deshalb hier der Link für meinen GIT Account:
https://github.com/paule32/dBaseReloaded

und siehe da in mainwindow.cc Zeilen 92 ff.
 
Zuletzt bearbeitet:
Mal angenommen, ich habe eine Schleife oder eine IF ELSE ENDIF Anweisung,
wie schreibt man das dann?
Rechts - Links? oder
Links - Rechts?
Äh...

Letzteres (ohne es gestetet zu haben) läuft alles scheinpaar Zeilenweise, da ich das Ganze in einen Vector untergebracht habem, um so besser die Anzahl Kommandos zu Zählen.
Äh...

und siehe da in mainwindow.cc Zeilen 92 ff.
Äh...

Ehrlich gesagt habe ich keine Ahnung, was du in der Gegend herumbastelst.
Also einmal das Beispiel von while:
Normalerweise gibst du dem Parser (den du nicht hast...) eine Syntax vor. Für while wäre das:
Code:
while: "while" "(" expr ")" statement_block

statement_block: "{" statement* "}" | "statement"

expr = ... //Das wäre viel zu viel, um es jetzt hinzuschreiben...

Dann bekommst du vom Parser deiner Wahl eine Struktur, die vielleicht "WhileContext" heisst. Dann baust du dir deinen Visitor, hier z.B. einen "AstVisitor", mit einer Memberfunktion "visitWhileContext", die als Argument einen WhileContext nimmt.

Dann gibt der der Parser schon die Expression und den Statement-Block als member des WhileContext, z.B. mit: WhileContext::expr() und WhileContext::stmt_block(). Diese Member sind selbst ExprContext / Statement_blockContext - Typen, also kannst du etwa so eine Funktion schreiben:
C++:
AstElement* AstVisitor::visitWhileContext(WhileContext* ctx)
{
    return new AstWhileStatement(visit(ctx->expr()), visit(ctx->stmt_block()));
}
Das alles ist nur grob umrissen, aber es sollte dir eine Idee geben.
Was genau meinst du jetzt mit links und rechts bei einem Whilestatement?

"Kommandos" (was auch immer das sein soll. Instruktionen? Zeilen? Zeichen?) zählen willst du ja eigentlich nicht. Falls du auf Zeilen-/Spaltennummern ansprichst: Das ist Aufgabe des Parsers oder des Lexers.

Was du da im Repository hast... So viel Redundanz, was genau soll "unget_char" machen? CPU-Cycles verheizen?

upload_2018-3-23_21-2-41.png


Kannst du das selbst lesen? Ich kann es nicht.

Ich sag dir, wie's ist: Bestenfalls kannst du einen Compiler oder einen Parser bauen. Beides in einem geht nicht.
Wenn du einen Parser bauen willst, musst du einen möglichst generellen Parser bauen. Dann verstehst du auch, wie er funktioniert. Wenn du von Anfang an eine Sprache im Hinterkopf hast, wirst du immer versuchen, einen Shortcut zu nehmen. Und das rächt sich.

Siehst du: Wenn du eine normale Applikation schreibst, und du vertust dich ein bisschen, dann kannst du es recht leicht wieder zurechtbiegen. Bei einem Compiler vertust du dich ein bisschen und du hast entweder Glück und es funktioniert einfach gar nicht mehr oder du hast Pech und es fällt dir nicht auf, bis plötzlich mal etwas nicht funktioniert und du keine Ahnung mehr hast, wo das Problem liegen könnte.

Gute Planung ist immer wichtig, hier aber ganz besonders. Und wenn ich sowas wie "unget_char" sehe, dann ist mir klar, dass du nicht geplant hast.

Ich kann dir natürlich nicht direkt sagen, was du zu tun hast, aber ich werde mich nicht vertieft mit deinem Code befassen. Ich sehe, dass du dich etablierten Lösungen verweigerst, und manchmal mache ich das auch, aber du solltest einsehen, dass du keine Chance hast, einen mit den "Standards" vergleichbaren Parser innert 5 Jahren aus dem Boden zu stampfen.

Gruss
cwriter
 
Zurück