Einleitung

Organisatorisches

Haus-Aufgaben

Bei Vorführung: Pool-Rechner benutzen (nicht mitgebrachte eigene) (Chancengleichheit, Reproduzierbarkeit), große (Control-Plus), schwarze Schrift auf weißem Grund

WS 25: 7, 5, 4, optional (wenn Zeit ist) 8

  1. Lesen Sie E. W. Dijkstra: On the foolishness of "natural language programming" https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD667.html

    und beantworten Sie

    • womit wird “einfaches Programmieren” fälschlicherweise gleichgesetzt?

    • welche wesentliche Verbesserung brachten höhere Programmiersprachen, welche Eigenschaft der Maschinensprachen haben sie trotzdem noch?

    • warum sollte eine Schnittstelle narrow sein?

    • welche formalen Notationen von Vieta, Descartes, Leibniz, Boole sind gemeint? (jeweils: Wissenschaftsbereich, (heutige) Bezeichnung der Notation, Beispiele)

    • warum können Schüler heute das lernen, wozu früher nur Genies in der Lage waren?

    • Übersetzen Sie den Satz “the naturalness …obvious”.

    Geben Sie dazu jeweils an:

    • die Meinung des Autors, belegt durch konkrete Textstelle und zunächst wörtliche, dann sinngemäße Übersetzung

    • Beispiele aus Ihrer Erfahrung

  2. zu John C. Reynolds: Some Thoughts on Teaching Programming and Programming Languages 2008, von An additional reason for teaching programming languages… bis Ende:

    • Warum wird auf Turing-Vollständigkeit verwiesen?

    • Geben Sie Beispiele aus Ihrer Erfahrung für problematische input formats, oder problemfreie.

    • partial list of the kind of capabilities…: ordnen Sie die Listenelemente konkreten Lehrveranstaltungen zu (bereits absolvierte oder noch kommende)

  3. zu Skriptsprachen: finde die Anzahl der "*.java"-Dateien unter $HOME/workspace, die den Bezeichner String enthalten (oder eine ähnliche Anwendung) (Benutze eine Pipe aus drei Unix-Kommandos.)

    Lösungen:

    find workspace/ -name "*.java" | xargs grep -l String       | wc -l
find workspace/ -name "*.java"   -exec grep -l String {} \; | wc -l

    Das dient als Wiederholung zur Benutzung von Unix (GNU/Linux): führen Sie vor:

  4. funktionales Programmieren in Haskell (http://www.haskell.org/)

    ghci
:set +t
length $ takeWhile (== '0') $ reverse $ show $ product [ 1 .. 100 ]

    • zeigen Sie (den Studenten, die das noch nicht gesehen haben), wo die Software (hier ghc) im Pool installiert ist, und wie man sie benutzt und die Benutzung vereinfacht (PATH)

    • Werten Sie den angegebenen Ausdruck aus sowie alle Teilausdrück ([1..100], product [1..100], usw.

    • den Typ von reverse durch ghci anzeigen lassen

    • nach diesem Typ in https://hoogle.haskell.org/ suchen. (Einschränken auf package:base) Die anderen (drei) Funktionen dieses Typs aufrufen.

    • eine davon erzeugt unendliche Listen, wie werden die im Speicher repräsentiert, wie kann man sie benutzen? (Am Beispiel zeigen.)

  5. PostScript

    42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage

    In eine Text-Datei what.ps schreiben (vgl. Aufgabe [aufg:edit]) ansehen mit gv what.ps (im Menu: State \(\to\) watch file).

    Mit Editor Quelltext ändern, Wirkung betrachten.

    • Ändern Sie die Strich-Stärke!

    • wie funktioniert die Steuerung einer Zählschleife?

    • warum ist PostScript: imperativ? strukturiert? prozedural?

    • führen Sie wenigstens ein weiteres ähnliches PostScript-Programm vor (kurzer Text, aber nichttriviale Rechnung). Quelle angeben, Programmtext erklären!

  6. In SICP 1.1 werden drei Elemente der Programmierung genannt. Illustrieren Sie diese Elemente durch Beispiele aus https://web.archive.org/web/20241109065141/https://www.99-bottles-of-beer.net/

    Führen Sie nach Möglichkeit vor (im Pool, nicht in Web-Oberfläche von Dritt-Anbietern).

  7. Stellen Sie Ihren Browser datenschutzgerecht ein (Wahl des Browsers, der Default-Suchmaschine, Blockieren von Schadsoftware.)

    In einem neuen Firefox-Profil (about:profiles) ausprobieren und diskutieren: Umatrix (dessen Log betrachten), Temporary Containers.

    Vgl.

    https://restoreprivacy.com/firefox-privacy/

    (hat selbst viele Tracker!) und weitere.

  8. erklären Sie https://xkcd.com/378/.

    führen Sie die vier genannten Editoren vor, in dem Sie jeweils eine einzeilige Textdatei erzeugen.

Einleitung

Programme und Algorithmen

Deutsch als Programmiersprache

§6 (2) …Der Zuteilungsdivisor ist so zu bestimmen, dass insgesamt so viele Sitze auf die Landeslisten entfallen, wie Sitze zu vergeben sind. Dazu wird zunächst die Gesamtzahl der Zweitstimmen aller zu berücksichtigenden Landeslisten durch die Zahl der jeweils nach Absatz 1 Satz 3 verbleibenden Sitze geteilt. Entfallen danach mehr Sitze auf die Landeslisten, als Sitze zu vergeben sind,…

§6 (5) Die Zahl der nach Absatz 1 Satz 3 verbleibenden Sitze wird so lange erhöht, bis jede Partei bei der zweiten Verteilung der Sitze nach Absatz 6 Satz 1 mindestens die bei der ersten Verteilung nach den Absätzen 2 und 3 für sie ermittelten zuzüglich der in den Wahlkreisen errungenen Sitze erhält, die nicht nach Absatz 4 Satz 1 von der Zahl der für die Landesliste ermittelten Sitze abgerechnet werden können.

https://www.gesetze-im-internet.de/bwahlg/__6.html

Struktur durch Klammern, ist doch klar

Beispiel: mehrsprachige Projekte

ein typisches Projekt besteht aus:

und das ist noch nicht die ganze Wahrheit:

nenne weitere Sprachen, die üblicherweise in einem solchen Projekt vorkommen

In / Into

Sprache

Wie unterschiedlich sind Sprachen?

Konzepte

Paradigmen

Ziele der LV

Arbeitsweise: Methoden, Konzepte, Paradigmen

Ziel:

Beziehungen zu anderen LV

Anwendungsspezifische Sprachen und Paradigmen:

Organisation

Literatur

Zum Vergleich/als Hintergrund:

Inhalt

(nach Sebesta: Concepts of Programming Languages)

Haus-Aufgaben

Bei Vorführung: Pool-Rechner benutzen (nicht mitgebrachte eigene) (Chancengleichheit, Reproduzierbarkeit), große (Control-Plus), schwarze Schrift auf weißem Grund

WS 25: 7, 5, 4, optional (wenn Zeit ist) 8

  1. Lesen Sie E. W. Dijkstra: On the foolishness of "natural language programming" https://www.cs.utexas.edu/users/EWD/transcriptions/EWD06xx/EWD667.html

    und beantworten Sie

    • womit wird “einfaches Programmieren” fälschlicherweise gleichgesetzt?

    • welche wesentliche Verbesserung brachten höhere Programmiersprachen, welche Eigenschaft der Maschinensprachen haben sie trotzdem noch?

    • warum sollte eine Schnittstelle narrow sein?

    • welche formalen Notationen von Vieta, Descartes, Leibniz, Boole sind gemeint? (jeweils: Wissenschaftsbereich, (heutige) Bezeichnung der Notation, Beispiele)

    • warum können Schüler heute das lernen, wozu früher nur Genies in der Lage waren?

    • Übersetzen Sie den Satz “the naturalness …obvious”.

    Geben Sie dazu jeweils an:

    • die Meinung des Autors, belegt durch konkrete Textstelle und zunächst wörtliche, dann sinngemäße Übersetzung

    • Beispiele aus Ihrer Erfahrung

  2. zu John C. Reynolds: Some Thoughts on Teaching Programming and Programming Languages 2008, von An additional reason for teaching programming languages… bis Ende:

    • Warum wird auf Turing-Vollständigkeit verwiesen?

    • Geben Sie Beispiele aus Ihrer Erfahrung für problematische input formats, oder problemfreie.

    • partial list of the kind of capabilities…: ordnen Sie die Listenelemente konkreten Lehrveranstaltungen zu (bereits absolvierte oder noch kommende)

  3. zu Skriptsprachen: finde die Anzahl der "*.java"-Dateien unter $HOME/workspace, die den Bezeichner String enthalten (oder eine ähnliche Anwendung) (Benutze eine Pipe aus drei Unix-Kommandos.)

    Lösungen:

    find workspace/ -name "*.java" | xargs grep -l String       | wc -l
find workspace/ -name "*.java"   -exec grep -l String {} \; | wc -l

    Das dient als Wiederholung zur Benutzung von Unix (GNU/Linux): führen Sie vor:

  4. funktionales Programmieren in Haskell (http://www.haskell.org/)

    ghci
:set +t
length $ takeWhile (== '0') $ reverse $ show $ product [ 1 .. 100 ]

    • zeigen Sie (den Studenten, die das noch nicht gesehen haben), wo die Software (hier ghc) im Pool installiert ist, und wie man sie benutzt und die Benutzung vereinfacht (PATH)

    • Werten Sie den angegebenen Ausdruck aus sowie alle Teilausdrück ([1..100], product [1..100], usw.

    • den Typ von reverse durch ghci anzeigen lassen

    • nach diesem Typ in https://hoogle.haskell.org/ suchen. (Einschränken auf package:base) Die anderen (drei) Funktionen dieses Typs aufrufen.

    • eine davon erzeugt unendliche Listen, wie werden die im Speicher repräsentiert, wie kann man sie benutzen? (Am Beispiel zeigen.)

  5. PostScript

    42 42 scale 7 9 translate .07 setlinewidth .5 setgray/c{arc clip fill
setgray}def 1 0 0 42 1 0 c 0 1 1{0 3 3 90 270 arc 0 0 6 0 -3 3 90 270
arcn 270 90 c -2 2 4{-6 moveto 0 12 rlineto}for -5 2 5{-3 exch moveto
9 0 rlineto}for stroke 0 0 3 1 1 0 c 180 rotate initclip}for showpage

    In eine Text-Datei what.ps schreiben (vgl. Aufgabe [aufg:edit]) ansehen mit gv what.ps (im Menu: State \(\to\) watch file).

    Mit Editor Quelltext ändern, Wirkung betrachten.

    • Ändern Sie die Strich-Stärke!

    • wie funktioniert die Steuerung einer Zählschleife?

    • warum ist PostScript: imperativ? strukturiert? prozedural?

    • führen Sie wenigstens ein weiteres ähnliches PostScript-Programm vor (kurzer Text, aber nichttriviale Rechnung). Quelle angeben, Programmtext erklären!

  6. In SICP 1.1 werden drei Elemente der Programmierung genannt. Illustrieren Sie diese Elemente durch Beispiele aus https://web.archive.org/web/20241109065141/https://www.99-bottles-of-beer.net/

    Führen Sie nach Möglichkeit vor (im Pool, nicht in Web-Oberfläche von Dritt-Anbietern).

  7. Stellen Sie Ihren Browser datenschutzgerecht ein (Wahl des Browsers, der Default-Suchmaschine, Blockieren von Schadsoftware.)

    In einem neuen Firefox-Profil (about:profiles) ausprobieren und diskutieren: Umatrix (dessen Log betrachten), Temporary Containers.

    Vgl.

    https://restoreprivacy.com/firefox-privacy/

    (hat selbst viele Tracker!) und weitere.

  8. erklären Sie https://xkcd.com/378/.

    führen Sie die vier genannten Editoren vor, in dem Sie jeweils eine einzeilige Textdatei erzeugen.

Syntax von Programmiersprachen

Konkrete und abstrakte Syntax

Fernschreiber, Editor…

Terminal (Konsole)

Ganz ganz ganz kurze Geschichte der (Programmiersprachen und) Betriebssysteme

Programme als Bäume

Token-Klassen

alle Token einer Klasse bilden eine formale Sprache.

Formale Sprachen

Beispiele:

Lexik (Bsp): numerische Literale

Spezifikation formaler Sprachen

man kann eine formale Sprache beschreiben:

Sprach-Operationen

Aus Sprachen \(L_1, L_2\) konstruiere:

Def: Sprache regulär \(:\iff\) kann durch diese Operationen aus endlichen Sprachen konstruiert werden.

Satz: Durchschnitt und Differenz braucht man dabei nicht.

Reguläre Sprachen/Ausdrücke

Die Menge \(E(\Sigma)\) der regulären Ausdrücke
über einem Alphabet (Buchstabenmenge) \(\Sigma\)
ist die kleinste Menge \(E\), für die gilt:

Jeder solche Ausdruck beschreibt eine reguläre Sprache.

Beispiele/Aufgaben zu regulären Ausdrücken

Wir fixieren das Alphabet \(\Sigma=\{a,b\}\).

Erweiterte reguläre Ausdrücke

  1. zusätzliche Operatoren (Durchschnitt, Differenz, Potenz),

    die trotzdem nur reguläre Sprachen erzeugen

    Beispiel: \(\Sigma^* \setminus ( \Sigma^* ab \Sigma^*)^2\)

    ähnlich in Konfiguration der autotool-Aufgaben

  2. zusätzliche nicht-reguläre Operatoren

    Beispiel: exakte Wiederholungen \(L^{\fbox{$k$}} := \{ w^k \mid w\in L \}\)

    Bsp.: \((ab^*)^{\fbox{2}} = \{aa, abab, abbabb, ab^3ab^3, \dots\}\notin\mathsf{REG}\)

  3. Markierung von Teilwörtern, definiert (evtl. nicht-reguläre) Menge von Wörtern mit Positionen darin

Implementierung regulärer Ausdrücke

Bemerkung zu Reg. Ausdr.

Wie beweist man \(w\in \operatorname{L}(X)\)?

(Wort \(w\) gehört zur Sprache eines regulären Ausdrucks \(X\))

Beispiel: \(w = abba, X = (ab^*)^*\).

\(w = abb\cdot a = ab^2 \cdot a b^0 \in ab^* \cdot ab^* \subseteq (ab^*)^2 \subseteq (ab^*)^*\).

Übungen zu Lexik (Testfragen)

(ohne Wertung, zur Wiederholung und Unterhaltung)

Aufgaben zu regulären Ausdrücken: autotool. Das ist Wiederholung aus VL Theoretische Informatik—Automaten und Formale Sprachen.

Hausaufgaben

WS 25: 1, (3 oder 4 oder 5), 7.

  1. Für jedes Monoid \(M=(D,\cdot,1)\) definieren wir die Teilbarkeits-Relation \(u\mid w := \exists v: u \cdot v = w\)

    Geben Sie Beispiele \(u\mid w\), \(\neg(u\mid w)\) an in den Monoiden

    • \((\mathbb{N},+,0)\)

    • \((\mathbb{Z},+,0)\)

    • \((\mathbb{N},\cdot,1)\)

    • \((\{a,b\}^*,\cdot,\epsilon)\)

    • \((2^\mathbb{N},\cup,\emptyset)\)

    Zeigen Sie (nicht für ein spezielles Monoid, sondern allgemein): die Relation \(\mid\) ist reflexiv und transitiv.

    Ist sie antisymmetrisch? (Beweis oder Gegenbeispiel.)

    NB: Beziehung zur Softwaretechnik:

    • Monoid ist die Schnittstelle (API, abstrakter Datentyp),

    • \((\mathbb{N},0,+)\) ist eine Implementierung (konkreter Datentyp).

    • allgemein zeigen bedeutet: nur die in den Axiomen des ADT (API-Beschreibung) genannten Eigenschaften benutzen

  2. Zeichnen Sie jeweils das Hasse-Diagramm dieser Teilbarkeitsrelation

    • für \((\mathbb{N},+,0)\), eingeschränkt auf \(\{0,1,\dots,4\}\)

    • für \((\mathbb{N},\cdot,1)\), eingeschränkt auf \(\{0,1,\dots,10\}\)

    • für \((2^{\{p,q,r\}},\cup,\emptyset)\)

    • für \((\{a,b\}^*,\cdot,\epsilon)\) auf \(\{a,b\}^{\le 2}\)

    Geben Sie eine Halbordnung auf \(\{0,1,2\}^2\) an, deren Hasse-Diagramm ein auf der Spitze stehendes Quadratnetz ist.

    Diese Halbordnung soll intensional angegeben werden (durch eine Formel), nicht extensional (durch Aufzählen aller Elemente).

  3. Führen Sie vor (auf Rechner im Pool Z430, vorher von außen einloggen und probieren)

    Editieren, Kompilieren, Ausführen eines kurzen (maximal 3 Zeilen) Pascal-Programms

    Der Compiler fpc (https://www.freepascal.org/) ist installiert (/usr/local/waldmann/opt/fpc/latest).

    (Zweck dieser Teilaufgabe ist nicht, daß Sie Pascal lernen, sondern der Benutzung von ssh, evtl. tmux, Kommandozeile (PATH), Text-Editor wiederholen)

    Zu regulären Ausdrücke für Tokenklassen in der Standard-Pascal-Definition https://archive.org/details/iso-iec-7185-1990-Pascal/

    Welche Notation wird für unsere Operatoren \(+\) und Stern benutzt? Was bedeuten die eckigen Klammern?

    In Ihrem Beispiel-Programm: erproben Sie mehrere (korrekte und fehlerhafte) Varianten für Gleitkomma-Literale. Vergleichen Sie Spezifikation (geben Sie den passenden Abschnitt der Sprachdefinition an) und Verhalten des Compilers.

    Dieser Compiler (fpc) ist in Pascal geschrieben. Was bedeutet das für: Installation des Compilers, Entwicklung des Compilers?

  4. Führen Sie vor (wie und warum: siehe Bemerkungen vorige Aufgabe): Editieren, Kompilieren (javac), Ausführen (java) eines kurzen (maximal 3 Zeilen) Java-Programms.

    Suchen und buchmarken Sie die Java Language Specification (Primärquelle in der aktuellen Version) Beantworten Sie damit (und nicht mit Hausaufgabenwebseiten und anderen Sekundärquellen):

    gehören in Java

    • null

    • Namen für Elemente von Aufzählungstypen

    zur Tokenklasse Literal, reserviertes Wort (Schlüsselwort), Bezeichner (oder evtl. anderen)?

    Wo stehen die Token-Definitionen im javac-Compiler? https://hg.openjdk.java.net/jdk/jdk15/file/ (bzw. aktuelle Version)

    In Ihrem Beispiel-Programm: erproben Sie verschiedene Varianten von Ganzzahl-Literalen (siehe vorige Aufgabe)

  5. Führen Sie vor (wie vorige Aufgaben): Kompilation und Ausführung eines sehr kurzen Ada-Programms

    with Ada.Text_IO; use Ada.Text_IO;
procedure floating is
begin put_line (float'image( 2)); -- fehlerhafter Quelltext!
end floating;

    Verwenden Sie den GNU Ada Translator, ist Teil von GCC (GNU Compiler Collection).

    Ist im Pool installliert, siehe https://www.imn.htwk-leipzig.de/~waldmann/etc/pool/

    Aufrufen mit gnatmake floating.adb (kompilieren und linken), ausführen mit ./floating.

    Erläutern Sie die Fehlermeldung durch Verweis auf den Sprachstandard. Setzen Sie passende Literale ein (ändern Sie den Rest des Programms nicht). Probieren Sie dabei alle Zweige und Optionen in den regulären Ausdrücken des Standards (2.4.1).

  6. Im WS22 hatten Teilnehmer dieser LV diese Fehler im GNU Ada Translator (gnat, Teil von gcc) gefunden:

    Untersuchen Sie ähnliches für Compiler für andere Sprachen.

  7. Suchen und diskutieren Sie Wadler’s law (of language design).

    Am Entwurf welcher Programmiersprachen war der Autor beteiligt? Welche Sprache hat er in einem aktuellen Lehrbuch benutzt?

    Untersuchen Sie für (wenigstens) Java und Haskell, ob Block-Kommentare geschachtelt werden können. Belegen Sie durch

    • Sprachstandard (exakte Definition von Kommentaren)

    • und eigene Beispiele (einfachste Programme, die vom Compiler akzeptiert oder abgelehnt werden)

  8. Gelten die Aussagen von Cox (2007) (but it’s slow in…) jetzt immer noch? Überprüfen Sie das praktisch (die Testfälle aus dem zitierten Paper oder ähnliche).

Syntaxbäume

Wort-Ersetzungs-Systeme

Berechnungs-Modell (Markov-Algorithmen)

Syntax: Programm ist Regelmenge \(R \subseteq \Sigma^* \times \Sigma^*\),
Semantik: die 1-Schritt-Ableitungsrelation \(\to_R\), Hülle \(\to_R^*\)

\(u \to_R v \iff \exists x,z\in\Sigma^*, (l,r) \in R: u = x \cdot l\cdot z \wedge x \cdot r \cdot z = v\).

Grammatiken

Grammatik \(G\) besteht aus:

Grammatik
  { terminale 
       = mkSet "abc"
  , variablen
       = mkSet "SA"
  , start = 'S'
  , regeln = mkSet
       [ ("S", "abc")
       , ("ab", "aabbA")
       , ("Ab", "bA")
       , ("Ac", "cc")
       ]
  }

von \(G\) erzeugte Sprache: \(L(G) = \{ w \mid S \to_R^* w \wedge w \in \Sigma^* \}\).

Formale Sprachen: Chomsky-Hierarchie

Tokenklassen sind meist reguläre Sprachen.

Syntax von Programmiersprachen meist kontextfrei.

Zusatzbedingungen (Bsp: Benutzung von Bezeichnern nur nach Deklaration) meist Teil der statischen Semantik

(Menge der stat. korrekten Programme ist nicht kontextfrei)

Typ-3-Grammatiken

(\(=\) rechtslineare Gr.) jede Regel hat die Form

(vgl. lineares Gleichungssystem), Beispiel

Anwendung: Kommentare in Java

https://docs.oracle.com/javase/specs/jls/se25/html/jls-3.html#jls-3.7

TraditionalComment:  |  CommentTail:         
  / * CommentTail    |    * CommentTailStar  
                     |    NotStar CommentTail

Sätze über reguläre Sprachen

Für jede Sprache \(L\) sind die folgenden Aussagen äquivalent:

Beweispläne:

Kontextfreie Sprachen

Def (Wdhlg): \(G\) ist kontextfrei (Typ-2), falls \(\forall (l,r) \in R(G): l \in V^1\)

geeignet zur Beschreibung von Sprachen mit hierarchischer Struktur.

Anweisung -> Bezeichner = Ausdruck
    | if Ausdruck then Anweisung else Anweisung
Ausdruck -> Bezeichner | Literal
    | Ausdruck Operator Ausdruck

Bsp: korrekt geklammerte Ausdrücke: \(G = ( \{ a,b\}, \{S\}, S, \{ S \to aSbS, S \to \epsilon \} )\).

Bsp: Palindrome: \(G = ( \{ a,b\}, \{S\}, S, \{ S \to aSa, S \to bSb, S \to \epsilon )\).

Bsp: alle Wörter \(w\) über \(\Sigma=\{a,b\}\) mit \(|w|_a = |w|_b\)

Klammer-Sprachen

Abstraktion von vollständig geklammerten Ausdrücke mit zweistelligen Operatoren

(4*(5+6)-(7+8)) \(\Rightarrow\) (()()) \(\Rightarrow aababb\)

Höhendifferenz: \(h : \{a,b\}^* \to \mathbb{Z}: w \mapsto |w|_a - |w|_b\)

Präfix-Relation: \(u \le w :\iff \exists v: u\cdot v = w\)

Dyck-Sprache: \(D=\{w \mid h(w)=0 \wedge \forall u\le w: h(u)\ge 0\}\)

CF-Grammatik: \(G = (\{a,b\},\{S\},S,\{S\to\epsilon,S\to aSbS\})\)

Satz: \(L(G)=D\). Beweis (Plan):

\(L(G)\subseteq D\) Induktion über Länge der Ableitung

\(D\subseteq L(G)\) Induktion über Wortlänge

(erweiterte) Backus-Naur-Form

Backus-Naur-Form (BNF) \(\approx\) kontextfreie Grammatik

<assignment> -> <variable> = <expression>
<number> -> <digit> <number> | <digit>

Erweiterte BNF

kann in BNF übersetzt werden

Ableitungsbäume für CF-Sprachen

Def: ein geordneter Baum \(T\) mit Markierung \(m: T \to \Sigma\cup\{\epsilon\}\cup V\) ist Ableitungsbaum für eine CF-Grammatik \(G\), wenn:

Ableitungsbäume (II)

Bsp. Ableitungsbaum (Deutsch)

bezüglich einer Phrasenstrukturgrammatik des Deutschen

image

G. Müller, Linguistische Grundlagen (VL 8), 2009

https://home.uni-leipzig.de/muellerg/1001/grundlagen.html

Bsp. Ableitungsbaum (Musik)

Fred Lerdahl and Ray Jackendoff: A Generative Theory of Tonal Music, 1983

image

vgl. Hansen: The Legacy of GTTM,

http://www.dym.dk/dym_pdf_files/volume_38/volume_38_033_055.pdf

2010

Eindeutigkeit

Assoziativität

Assoziativität (II)

Präzedenzen

Zusammenfassung Operator/Grammatik

Ziele:

Festlegung:

Realisierung in CFG:

Hausaufgaben

WS 25: 2, 4, 6

  1. Definition: für ein Wortersetzungssystem \(R\):

    Die Menge der \(R\)-Normalformen eines Wortes \(x\) ist: \(\textsf{Nf}(R,x):=\{y \mid x\to_R^* y \wedge \neg\exists z: y\to_R z\}\)

    Für das \(R=\{ab\to baa\}\) über \(\Sigma=\{a,b\}\):

    bestimmen Sie die \(R\)-Normalformen von

    • \(a^3 b\), allgemein \(a^kb\),

    • \(a b^3\), allgemein \(a b^k\),

    die allgemeinen Aussagen exakt formulieren, für \(k=3\) überprüfen, durch vollständige Induktion beweisen.

  2. Für Alphabet \(\Sigma=\{a,b\}\), Sprache \(E=\{w : w\in \Sigma^* \wedge |w|_a=|w|_b \}\), Grammatik \(G=(\Sigma,\{S\}, S,\{ S\to \epsilon, S\to SS, S\to aSb, S\to bSa \})\):

    • Geben Sie ein \(w\in E\) mit \(|w|=8\) an mit zwei verschiedenen \(G\)-Ableitungsbäumen.

    • Beweisen Sie \(L(G)\subseteq E\) durch strukturelle Induktion über Ableitungsbäume.

    • Beweisen Sie \(E\subseteq L(G)\) durch Induktion über Wortlänge. Benutzen Sie im Induktionsschritt diese Fallunterscheidung für \(w\in E\): hat \(w\) einen nicht leeren echten Präfix \(u\) mit \(u\in E\)? Wenn ja, dann beginnt eine Ableitung für \(w\) mit \(S\to SS\). Wenn nein, dann mit welcher Regel?

  3. Vergleichen sie Definitionen und Bezeichnungen für phrase structure grammars Noam Chomsky: Three Models for the Description of Language, 1956, Abschnitt 3, https://chomsky.info/articles/, mit den heute üblichen (kontextfreie Grammatik, Ableitung, erzeugte Sprache, Ableitungsbaum)

    Erläutern Sie The rule (34) … cannot be incorporated… (Ende Abschnitt 4.1)

  4. vergleichen Sie die Syntax-Definitionen von Fortran (John Backus 1956) und Algol (Peter Naur 1960),

    Quellen: Historic Documents in Computer Science, collected by Karl Kleine, http://web.eah-jena.de/~kleine/history/ (benutze Wayback Machine https://web.archive.org/)

    Führen Sie Kompilation und Ausführen eines Fortran-Programms vor (im Pool ist gfortran installiert, als Teil von GCC (GNU Compiler Collection))

    Verwenden Sie dabei nur einfache Arithmetik und einfache Programmablaufsteuerung.

    Geben Sie den Assembler-Code aus (Option -S). Vergleichen Sie mit Assembler-Code des entsprechenden C-Programms.

  5. für die Java-Grammatik (nach JLS in aktueller Version)

    • es werden tatsächlich zwei Grammatiken benutzt (lexikalische, syntaktische), zeigen Sie deren Zusammenwirken an einem einfachen Beispiel (eine Ableitung, bei der in jeder Grammatik nur wenige Regeln benutzt werden)

    • bestimmen Sie den Ableitungsbaum (bzgl. der syntaktischen Grammatik) für das übliche hello world-Programm,

    • Beispiele in jshell vorführen. Wie lautet die Grammatik für die dort erlaubten Eingaben? Ist das Teil der JLS? Wenn nein, finden Sie eine andere Primärquelle.

  6. bzgl. der eindeutigen Grammatik für arithmetische Ausdrücke (aus diesem Skript):

    • Ableitungsbaum für 1*2-3*4

    • Grammatik erweitern für geklammerte Ausdrücke,

      Eindeutigkeit begründen,

      Ableitungsbaum für 1*(2-3)*4 angeben

    arithmetische Ausdrücke in Java:

    • welche Variable der Java-Grammatik erzeugt arithmetische Ausdrücke?

    • Ableitungsbaum für 1*(2-3)*4 von dieser Variablen aus angeben (und live vorführen durch Verfolgung der URLs der Grammatik-Variablen)

    • Beziehung herstellen zu den Regeln auf Folie Zusammenfassung Operator/Grammatik.