Compilerbau

[gizno82]

Hallo Leute,

Sehe ich das richtig, dass man einen Syntaxbaum nach der Wertigkeit der Operatoren der festgelegten Grammatik aufbaut ?
sprich: 2*5+3 = Punkt vor Strich Prinzip, * wäre die Würzel des Baumes, 2 geht links davon weg, 5 rechts davon. + geht
von der 5 weg und die 3 geht vom + als Blatt weg.
Ist der Baum richtig aufgebaut ?

Wozu braucht man beim Compilerbau eine Statemachine und welche Statemachine nutzt man ?

Grüße

gizno

[Xin]

Sehe ich das richtig, dass man einen Syntaxbaum nach der Wertigkeit der Operatoren der festgelegten Grammatik aufbaut ?

Richtig.

sprich: 2*5+3 = Punkt vor Strich Prinzip, * wäre die Würzel des Baumes, 2 geht links davon weg, 5 rechts davon. + geht
von der 5 weg und die 3 geht vom + als Blatt weg.
Ist der Baum richtig aufgebaut ?

Nein. Punktrechnung vor Strichrechnung bedeutet gewissermaßen, dass man die Punktrechnung vor der Strichrechnung klammert: (2*5)+3. Du trennst also die Punktrechnung erstmal nicht auf.
Die Klammern beschreiben zusammengehörige Blätter. Komplett wäre das [ [(2)*(5)] + (3) ], wobei die äußerste Klammer die Wurzel repräsentiert. Klammern für Operatoren habe ich hier mal eckig gemacht. Die Aufgabe ist mathematisch gleichwertig, die Klammern beschreiben aber jetzt die Rechenvorschriften, die man in der Grundschule automatisch lernt. Die Werte der Zahlen sind am einfachsten zu ermitteln: durch Ablesen.

Dein Baum sieht also so aus:

Code: Alles auswählen

        +
      /   \
     *      3
   /  \
  2    5

Um den Baum auszurechnen, fragt Du den Wert der Wurzel ab. Um + auszurechen, fragst Du den Wert links und rechts ab und addiert diese. Der Wert links ergibt sich aus der Multiplikation aus dem Produkt der Kinder. Diese sind einfach zu Berechnen. Um das linke Kind von + zu berechnen wird also erst multipliziert: Punktrechnung vor Strichrechnung.

Du siehst: im eigentlichen Compilerbaum musst Du Dich nicht mehr um Prioritäten von Operatoren kümmern. Dein Vorschlag

Code: Alles auswählen

        *
      /   \
     2      5
               \
                 +
                   \
                    3

ermöglicht es nicht einfach zu fragen, welchen Wert ein Kind hat. (2) hat den Wert 2. Aber was hat 5 \ + \ 3 für einen Wert und wie rechne ich das in die Multiplikation ein?

Also kommen wir nochmal zur ursprünglichen Frage zurück:

Sehe ich das richtig, dass man einen Syntaxbaum nach der Wertigkeit der Operatoren der festgelegten Grammatik aufbaut ?

Der Operator mit der stärksten Bindung (Punkt vor Strich) findet sich tief im Baum, damit er bevorzugt abgearbeitet wird. Der Operator mit der niedrigen Bindung, findet sich näher an der Wurzel.

Wozu braucht man beim Compilerbau eine Statemachine und welche Statemachine nutzt man ?

Was verstehst Du unter einer Statemaschine?

Du kannst den Compiler als Statemaschine verstehen, welcher sich in unterschiedlichen Kontexten unterschiedlich verhalten kann. Im Status "Klassendefinition" wäre das Statement "break" in C ungewünscht - im Status "Befehlspaket einer while-Schleife" hingegen ist "break" akzeptabel.

Oder Du kannst die CPU als Statemaschine verstehen. Die CPU kann (muss nicht) ein Ziel für eine Übersetzung sein.

[Panke]

Bei (LA)LR(x)-Parsern wird die Kontrolleinheit in der Regel als endlicher Automat dargestellt.
Realisiert wird dies häufig über Sprungtabellen. Ich kann dir dieses Buch
sehr ans Herz legen. Da steht alles was man über Parser wissen kann und ist sehr verständlich
erklärt.

[Xin]

@Panke: Kennst Du auch ein interessantes Buch, was sich mit der semantische Analyse beschäftigt? Parserbau ist schließlich nur die erste Stufe im Frontend eines Compilers. Dahinter fängt es an interessant zu werden und wird selbst das berühmte Drachenbuch eher schweigsam.

[Panke]

Habe kein gutes Buch zu diesem Thema gelesen. Das Drachenbuch wird meiner Meinung aber
auch stark über Wert verkauft. Wo ich mal reinschauen will ist Principles Of Program Analysis

Program analysis concerns static techniques for computing reliable approximate information about the dynamic behaviour of programs. Applications include compilers (for code improvement), software validation (for detecting errors in algorithms or breaches of security) and transformations between data representation (for solving problems such as the Y2K problem). This book is unique in giving an overview of the four major approaches to program analysis: data flow analysis, constraint based analysis, abstract interpretation, and type and effect systems. The presentation demonstrates the extensive similarities between the approaches; this will aid the reader in choosing the right approach and in enhancing it with insights from the other approaches. The book covers basic semantic properties as well as more advanced algorithmic techniques. The book is aimed at M.Sc. and Ph.D. students but will be valuable also for experienced researchers and professionals.

Das empfiehlt der Prof, der hier Software Reengineering liest. Der baut damit aber keine Übersetzer, sondern Analyse- und Transformationswerkzeuge.

[Xin]

Klingt interessant, wenngleich es schon was älter ist.

Ich glaube, das lasse ich mir beizeiten mal kommen. Danke für den Tip

[Panke]

Angeblich kam 2004 noch eine zweite Auflage raus. Habe ich aber auf Amazon nicht gefunden.