Compilerbau: Design des Frontends

Algorithmen, Sprachunabhängige Diskussionen zu Konzepten, Programmiersprachen-Design
Panke
Beiträge: 70
Registriert: So Nov 14, 2010 10:47 am

Compilerbau: Design des Frontends

Beitrag von Panke » Fr Mär 16, 2012 4:38 pm

Moin,

da sich hier ja mindestens zwei Leute mit Compilerbau beschäftigen, hoffe ich auf Einsicht(en). Mir fehlt hier eindeutig die Erfahrung.

Und zwar schreibe ich gerade eine Lexer/Parser-Kombination für eine einfache Sprache per Hand. Das ganze ist simpel rekursiv absteigend und am Ende des Tages brauche ich einen AST.

Wie das geht habe ich wohl verstanden. Die Frage ist nun: Wie sollte ich meinen Code aufbauen, sodass ich die Wiederverwendbarkeit des Parsercodes möglichst groß halte. Also z.B. für "schlaueres" Syntaxhighlighting, Indexer etc. verwendet werden kann, ohne einen ganzen AST zu bauen?

clang geht den Weg, dass der Parser Aktions aufruft, wenn er Produktionen verarbeitet. Ich gucke mir das gerade an, bin aber noch nicht sehr viel schlauer. Meine Befürchtung dabei ist, dass ich viel Zustand mit den Aktionen verwalten muss, den der Parser implizit sowieso vorhält.

(Andere) Ideen | Erfahrungen?

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Compilerbau: Design des Frontends

Beitrag von Xin » Fr Mär 16, 2012 5:00 pm

Bei mir ist der Zustand die Programmposition.

Über Syntaxhighlighting habe ich mir auch schon Gedanken gemacht, bin aber zu dem Schluss gekommen, dass ich diesen Part erstmal ausklammere. Was meinst Du mit Indexer?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Panke
Beiträge: 70
Registriert: So Nov 14, 2010 10:47 am

Re: Compilerbau: Design des Frontends

Beitrag von Panke » Fr Mär 16, 2012 5:24 pm

Indexer: Ausgabe aller Funktionen mit Parametern --> Kein Ast nötig dafür.

Naja, der Parser hat als Zustand die Programmposition, klar. Aber wenn ich einen Ast baue und bspw. eine Funktion parsiere, muss ich die enthaltenen Anweisungen dem Funktionsrumpf zuordnen. Wenn man das direkt im Parser macht, geht das halt einfacher als wenn ich alles in Callbacks regeln muss, wie clang das löst. Das ist hier wohl der Preis der Entkopplung.

Ich denke ich baue erstmal einen Akzeptor für die Sprache. Das lässt mich die Entscheidung noch nach hinten schieben.

Benutzeravatar
fat-lobyte
Beiträge: 1398
Registriert: Sa Jul 05, 2008 12:23 pm
Wohnort: ::1
Kontaktdaten:

Re: Compilerbau: Design des Frontends

Beitrag von fat-lobyte » Fr Mär 16, 2012 6:03 pm

Also ich kenn mich ja nicht aus, aber einen Parser hab ich auch mal geschrieben, und der hat beim Auftreffen auf eine Regel eine bestimmte Aktion ausgeführt.

Wie das bei Compilern gemacht wird weiß ich nicht, aber ich stelle mir das so vor:

Du hast eine Art Baumstruktur, wo du deinen Code abspeicherst. Bei jeder gefundenen Regel hängst du das Syntaktische Element (evtl. mit Zeilennummern) in den Baum ein.

Wo hängst du ihn ein? Naja, nachdem du von oben nach unten gehst, weißt du zu jedem Zeitpunkt, in welcher Struktur du dich befindest, denn du kannst bei jeder neuen Struktur den Zustand des Parsers darauf setzen.

Ok, das war jetzt nicht so klar. So stell ich mir Pseodocode für eine C-Funktionsdeklaration vor:

Code: Alles auswählen

function-declaration := return-type unqualified-id  "(" parameter-list ")"
{
    fdecl = new FunctionDeclaration($return-type$, $unqualified-id$, $parameter-list$)
    return fdecl
}

parameter-list := 
    parameter-decl 
    {
        parameter_list = new ParameterList()

        parameter_list.add($parameter-decl$)
        return parameter_list
    }
    | 
    parameter-decl parameter-list
    {
        $parameter_list$.add($parameter-decl$)
        return parameter_list
    }


parameter-decl := parameter-type unqualified-ld
{
    decl = new ParameterDecl(...)
    return decl
}
Bei jeder Regel wird ein Objekt erzeugt, und and die nächsthöhere zurückgegeben. Anschließend hälst du in der obersten Regel ein "FucntionDeclaration" objekt in der Hand, das dann in die Nächsthöhere Regel eingebunden werden kann (z.B. ein Namespace). Am ende hast du einen Baum (z.B.) deinen Namespace mit Funktionsdeklarationen, über die du iterieren kannst:

Code: Alles auswählen

Programm:
  -> Namespace X
    -> Funktion f
      -> Typ int (int, int)
      -> Anweisung 1
      -> Anweisung 2
      -> Anweisung 3
    -> Funktion g
      -> Typ char (int, double)
      -> Anweisung 1
      -> Anweisung 2
    -> Funktion h
      -> Typ double ()
      -> Anweisung 1
      -> Anweisung 2
      -> Anweisung 3
      -> Anweisung 4
      
Macht was davon Sinn? Oder habe ich die Schwierigkeit nicht ganz verstanden?
Haters gonna hate, potatoes gonna potate.

Panke
Beiträge: 70
Registriert: So Nov 14, 2010 10:47 am

Re: Compilerbau: Design des Frontends

Beitrag von Panke » Fr Mär 16, 2012 7:44 pm

Das ist genau das normale vorgehen. Am Ende nennt man diese Baumstruktur dann einen (Abstrakter | Konkreten) Syntaxbaum,
auf englisch Abstract Syntax Tree (AST).

Die Frage ist jetzt: Wie trenne ich den Parser vom Aufbau des Syntaxbaums, wenn ich den Parser für Aufgaben wiederverwenden will, die keinen Ast brauchen und für die daher erst gar kein AST aufgebaut werden soll?

clang macht das, indem es eine Klasse Sema gibt, mit Methoden ala
Sema::ActOnStartNamespaceDef(/* ne menge Parameter */)

Der Parser ruft dann diese Methoden an der entsprechenden Stelle mit geeigneten Parametern auf. Ich habe diesen Ansatz noch nie gewählt und weiß daher nicht, ob sich der Mehraufwand lohnt. Zumal ich auch momentan noch keinen Schimmer habe, wie meine Callbacks denn dann mal Aussehen sollten :-)

Benutzeravatar
fat-lobyte
Beiträge: 1398
Registriert: Sa Jul 05, 2008 12:23 pm
Wohnort: ::1
Kontaktdaten:

Re: Compilerbau: Design des Frontends

Beitrag von fat-lobyte » Fr Mär 16, 2012 8:44 pm

Naja, ist der Unterschied denn so groß?

Das, was ich jetzt (in Hinblick auf Bison) in geschweifte Klammern geschrieben habe, könnte man durch einen Funktionsaufruf ersetzen, und das wäre dann genau das gleiche wie Sema::ActOnStartNamespaceDef, oder nicht?

Im Endeffekt wird dann aus deinem Syntaxbaum ein "Semantischer" (deswegen wohl "Sema"?) Baum, der eingehängt alles was Bedeutung hat enthält.
Zumal ich auch momentan noch keinen Schimmer habe, wie meine Callbacks denn dann mal Aussehen sollten
Na wie sollen die denn schon aussehen? Parameter: Namen, Scope, Zeile, inline oder nicht, ... Aktion: speichere in Baum, merke alles. Gibts da etwa alternativen?
Ich habe diesen Ansatz noch nie gewählt und weiß daher nicht, ob sich der Mehraufwand lohnt.
Das hängt wohl ganz davon ab, wie weit du mit deiner Sprache gehen willst. Schreibst du sie mit einem richtigen "Ziel" (= Verwendungszweck den du jetzt schon weißt), oder eher als Proof-of-konzept, um deine Ideen zu zeigen?
Bei ersterem würde ich mich nicht zu weit aus dem Fenster lehnen, und das Ding erstmal zum Funktionieren bringen.
Bei letzterem wäre es schon gut, wenn du eine gute Repräsentation deiner Programme auch in Code hast! Soweit ich das mitbekommen habe ist der Grund warum Clang gerade so populär wird, dass GCC mit seinen 3 schritten zwischendurch einfach ALLE information wegschmeißt. Deshalb haben sich die Clang Leute dazu entschieden einfach jede kleinste Information bis zum Ende mitzuschleppen - das ist die Philosophie. Nur so kannst du Wiederverwendbarkeit garantieren.
Haters gonna hate, potatoes gonna potate.

Panke
Beiträge: 70
Registriert: So Nov 14, 2010 10:47 am

Re: Compilerbau: Design des Frontends

Beitrag von Panke » Fr Mär 16, 2012 8:53 pm

Vielleicht mache ich mir da wirklich zu viele Gedanken. Einer der Gründe, warum ich das mache, ist überhaupt herauszufinden, wie man das ordentlich macht :-)

Anwendungszweck gibt's im Grunde nicht, reine Übungssache + Modul an der Uni.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Compilerbau: Design des Frontends

Beitrag von Xin » Fr Mär 16, 2012 9:06 pm

Ich schreibe zwar einen Compiler, aber ob Du einen AST brauchst, hängt auch ein wenig von der Sprache ab.
Deswegen fällt mir eine Antwort im Sinne von "Ja" oder "Nein" nicht leicht.

Wenn Du eine typsichere Sprache hast, muss man die Typen ja auch irgendwo festhalten - abhängig vom Namensraum und ob sie an der aktuellen Position überhaupt erreichbar ist. Es bleibt also die Frage, wie ein Indexer auf einen Quelltext reagieren soll, wo Datentypen nicht bekannt sind.

Ich habe mir da eigentlich nie soviele Gedanken drüber gemacht, weil ich für einen Compiler sowieso einen Compilerbaum brauche - ergo sich die Frage gar nicht das zu vereinfachen.

Grundsätzlich kann ich mir durchaus vorstellen, das mit Funktionspointern zu machen. Eine Interfaceklasse, die entweder den Baum erweitert oder klarstellt, dass eine Anweisung aktuell nicht interessiert.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Panke
Beiträge: 70
Registriert: So Nov 14, 2010 10:47 am

Re: Compilerbau: Design des Frontends

Beitrag von Panke » Sa Mär 17, 2012 11:01 am

Um mal die Werbung von Clang zu kopieren:

Bei einem Compiler braucht es nicht den AST des ganzen Programmes, es sei denn man macht Optimierungen über das ganze Programm. Bei Refactoring-Tools braucht man aber genau den => Flexibel sein. Bei uns in der Arbeitsgruppe nutzt einer den gcc um Programme zu analysieren. Geht wohl leidlich gut, zeigt aber dass für den Code eines Compilers durchaus Wiederverwendungsmöglichkeiten bestehen. Gut: Mein Code wird wahrscheinlich nie "fertig" noch wiederverwendet 8-)

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Compilerbau: Design des Frontends

Beitrag von Xin » Sa Mär 17, 2012 12:26 pm

Panke hat geschrieben:Um mal die Werbung von Clang zu kopieren:
Schreibst Du einen C-Compiler?

Ich verstehe derzeit das Problem noch nicht so ganz. Du machst das für einen Schein. Für einen Schein wird man zum einen kein Executable von Dir fordern und zum anderen kein Syntax-Highlighting. Es geht also mehr ums Prinzip?
Was genau willst bzw. musst Du erreichen?
Panke hat geschrieben:Gut: Mein Code wird wahrscheinlich nie "fertig" noch wiederverwendet 8-)
Das hängt ganz von Dir ab.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten