"Python" Compiler

[burli]

Keine Angst, ich habe nicht vor, einen echten Python Compiler zu schreiben. Deshalb steht Python in Anführungszeichen.

Mir geistert vielmehr die Idee durch den Kopf, einen Compiler für eine Sprache zu schreiben, deren Syntax sich an Python orientiert, aber mit deutlich reduziertem Sprachumfang und mit statischer Typisierung. Das Compilat soll später auch nicht auf einem PC laufen sondern auf einen Mikrocontroller.

Viele Python Funktionen werde ich vermutlich erst gar nicht implementieren. Ich habe zwar überlegt, Klassen zu implementieren, aber nur sehr rudimentär ohne Vererbung und nur statisch. Aber eventuell lasse ich es ganz unter den Tisch fallen und mache nur etwas einfacheres wie Namspaces.

Ich weiß, Compilerbau ist die Königsdisziplin in der Softwareentwicklung, aber es soll auch kein High End Produkt werden, das in jeder Situation hochoptimierten Code produziert.

Denkt ihr, dass ist machbar? Wo könnten Stolperfallen lauern?

[BlackJack]

@burli: Machbar sollte das schon sein. Was ist denn das Zielformat? C oder C++ oder willst Du direkt Assembler erzeugen lassen? Du könntest ja erst einmal anfangen einfach nur eine mehr oder weniger 1:1 Umsetzung von einer Python-ähnlichen Syntax auf C zu implementieren. Klassen die nur Attribute enthalten bräuchte man dann für ``struct``\s.

[burli]

Ziel soll schon ASM werden. Da fühle ich mich wohler, auch wenn C vielleicht ein paar Vorteile hätte, gerade was Optimierung angeht. Ich bin mir aber noch nicht 100% sicher, was das angeht.

Bevor ich aber überhaupt das erste Byte ausgebe will ich den Sprachumfang halbwegs definieren und einen Parser schreiben, der mir zuverlässig die Tokens liefert. Bietet mir Python hier etwas, außer das re Modul? Die Syntax soll wie gesagt möglichst identisch zu Python werden, nur dass einige Dinge wegfallen. Und die statische Typisierung möchte ich von Boo übernehmen. Also

def foo(bar as int) as char:

zumindest so in der Art. Vielleicht lasse ich das Schlüsselwort "as" auch weg.

[BlackJack]

@burli: Das `ast`-Modul liefert Dir sogar ganze Baumstrukturen. Und die Typisierung könntest Du vielleicht mit PEP 3107: Function Annotations machen, wenn es Python 3.x sein darf.

Ansonsten könntest Du schauen ob Du beim `cython`-Projekt Quelltext wiederverwenden kannst.

[C4S3]

Hi,

entschuldigt meine Unwissenheit zu solchen Themen, aber als ich "compiler statisch Python" sah, musste ich an Genie denken:

http://en.wikipedia.org/wiki/Genie_%28p ... anguage%29
http://bkhome.org/genie/

Vielleicht könnte dir das ja helfen/Arbeit sparen/einen Denkanstoß geben?

Viele Grüße,

[burli]

@C4S3: ja, Vala/Genie kenne ich. Es gäbe auch noch LLVM. Für LLVM gibt es sogar schon einen Versuch, ein Backend für die Zielplattform zu erstellen. Ob das gut funktioniert oder, im Fall von Vala überhaupt möglich ist, weiß ich nicht. Und aufgrund von der Zielplattform müsste man auch Anpassungen an der Sprache selbst vornehmen.

Das ist auch mein Problem bei C. Viele Dinge mussten angepasst werden, damit sie zwar C konform sind, aber auf dem Mikrocontroller funktionieren. Da möchte ich ausbrechen und mit Bestehenden Systeme, die für PCs gedacht sind, sehe ich da keine Möglichkeit.

[BlackJack]

@burli: Assembler hat den Nachteil, dass Du da für jedes Ziel — x86, IA64, und jede Embedded-Plattform — ein eigenes Backend schreiben musst, während bei C als Zielsprache schon alles, für das es einen C-Compiler gibt, abgedeckt ist.

Dein Problem mit C verstehe ich nicht so ganz!? Das ist doch wirklich sehr nah an der Hardware – im Grunde eine Art portabler Makroassembler.

@C4S3: Genie hat den Nachteil, dass es von der Glib abhängt und damit Code für Embedded-Plattformen problematisch werden kann.

Der Mensch, der hinter dem zweiten Link steckt ist ja niedlich. „Why not Python? In a nutshell, incredible bloat and slowness”. Speziell zur Langsamkeit hat er dann noch diesen Satz: „A runtime interpreted language is inherently slow, even if compiled to bytecode. Python, Perl, Tcl, Java, PHP and applications that require mono/.net are all in this category.” Das zumindest Java- und .NET-Programme in der Regel durch einen JIT-Compiler gehen, hat er wahrscheinlich noch nie gehört. An anderer Stelle „…, and even if they did seem fast enough I was aware that they do chew up CPU time due to the runtime interpretation.” Das klingt ein bisschen nach einem psychologischen Problem das durch einen statischen Compiler gelöst werden soll.

[burli]

@burli: Assembler hat den Nachteil, dass Du da für jedes Ziel — x86, IA64, und jede Embedded-Plattform — ein eigenes Backend schreiben musst, während bei C als Zielsprache schon alles, für das es einen C-Compiler gibt, abgedeckt ist.

Dein Problem mit C verstehe ich nicht so ganz!? Das ist doch wirklich sehr nah an der Hardware – im Grunde eine Art portabler Makroassembler.

Ich habe nicht geplant, dass der Compiler auf beliebigen Plattformen läuft. Für x86 und co sollte man lieber zum Original greifen. Meine Anpassungen ergeben da keinen Sinn.

Bei Embedded Plattformen sieht es etwas anders aus, da gebe ich dir Recht. Allerdings sind da auch C Programme nicht wirklich portabel, da es teilweise erhebliche Unterschiede gibt. Ich müsste also auch bei C für jeden µC einen eigenen Backend schreiben, der die Ausgabe an die entsprechenden Besonderheiten anpasst.

Mir gehen allerdings gerade noch ein paar andere Dinge durch den Kopf, die vielleicht doch für C sprechen. Muss ich mir mal Gedanken machen.

[noisefloor]

Hallo,

Bietet mir Python hier etwas, außer das re Modul?

Es gibt noch das shelex-Modul, siehe z.B. http://www.doughellmann.com/PyMOTW/shlex/index.html

Gruß, noisefloor

[burli]

Es gibt noch das shelex-Modul

Danke. Ich schau es mir mal an

[deets]

Ausserdem natuerlich pyparsing.

[burli]

Ausserdem natuerlich pyparsing.

Sieht vielversprechend aus. Damit werde ich es mal versuchen.

[sma]

Ich halte ein Projekt, einen Compiler für eine Python-artige Sprache für durchaus machbar. Tatsächlich finde ich auch die Grundlagen des Compilerbaus: Parsing und Code Generation vergleichsweise einfach. Ich würde mir jetzt nicht geben wollen, ein komplexes Typsystem zu entwerfen, vielleicht sogar noch zu beweisen, dass es "sound" ist, oder eine optimierer für 3-Address-Ausdrücke und Codeblöcke zu entfernen, aber wenn man C als Zielsprache nimmt, macht dieser Compiler das "heavy lifting".

Hier habe ich einen Python-Interpreter (ohne Laufzeitsystem) in Python geschrieben: https://gist.github.com/760937

Unter Namensnennung darfst du dich da gerne am Code bedienen. Das AST-Modul ist natürlich ein weiterer Weg, wie man sehr schnell zu einem AST kommt, aus dem man dann Code generieren kann. Dann muss man aber in jedem Fall kompatibel zur Syntax von Python 2 oder 3 bleiben.

Ich fand es übrigens nicht notwendig, einen Parser-Generator zu benutzen, denn Python ist sehr simpel strukturiert und die einzige Schwierigkeit ist der Lexer, der Einrückung in Token umwandeln sollte, damit der Parser einfacher ist. Auch wenn ich's nicht verstehe gibt es AFAIK keinen fertiger Generator, der Sprachen mit Einrückung beherrscht, hier müsste man also eh den Lexer selbst schreiben. Und der Rest ist dann Routine.

Das ich Standard-C und nicht Assembler (oder gar Maschinencode) erzeugen würde, schrieb ich ja schon.

Eine wichtige Entscheidung ist IMHO, ob du eine automatisch Speicherverwaltung haben willst. Die selbst zu bauen, ist nicht ganz ohne, speziell wenn es im Mikrocontroller-Bereich vielleicht nicht geht, dass das Programm alle paar Sekunden für 100ms oder so stoppt oder du nicht so viel Speicher hast, dass du den einfachsten, aber speicherhungrigsten Stop&Copy-Algorithmus so runter programmieren kannst. Bleibt also Mark&Sweep oder Mark&Compact, wenn du nicht darauf angewiesen bist, dass Datenstrukturen ihre Adresse behalten müssen. Moderne GCs kombinieren verschiedene Grundalgorithmen. Vielleicht kannst du auch einfach den Weg gehen, den sie alle gehen und den Boehm GC nutzen. Ein eigener GC wird aber in der Regel effizienter sein. Natürlich könntest du auch Reference Counting benutzen, was vielleicht gerade im Microcontroller-Umfeld ein guter (wenn auch langsamerer) Weg wäre. Und hey, tausende Mac und iOS-Entwickler kommen damit auch klar.

Bei der statischen Typisierung würde ich empfehlen sehr pragmatisch vorzugehen und nicht zu versuchen, ein korrektes Typsystem zu entwickeln, insbesondere nicht, wenn dir co- und contravariant als Begriff nichts sagen. Habe einfach Container-Datentypen in denen du primitive Datentypen wie Zahlen explizit wrappen musst. Oder benutze nur Objekte - doch dann ist der Vorteil weg, den du dir wahrscheinlich durch statische Typisierung erhoffst.

Klassen sind (auch statisch) harmlos, ich würde allerdings auf die Mehrfachvererbung verzichten, weil der Linearisierungsalgorithmus von Python nicht trivial ist. Bei einfacher Vererbung ist es offenkundig trivial die Vorgänger abzulaufen.

Wenn du auf Effizienz wert legt, würde ich Python entschlacken, was die ganze "__"-Methoden angeht. Insbesondere würde ich "__dict__" weglassen und fordern, dass man für jede Klasse definieren muss, welche Variablen ihre Exemplare haben können.

Schließlich würde ich auch verbieten, dass man auf "toplevel" Code ausführen kann.

Geht das zu weit, möchte man also z.B. beim Laden eines Moduls erst die Klassen oder Funktionen erzeugen, würde ich den Weg gehen, den Pypy geht. Kompiliere nicht den Quelltext, sondern das, was entstanden ist, nachdem das Modul geladen wurde. Das erlaubt dann noch ein bisschen Metaprogrammierung.

Ein alternative Ansatz wäre, ein Makro-Konzept einzuführen, doch das ist bei Python nicht so einfach wie bei den ganzen Lisp-Dialekten, weil die Syntax viel komplexer ist. Das hat die Sprache Boo aber dennoch nicht daran gehindert, es trotzdem zu machen. Da diese Sprache aber syntaktisch für alles, was die .NET CLR so bietet, eine Antwort haben muss, finde ich die viel zu kompliziert.

Stefan

[burli]

Ich gebe zu, dass ich mir die meisten Grundkenntnisse im Compilerbau noch aneignen muss. Deinen Interpreter werde ich mir auf jeden Fall mal anschauen. Zumindest der Parser könnte mir sicher ein paar Tipps geben. Problem ist, dass ich von der Standard Python Syntax abweichen muss, allein schon wegen der statischen Typisierung

Ich hab aber ein bestimmtes Ziel vor Augen und ich möchte, wenn es irgendwie geht, auf den Umweg über einen C Compiler verzichten. Über die Konsequenzen bin ich mir im klaren.

Ich werde zunächst ganz einfach anfangen, einen kleinen Boilerplate Code schreiben um den µC zu initialisieren und über die serielle Schnittstelle Daten senden zu können, um den erzeugten Code zu testen (mir fehlt leider ein brauchbarer Simulator). Also einfache Variablenzuweisungen, ein bisschen rechnen und das Ergebnis dann ausgeben.

Die "Speicherverwaltung" ist so eine Sache. Der Speicher ist natürlich bei so einem Teil recht begrenzt. Dazu kommt noch, dass manche Daten nicht im Ram sondern auch zum Beispiel im Flash stehen können. Da bin ich noch am überlegen wie ich das (syntaktisch) lösen kann.

Generell ist es eine ordentliche aAufgabe, auch schon bei Parser. Ich muss ja auch Fehler abfangen und brauchbare Fehlermeldungen ausgeben. Aber mich reizt das schon lange bzw mich nervt auch die Tatsache, dass es speziell unter Linux eigentlich nur C als Programmiersprache gibt.

[burli]

@sma: ich habe mal deine tokenize() Funktion ausprobiert. Die gibt aber, im Gegensatz zu deiner Beschreibung, in jeder Zeile für jeden Indent einen Token aus und am Ende jeder Zeile einen Dedent.

Ich denke, dass ist nicht im Sinne des Erfinders, oder?

Code: Alles auswählen

def main():
	f = open('parse.py', 'r')
	print tokenize(f.read())
	return 0

if __name__ == '__main__':
	main()

ergibt (gekürzt)

Code: Alles auswählen

['from', 'port', 'ndall', '\n', 'def', 'kenize', '(', 's', ')', ':', '\n', '!INDENT', 'tokens', '!DEDENT', '[', ']', '\n', '!INDENT', 'cur_indent', '!DEDENT', '0', '\n', '!INDENT', 'new_indent', '!DEDENT', '0', '\n', '!INDENT', 'for', '!DEDENT', 'ken', 'ndall', '(', '"(?', 'm', ')', '^ *', '(', '?:#', '.', '*)?', '\\n|', '\n', '!INDENT', '!INDENT', 'if', '!DEDENT', '!DEDENT', 'ken', ':', '\n', '!INDENT', '!INDENT', '!INDENT', 'if', '!DEDENT', '!DEDENT', '!DEDENT'

Wenn ich die Zeilen mit readline() einzeln lese und an tokenize() übergebe bekomme ich einen IndexError: list index out of range

[sma]

In dem Code-Beispiel steht nicht der vollständige RE, sondern er endet auf "...". Versuch mal diesen:

Code: Alles auswählen

'(?m)^ *(?:#.*)?\n|#.*$|(^ +|\n|\\d+|\\w+|[()\\[\\]{}:.,;]|[+\\-*/%<>=]=?|!=|\'(?:\\\\[n\'"\\\\]|[^\'])*\'|"(?:\\\\[n\'"\\\\]|[^"])*")'

Stefan

[burli]

Ah, ergibt Sinn. Aber bei RegEx kannst du mir alles verkaufen

[sma]

Das stand aber auch so im Text...

Stefan

[burli]

Ich hab die schlechte Angewohnheit, bei sowas quer zu lesen.

[burli]

Ich bin gerade dabei, mir eine Syntax Definition zu überlegen. Ich möchte dabei so wenig wie möglich der Python Syntax hinzufügen.

Bei der Typisierung werde ich nicht um zusätzliche Schlüsselwörter wie "int" oder "float" herum kommen. Da es sich aber um einen Mikrocontroller handelt und dieser neben RAM auch noch andere Speichertypen wie Flash oder Eeprom enthält suche ich noch nach einer Möglichkeit, Variablen zur Compile Zeit so zu definieren, dass sie eben nicht im RAM abgelegt werden sondern im Flash bzw Eeprom.

Man könnte natürlich zusätzliche Schlüsselwörter definieren, aber vielleicht kennt jemand eine Möglichkeit, dafür Python Hausmittel zu verwenden. Das einzige, was mir einfallen würde, wäre ein Decorator. Ich weiß aber nicht, ob das ausreichend ist bzw wie man das implementieren müsste. Der Compiler muss bei späterem Auftreten ja immer noch wissen, dass die Variable anders zu behandeln ist.

Ansonsten sähe das so aus

Code: Alles auswählen

flash str as string = "Hello World"
eeprom i as int = 10