Warum versteht mich mein Taschenrechner?

 Funktionale Programmierung

 30 views
of 31
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
Anmerkung des Autor Diese Präsentation ist mit Powerpoint für MacOS erstellt. Leider ist sie nicht vollständig mit Powerpoint für Windows kompatibel. Das…
Share
Transcript
Anmerkung des Autor Diese Präsentation ist mit Powerpoint für MacOS erstellt. Leider ist sie nicht vollständig mit Powerpoint für Windows kompatibel. Das hat zur Folge, dass die Animationen nicht korrekt abgearbeitet werden und erscheinende Elemente zum Teil nicht wieder verschwinden. Dirk Pape. Warum versteht mich mein Taschenrechner? Von der Formel zum Ergebnis Dr. Dirk Pape, Institut für Informatik, Freie Universität Berlin http://www.inf.fu-berlin.de/~pape/ zum 1. Berliner MNU-Kongress, Sept. 2002 Der klassische Taschenrechner reagiert auf Tastendrucke 5 5 * 5.0 3 0 30 sin 0.5 = 2.5 Der Computer interpretiert Formeln 5 * sin(30) =2.5 speichert Formeln f(x) = 5 * sin(x) ok. f(30) =2.5 formt Formeln um, etc. Was bedeutet „interpretieren“? • Wörter (Symbole) erkennen Z.B. Pferd, das oder Satzzeichen • Sätze (Syntax) erkennen Z.B. Das Pferd hält schwarz • Bedeutung (Semantik) ermitteln ??? Formeln interpretieren • Wörter (Symbole) erkennen 5, *, sin, (, 30, ) • Sätze (Syntax) erkennen * 5 sin 30 • Bedeutung (Semantik) ermitteln =2.5 Phasen des Interpretierens Formel in abstrakter Syntax * 5 sin 30 Analyse Synthese Formel als Text Berechne Formel 5*sin(30) =2,5 Abstrakte Syntax – Beispiel: eine Datenstruktur für Formeln data Formel = ZAHL Int | PLUS Formel Formel | MAL Formel Formel | SIN Formel | COS Formel | VAR String Formeln rekursiv berechnen Berechne 1 1 1. Berechne 2 * -> 5 2 3 2. Berechne 3 5 sin Berechne 4 -> 30 4 Berechne sin (30) 30 -> 0.5 3. Berechne 5 * 0.5 -> 2.5 Berechnen – Beispiel berechnen(f) = case f of ZAHL n -> n PLUS f1 f2 -> berechnen(f1) + berechnen(f2) MAL f1 f2 -> berechnen(f1) * berechnen(f2) SIN f -> sin (berechnen(f)) COS f -> cos (berechnen(f)) VAR v -> [„auslesen von Variable v“] Formeln umformen Forme x * (... + ...) um 1 2 * (4 + 5) * -> 2 * 4 + 2 * 5 2 3 x + + 4 5 ... ... * * 2 4 2 5 x ... x ... Umformen – Beispiel umformen(f) = case f of ZAHL n -> ZAHL n PLUS f1 f2 -> PLUS (umformen(f1)) (umformen(f2)) MAL f1 (PLUS f2 f3) -> PLUS (umformen(MAL f1 f2)) (umformen(MAL f1 f3)) MAL f1 f2 -> MAL (umformen(f1)) (umformen(f2)) SIN f -> SIN (umformen(f)) COS f -> COS (umformen(f)) VAR v -> VAR v Formeln interpretieren • Wörter (Symbole) erkennen 5, *, sin, (, 30, ) • Sätze (Syntax) erkennen * 5 sin 30 • Bedeutung (Semantik) ermitteln Berechnen =2.5, Umformen, Speichern, ... Wie versteht mich der Computer? Zeichen werden zu Wörtern ... --- ... SO...S? So...nntag? So...ndermeldung? Wörter erkennen a n s o start s x pause SOS Formelsymbole erkennen Var „cost“ ( c o start 2 3 t 5 s + 4 ( cos Tabellengesteuerter Automat ( + ) c o s * t 1 19 13 58 2 . . . . 7 2 3 3 4 4 Cos 5 1 5 Var 1 Informatiker sind erfindungsreich Computerprogramme erzeugen die Tabellen Computerprogramme erzeugen Computerprogramme, die Formeln erkennen Computerprogramme erzeugen Tabellen und Computerprogramme aus Formeln „Scanner“ erkennen Symbole bs = [a-z] zf = [0-9] cos = cos var = bs+ zahl = -?zf+ ... „Scanner“ erkennen Symbole 5*sin(30) Zahl 5 Mal Sin Klammerauf Zahl 30 Klammerzu „Scanner“ erkennen Symbole 5*cost*30 Zahl 5 Mal Var cost Mal Zahl 30 „Scanner“ erkennen Symbole 5*sin)30( Zahl 5 Mal Sin Klammerzu Zahl 30 Klammerauf Scanner-Generatoren • Lex für C, C++, Java, ... • Flex für C, C++, Java, ... • Alex für Haskell • ... Wie versteht mich der Computer? Wörter werden zu Sätzen Zahl 5 * Sinus Klammerauf Zahl 30 Klammerzu * 5 sin 30 Kellerautomat formel1 + + + formel1 formel1 + ( ) formel1 formel1 + + ( formel2 Eine Grammatik für Formeln formel : Zahl | formel Plus formel | formel Mal formel | Sinus Klammerauf formel Klammerzu | Cosinus Klammerauf formel Klammerzu | Variable | Klammerauf formel Klammerzu „Parser“ erkennen Sätze 5, *, Sinus, (, 30, ) * 5 sin 30 Formel 1 * ( ... Parser-Generatoren • Yacc für C, C++, Java, ... • Bison für C, C++, Java, ... • Happy für Haskell • ... Übersetzerbau Programmiersprachen • sind Sprachen, mit denen der Computer programmiert wird (C, Java, Haskell, ...) • haben eine Grammatik Programme • sind grammatikalisch korrekte Formeln in einer Programmiersprache • werden mit Hilfe von Scannern und Parsern analysiert • und in einfache Maschinenbefehle übersetzt (Synthese) Algorithmen im Übersetzerbau Scannen und Parsen •Endlicher Automat • Endlicher Kellerautomat • Rekursiver „Ad-hoc-Parser“ Scanner- und Parsergeneratoren • Anspruchsvolle Algorithmen Synthese • Rekursive Funktionen und Prozeduren auf baumartigen Datenstrukturen weitere „Highlights“, z. B. „bootstrapping“ Ich wünsche noch viel Spaß beim MNU-Kongress
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks