Hi,

zunächst brauchst du für alle (!) Terminale ein Token - bei dir fehlen z.B. die Klammern und das Semikolon. Einige Tokens wie [Expression] sehen eher wie Nichtterminale aus - so weit bist du aber noch gar nicht, die Grammatik kommt später. Für deinen Beispielcode schlage ich folgende Token vor:
if IF
( LPAREN
) RPAREN
true TRUE
{ LBRACK
} RBRACK
int INT
= ASSIGN
; LEND
[Zahlen] NUM(index)
[Bezeichner] ID(index)

Also: Token = Terminal. Der Tokenizer erzeugt aus deinem Code und den genannten Tokens folgende Ausgabe:
IF LPAREN TRUE RPAREN LBRACK INT ID(1) ASSIGN NUM(1) LEND RBRACK

Außerdem entsteht die Bezeichnertabelle mit dem Eintrag "1|x" und die Konstantentabelle mit dem Eintrag "1|10". Wie du schon weißt, brauchst du eine Grammatik, aus der du den Syntaxbaum erzeugst. Beispiel:

Schriftart: TERMINAL, Nichtterminal

Program --> StmtList
StmtList --> Stmt StmtList | [empty]
Stmt --> [empty] | IF LPAREN Expression RPAREN IfBody | Type ID ASSIGN NUM LEND
Expression --> TRUE | FALSE
IfBody --> LBRACK StmtList RBRACK
Type --> INT | BOOL | ...

Daraus kannst du den Ableitungsbaum erzeugen; der sieht so aus:


Du beginnst also beim Startsymbol der Grammatik und zeichnest deinen Weg auf, den du durch die Grammatik zurücklegst. Immer wenn du ein Nichtterminal auflöst, beginnt im Baum die nächsttiefere Ebene. Wenn du aus gegebenem Code keinen Baum erzeugen kannst, liegt ein Syntaxfehler vor. Ist alles in Ordnung, kannst du den Ableitungsbaum optimieren (z.B. das [empty] streichen), sodass daraus der Syntaxbaum entsteht.

Das Ganze geht auch automatisch mit einem "tabellengesteuerten Parser", der überprüft, ob der "Satz zur Sprache gehört", d.h. ob die Tokenfolge mit der Grammatik gebildet werden kann. Da du dich mit Universitätsstoff beschäftigst (sofern du noch nicht studierst), hier die passende Literatur: cs.rochester.edu/u/scott/pragmatics/

Edit: Der Syntaxbaum ist durch die Optimierung relativ unspektakulär:


Interessanter wäre er, wenn es noch einen Else-Zweig gäbe. Dann kannst du beim IF anfangen (Wurzel des Baumes) und machst durch die Auswertung entweder im IfBody oder im ElseBody weiter. Vorteil des Syntaxbaumes: Man kann ihn direkt "ausführen", wie du siehst. Darauf basierend generiert der Compiler seinen Zwischencode, der dann noch optimiert wird.

Die Thematik heißt übrigens Compilerbau (wirst du vermutlich wissen) und ist Stoff des 2. Semesters im Informatikstudium (an anderen Unis vielleicht auch später). Vorher lernt man was über formale Sprachen, weil das fürs Verständnis unbedingt erforderlich ist. Wichtig ist bei allem formalen / (höherem) mathematischen / theoretischen Kram: Nimm nichts als "bekannt" an - es hat meistens eine andere Bedeutung, als du denkst.

RushDen schrieb:

Also Terminale sind die Grundbausteine einer Sprache (beispielsweise If, while, etc.) und Nichtterminale setzen sich aus diesen und/oder aus weiteren Nichtterminalen zusammen.

Stimmt. Die Liste der Grundbausteine (Terminale) heißt auch "Alphabet". In der deutschen Sprache hat jedes Objekt des Alphabets nur ein Zeichen - bei Programmiersprachen ist das anders. Ein "Wort" ist dabei nicht "while", sondern der ganze Programmcode.

Eine Sprache ist eine Menge von Wörtern. Deutsch: "Baum" ist in der Menge der deutschen Sprache, "Kkjabsdk" dagegen nicht. Wann ist ein Wort "in einer Sprache"? Das legt die Grammatik fest. Sie beschreibt, welche Wörter für eine Sprache gültig sind. Dazu definiert sie Regeln, die aus Terminalen und Nichtterminalen bestehen. Nichtterminale müssen durch Anwendung weiterer Regeln ersetzt werden, Terminale bleiben stehen. Gibt es eine Möglichkeit, ein Wort mit den gegebenen Regeln aufzubauen, ist das Wort in der Sprache, sonst nicht.

Formal betrachtet ist die Grammatik der deutschen Sprache erstmal ziemlich primitiv: Es gibt nur einen Regeltyp, der alle Wörter auflistet, ähnelt also eher dem Duden:
START --> Affe
START --> Apfel
START --> Banane
[...]

Daneben gibt es auch die Regel Subjekt - Prädikat - Objekt und natürlich viele weitere. So ist, formal betrachtet, "Ich hacke Holz" ein "Wort" der deutschen Sprache, nur "Haus" aber auch. Beachte die erweitere Bedeutung von "Wort".

RushDen schrieb:

im erzeugten Token nur die ID in der Symboltabelle quasi als Verweiß auf den Eintrag gespeichert

Jop - das macht man zur Verallgemeinerung, damit (z.B.) die Grammatik nicht jede mögliche Zahl als Terminal enthalten muss, sondern einfach "NUMBER". Für einen Compiler ist es ja egal, welche Zahl das ist - hauptsache er weiß, dass es eine ist.

RushDen schrieb:

das Verfahren von dir ist soviel Ich weiß Top-Down-Parsing

Ist es, wie oben gewünscht. Der Parser heißt auch "LL(k)-Parser" (von Links nach rechts mit Linksseitiger Ableitung). Die andere Richtung heißt "LR(k)-Parser" (Li->re mit Rechtsseitiger Ableitung).

RushDen schrieb:

von links nach rechts

...arbeiten beide Parser, siehe oben. Die Ableitung macht den Unterschied.

RushDen schrieb:

Was Ich nicht verstehe, wofür braucht man denn diese empty Knoten?

Die braucht man nicht wirklich - sie gehören laut Definition aber dazu. Korrekterweise heißen sie "Epsilon" (ε), oder "das leere Wort".

Bedenke: Maschinen sind nicht intelligent - sie müssen zwischen "es kommt noch was" und "Eingabe ist zuende" unterscheiden. Entweder führt man ein spezielles Symbol ein, das das Ende markiert, oder die Grammatik regelt das. Beispiel, wenn eine Maschine eine Addition erkennen soll:

Grammatik, in der das ε fehlt:
START --> [0...9] OP
OP --> + START

Ausdruck: 1 + 2 + 5
Der Parser liest und leitet ab: START --> 1 OP --> 1 + START --> 1 + 2 OP --> 1 + 2 + START --> 1 + 2 + 5 OP --> Fehler: Kann OP nicht ableiten

Bessere Grammatik:
START --> [0...9] OP
OP --> + START | ε

Ableitung: START --> 1 OP --> 1 + START --> 1 + 2 OP --> 1 + 2 + START --> 1 + 2 + 5 OP --> 1 + 2 + 5 ε = 1 + 2 + 5, weil ε das leere Wort, also "nix" ist.

PS: In dem unoptimierten Ableitungsbaum oben ist ein kleiner (unwichtiger) Fehler im Zusammenhang mit dem ε. Wenn du alles verstanden hast, kannst du mir jetzt sagen, wo genau und warum. Kleiner Hinweis: Ich habe beim Erstellen schon (aus Gewohnheit) was wegoptimiert.

Edit: Im .NET Framework kannst du live beobachten, wie ein Compiler arbeitet. Hier der Schritt mit dem Syntaxbaum (siehe Screenshot dort): github.com/dotnet/roslyn/wiki/…rted-C%23-Syntax-Analysis

Ich meinte das erste Bild in Post #2 - da ist der Fehler drin.

Genau. Sehr gut