Bezeichner-Automat und reservierte Wörter
Im Informatikunterricht wird ein Mini-Interpreter für eine einfache Sprache entwickelt. Bezeichner (Variablennamen) sollen so gebildet werden: erstes Zeichen ein ASCII-Buchstabe (a–z, A–Z), danach null bis sieben Zeichen aus Buchstaben und Ziffern; Umlaute, Unterstriche und Sonderzeichen sind nicht erlaubt. Zusätzlich sind die Wörter if, else und while reserviert und dürfen nicht als Bezeichner verwendet werden. Ein Schüler entwirft einen endlichen Automaten mit einem Startzustand, einem Zustand „Buchstabe gelesen“ und einem Zustand „Ziffer gelesen“, der nach jedem Zeichen prüft, ob die Gesamtlänge höchstens 8 ist. Beim Test werden „x1“, „Länge“, „if“ und „_tmp“ eingegeben; der Automat akzeptiert „Länge“ und „if“. Die Lehrkraft bezweifelt, dass ein endlicher Automat die reservierten Wörter überhaupt ausschließen kann.
1. Entwerfen Sie einen korrekten DEA für die Bezeichner-Syntax (ohne Rücksicht auf reservierte Wörter) als Übergangstabelle und begründen Sie die Zustandsanzahl.
Read the worked answer
Kritik am Entwurf. Die Unterscheidung „Buchstabe gelesen“ und „Ziffer gelesen“ ist überflüssig: Nach dem ersten Zeichen sind Buchstaben und Ziffern gleichwertig. Ein Zustand „Ziffer gelesen“ suggeriert eine Unterscheidung, die die Sprache nicht macht, und verleitet zu Fehlern. Nötig ist stattdessen, die Länge mitzuzählen – hier als Kette von Zuständen L1 bis L8, die die bereits gelesene Zeichenzahl repräsentieren.
Übergangstabelle (B = a–z, A–Z; Z = 0–9; sonst = alles andere):
| Zustand | B | Z | sonst |
|---|---|---|---|
| Z0 (Start) | L1 | – | – |
| L1 | L2 | L2 | – |
| L2 | L3 | L3 | – |
| … | … | … | – |
| L7 | L8 | L8 | – |
| L8 | – | – | – |
L1 bis L8 sind akzeptierende Zustände; Z0 ist nicht akzeptierend. „–“ ist ein Senkenzustand (Fehlerzustand), aus dem es keinen Weg zurück gibt.
Begründung der Zustandsanzahl. Die Sprache ist { w | w beginnt mit Buchstabe, Rest aus Buchstaben/Ziffern, 1 ≤ |w| ≤ 8 }. Die Längenprüfung erfordert Gedächtnis bis 8, also eine Zustandskette. Man braucht 1 Startzustand + 8 Längenzustände + 1 Senke = 10 Zustände. Ohne Längenbegrenzung käme man mit 3 Zuständen aus (Start, akzeptierend, Senke) – die Begrenzung ist es, die den Automaten aufbläht. Das ist ein wichtiger Punkt: Der Automat ist endlich, weil die Sprache endlich lang ist.
2. Kann ein endlicher Automat die reservierten Wörter ausschließen? Begründen Sie formal und bewerten Sie zwei Umsetzungsvarianten.
Read the worked answer
Formale Antwort. Ja. Reguläre Sprachen sind unter Komplement und Schnitt abgeschlossen, also auch unter Differenz. Sei L die Sprache der syntaktisch gültigen Bezeichner und K = {if, else, while} endlich (also regulär). Dann ist L \ K regulär, es gibt also einen DEA. Konstruktiv: Man bildet das Produkt aus dem Automaten für L und einem Automaten, der die drei Wörter erkennt, und markiert die Zustände, in denen ein reserviertes Wort vollständig gelesen wurde, als nicht akzeptierend.
Variante 1: Produktautomat. Sauber und in einem Schritt. Nachteil: Zustandsexplosion – hier wegen der Längenschranke noch beherrschbar (10 × 6 ≈ 60 Zustände), aber unübersichtlich und fehleranfällig von Hand.
Variante 2: Zwei Stufen. Der DEA prüft nur die Syntax; danach vergleicht ein Hash-Set oder eine if-Kette den erkannten String mit der Liste der Schlüsselwörter. Das ist O(1) bzw. O(k) pro Token, wartbar und in der Praxis üblich (Lexer mit Keyword-Tabelle).
Bewertung. Didaktisch zeigt Variante 1 die theoretische Machbarkeit, technisch ist Variante 2 klar überlegen: Die Schlüsselwortliste ändert sich häufig, der Automat müsste jedes Mal neu gebaut werden. Die Skepsis der Lehrkraft ist also unbegründet, aber der Einwand führt zur richtigen Architekturentscheidung. Wenn die Sprache unbegrenzte Bezeichnerlänge hätte, bliebe die Aussage übrigens gültig – die Konstruktion hinge nicht von der Längenschranke ab.
3. Prüfen Sie die vier Testeingaben „x1“, „Länge“, „if“ und „_tmp“ gegen den korrigierten Automaten und geben Sie jeweils die Zustandsfolge an.
Read the worked answer
„x1“ → Z0 –x→ L1 –1→ L2. L2 ist akzeptierend, also gültig. Der Bezeichner hat Länge 2 und ist nicht reserviert.
„Länge“ → Z0 –L→ L1 –ä→ Senke. Das „ä“ ist kein ASCII-Buchstabe im definierten Alphabet; der Automat geht in den Fehlerzustand und bleibt dort. Ergebnis: ungültig. Das ist der Fall, den der ursprüngliche Entwurf falsch akzeptiert hat – vermutlich, weil er „Buchstabe“ zu weit gefasst oder die Zeichenprüfung gar nicht durchgeführt hat.
„if“ → Z0 –i→ L1 –f→ L2. L2 ist akzeptierend, also nach der reinen Syntax gültig. Erst die zweite Stufe (oder der Produktautomat) erkennt „if“ als reserviert und weist es zurück. Genau hier zeigt sich, dass Syntaxprüfung und Schlüsselwortprüfung getrennte Aufgaben sind. Wer beides im DEA vermischt, muss die Zustände für i, f, e, l, s, w, h separat führen.
„_tmp“ → Z0 –_→ Senke. Der Unterstrich ist im ersten Zeichen nicht erlaubt. Ergebnis: ungültig.
Zusatzfälle, die man testen sollte. „a“ (Länge 1, gültig), „abcdefgh“ (Länge 8, gültig), „abcdefghi“ (Länge 9, ungültig – der L8-Zustand hat keinen Ausgang), „9x“ (erstes Zeichen Ziffer, ungültig) und „ifx“ (gültig, da es kein reserviertes Wort ist). Der letzte Fall ist wichtig, weil er zeigt, dass nicht auf Präfixe geprüft werden darf.