C-Compiler selbstgeschrieben.

[Rene B. (themason)]

Ich bin schon seit längerem dabei mir Voraussetzungen zu schaffen um 
einen C-Compiler zu schreiben.

Meine Frage ist eher allgemein (daher auch etwas schwammig) gehalten, 
und richtet sich an die Leute die schonmal das "Vergnügen" hatten einen 
C-Compiler selbst zu schreiben.

Habt ihr den kompletten C-Standard (C99 und was es sonst noch gibt) 
implementiert, oder gabs/gibts Teile die ihr weggelassen habt damit der 
Compiler nicht explodiert (also vom Aufwand her), und wenn ja welche 
waren das und warum.

Der C-Standard selbst ist ja schon recht mächtig (selbst wenns "nur" an 
die 40 Grammatik-Vorschriften sind, die aber durch die Rekursion leicht 
den Speicher in 0,nix aufgefressen haben, bzw sehr schwer zu debuggen 
sind)

Ich frage deshalb da ich am überlegen bin, welche Vereinfachungen man 
machen kann ohne die Funktionalität des Compilers zu sehr 
einzuschränken.
Der Programm-Teil für das Auswerten von Ausdrücken ist m.M. der 
schwierigste (zumal die ganzen 
Typen/Typ-Umwandlungen/Zeiger-Operationen/ 
Referenzierungen/Dereferenzierungen denke ich das ganze enorm aufblähen, 
aber an der Stelle nichts weggelassen werden darf).

Habt ihr eine Art Zwischensprache verwendet ? Wenn ja, war/ist das ein 
eigenes Format, oder an die .obj's angelehnt ?

[MaWin (Gast)]

> gabs Teile die ihr weggelassen habt

Alles was mit floating-point-Zahlen zu tun hatte (ja, damals war ich 
noch klein und dumm und traute mir transzendente Funktionen nicht zu, 
heute hab ich Cordic auf Tasche).

> Der Programm-Teil für das Auswerten von Ausdrücken ist m.M. der schwierigste

Wenn dir der bereits Schwierigkeiten macht, solltest du noch mal im 
Informatik-Studium gut aufpassen bevor du anfängst. Ich befürchte, es 
gibt noch viele Dinge, von denen du nicht ahnst, daß sie schwierig 
werden.


Nimm lieber einen bestehenden Compiler als Vorlage den du nur noch 
änderst.
Es muss ja nicht GCC sein, es reicht vielleicht ja TinyC (oh Mann, vor 
20 Jahren war das aber ein andere Tiny als heute).

Sonst: Ich bin kein Freund von YACC, aber wenn du schon so wenig 
durchblickst, setz so ein Compiler-Tool ein, um den ganzen Parserteil zu 
erledigen.

[Karl H. (kbuchegg)]

Rene Böllhoff schrieb:


> Der Programm-Teil für das Auswerten von Ausdrücken ist m.M. der
> schwierigste (zumal die ganzen
> Typen/Typ-Umwandlungen/Zeiger-Operationen/
> Referenzierungen/Dereferenzierungen denke ich das ganze enorm aufblähen,
> aber an der Stelle nichts weggelassen werden darf).


Der Teil ist eigentlich sogar relativ einfach.
Der Syntaxparser baut für einen Ausdruck einen Baum auf (Achtung: Auch 
eine Zuweisung ist ein Ausdruck!)

Der Baum wird zunächst so aufgebaut, wie er geparst wird.

Danach laufen verschiedene Funktionen über den Baum, die ihn 
modifizieren. Als erstes wird das wahrscheinlich eine Funktion sein, die 
bei den Blättern beginnend den Knoten (so sie nicht schon einen haben) 
einen Datentyp zuweist. Ein 'Additionsknoten' erhält zb so den Datentyp 
des 'größeren' seiner Kindknoten (wird ein int mit einem long addiert, 
so kriegt der Additionsknoten den Typ long).

Haben alle Knoten einen Datentypen, so kann die nächste Funktion 
drüberlaufen, die von einem Knoten ausgehend seine Kinder durchforstet 
und Cast Knoten einfügt, wenn sich die Datentypen unterscheiden.
Bei besagtem Additionsknoten wird so in den int Teilzweig ein Cast nach 
long eingebaut.

Und so wird es noch mehrere weitere Funktionen geben, die sich 
verschiedenen Aspekten widmen, diese im Baum identifizieren und durch 
Einfügen und/oder Löschen und/oder Modifizieren von Baum-Knoten 
bearbeiten.

Zum Schluss landet man dann bei einem Baum, der ohne irgendwelche 
Sonderfälle mehr berücksichtigen zu müssen, direkt in die 
Codegenerierung weitergegeben werden kann.

Der Teil ist eigentlich nicht wirklich schwer, weil man im Grunde nur 
die C-Regeln für automatisches Casten anwenden muss. Eher mehr eine 
Fingerübung mit diversen Baumoptimierungen als Zugabe.

>
> Habt ihr eine Art Zwischensprache verwendet ? Wenn ja, war/ist das ein
> eigenes Format, oder an die .obj's angelehnt ?

Ich bau mir am liebsten eine Stackmaschine als Runtime-Unit. Dadurch 
fällt der Teil Register-Allokierung weg und ich kann mir die 'CPU' so 
anpassen, wie ich sie gerne hätte.

[(prx) A. K. (prx)]

Besteht dein Ziel primär darin, einen Compiler vollständig neu zu 
schreiben, oder hat das auch einen konkreten Zweck, eine konkrete 
Zielmaschine?

[(prx) A. K. (prx)]

Eine Zwischensprache mit der du es unweigerlich zu tun kriegst ist der 
Baum, wie schon erwähnt. GCC hat noch eine zweite Zwischensprache, aber 
das muss man sich für einen eher einfach gebauten Compiler nicht 
unbedingt antun und kann den Code direkt aus dem Baum heraus generieren. 
Ein Vorbild dafür kann der zwar uralte aber mittlerweile renovierte PCC 
abgeben, der sehr sehr viel einfacher aufgebaut ist als GCC. Dessen 
Codegenerator ist allerdings eher für registerorientierte Architekturen 
geeignet, für Akkumulator-orientierte Architekturen nicht so.

[Rene B. (themason)]

Erstmal danke für die Infos.

Hatte mich etwas falsch ausgedrückt.

Hätte statt :

>Der Programm-Teil für das Auswerten von Ausdrücken ist m.M. der
>schwierigste

Schreiben sollen :

Ist der Programm-Teil, der die meiste Funktionalität beinhaltet, und 
somit auch die meisten Fälle abdecken muß 
(Casting/Zeiger-Ops/Datentypen).

Mit einem rekursiven Parser bin ich schon recht weit gekommen was das 
Thema Ausdrücke angeht.
Funktionsaufrufe (die im Moment testhalber fest eingebaut sind, wird 
aber über eine Such/Aufbau-Funktion noch erweitert) und Variablen (hier 
auch nur testhalber) können schon verwendet werden. Was noch fehlt sind 
Boolsche Ausdrücke und noch ein paar Operatoren, dann kommen die 
Datentypen und Zeiger-Operationen dran.

@Karl-Heinz

Danke für die hinweise mit dem umsortieren/modifizieren des Baumes.
Im Moment läuft das bei mir so das ich "rekursiv" (später mehr dazu) den 
Text Parse und mir an bestimmten stellen meine Operationen in ein Array 
Wegschreibe.

So wird also aus

"test (time * 4, (half (sqr (1+4*(5+half(4*5))))))" ->

"time 4 * 1 4 5 4 5 * half + * + sqr half test"

in Post-Fix Notation.

Wobei test eine Funktion mit 2 Parametern, sqr und half jeweils einen 
Parametern sind und time eine Variable.

@A.K.

Mein Ziel ist es erstmal ein Grundgerüst zu haben mit dem man 
nicht-optimierten Code für mehrere Prozessoren (oder auch einen 
Byte-Code Interpreter) generieren kann.
Ich bin im moment dabei mir für einen FPGA einen Prozessor zu designen 
und möchte mir offenhalten einen C-Compiler dafür schreiben zu können.
Als "Werkzeuge" habe ich halt den Parser und eben diese 
Ausdrucks-Auswertung. Damit lassen sich u.U. auch andere Sprachen wie 
Pascal/Basic/Eigene Sprachen realisieren, so der Traum :-).
Aber eine konkrete Zielmaschine gibts nicht.

Das ich in Compilerbau nicht so fit bin, liegt daran das die Vorlesung 
schon 12 Jahre her ist :-)). Habe damals die Grundlagen schon 
mitbekommen, aber seit dem ist viel Wasser durchn Rhein geflossen, und 
da ich bisher noch keine Konkrete Anwendung für das Fach Compilerbau an 
der Uni hatte will ich mich mal an einem Compiler versuchen.

[Karl H. (kbuchegg)]

Ach ja:

Die Sprache parsen und dafür plain/vanilla Code zu generieren ist (mit 
einer Stack Maschine) nicht wirklich schwer. Das ist straight-forward.

Richtig schwer wird es dann, wenn Optimierungen gemacht werden sollen, 
die über die einfachsten Formen der Optimierung (Constant-Folding, 
Common Subexpression Elimination, Multiplikationen durch Shift ersetzen, 
Divisionen durch & u. dgl.) hinausgehen. Sobald Optimierungen über 
mehrere Statements bzw. mehrere Funktionen hinweg greifen sollen, wirds 
aufwändig. Mehrere Statements gehen noch, indem man eine Funktion als 
ganzes als einen Baum darstellt, aber darüber hinaus wirds dann schon 
unangenehm.

[Karl H. (kbuchegg)]

Rene Böllhoff schrieb:

> Text Parse und mir an bestimmten stellen meine Operationen in ein Array
> Wegschreibe.

Mit solchen Dingen habe ich am Anfang auch experimentiert. Irgendwann 
bin ich dann aber draufgekommen, dass ich mir viel Kopfzerbrechen und 
Ungemach sparen kann, wenn ich gleich auf einen richtigen Baum gehe und 
mir nicht mühsam Bearbeitungsfunktionen für die Arrays machen muss. Denn 
im Array ist Information schon gut versteckt, die man gerade für die 
Teile die dir jetzt schwer vorkommen gut brauchen kann. Im Baum ist sie 
aber noch direkt vorhanden. Es geht um die Frage: Welche Operation wird 
auf welche Teilausdrücke angewendet?

Die Behandlungsfunktionen werden einfach einfacher, als wie wenn man 
ständig im Array umsortieren und suchen muss.

>
> So wird also aus
> "test (time * 4, (half (sqr (1+4*(5+half(4*5))))))" ->
>
> "time 4  1 4 5 4 5  half + * + sqr half test"
>
> in Post-Fix Notation.

Das ist in meinen Compilern im Grunde dann schon die Ausgabe an die 
Statemaschine, die dieses 'Programm' abarbeitet. Aus einem Baum heraus 
ist es ein Kinderspiel die Post-fix Version zu generieren

[Rene B. (themason)]

@Karl-Heinz

Alles was mit Optimiertug zu tun hat lasse ich außen vor. Mir gehts 
erstmal nur darum das ich C-Code (Ausdrücke, Funktionen, Variablen, 
Schleifen usw) richtig in eine zwischensprache übersetzt bekomme und mir 
diese Zwischensprache als Listing ausgeben kann. Die umsetzung der 
Zwischensprache für die Zielmaschine ist nachher denke ich sehr einfach 
(eben wenn man die ganzen Optimierungsfunktionen weglässt).

[Rene B. (themason)]

Vllt nochmal eine Frage zum Thema rekursiver Abstieg. (hoffe es ist nich 
zu peinlich)

Ist es mittels rekursivem Abstieg möglich C-Code komplett zu durchlaufen 
?
Sprich das wenn ich nach der Grammatik mir einen rekursiven Abstieg 
baue, ich C-Code zumindest syntaktisch und grammatikalisch richtig 
erfassen kann, selbst wenn ich mir keinen Baum erzeuge ?

[Karl H. (kbuchegg)]

Rene Böllhoff schrieb:

> Ist es mittels rekursivem Abstieg möglich C-Code komplett zu durchlaufen
> ?

Ja

Vielleicht nicht ganz in der klassischen Manier, aber machbar ist es.
Das Problemkind ist

 void foo( void ) ;

versus

 void foo( void ) {

erst das abschliessende ';' bzw '{' sagt dir, ob du es mit einer 
Deklaration bzw. einer Definition zu tun hast.

Dementsprechend must du aber auch die Auswertung von Argumenten solange 
verzögern, bis dies feststeht. Im einen Fall wandern Argumente (und ihre 
Datentypen) als Attribute zum Funktionsnamen in die Liste der bekannten 
Funktionen, im anderen Fall erzeugt die Argumentliste die Anweisung zur 
Übernahme der Argumente (vom Stack oder vom Callframe oder wie auch 
immer du das dann machen willst).

Der klassische rekursive Abstieg mit einem Token Vorschau (also eine 
LL(1) Grammatik) kann das aber naturgemäss nicht leisten. Der geht immer 
von der Annahme aus, dass ihn das nächste Input-Token in die richtige 
Richtung weisen wird.

[(prx) A. K. (prx)]

Was den Parser angeht ist C auch sonst nicht so ganz theoriekonform. Zu 
den "netten" Eigenheiten von C gehört es nämlich, dass Informationen aus 
der Symboltabelle in den Parser einfliessen. Typnamen sind Schlüsselwort 
und typedefs sind es auch ein bischen - der Name eines typedefs muss auf 
ein anderes Token kriegen als andere Bezeichner.

[(prx) A. K. (prx)]

Karl heinz Buchegger schrieb:

> Der klassische rekursive Abstieg mit einem Token Vorschau (also eine
> LL(1) Grammatik) kann das aber naturgemäss nicht leisten. Der geht immer
> von der Annahme aus, dass ihn das nächste Input-Token in die richtige
> Richtung weisen wird.

Da sehe ich grad das Problem nicht. Dass es sich um eine 
Deklaration/Definition handelt ist vorne schon bekannt (type oder 
storage class oder sowas vorneweg, siehe eben). Die unterscheiden sich 
syntaktisch vorerst kein bischen und man kann das parsen, ohne zu wissen 
ob es nun Deklaration oder Definition ist.

Wenn das durch ist entscheidet das nächste Token mit ; oder { zwischen 
diesen beiden Varianten. Die Unterscheidung zwischen Variablen mit und 
ohne Initialisierung läuft genauso.

Irgendeine Codererzeugung kommt ohnehin erst viel später.

Richtig haarig wird's erst mit C++.

[Rene B. (themason)]

@Karl-Heinz & A.K.

Nochmals danke für eure Ausführungen. Einfach ist das alles wirklich 
nicht. Das das reine Parsen (abgesehen von der Problematik das bestimmte 
Symbole wie z.b. die typedefs schon "mitgeführt" werden müssen) nicht so 
das Thema ist war mir eig. schon fast klar (daher nochmal die Frage).
Aber ich denke mit dem Wissen das die Baumstruktur die Lösung der 
Probleme ist (selbst wenn ich noch nicht weiß welche Fkt. alle für die 
Baumumsortierung nötig sind), bzw der einzig gescheite Weg ist einen 
C-Compiler zu bauen hilft mir erstmal weiter. Ich schau mir mal den PCC 
an. In den cc65 hab ich schon kurz reingeschaut.

Wenn ich noch weitere Fragen habe weiß ich ja wo ich nachfragen kann ;-P

Nochmals vielen Dank


>Richtig haarig wird's erst mit C++.

Daran denk ich erstmal gar nicht :-)

[Karl H. (kbuchegg)]

A. K. schrieb:

> storage class oder sowas vorneweg, siehe eben). Die unterscheiden sich
> syntaktisch vorerst kein bischen und man kann das parsen, ohne zu wissen
> ob es nun Deklaration oder Definition ist.

Hast recht.
Hab ich mir auch gerade überlegt.
In der Grammatik muss man die beiden parallel führen

  FuncDeklOrDef = dataType Identifier "(" argList ")" ( FuncDekl | FuncDef ).

  FuncDekl = ";".

  FuncDef = "{" BlockBody "}".

Das kann man auch formal LL(1) hinkriegen. Beim Programmieren ist es 
sowieso keine Schwierigkeit.

> Zu den "netten" Eigenheiten von C gehört es nämlich, dass
> Informationen aus der Symboltabelle in den Parser einfliessen.
> Typnamen sind Schlüsselwort und typedefs sind es auch ein bischen
> - der Name eines typedefs muss auf ein anderes Token kriegen als
> andere Bezeichner.

Du meinst die Fragestellung:
Was ist

   x * y;

ist das eine Multiplikation, deren Ergebnis verworfen wird, oder

typedef int x;
...
  x * y;

ist es die Definition eines Pointers auf x
:-)

[(prx) A. K. (prx)]

Zur Originalversion des PCC (K&R-C, kein ANSI-C):
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.48.3512&rep=rep1&type=pdf

[(prx) A. K. (prx)]

Karl heinz Buchegger schrieb:

> ist das eine Multiplikation, deren Ergebnis verworfen wird, oder
> ist es die Definition eines Pointers auf x
> :-)

Genau. Besonders fies ist C++. Ist
  x(y);
nun Typkonvertierung/Konstrukturaufruf oder die Deklaration der 
Variablen "y" vom Typ "x" mit überflüssigen aber zulässigen Klammern 
drumrum? Beides mit "x" als Typname.

[Andreas F. (aferber)]

A. K. schrieb:
> Was den Parser angeht ist C auch sonst nicht so ganz theoriekonform. Zu
> den "netten" Eigenheiten von C gehört es nämlich, dass Informationen aus
> der Symboltabelle in den Parser einfliessen. Typnamen sind Schlüsselwort
> und typedefs sind es auch ein bischen - der Name eines typedefs muss auf
> ein anderes Token kriegen als andere Bezeichner.

Und dabei ist dann als Bonus auch noch der Scope zu berücksichtigen.

typedef int identifier;

struct identifier {
        identifier identifier;
};

identifier test(struct identifier i)
{
        identifier identifier;
        // identifier i2; // waere ein Fehler!
        
        identifier = i.identifier;
        
        goto identifier;
identifier:
        
        return identifier;
}

Ausserdem ein Beispiel dafür, warum C++ keine Obermenge von C darstellt 
;-)

Andreas

[(prx) A. K. (prx)]

Falls sich jemand wundert, wie man sich sowas Böses ausdenken kann: Die 
ursprüngliche Version von C (pre-K&R) kannte noch kein typedef. Da war 
die Syntax noch einigermassen sauber.

[(prx) A. K. (prx)]

Andreas Ferber schrieb:

> Und dabei ist dann als Bonus auch noch der Scope zu berücksichtigen.

Im PCC kann man das bewundern. Da enthält der Lexer eine kleine 
Statemachine (einen winzigkleinen Parser sozusagen ;-), um auf 
struct/union/enum folgende Namen als normale Namen und nicht als 
Typenames zu kennzeichnen.

PS: Bei goto Labels hat man das im PCC anscheinend vergessen. ;-)

[der mechatroniker (Gast)]

Hilft mir mal bitte jemand auf die Sprünge? Warum wäre

identifier i2;

ein Fehler?

Abgesehen davon ist "krank" für das Beispiel noch untertrieben ;-)

[der mechatroniker (Gast)]

Ah jetzt wirds mir klar, die Variable im lokalen Scope verdeckt den Typ 
im globalen Scope. Damit steht da keine Variablendefinition. Ein 
Statement vorher existierte das Problem natürlich noch nicht.

Wieder was gelernt ;-)

[Stefan (Gast)]

Für den Compilerbau:
http://de.wikipedia.org/wiki/Yacc

[(prx) A. K. (prx)]

Der stammt vom gleichen Autor wie die ursprüngliche Version des PCC. 
Wenn man also beim PCC vorbei schaut, dann stolpert man auch über 
darüber (und über lex).