Rekursion und EBNF

Question 1

Was bedeutet es, wenn eine Funktion rekursiv definiert ist?

Answer 1

Ist eine Funktion rekursiv definiert, so erscheint die Funktion in ihrer eigenen Definition, z.B.:

𝚒𝚗𝚝 𝚏𝚊𝚔𝚞𝚕𝚝𝚊𝚎𝚝(𝚒𝚗𝚝 𝚗) {
  𝚒𝚏 (𝚗 <= 𝟷)
    𝚛𝚎𝚝𝚞𝚛𝚗 𝟷;
  𝚎𝚕𝚜𝚎
    𝚛𝚎𝚝𝚞𝚛𝚗 𝚗 * 𝚏𝚊𝚔𝚞𝚕𝚝𝚊𝚎𝚝(𝚗-𝟷);
}

Question 2

Was ist ein mögliches Problem rekursiv definierter Funktionen und wie lässt sich dieses umgehen?

Answer 2

Rekursive Funktionen können in einer unendlichen Rekursion enden, z.B.: 𝚟𝚘𝚒𝚍 𝚏() {𝚏()}.
Man braucht also einen garantierten Fortschritt in Richtung einer Abbruchbedingung, z.B. bei folgendem Code…
𝚒𝚗𝚝 𝚏𝚊𝚔𝚞𝚕𝚝𝚊𝚎𝚝(𝚒𝚗𝚝 𝚗) {
𝚒𝚏 (𝚗 <= 𝟷)
𝚛𝚎𝚝𝚞𝚛𝚗 𝟷;
𝚎𝚕𝚜𝚎
𝚛𝚎𝚝𝚞𝚛𝚗 𝚗 * 𝚏𝚊𝚔𝚞𝚕𝚝𝚊𝚎𝚝(𝚗-𝟷);
}
…endet die Rekursion, falls n ≤ 1 und es entsteht ein neuer rekursiver Aufruf mit einem Argument kleiner n.
Die Abbruchbedingung wird daher garantiert erreicht.

Question 3

Wie wird eine rekursive Funktion ausgewertet?

Answer 3

Bei jedem Funktionsaufruf kommt der Wert des Aufrufarguments auf einen Stapel und es wird immer mit dem obersten Wert des Stapels gearbeitet.
Am Ende eines Aufrufs wird der oberste Wert wieder vom Stapel gelöscht.

(Gutes Bild in PPT-Slides von 05.11.2019!)

Question 4

Betrachte folgenden Codeausschnitt:

𝚞𝚗𝚜𝚒𝚐𝚗𝚎𝚍 𝚒𝚗𝚝 𝚏𝚒𝚋(𝚞𝚗𝚜𝚒𝚐𝚗𝚎𝚍 𝚒𝚗𝚝 𝚗) {
  𝚒𝚏 (𝚗 == 0) 𝚛𝚎𝚝𝚞𝚛𝚗 0; 
  𝚒𝚏 (𝚗 == 𝟷) 𝚛𝚎𝚝𝚞𝚛𝚗 𝟷; 
  𝚛𝚎𝚝𝚞𝚛𝚗 𝚏𝚒𝚋(𝚗-𝟷) + 𝚏𝚒𝚋(𝚗-𝟸);
}

Wo liegt hier das Problem und wie kann es behoben werden?

Answer 4

Der Code funktioniert gut für kleine Zahlen, für grosse Zahlen jedoch dauert die Berechnung viel zu lange.

Für 𝚏𝚒𝚋(𝟻0) z.B. wird F₄₈ 2-mal, F₄₇ 3-mal, F₄₆ 5-mal, F₄₅ 8-mal, F₄₄ 13-mal, F₄₃ 21-mal und F₁ eine Milliarde mal berechnet!
Um dies zu verbessern, schaut man, dass jede Zahl nur einmal berechnet wird und jeweils nur die letzten beiden berechneten Werte gespeichert werden.
Eine Lösung wäre z.B. folgender Codeausschnitt:

𝚞𝚗𝚜𝚒𝚐𝚗𝚎𝚍 𝚒𝚗𝚝 𝚏𝚒𝚋(𝚞𝚗𝚜𝚒𝚐𝚗𝚎𝚍 𝚒𝚗𝚝 𝚗) {
𝚒𝚏 (𝚗 == 0) 𝚛𝚎𝚝𝚞𝚛𝚗 0;
𝚒𝚏 (𝚗 == 𝟷) 𝚛𝚎𝚝𝚞𝚛𝚗 𝟷;

𝚞𝚗𝚜𝚒𝚐𝚗𝚎𝚍 𝚒𝚗𝚝 𝚊 = 0;
𝚞𝚗𝚜𝚒𝚐𝚗𝚎𝚍 𝚒𝚗𝚝 𝚋 = 𝟷;

  𝚏𝚘𝚛 (𝚞𝚗𝚜𝚒𝚐𝚗𝚎𝚍 𝚒𝚗𝚝 𝚒 = 𝟸; 𝚒 <= 𝚗; ++𝚒) {
    𝚞𝚗𝚜𝚒𝚐𝚗𝚎𝚍 𝚒𝚗𝚝 𝚊_𝚘𝚕𝚍 = 𝚊;
    𝚊 = 𝚋;
    𝚋 += 𝚊_𝚘𝚕𝚍;
  }
  𝚛𝚎𝚝𝚞𝚛𝚗 𝚋;
}

Question 5

Welche anderen zwei “Methoden” kann man anstelle einer rekursiven Funktion verwenden?

Answer 5

Eine Rekursion kann immer simuliert werden durch…

(1) … Iteration (Schleifen).
(2) … expliziten “Aufrufstapeln” (z.B. mit einem Vektor).

Question 6

Betrachte folgenden Codeausschnitt zur Berechnung einfacher arithmetischer Operationen:

𝚍𝚘𝚞𝚋𝚕𝚎 𝚕𝚟𝚊𝚕;
𝚜𝚝𝚍::𝚌𝚒𝚗&raquo_space; 𝚕𝚟𝚊𝚕;

𝚌𝚑𝚊𝚛 𝚘𝚙; 
𝚠𝚑𝚒𝚕𝚎 (𝚜𝚝𝚍::𝚌𝚒𝚗 >> 𝚘𝚙 && 𝚘𝚙 != ’=’) { 
  𝚍𝚘𝚞𝚋𝚕𝚎 𝚛𝚟𝚊𝚕; 
  𝚜𝚝𝚍::𝚌𝚒𝚗 >> 𝚛𝚟𝚊𝚕;
  𝚒𝚏 (𝚘𝚙 == ’+’) 
    𝚕𝚟𝚊𝚕 += 𝚛𝚟𝚊𝚕; 
  𝚎𝚕𝚜𝚎 𝚒𝚏 (𝚘𝚙 == ’*’) 
    𝚕𝚟𝚊𝚕 *= 𝚛𝚟𝚊𝚕; 
  𝚎𝚕𝚜𝚎 ...
} 
𝚜𝚝𝚍::𝚌𝚘𝚞𝚝 << "𝙴𝚛𝚐𝚎𝚋𝚗𝚒𝚜 " << 𝚕𝚟𝚊𝚕 << "\𝚗";

Wo kommt es hier zum Problem und weshalb ist es nicht so einfach, dieses Problem zu lösen?

Answer 6

Die Präzedenzen werden nicht eingehalten: Der Code lässt mehrfache Operationen hintereinander zu (durch die while-Schlaufe), z.B. 3 + 2 * 4 oder 1 + 1 * 2 + 2 * … .
Jedoch wird das Ergebnis falsch sein, wenn Punkt- und Strichrechnung gemischt wird, da lediglich die Linkspräzedenz eingehalten wird mit diesem Code.
Da die Lösung dieses Problems erfordert, dass der Code alle noch folgenden Präzedenzen kennt (*), braucht man ein neues formales (von C++ unabhängiges) Handwerkszeug (= Grammatiken).

(*) z.B. muss das Programm, um 13 + 4 * (15 - 7 * 3) zu berechnen, bis zur "3" am Ende der Rechnung alle Werte zwischenspeichern, da es aufgrund der Teilrechnungen nie weiss, ob noch ein Schritt folgt oder nicht:
13 + …?
13 + 4 * …?
13 + 4 * (15 - …?
13 + 4 * (15 - 7 * …?
13 + 4 * (15 - 7 * 3) !

Question 7

Was ist ein terminales Symbol bzw. ein nicht terminales Symbol und wo werden diese Symbole gebraucht?

Answer 7

Ein terminales Symbol ist ein Symbol, z.B. ‘8’, welches nicht weiter gekürzt werden kann.
Ein nicht-terminales Symbol kann durch erneute Berechnung eines rekursiven Funktionsaufrufs immer wieder verwendet werden und entsprechend gekürzt werden.
Man braucht diese Symbole folglich in rekursiven Funktionen.

Question 8

Wie kann man den Begriff “Zahl” mit Hilfe des Begriffs “Ziffer” definieren, und zwar…

(1) … rekursiv?
(2) … nicht rekursiv?

Answer 8

(1) Eine Zahl ist eine Folge von Ziffern. Eine Folge von Ziffern ist:
- nur eine Ziffer (z.B. “2”), oder
- eine Ziffer gefolgt von einer Folge von Ziffern (z.B. “2019”).
Man sieht hier, dass “Folge von Ziffern” mit “Folge von Ziffern” definiert wird, also rekursiv.

(2) Eine Zahl ist eine Folge von Ziffern. Eine Folge von Ziffern ist:
- nur eine Ziffer (z.B. “2”), oder
- eine Ziffer gefolgt von beliebig vielen Ziffern (z.B. “2019”).
Man sieht hier, dass “Folge von Ziffern” nur mit der Definition von “Ziffer” auskommt, also nicht rekursiv.

Question 9

Was ist die EBNF?

Answer 9

Die Extended Backus-Naur Form (EBNF) ist eine formale Metasprache (also eine Sprache über eine Sprache), die verwendet wird, um formale Grammatiken zu definieren. Man kann also ganze Programmiersprachen (z.B. C++) in EBNF umschreiben.

(Gutes Beispiel: https://de.wikipedia.org/wiki/Erweiterte_Backus-Naur-Form#Beispiel_Programmiersprache).

Question 10

Was bedeutet Parsing und was ist ein Parser? Wozu braucht man das Parsing?

Answer 10

Parsing ist per Definition die Syntaxanalyse einer Sprache, um danach auf die Semantik schliessen zu können.
(Bsp. in einer “menschlichen” Sprache: Man würde einen Satz in seine grammatikalischen Bestandteile zerlegen, was z.B. ein wichtiger Bestandteil der Linguistik ist.)
In C++ wird folglich mit dem Parsing festgestellt, ob ein Satz nach der EBNF gültig ist.
Dazu braucht man einen Parser, also das Programm zum Parsen.

Question 11

Wie generiert man aus der EBNF einen Parser, um zu überprüfen, ob sein Satz in C++ gültig ist?

Answer 11

Man konvertiert EBNF-Elemente zu C++-Elementen:

• Regeln werden zu Funktionen.
• Alternativen und Optionen werden zu if-Anweisungen.
• Nichtterminale Symbole auf der rechten Seite werden zu Funktionsaufrufen.
• Optionale Repetitionen werden zu while-Anweisungen.

Beispiel:
Man definiert durch EBNF:

𝚏𝚊𝚌𝚝𝚘𝚛 = 𝚞𝚗𝚜𝚒𝚐𝚗𝚎𝚍_𝚗𝚞𝚖𝚋𝚎𝚛 | “(“ 𝚎𝚡𝚙𝚛𝚎𝚜𝚜𝚒𝚘𝚗 “)” | “-“ 𝚏𝚊𝚌𝚝𝚘𝚛.

𝚝𝚎𝚛𝚖 = 𝚏𝚊𝚌𝚝𝚘𝚛 { “*” 𝚏𝚊𝚌𝚝𝚘𝚛 | “/” 𝚏𝚊𝚌𝚝𝚘𝚛 }

𝚎𝚡𝚙𝚛𝚎𝚜𝚜𝚒𝚘𝚗 = 𝚝𝚎𝚛𝚖 {“+” 𝚝𝚎𝚛𝚖 | “-“ 𝚝𝚎𝚛𝚖}

Hier wurde “unsigned_number” schon vordefiniert. Weiterhin bedeuten “|” Alternativen, geschweifte Klammern Wiederholungen, und in Anführungszeichen gestellte Symbole Terminalsymbole.
Es wird also z.B. ein Faktor definiert als eine natürliche Zahl ODER einen Ausdruck in Klammern ODER eine natürliche Zahl mit einem Minus vorne dran (was ja dann eine ganze Zahl wird).
In C++ wird dann eine Funktion definiert…
𝚋𝚘𝚘𝚕 𝚏𝚊𝚌𝚝𝚘𝚛 (𝚜𝚝𝚍::𝚒𝚜𝚝𝚛𝚎𝚊𝚖& 𝚒𝚗_𝚜𝚝𝚛𝚎𝚊𝚖);
… um zu überprüfen, ob es sich beim Eingabestrom tatsächlich um einen “Faktor” handelt, und falls ja, wird dieser extrahiert.

(Für genauere Angaben siehe PPT-Slides vom 12.11.2019)