Token -> AST

[Hi]

Hallo,

ich versuche jetzt seit Tagen verzweifelt aus Tokens (entstanden aus leichtem Pascal Sourcecode) einen AST aufzubauen...

Das Problem ist, dass Pascal Source natürlich als Argument bei einem Funktionsaufruf wieder einen Funktionsaufruf zulässt...
-> Ich brauche definitiv Rekursion

Ich hab aber keine Ahnung wie ich den Parser aufbauen soll Alle meine Versuche enden in einem endlos komplizierten, nicht schön programmierten, nicht allgemein anwendbaren, und nicht funktionierenden Wirwarr

Das Tutorial zum Interpreterbau hab ich schon gesehen (ohne ein Zuweisungsstatement, ist es ja auch leicht einen Parser zu bauen, sobald aber Funktionsaufrufe und Zuweisungen im geparsten Text sind wirds kompliziert )

Ich hoffe ihr könnt mir z.B. mit Pseudocode helfen

[Skym0sh0]

Hä?

Abstrakte Syntax Bäume bauen auf formalen Sprachen und damit auf Grammatiken auf. Bei denen ist die Rekursion nicht nur der stärkste sondern auch einzigste Weg Wiederholungen darzustellen oO.

Und wenn du das programmierst bist du mit normalen Schleifen so mies bedient, dass dus gleich lasssen kannst.Aber ich versteh nicht ganz was dein Problem jetzt ist, dafür hast du zu wenig Infos da gelassen.

[Hi]

Also ich hab ein vector<Token> und muss daraus einen AST machen, Die Tokens könnten z.B. sein:

Tokens[0] (Name: "i", Type: Identifier)
Tokens[1] (Name: "=", Type: Symbol)
Tokens[2] (Name: "2", Type: Number)
Tokens[3] (Name: "*", Type: Operator)
Tokens[4] (Name: "14", Type: Number)

und ich muss daraus jetzt einen AST, hier die bildliche Darstellung:

Assignment
| |
i Multiplikation
| |
2 14

aufbauen. Das war allerdings ein leichtes Beispiel, schwieriger wirds bei Tokens, die aus einem Sourcecode sind, bei dem beim Aufrufen einer Funktion, als Parameter wieder der Rückgabewert einer anderen Funktion genutzt wird...

Ich brauch ein Beispiel (am besten sogar Pseudocode), weil ich absolut keine Ahnung habe wie ich das am besten mache Ich hab es jetzt schon öfters versucht, immer waren aber Fehler im "Konzept", sodass das Programm, eine Ansammlung von Ausnahmen war

Danke an alle

[Ethon]

http://en.wikipedia.org/wiki/LL_parser

Informier dich zuerst über Compiler-/Parserbau, sonst wird das nichts.

[jjjjjjjjjj]

Ich kann dein Problem nicht nachvollziehen. Auch die Aussage, dass Funktionsaufrufe und ähnliches es schwieriger machen einen AST zu erstellen, kann ich nicht nachvollziehen. Denn die Theorie dahinter bleibt absolut die gleiche.

Das einzige was passen muss ist die Grammatik und die daraus abgeleitete Klassenhierachie.

[Hi]

Sorry, das ich mich irgendwie unverständlich ausgedrückt habe:

Ich möchte aus einem Pascal Sourcecode, den mein Programm einliest ein AST machen. Das Tokenizen (also in Tokens zerlegen) funktioniert wunderbar! Da jedes Programm, aber so eine Art Konzept haben sollte, und nicht eine Ansammlung von If-Abfragen, brauch ich so eine Art Grundlegendes Konzept, wie ich die Tokens zu einem AST zusammenbekomme...

Ich hoffe ihr könnt mir sagen, wie ich den Parser strukturieren sollte
Ich hoffe ich habe mich jetzt verständlich ausgedrückt

[fghfghfgh]

Hi schrieb:

Sorry, das ich mich irgendwie unverständlich ausgedrückt habe:

Ich möchte aus einem Pascal Sourcecode, den mein Programm einliest ein AST machen. Das Tokenizen (also in Tokens zerlegen) funktioniert wunderbar! Da jedes Programm, aber so eine Art Konzept haben sollte, und nicht eine Ansammlung von If-Abfragen, brauch ich so eine Art Grundlegendes Konzept, wie ich die Tokens zu einem AST zusammenbekomme...

Ich hoffe ihr könnt mir sagen, wie ich den Parser strukturieren sollte
Ich hoffe ich habe mich jetzt verständlich ausgedrückt

Es gibt im Magazin 2 gute Artikel zum Thema Interpreterbau bzw. Compilerbau. In mindestens einem wird ein AST beschrieben.

Wenn du das nicht auf deine Situation umsetzen kannst, dann fehlt es dir eindeutig an Grundlagen und dann solltest du erst mal diese auffrischen.

Wie sieht denn deine Grammatik aus? Oder baust du das nach Lust und Laune?

[Hi]

Wie ich bereits geschrieben habe, wird in dem Artikel zwar ein AST beschrieben, jedoch ist dieser so simpel, das das Konzept auf dem er baut (ich les mal das nächste Zeichen ein und schreib das in eine Node) nicht funktioniert, wenn man komplexere Strukturen wie Zuweisungen hat...
Wie bereits gesagt, die Grammatik ist von Pascal übernommen

[mcko]

Um sowas umsetzen zu können muss man Informatik studiert haben. Das kann ein Otto-Normal Progger nie und nimmer hinbekommen!

[fghfghfgh]

Hi schrieb:

Wie ich bereits geschrieben habe, wird in dem Artikel zwar ein AST beschrieben, jedoch ist dieser so simpel, das das Konzept auf dem er baut (ich les mal das nächste Zeichen ein und schreib das in eine Node) nicht funktioniert, wenn man komplexere Strukturen wie Zuweisungen hat...
Wie bereits gesagt, die Grammatik ist von Pascal übernommen

Je nach Grammatik muss es einfach möglich sein, dass man ein Token im voraus lesen kann. Und dann ist das auch kein Problem mit dem AST.

Ich sehe echt das Problem nicht. Wenn du auf einen Identiefer triffst, dann hast du aufjedenfall schon mal ein Node für den Identifier.

NodeIdent(i)

Wenn du dann auf ein = triffst, hast du eben eine Zuweisung und zwar vom vorher eingelesenen Identifier.

NodeAssignment(NodeIdent(i))

Was dann folgt ist ein Ausdruck. Das sieht dann letztendlich so aus:

NodeAssignment(NodeIdent(i), NodeExpression(NodeOp(*), NodeNumber(12), NodeNumber(14))

Und wenn man die entsprechenden Nodes hat, kann das in C++ auch manuell so angelegt werden:

Node *root = new NodeAssignment(new NodeIdent("i"), new NodeExpression(new NodeOp("*"), new NodeNumber(12), new NodeNumber(14));

root->Evaluate(); // Oder was auch immer

Und ein Funktionsaufruf kann eben auch ein Ausdruck sein...
Was du also brauchst ist:

struct NodeAssignment : public Node
{
 NodeIdent *ident;
 NodeExpr *expr;

 // ...
};

struct NodeExpr : public Node
{
 NodeOp *op;

 struct NodeExpr *left;
 struct NodeExpr *right;

 // ...
};

// ...