MINT lernen

Abituraufgaben: Kontextfrei

Rechenausdrücke mit Punkt vor Strich und Programme aus verschachtelten Blöcken — Grammatik, Baum und Keller.

Dein Fortschritt:
0 / 0 Aufgaben
1

Rechenausdrücke für einen Parser

13 BEAFB I–II

Ein Taschenrechner-Programm prüft Rechenausdrücke, bevor es sie auswertet. z steht für eine beliebige Zahl. Die Syntax wird durch die Grammatik G festgelegt:

N = {A}
T = {z, +, *, (, )}
Startsymbol: A
Produktionsregeln:
A → A+A | A*A | (A) | z
  1. Wenden Sie G an: Geben Sie eine Linksableitung von (z+z)*z an. (3 BE)
  2. Zeigen Sie mit zwei Ableitungsbäumen, dass G für z+z*z mehrdeutig ist, und erläutern Sie die Folge für den Wert von 1 + 2 · 3. (4 BE)
  3. Begründen Sie, dass L(G) nicht regulär ist. (3 BE)
  4. Die Entwickler ersetzen G durch A → A+P | P, P → P*F | F, F → (A) | z. Erläutern Sie, warum mit dieser Grammatik * stärker bindet als +. (3 BE)

Hinweise

Hinweis zu Aufgabe a)
Linksableitung: Immer das am weitesten links stehende A ersetzen. Beginnen Sie mit A → A*A.
Hinweis zu Aufgabe b)
Einmal steht + an der Wurzel, einmal *. Welcher Teil wird jeweils zuerst ausgerechnet?
Hinweis zu Aufgabe c)
Denken Sie an Ausdrücke wie ((((z)))) mit beliebig vielen Klammern.
Hinweis zu Aufgabe d)
Leiten Sie z+z*z mit der neuen Grammatik ab. Kann * an der Wurzel stehen, wenn ein + außerhalb von Klammern vorkommt?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

A ⇒ A*A ⇒ (A)*A ⇒ (A+A)*A ⇒ (z+A)*A ⇒ (z+z)*A ⇒ (z+z)*z

Erwartungshorizont zu Aufgabe b)
Baum 1: + an der Wurzel
A A + A z A * A z z
Baum 2: * an der Wurzel
A A * A A + A z z z

Zu einem Wort gibt es zwei verschiedene Ableitungsbäume — G ist mehrdeutig. Wertet der Rechner nach dem Baum aus, ergibt Baum 1 den Wert 1 + (2 · 3) = 7, Baum 2 aber (1 + 2) · 3 = 9.

Erwartungshorizont zu Aufgabe c)

Die Ausdrücke \(\texttt{(}^n\,z\,\texttt{)}^n\) — n öffnende Klammern, z, n schließende — gehören alle zu L(G). Ein DEA mit k Zuständen landet nach zwei der Anfangsstücke \(\texttt{(}^0,\dots,\texttt{(}^k\), etwa \(\texttt{(}^i\) und \(\texttt{(}^j\) mit \(i<j\), im selben Zustand (Schubfachprinzip). Dann behandelt er \(\texttt{(}^i z\texttt{)}^i\) und \(\texttt{(}^j z\texttt{)}^i\) gleich — das erste gehört zu L(G), das zweite nicht. Also erkennt kein DEA L(G): Die Sprache ist nicht regulär.

Erwartungshorizont zu Aufgabe d)

Ein + kann nur mit A → A+P entstehen, also nur „oben“ im Baum. Ein * entsteht nur mit P → P*F innerhalb eines P, also unterhalb eines +. Für z+z*z gibt es deshalb nur den Baum A → A+P mit P ⇒ P*F: z + (z · z). Ein * über einem + ist nur möglich, wenn das + in Klammern steht (F → (A)). Damit ist die Grammatik eindeutig und bildet „Punkt vor Strich“ ab.

2

Verschachtelte Blöcke

17 BEAFB II–III

In einer kleinen Programmiersprache bestehen Programme aus Blöcken: b steht für „begin“, e für „end“, x für eine einfache Anweisung. Ein Programm ist genau ein Block; Blöcke dürfen Anweisungen und weitere Blöcke enthalten. Die Syntax wird festgelegt durch:

N = {P, A}
T = {b, e, x}
Startsymbol: P
Produktionsregeln:
P → bAe
A → xA | PA | ε
  1. Stellen Sie die Linksableitung von bxbxee dar. (3 BE)
  2. Entwerfen Sie einen deterministischen Kellerautomaten in der Notation der Anlage, der genau die Programme akzeptiert. Geben Sie Eingabe- und Kelleralphabet an. (6 BE)
  3. Implementieren Sie in Java eine Methode boolean istBlock(String s), die entscheidet, ob s ein Programm ist. Nutzen Sie aus, dass im Keller nur eine Art von Symbol liegt. (5 BE)
  4. Die Sprache wird um geschweifte Klammern { } als zweite Blockart erweitert, die korrekt mit b … e geschachtelt sein müssen. Erörtern Sie, ob dann ein Zähler statt des Kellers noch genügt. (3 BE)

Hinweise

Hinweis zu Aufgabe a)
Das einzige Nichtterminal ganz links wird ersetzt; nach P → bAe steht A an zweiter Stelle.
Hinweis zu Aufgabe b)
Für jedes b wird ein Symbol abgelegt, für jedes e eines entnommen. Wann ist das Programm fertig? Denken Sie an den ε-Übergang mit #.
Hinweis zu Aufgabe c)
Der Keller enthält nur B-Symbole — seine Höhe ist alles, was man wissen muss.
Hinweis zu Aufgabe d)
Prüfen Sie ein Wort wie b { e }: Stimmen die Anzahlen? Stimmt die Reihenfolge?

Erwartungshorizont

Erwartungshorizont zu Aufgabe a)

P ⇒ bAe ⇒ bxAe ⇒ bxPAe ⇒ bxbAeAe ⇒ bxbxAeAe ⇒ bxbxeAe ⇒ bxbxee

(Die letzten beiden Schritte verwenden A → ε.)

Erwartungshorizont zu Aufgabe b)

Σ = {b, e, x}, Γ = {B, #}; Zustände z0 (Start), z1, z2 (Endzustand).

ÜbergangBedeutung
z0 → z1: (#,b):B#Das Programm beginnt mit einem Block.
z1 → z1: (B,b):BBweiterer Block geöffnet
z1 → z1: (B,x):BAnweisung im offenen Block
z1 → z1: (B,e):εinnersten Block schließen
z1 → z2: (#,ε):#äußerster Block geschlossen — fertig

Deterministisch: Von z1 geht der ε-Übergang nur mit # aus, alle anderen Übergänge von z1 haben B oben. Nach dem ε-Übergang ist z2 erreicht; ein weiteres Zeichen findet keinen Übergang, sodass bebe abgelehnt wird.

Erwartungshorizont zu Aufgabe c)
Java
// Der Keller enthält nur B-Symbole: ein Zähler genügt.
public static boolean istBlock(String s) {
    if (s.length() == 0 || s.charAt(0) != 'b') return false;
    int tiefe = 0;
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == 'b') {
            tiefe++;                     // (B,b):BB bzw. (#,b):B#
        } else if (c == 'e') {
            tiefe--;                     // (B,e):ε
            if (tiefe == 0 && i < s.length() - 1) return false;
        } else if (c != 'x') {
            return false;                // Zeichen außerhalb von T
        }
    }
    return tiefe == 0;                   // (#,ε):# führt in den Endzustand
}

Test: bxbxee → true, bebe → false (zweites Programm), bxbe → false (Block offen).

Erwartungshorizont zu Aufgabe d)

Ein Zähler speichert nur die Tiefe, nicht die Reihenfolge der offenen Blockarten. Beide Zähler bzw. die Summe würden bei b { e } dieselben Werte liefern wie bei b { } e — das erste ist aber falsch geschachtelt, weil e den inneren {-Block schließen würde.

Man braucht deshalb einen Keller mit zwei Symbolen (B und K), um beim Schließen das zuletzt geöffnete Symbol zu vergleichen. Die Sprache bleibt kontextfrei, ein einfacher Zähler genügt nicht mehr.