Ich suche gute Beschreibungen zur Programmierung von Interpretern. Ich
möchte einen Bytecode Interpreter schreiben. Das heißt, ich brauche auch
einen Compiler, der die Soucen in den Bytecode übersetzt Welche Syntax
es wird ist mir noch nicht klar.
Es wäre wichtig, dass die Beschreibung in Deutsch ist. Können auch
Bücher sein.
Vielleicht gibts heute bessere Bücher, mag sein.
Aber "N. Wirth, Compilerbau" hat mir vieles erklärt und beigebracht.
Dann natürlich die berühmten "Drachenbücher". Aho, Sethi, Ullmann -
Compilers, Principles ....
Obowhl, die Drachenbücher hab ich noch als mehr theorielastig im Kopf
und auch nicht unbedingt leichte Kost. Sind allerdings DIE Bibel in
dieser Szene.
hm, Wirth kenne ich glaube ich noch. Hat ein Bekannter im Info Studium
gehabt. Und ich glaube, dafür muss man auch Info studiert haben, um das
zu verstehen.
Mal schauen, ob der das noch hat.
Das sind zwei verschiedene Themen:
1. Compiler Quelltext -> Bytecode
2. Interpreter für den Bytecode
Dazu kommt, sich die Regeln für den Bytecode auszudenken.
Ein Klassiker für 1. ist "Compilerbau" von Niklaus Wirth.
Je nach Vorkenntnissen übernimmt man sich evtl. dabei.
Du bist sicher, nicht mit etwas leichterem anfangen zu wollen?
Klaus Wachtler schrieb:> Du bist sicher, nicht mit etwas leichterem anfangen zu wollen?
Naja, die Schwierigkeit steigt ja mit der Komplexität der Sprache. Einen
einfachen Interpreter würde ich glaube ich noch so zusammen bekommen.
Aber ich würde das halt recht pragmatisch angehen.
Ich glaube sogar, dass mir ein Compiler mehr Probleme machen würde als
ein Interpreter.
ein (sehr sehr sehr) einfaches Beispiel gibt es ja auf Wikipedia und
hier
http://www.stefan-baur.de/cs.lang.interpreter.0.html
ok, ein Interpreter ist ziemlich geradlinig zu programmieren.
Einen habe ich auch mal gebraucht und gebaut, das geht und ist
eigentlich Fleißarbeit.
Aber für die ganze Kombination aus
- Bytecodesprache sinnvoll definieren
- dafür einen Compiler
- und Interpreter (der leichtere Teil)
brauchst man schon etwas Überblick, damit es Sinn macht.
Nur: der ganze Aufriß lohnt doch nicht für ein Primitivbeispiel,
sondern erst wenn etwas mehr dahinter steckt, oder?
Deshalb habe ich etwas Zweifel.
Naja, als "Bytecode" wollte ich mich an Assembler orientieren.
Allerdings mit etwas "mächtigeren" Befehlen. Befehle wie move, store
oder load könnten dann zb nicht nur einzelne Bytes sondern komplette
Strukturen bewegen (nur so ein Gedanke)
Bevor ich dann dafür einen Compiler schreiben würde würde ich zuerst
einen Assembler schreiben
Klaus-Ulrich B. schrieb:> Klaus Wachtler schrieb:>> Du bist sicher, nicht mit etwas leichterem anfangen zu wollen?>> Naja, die Schwierigkeit steigt ja mit der Komplexität der Sprache.
Nicht wirklich.
Wenn du das Prinzip des Compilerbaus verstanden hast, ist die
Komplexität der Sprache erst mal relativ egal (solange du ein paar
Grundlagen des Sprachdesigns einhältst)
> hm, Wirth kenne ich glaube ich noch. Hat ein Bekannter im> Info Studium gehabt. Und ich glaube, dafür muss man auch> Info studiert haben, um das zu verstehen.
Nicht wirklich.
Wirths Buch ist sehr praxisorientiert.
Klaus-Ulrich B. schrieb:> Naja, als "Bytecode" wollte ich mich an Assembler orientieren.
Schlechte Wahl.
Wenn du dir schon deine eigene CPU definieren kannst, dann definiere sie
so, dass du leicht mit ihr arbeiten kannst.
Defnierst du dir eine Stack-Maschine, dann ist zwar der Interpreter ein
klein wenig umfangreicher, dafür wird aber der Compiler simpler, weil
der ganze komplizierter Abschnitt: Life-Span von Zwischenergebnissen
bzw. Register-allokierung komplett weg fällt.
> Allerdings mit etwas "mächtigeren" Befehlen. Befehle wie move, store> oder load könnten dann zb nicht nur einzelne Bytes sondern komplette> Strukturen bewegen (nur so ein Gedanke)
Du denkst jetzt schon viel zu sehr in Details.
Deine Stackmaschine soll für einen Ausdruck
i = 3 * ( j + 5 );
diesen Code erzeugen
1
PUSH Adresse_von_i
2
PUSH Adresse_von_j
3
REF
4
PUSH 5
5
ADD
6
PUSH 3
7
MULT
8
ASSIGN
(*)
Und dein Interpreter, der das abarbeitet, macht dann das Richtige.
Befehle:
PUSH legt einen Wert auf den Stack
REF nimmt den obersten Wert von Stack, interpretiert diesen als
Adresse im Speicher, holt den Wert aus dem Speicher und legt
den Wert auf dem Stack ab
Push( Mem[Pop()] )
ADD holt den obersten und den zweit obersten Wert vom Stack,
addiert die beiden und legt das Ergebnis auf den Stack
Push( Pop() + Pop() )
MULT holt den obersten und den zweit obersten Wert vom Stack,
multipliziert die beiden und legt das Ergebnis auf den Stack
Push( Pop() * Pop() )
ASSIGN holt den obersten und den zweit obersten Wert vom Stack
der zweite Wert wird als Adresse verstanden, unter der der
oberste Wert abgelegt werden soll
x = Pop()
Mem[ Pop() ] = x
Beschränke dich am Anfang auf reine Integer. Der Rest kommt dann schon
von alleine.
> Bevor ich dann dafür einen Compiler schreiben würde würde ich zuerst> einen Assembler schreiben
Falscher Weg. Diesen Weg geht man maximal, wenn einem die
Zielarchitektur vorgegeben ist.
Eine gute Vorstufe für Compiler/Interpreter sind zb. Formelplotter:
Du gibst eine Formel ein, ein Compiler übersetzt die in eine
Zwischensprache und ein Interpreter/Zeichensystem erzeugt eine
Funktions-Grafik für die Formel.
(*) Edit:
Wohingegen das hier raus kommt, wenn dein Compiler die Rechenregeln
richtig macht
Karl heinz Buchegger schrieb:> Defnierst du dir eine Stack-Maschine, dann ist zwar der Interpreter ein> klein wenig umfangreicher, dafür wird aber der Compiler simpler, weil> der ganze komplizierter Abschnitt: Life-Span von Zwischenergebnissen> bzw. Register-allokierung komplett weg fällt.
Ok, auch ein Ansatz. Werde ich mir mal anschauen.
Klaus-Ulrich B. schrieb:> hm, Wirth kenne ich glaube ich noch. Hat ein Bekannter im Info Studium> gehabt. Und ich glaube, dafür muss man auch Info studiert haben, um das> zu verstehen.
M.W. hat Wirth mehrere Bücher zu dem Thema geschrieben. Das, was Karl
Heinz wahrscheinlich meint, ist schon zig Jahre alt, nur gute 100 Seiten
dick und hat die ISBN 3519323389. Ich selbst habe die Grundlagen des
Compilerbaus damals als absoluter Anfänger ebenfalls aus diesem Buch
gelernt. Es beschränkt sich konsequent auf das Allernotwendigste, um
einen einfachen Compiler selber zusammenpappen zu können, deswegen ist
es auch so dünn. Die einzige Vorraussetzung: Man sollte programmieren
können.
Wenn man dieses Buch durchgearbeitet hat und wirklich tief in das Thema
einsteigen will, kommt als nächstes das Dragon-Book. Im Gegensatz zu
Wirths Buch ist es dick (in der deutschen Übersetzung sogar zwei Bände),
vollständig und schwieriger zu verstehen, auf jeden Fall aber Klasse.
Dafür kann man hinterher nicht nur einen hochoptimierenden Compiler
schreiben, sondern auch gleich die Entwicklungstools wie Scanner- und
Parsergeneratoren mit dazu.
Mehr als diese Bücher braucht man nicht, höchstens noch ein paar
Konferenzartikel, wenn man sich auf dem neuesten Stand der Technik
halten will.
Bei der Gelegenheit kannst Du Dir auch mal die Programmiersprache
'Forth' ansehen. Die basiert genau auf einer solchen Stack-Maschine und
ähnelt auch sonst dem was Du vorhast.
http://de.wikipedia.org/wiki/Forth_(Informatik)
Klaus-Ulrich B. schrieb:> Karl heinz Buchegger schrieb:>> Wirths Buch ist sehr praxisorientiert.>> Mir ist gerade aufgefallen, dass die Ausgabe, die ich kenne, schon> "etwas" älter ist>> http://www.inf.ethz.ch/personal/wirth/books/Compilerbau0/Compilerbau0.gif
Anhand des Titelbildes kann ich es nicht entscheiden. Aber wenn das die
'ältere' Ausgabe ist, die mir in meiner Studienzeit untergekommen ist:
unbedingt lesen! Die ist enorm praxisorientiert. Sie beginnt damit einen
'Compiler' zu bauen, der eine EBNF in einen Baum übersetzt und einen
Interpreter benutzt um diese EBNF abzuarbeiten um damit einen Input auf
Korrektheit zu prüfen. Sozusagen ein einfacher 'Compiler-Compiler',
wobei der Compiler nichts übersetzt sondern nur 'entspricht der EBNF'
oder 'entpsricht nicht' ausgibt.
Dann kommt ein 'richtiger' Compiler, der eine Pascal-ähnliche Sprache
verarbeitet. Wenig Theorie, dafür viele Codebeispiele. Von vorne weg
(lexikalische Analyse) bis hin zur virtuellen CPU, die den Code
abarbeitet. Komplett mit Funktionsverwaltung etc.
Könnte mich heut noch in den A.... beißen, dass ich das Büchlein nicht
vollständig durch den Kopierer gejagt habe.
... schrieb:> Bei der Gelegenheit kannst Du Dir auch mal die Programmiersprache> 'Forth' ansehen. Die basiert genau auf einer solchen Stack-Maschine und> ähnelt auch sonst dem was Du vorhast.
Wenn ich ehrlich bin, wäre mir das nur recht. Werde ich mir auf jeden
Fall anschauen. Und wie ich sehe gibt es da schon etwas für den AVR
Wobei Forth insofern "gewöhnungsbedürftig" ist, als der Programmierer
die Umsetzung in UPN (und damit die Stackmaschine) machen muss. Bei
arithmetischen Ausdrücken geht das noch, aber bei Kontrollstrukturen bin
ich da regelmässig immer durcheinander gekommen.
Karl heinz Buchegger schrieb:> Wobei Forth insofern "gewöhnungsbedürftig" ist, als der Programmierer> die Umsetzung in UPN (und damit die Stackmaschine) machen muss. Bei> arithmetischen Ausdrücken geht das noch, aber bei Kontrollstrukturen bin> ich da regelmässig immer durcheinander gekommen.
Wenn man das umdreht, d.h. von rechts nach links ausführt, dann wird's
m.E. einfacher:
Klassisch:
1
1a@=IF
2
ab+c!
3
ENDIF
"Verkehrt" herum:
1
IFEQ@a1
2
ASSIGNc+@a@b
3
ENDIF
Habe ich seltsamerweise noch nirgends in ähnlicher Weise gesehen.
Vielleicht beschreibst Du mal, warum Du einen Interpreter bauen musst.
Es gibt bereits so viele Programmiersprachen. Da ist sicher auch was für
Dich dabei.
Dieter Engelhardt schrieb:> Vielleicht beschreibst Du mal, warum Du einen Interpreter bauen musst.
Mein "Endziel" ist eine einfache Entwicklungsumgebung in Stil von der
C-Control, einschließlich Simulator und Debugger.
Mit einfach meine ich einfach zu bedienen
Alles, was ich da bisher (für den AVR) gefunden habe, sind so Dinge wie
Chipbasic, wo gleich noch VGA Ausgabe dabei ist oder ganz einfache Basic
Interpreter mit Zeilennummern
Klaus-Ulrich B. schrieb:> Gibt es denn Compiler, die z.B. Basic in Forth übersetzen?
Wenn wir mal 'Basic' als Synonym für 'einfache Hochsprache' und 'Forth'
als Synonym für 'Stackmaschine' ansehen, dann ist es doch genau das was
du bauen willst.
Und wenn schon Forth, dann auch konsequent.
Einen Basic->Forth Compiler, nur damit du dir die Details der
Implementierung ersparst, macht keinen Sinn. Die Stackmaschine ist ja
nicht das Problem. Die hast du in einer Stunde programmiert.
Karl heinz Buchegger schrieb:> Einen Basic->Forth Compiler, nur damit du dir die Details der> Implementierung ersparst, macht keinen Sinn. Die Stackmaschine ist ja> nicht das Problem. Die hast du in einer Stunde programmiert.
Ok, mal ganz ausführlich, was ich mir vorstelle. Ich möchte eine
Entwicklungsumgebung entwickeln. Im AVR (Xmega) soll eine Art Mini OS
laufen. Am PC soll man ein Programm (z.B. in Basic) schreiben und
simulieren können. Das Programm wird in einen Bytecode übersetzt,
welcher z.B. über die serielle Schnittstelle in den Controller geladen
wird.
Im Controller soll man auch die Möglichkeit haben, dass Programm zu
debuggen
Vor allem Simulator und Debugger sind mit einem Interpreter IMHO
einfacher und günstiger zu realisieren als mit einem Compiler und
Hardware Debugger
Vorbilder sind hier wie gesagt C-Control, BasicStamp oder 8051 AH Basic.
Für AVR gibt es afaik (außer C-Control Pro) nicht viel und vor allem
nichts im Bereich OpenSource/Linux.
Karl heinz Buchegger schrieb:> Aber im Moment denke ich, du willst zu viel auf einmal :-)
Eigentlich will ich erstmal einen einfachen Interpreter, um zu schauen,
wie das funktioniert. Der Rest ist Wunschdenken und Zukunftsmusik.
Der Interpreter darf auch erstmal am PC laufen, weshalb ich es hier
gepostet hab.
Vielleicht schaue ich mir einfach mal Forth an, um zumindest mal eine
Variante zu sehen und ein Gefühl zu bekommen
Wir standen vor einigen Monaten auch vor einer sehr ähnlichen Aufgabe,
nämlich Konfigurationen, die in einer Art IDE erstellt werden, in ein
Format zu übersetzen, das von einem Microcontroller verarbeitet werden
kann und hinreichend flexibel ist.
Hierbei sollte es auch Möglichkeiten geben, die von der IDE erstellten
Konfigurationen auch händisch um eigene Anteile zu ergänzen.
Letztendlich sind wir immer wieder bei Forth gelandet, da es doch eine
Vielzahl von Implementierungen gibt. Leider unterscheiden sie sich -
trotz der eigentlich gleichen Sprache - ganz erheblich in der Art und
Weise ihrer Umsetzung. Für unseren Zielprozessor STM32 am besten
geeignet ist pForth.
Für uns ganz besonders wichtig ist das Laufzeitverhalten; verwendet man
"moderne" Sprachen wie z.B. Java, dann kann man sehr schnell den
Überblick über die Lebensdauer von Objekten verlieren und sich durch die
gelegentlich stattfindende Garbage Collection empfindliche Verzögerungen
einhandeln. Bei Forth gibt es den/die Stacks. Da weiß man ganz genau,
wie hoch der Speicherverbrauch eines Programm ist, weil man eh immer
mitzählen muss.
Worum geht es bei unserem Projekt?
Es handelt sich um eine Funkfernsteuerung für den Modellbau. Die meisten
konventionellen Produkte sind einfach zu kompliziert zu konfigurieren
oder nicht flexibel genug. Statt nun die Konfiguration auf einem
winzigen LCD durchzuführen, gibt es eine ordentliche PC-Software, die
dann auch einen Austausch von Konfigurationen mit anderen Nutzern bzw.
Fernsteuerungen erlaubt. Und die "Hardcore-Programmierer" können eben
auch die ganze Steuerung per Forth-Skript konfigurieren. Erhältlich wird
die Fernsteuerung (iVol Blu) noch im Laufe des Frühjahrs 2010 sein.
Mal ein Beispiel.
Das angehängte Programm ist ein in C ausprogrammierter 'Compiler', der
eine winzige Eingabesprache in Tokens 'compiliert', die zb über eine
Schnittstelle zu einer Stackmaschine geschickt werden können, die auf
einem AVR läuft und die diese dann abarbeitet.
Eine Eingabesprache von
1
CONFIGUREPORTB,6,INPUT;
2
SETBITPORTB,5;
3
CLEARBITPORTB,4;
setzt sie um in Anweisungstokens, die im Klartext ausgeschrieben sich so
präsentieren:
1
Number 2
2
Number 6
3
clear Bit on DDR
4
Number 2
5
Number 5
6
set Bit on Port
7
Number 2
8
Number 4
9
clear Bit on Port
10
End of Execution
eine Stackmaschine dafür zu bauen, ist wiederrum trivial.
Einfach eine while Schleife, die sich einen Token nach dem anderen holt,
und die zugehörige Aktion ausführt.
In der Praxis wird man so einen 'Compiler' allerdings höchst
wahrscheinlich nicht in C ausprogrammieren, sondern Compilerbau Tools
benutzen, die einem das ganze Syntaxgerüst abnehmen.
Der erste Schritt allerdings, das Überlegen, wie denn die Syntax der
neuen Sprache aussehen soll (die Grammatik), bleibt einem nicht erspart.
Damit beginnt alles.
Karl heinz Buchegger schrieb:> In der Praxis wird man so einen 'Compiler' allerdings höchst> wahrscheinlich nicht in C ausprogrammieren, sondern Compilerbau Tools> benutzen, die einem das ganze Syntaxgerüst abnehmen.
YACC, Lex usw. Ist mir bekannt, hab ich mich aber noch nicht näher damit
beschäftigt
Karl heinz Buchegger schrieb:> Der erste Schritt allerdings, das Überlegen, wie denn die Syntax der> neuen Sprache aussehen soll (die Grammatik), bleibt einem nicht erspart.> Damit beginnt alles.
Meinst du die "Hochsprache" oder die "Zwischensprache" für den
Interpreter? Die Hochsprache habe ich noch nicht festgelegt. Bevorzugt
wäre (Q)Basic, alternativ (Turbo)Pascal. Ich will da also das Rad nicht
neu erfinden
Klaus-Ulrich B. schrieb:> Karl heinz Buchegger schrieb:>> In der Praxis wird man so einen 'Compiler' allerdings höchst>> wahrscheinlich nicht in C ausprogrammieren, sondern Compilerbau Tools>> benutzen, die einem das ganze Syntaxgerüst abnehmen.>> YACC, Lex usw. Ist mir bekannt, hab ich mich aber noch nicht näher damit> beschäftigt>> Karl heinz Buchegger schrieb:>> Der erste Schritt allerdings, das Überlegen, wie denn die Syntax der>> neuen Sprache aussehen soll (die Grammatik), bleibt einem nicht erspart.>> Damit beginnt alles.>> Meinst du die "Hochsprache" oder die "Zwischensprache"
Die Hochsprache.
Bei der Zwischensprache hast du den Luxus, dass du dich danach richten
kannst, was die Hochsprache so alles bräuchte und hier dem Compiler
entgegen kommen kannst.
Klaus-Ulrich B. schrieb:> Meinst du die "Hochsprache" oder die "Zwischensprache" für den> Interpreter? Die Hochsprache habe ich noch nicht festgelegt. Bevorzugt> wäre (Q)Basic, alternativ (Turbo)Pascal. Ich will da also das Rad nicht> neu erfinden
LOL.
Dann hol dir den frei verfügbaren Pascal Compiler und brenn in deinen
AVR einen Bootloader rein :-)
Karl heinz Buchegger schrieb:> Dann hol dir den frei verfügbaren Pascal Compiler und brenn in deinen> AVR einen Bootloader rein :-)
Und wie debugge oder simuliere ich nachher? Ne, muss schon ein
Interpreter werden. Ich will ja gerade KEINEN nativen Compiler. Oder
soll ich einen virtuellen AVR Kern auf dem AVR laufen lassen? Wäre
sicher auch lustig
Karl heinz Buchegger schrieb:> Klaus-Ulrich B. schrieb:>>> Meinst du die "Hochsprache" oder die "Zwischensprache" für den>> Interpreter? Die Hochsprache habe ich noch nicht festgelegt. Bevorzugt>> wäre (Q)Basic, alternativ (Turbo)Pascal. Ich will da also das Rad nicht>> neu erfinden>> LOL.> Dann hol dir den frei verfügbaren Pascal Compiler und brenn in deinen> AVR einen Bootloader rein :-)
Man könnte sich auch auf der ETHZ-Seite umsehen, um dann vllt dieses
hier zu finden http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf
p.s. wer sich mal ein aktuelles, in Oberon geschriebenes, OS ansehen
will
http://bluebottle.ethz.ch/
Arc Net schrieb:> Man könnte sich auch auf der ETHZ-Seite umsehen, um dann vllt dieses> hier zu finden http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf
Das hab ich zwischenzeitlich sogar schon gefunden
Oberon für AVR klingt auch interessant. Allerdings werde ich nicht so
ganz schlau daraus, wie das funktionieren soll
Klaus-Ulrich B. schrieb:> Arc Net schrieb:>> Man könnte sich auch auf der ETHZ-Seite umsehen, um dann vllt dieses>> hier zu finden http://www-old.oberon.ethz.ch/WirthPubl/CBEAll.pdf>> Das hab ich zwischenzeitlich sogar schon gefunden>> Oberon für AVR klingt auch interessant. Allerdings werde ich nicht so> ganz schlau daraus, wie das funktionieren soll
Man könnte den Code, so wie er im Anhang steht, nehmen...
da der Compiler eh schon Code für eine sehr einfache virtuelle
RISC-Architektur erzeugt, welcher auch interpretiert wird (Kapitel 9).
Dieser Interpreter müsste dann auf den AVR portiert werden.
Selbstgemacht werden müssten dann nur Erweiterungen für das Debuggen und
möglicherweise Erweiterungen für den Zugriff auf die AVR-Hardware
(eigene Syntax-Erweiterungen oder Funktionsaufrufe)
Karl heinz Buchegger schrieb:> Ich hab noch nicht gegoogelt, aber UCSD Pascal mit dem P-Code> Interpreter sollte sich auch nicht allzuschwer portieren lassen.
Ja, hatte ich weiter oben schonmal erwähnt. Sieht interessant aus, wenn
ich es zum laufen bekomme