Was ist ein Compiler?
Compiler sind Programme, die Quellcode einer Programmiersprache in ausführbare Dateien übersetzen.
Ähnliche Prinzipien gelten für andere Systeme, wie Browser (für HTML) oder Editoren (z. B. XML-Editoren).
Aufbau eines Compilers
Ein Compiler hat typischerweise zwei Hauptphasen.
Benenne beide.
Analyse (Frontend)
Synthese (Backend)
Aus welchen Phasen besteht die Analyse?
Analyse (Frontend):
Lexikalische Analyse (Scanning)
Syntaktische Analyse (Parsing)
Semantische Analyse:
Ein Compiler hat typischerweise zwei Hauptphasen:
Lexikalische Analyse (Scanning):
Was geschieht dabei?
Wandelt Quelltext in eine Token-Kette um. Dies geschieht mithilfe von regulären Ausdrücken und endlichen Automaten.
Lexikalische Analyse (Scanning): Wandelt Quelltext in eine Token-Kette um. Dies geschieht mithilfe von regulären Ausdrücken und endlichen Automaten.
Syntaktische Analyse (Parsing):
Erstellt aus der Token-Kette einen Syntaxbaum, der die Grammatik des Programms widerspiegelt. Kontextfreie Grammatiken kommen hier zum Einsatz.
Syntaktische Analyse (Parsing): Erstellt aus der Token-Kette einen Syntaxbaum, der die Grammatik des Programms widerspiegelt. Kontextfreie Grammatiken kommen hier zum Einsatz.
Semantische Analyse
Überprüft den Syntaxbaum auf inhaltliche Korrektheit, z. B. ob Variablen deklariert wurden oder ob Datentypen korrekt genutzt werden. Bei Bedarf werden Typen umgewandelt (Type Casting).
Synthese (Backend):
Zwischencode-Erzeugung: Was geschieht dabei?
Zwischencode-Erzeugung: Wandelt den Syntaxbaum in eine abstrakte Darstellung des Programms.
Code-Optimierung: Was geschieht dabei?
Code-Optimierung: Verbessert die Effizienz des Codes.
Code-Erzeugung: Was geschieht dabei?
Code-Erzeugung: Generiert den endgültigen Maschinencode.
Was ist und welchen Zweck hat der Lookahead in einem Parser?
Bei einem Parser ist wichtig,
dass immer eindeutig ist, welche Grammatikregel in einer bestimmten Konstellation anzuwenden ist, und dass diese Regel einfach identifizierbar ist.
Der Lookahead beschreibt,
dass ein Parser beim Einlesen nur ein Zeichen weit vorausblicken muss, um zu entscheiden, welche Regel angewendet werden soll.
Das schränkt die Möglichkeiten bei der Sprachdefinition ein, macht aber die Analyse und damit auch die Übersetzung der Sprache einfacher.
Einfluss der Theorie der formalen Sprachen
Die Theorie der formalen Sprachen hat die Entwicklung von Compilern stark geprägt.
In welche Richtung erlauben effiziente Grammatiken wie LR(1) oder LALR(1) die Übersetzung? Und welches Zeichen wird dabei genuzt?
Effiziente Grammatiken wie LR(1) oder LALR(1) erlauben die Übersetzung von links nach rechts
mit einem Lookahead-Zeichen.
Auf welcher Grammatik basiert Java?
Java basiert z. B. auf einer LALR(1)-Grammatik.
Welche Werkzeuge werden für die Analyse genutzt?
Werkzeuge für die Analyse
Lex: Erstellt einen Scanner, der Quelltext in Token umwandelt.
Yacc: Baut auf Lex auf und generiert einen Parser, der die Token analysiert und einen Syntaxbaum erstellt.
Lex:
Yacc:
Beide Werkzeuge wurden im Unix-Umfeld entwickelt und sind heute als welche Versionen verfügbar?
Beide Werkzeuge wurden im Unix-Umfeld entwickelt und sind heute als GNU-Versionen (Flex, Bison) verfügbar.
Was wird auf folgendem Bild dargestellt?
Wie könnte eine Abbildung für das Zusammenspiel von Lex und Yacc aussehen?
Das Ziel der Softwareentwicklung ist, Programme zu erstellen, die korrekt funktionieren. In welche 3 Bereiche lässt sich die Korrektheit aufteilen?
1. Syntaktische Korrektheit
2. Semantische Korrektheit
3. Pragmatische Korrektheit
Das Ziel der Softwareentwicklung ist, Programme zu erstellen, die korrekt funktionieren. Die Korrektheit lässt sich in drei Bereiche aufteilen:
Was bedeutet die Syntaktische Korrektheit?
Bedeutet, dass ein Programm den Regeln der Programmiersprache entspricht.
Erreicht, wenn ein Programm fehlerfrei kompiliert.
Die Überprüfung erfolgt durch die Syntaxregeln der Programmiersprache und ist in der Praxis entscheidbar.
Was bedeutet Semantische Koeektheit?
Stellt sicher, dass ein Programm das tut, was es soll.
Schwieriger zu prüfen, da oft unklar ist, was ein Programm genau leisten soll.
Tests und Reviews helfen, können aber keine allgemeingültige Garantie bieten.
Formale Methoden wie mathematische Beweise und Spezifikationen können eingesetzt werden, sind aber aufwendig und meist nur für sicherheitskritische Anwendungen sinnvoll.
Was bedeutet Pragmatische Korrektheit?
Prüft, ob ein Programm praktische Anforderungen erfüllt, z. B. Effizienz oder Einhaltung von Programmierstandards.
Einfachere Eigenschaften wie Namenskonventionen sind automatisierbar.
Komplexere Eigenschaften, die Verständnis erfordern, sind schwieriger entscheidbar.
Formale Methoden
Was ist das Ziel, die Vorraussetzung und wo werden sie angewendet?
Ziel: Entwicklung von Software, deren Korrektheit nachweisbar ist.
Voraussetzung: Eine klare Spezifikation, was das Programm leisten soll.
Anwendung: Vor allem bei sicherheitskritischen Projekten (z. B. Flugzeugsoftware oder industrielle Steuerungen).
Davon gibt es zwei Varianten welche im deutschen nur als Sicherheit bezeichnet werden. Wie heißen diese?
„Safety“ und „Security“
Sicherheit
Was beschreibt die Funktionale Sicherheit (Safety)?
Funktionale Sicherheit (Safety): Verhindert, dass ein System Schäden verursacht (z. B. funktionierende Bremsen).
Was beschreibt die Betriebssicherheit (Security)?
Betriebssicherheit (Security): Schützt ein System vor äußeren Einflüssen (z. B. IT-Sicherheit).
Wie lautet der wichtige Nachweis wenn es um die Sicherheit von sicherheitskritischen Systemen geht?
der Nachweis der Freiheit von Deadlocks,
dass also kein Fall eintreten kann, in dem sich verschiedene Teile eines Systems gegenseitig blockieren,
meist durch gleichzeitigen Zugriff auf gemeinsame Ressourcen.
Was ist die Horate-Logik?
Mathematisches System, um Programme zu beweisen.
Was ist der Grundbaustein der Horare-Logik?
Das Hoare-Tripel:
{P}S{Q} – Wenn Vorbedingung P gilt und Programm S ausgeführt wird, gilt Nachbedingung Q.
Was ist der Unterschied von
Partieller Korrektheit und
Totaler Korrektheit?
Unterschied zwischen:
Partielle Korrektheit: Das Programm liefert das richtige Ergebnis, falls es terminiert.
Totale Korrektheit: Das Programm liefert immer ein Ergebnis und terminiert sicher.
Was ist die Grundidee der künstlichen Intelligenz?
Die Grundidee der künstlichen Intelligenz ist es,
Verhalten oder Verfahren zu automatisieren, die man sonst als „intelligent“ bezeichnen würde.
Einer der ersten, der sich systematisch mit dieser Frage befasst hat, war Alan Turing, der dafür den heute als Turing-Test bekannten Test entwickelte.
Was ist die Grundidee des Turing-Tests?
Grundidee des Turing-Tests ist es,
Dabei versucht ein Mensch, durch einen elektronischen Kanal herauszufinden,
ob er mit einem Menschen oder einem Computer kommuniziert. Kann er dies nicht erkennen, gilt der Computer als intelligent.
Anwendungen der Künstlichen Intelligenz:
Welche 2 Anwendungen der KI gibt es?
Expertensysteme:
Verarbeitung natürlicher Sprache (NLP):
Was unterstützen diese und woraus bestehen sie?
Expertensysteme: Diese Systeme unterstützen wie ein menschlicher Experte bei speziellen Aufgaben, z. B. in der Medizin. Sie bestehen aus:
Einer Wissensbasis (Fakten und Regeln, oft mit der Logik-Programmiersprache Prolog erstellt)
Einer Regelmaschine (führt die Regeln aus). Die größte Herausforderung dabei ist, das Wissen von Experten in Regeln und Fakten zu übersetzen.
Worum geht es dabei und was sollen sie können?
Verarbeitung natürlicher Sprache (NLP): Hier geht es um das Verstehen und Erzeugen von menschlicher Sprache.
Sätze erzeugen ist vergleichsweise einfacher, weil Sonderfälle oft ignoriert werden können.
Sprache analysieren ist schwieriger, da natürliche Sprachen weniger strukturiert sind als formale Sprachen.
Was nutzen moderne KI-Methoden um aus großen Datenmengen zu lernen und neue Erkenntnisse zu gewinnen?
Data Science
Warum ist es so schwierig, Wissen von Experten in Form von Fakten und Regeln zu formulieren?
Die größte Schwierigkeit besteht darin, dass Experten durch ihre Erfahrung zwar oft in der Lage sind, korrekte Entscheidungen zu treffen,
aber nur schwer erläutern und begründen können, wie sie zu dieser Entscheidung gekommen sind.
Was ist Kryptologie und auf welchem kryptoligischen Verfahren basieren diese?
Kryptologie ist die Wissenschaft der Ver- und Entschlüsselung von Nachrichten und existiert schon seit der Antike.
Dabei wird ein Schlüssel genutzt, um Nachrichten zu verschlüsseln und später wieder zu entschlüsseln. Ohne den Schlüssel soll die Entschlüsselung sehr schwierig sein
Welche 2 Verschlüsselungsverfahren gibt es?
Symmetrische Verschlüsselung
Asymmetrische Verschlüsselung (Public-Key-Kryptographie):
Wie funktioniert die Symmetrische Verschlüsselung?
Symmetrische Verschlüsselung:
Sender und Empfänger verwenden denselben Schlüssel zum Ver- und Entschlüsseln.
Problem: Der Schlüssel muss vorher sicher ausgetauscht werden.
Schwierigkeit: Bei vielen Kommunikationspartnern braucht man für jede Verbindung einen eigenen Schlüssel.
Wie funktioniert die Asymmetrische Verschlüsselung?
Jeder hat ein Schlüsselpaar:
Öffentlicher Schlüssel: Wird für die Verschlüsselung genutzt.
Geheimer Schlüssel: Wird für die Entschlüsselung genutzt.
Vorteil: Der öffentliche Schlüssel kann frei weitergegeben werden, und die Kommunikation bleibt auch über unsichere Kanäle (z. B. Internet) geheim.
Herausforderung: Der geheime Schlüssel darf nicht aus dem öffentlichen Schlüssel ableitbar sein.
Auf welchen Funktionen beruhen Asymetrische Verfahren?
Asymmetrische Verfahren beruhen auf Einwegfunktionen.
Was sind deren Eigenschaften?
Diese sind leicht zu berechnen, aber schwer umzukehren (also die "Rückrichtung" zu berechnen). Ein Beispiel:
Telefonbuch: Es ist einfach, zu einem Namen die Telefonnummer zu finden, aber schwer, umgekehrt den Namen zu einer Telefonnummer herauszusuchen.
Benenne 3 Beispiele für Einwegfunktionen in der Kryptologie.
Beispiele für Einwegfunktionen in der Kryptologie:
Primfaktorzerlegung:
Modulare Exponentiation:
Kryptografische Hash-Funktionen (z. B. MD5, SHA):
Komplexität und Sicherheit
Worauf basierd die Sicherheit Asymetrischer Verfahren?
Die Sicherheit asymmetrischer Verfahren wie RSA basiert darauf, dass es aktuell keinen schnellen Algorithmus für die Primfaktorzerlegung gibt:
Was ist die bekannteste Einwegfunktion und woraus besteht dieses Verfahren?
Wofür bildet sie die Basis?
Multiplikation großer Primzahlen
Leicht vereinfacht besteht bei diesem Verfahren der öffentliche Schlüssel aus dem Produkt der beiden Primzahlen,
der geheime Schlüssel aus den beiden Faktoren.
Damit ist das Verfahren nur solange sicher, wie es praktisch nicht möglich ist, das Produkt in seine Primfaktoren zu zerlegen.
bildet die Basis für den
RSA-Algorithmus
Quantencomputer könnten viele heutige Verschlüsselungen unsicher machen:
Wie heißt der Algorithmus welcher auf einem Quantencomputer die Primfaktorzerlegung und die Berechnung des diskreten Logarithmus in Polynomialzeit erlaubt?
Um zukünftige Bedrohungen abzuwehren, entwickelt man neue Verfahren, die auch mit Quantencomputern sicher sind.
Wie nennt man diese Verfahren?
Last changed20 days ago
