Welche Informatikfächer sind erforderlich, um einen Einführungskurs in Compiler zu absolvieren? [geschlossen]

10

Ich bin kein Informatik-Student und arbeite als Webentwickler (Java, Python, AS3 usw.) als Profi. Ich nehme 1 Kurs pro Semester an meiner örtlichen Universität. Ich hatte im letzten Semester künstliche Intelligenz (bestehend aus Logik, kontextfreier Grammatik, CYK-Analyse, einführendem NLP, Markov-Ketten, HMM usw.) absolviert.

Ich plane, im kommenden Semester einen Einführungskurs in Compiler zu belegen, der den folgenden Lehrplan abdeckt:

Lexikalische Analyse, Syntaxanalyse, semantische Analyse, Laufzeitumgebung, Zwischendarstellungen, Codegenerierung, Registerzuordnung, Auswahl und Planung von Befehlen, Einführung in lokale und globale Codeoptimierungen, Datenflussanalyse

Meine Frage ist, gibt es Informatikfächer, die ich vor dem Besuch dieses Kurses kennen sollte? Wenn ja, wäre es großartig, wenn Sie diese Kurse auflisten könnten.

education computer-science compiler gestresste_geek
quelle
1
Kommt auf deine Schule an. Meins war nicht so schwierig, also waren grundlegende Datenstrukturen und grundlegende Algorithmen erforderlich - das ist alles. Leider haben sie Compiler optional gemacht und ich habe mich rausgeschmissen und es nicht genommen.
Job

Antworten:

8

Sie sollten wahrscheinlich ein einfaches Verständnis der folgenden Themen haben:

  • Diskrete Mathematik (Mengen, Beziehungen, Bäume, Graphen, Matrizen, Zahlentheorie)
  • Datenstrukturen (in einem angewandten Sinne, wie Bäume, Listen, Stapel, Warteschlangen und Zeichenfolgen funktionieren)
  • Grundlegende Algorithmen (Kernkonzepte, Sortieren, Suchen, Big-O-Notation usw.)
  • Computerarchitektur (digitale Logik, Bitoperationen, Mikrokomponenten, Cache, Speicher, Baugruppenprogrammierung)
  • Verschiedenes (reguläre Ausdrücke, kontextfreie Sprachen, Automaten mit endlichem Zustand / Pushdown, Turing-Maschinen und Berechenbarkeit, lexikalische und Parsing-Tools)

Optional und wird wahrscheinlich viel helfen:

  • Betriebssystemdesign (Prozessmanagement, Kernel-Design, Synchronisation, Zeitplanung, Ereignisse, Sperren, Threads und Stack vs Heap)
Pewpewarrows
quelle
4

Nun, ich habe ein bisschen Arbeit beim Schreiben meiner eigenen Compiler geleistet, und ich würde sagen, dass die Hauptvoraussetzung ein solides Verständnis der Dinge ist, die Sie in einer Data Structures-Klasse erhalten. Insbesondere wenn Sie Rekursion, Bäume und Karten / Hash-Tabellen nicht verstehen, gehen Sie sehr schnell verloren, wenn Sie lernen, einen Compiler zu erstellen.

Mason Wheeler
quelle
3

Sie benötigen einige grundlegende Hintergrundinformationen zur Computerarchitektur (Register, Speicher, Spezialregister usw.) und haben bereits Assembler-Code gesehen. Es wäre sogar noch besser, wenn Sie zuvor einen Assembler-Code geschrieben hätten, damit Sie ein gutes Verständnis für die Funktionsweise der Maschinensprache haben.

Abhängig vom Kursniveau kann erwartet werden, dass Sie ein wenig über die superskalare Verarbeitung und dergleichen wissen.

Peter Smith
quelle
1
Dies gilt nur, wenn wir davon ausgehen, dass der betreffende Compiler Maschinencode und keinen Bytecode generiert.
Mason Wheeler
3

Wenn dies überhaupt etwas mit der Compiler-Klasse zu tun hat, die ich in der späten Kreidezeit (ca. 1988) zurückgenommen habe, wären die einzigen wirklichen Voraussetzungen Datenstrukturen (insbesondere Bäume und Hash-Tabellen), möglicherweise eine Assemblersprache (für den generierten Code) Einige Computerarchitekturen und jede Klasse, die Dinge wie reguläre Ausdrücke, endliche Automaten, Turing-Maschinen usw. lehrt, obwohl diese möglicherweise als Teil des Compilerkurses selbst behandelt werden (FWIW, meine nicht). Sie sollten auch sicherstellen, dass Sie die Rekursion verstehen.

John Bode
quelle
2

Sie müssen wahrscheinlich auch einen Kurs über formale Modelle und Sprachen belegen. Alles, was die grundlegende Chompsky-Hierarchie abdeckt, wäre in Ordnung: Reguläre Sprachen + kontextfreie Sprachen. Dies liegt daran, dass es wichtig ist, die mathematischen Grundlagen des Parsens zu verstehen, damit Ihr Parser sauber, performant und korrekt ist. Ich denke, dass eine gute Compiler-Klasse häufig sowohl reguläre Ausdrücke als auch LALR / LL (k) -Parser und die dahinter stehende Theorie abdeckt.

Mark Pauley
quelle
0

Da es sich um Codeoptimierung handelt, ist möglicherweise eine Assembler-Codierung enthalten. Es könnte also gut sein, zumindest eine vorübergehende Vertrautheit damit zu haben. Es würde davon abhängen, wie dieser spezielle Kurs aufgebaut ist. Ansonsten sollte es ausreichen, nur über gute Programmierkenntnisse zu verfügen, um eine Einführung in die Compiler-Klasse zu erhalten. Es wird eine sehr wertvolle Klasse sein.

GroßmeisterB
quelle
0

Hängt von Ihrer Uni ab, aber die meisten erfordern folgende Voraussetzungen:

=> Discrete Mathematics
Should include: propositional logic, predicate logic, set theory etc etc 

=> General Concepts of Programming (In any language of choice would be okay)
=> Algorithms and Data Structures
Should include: data structures, abstract data types, recursive algorithms
rrazd
quelle