Bezeichner im Compiler
14 BEAFB I–IIDer Compiler einer Lernsprache prüft Bezeichner (Namen von Variablen und Methoden) mit einem DEA. Vorher ersetzt er jeden Buchstaben durch b, jede Ziffer durch z und den Unterstrich durch u; es gilt also \(\Sigma=\{b,\,z,\,u\}\). Ein Bezeichner ist gültig, wenn
- er mit einem Buchstaben beginnt,
- danach beliebig viele Buchstaben, Ziffern und Unterstriche folgen,
- nirgends zwei Unterstriche direkt hintereinander stehen und
- er nicht auf einen Unterstrich endet.
- Bestimmen Sie für die Bezeichner
zaehler_2,_temp,max__wert,wert_das Wort über \(\Sigma\) und entscheiden Sie mit Begründung, ob der Bezeichner gültig ist. (4 BE) - Zeichnen Sie den Zustandsgraphen eines DEA, der genau die gültigen Bezeichner akzeptiert. Geben Sie die Bedeutung jedes Zustands an. (6 BE)
- Erläutern Sie, wie viele Übergänge Ihr vollständiger Automat hat, und stellen Sie eine möglichst kleine Liste von Testwörtern zusammen, mit der jeder Übergang, der nicht in zF beginnt, mindestens einmal benutzt wird. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| Bezeichner | Wort über Σ | gültig? |
|---|---|---|
zaehler_2 | bbbbbbbuz | ja |
_temp | ubbbb | nein |
max__wert | bbbuubbbb | nein |
wert_ | bbbbu | nein |
_temp beginnt nicht mit einem Buchstaben, max__wert enthält zwei Unterstriche hintereinander, wert_ endet auf einen Unterstrich. Nur zaehler_2 erfüllt alle Regeln.
Erwartungshorizont zu Aufgabe b)
- z0: noch nichts gelesen (Start)
- z1: gültiger Bezeichner, letztes Zeichen Buchstabe oder Ziffer (Endzustand)
- z2: zuletzt ein Unterstrich — es muss noch ein Buchstabe oder eine Ziffer folgen
- zF: Regel verletzt (Ziffer oder Unterstrich am Anfang, zwei Unterstriche)
Erwartungshorizont zu Aufgabe c)
Vier Zustände (mit zF) und drei Zeichen: \(4\cdot3=12\) Übergänge, davon 9, die nicht in zF beginnen.
Mögliche Testliste: bbzubzuu (nutzt z0-b, z1-b, z1-z, z1-u, z2-b, z2-u), buz (z2-z), z (z0-z), u (z0-u).
Damit sind alle 9 Übergänge abgedeckt; zusätzlich prüft man die Grenzfälle \(\varepsilon\) (abgelehnt) und b (kürzester gültiger Bezeichner).
Das Kfz-Kennzeichen
17 BEAFB II–IIIEine Parkhauskamera liest Kfz-Kennzeichen und prüft ihr Format (vereinfacht, ohne Leerzeichen): zuerst 1 bis 3 Buchstaben (Unterscheidungszeichen, z. B. H für Hannover), dann ein Bindestrich, dann 1 oder 2 Buchstaben und zuletzt 1 bis 4 Ziffern, wobei die erste Ziffer keine 0 sein darf.
Die Kamera übersetzt jedes Zeichen: Buchstabe → B, Bindestrich → -, Ziffer 0 → N, Ziffer 1 bis 9 → Z. Es gilt also \(\Sigma=\{B,\,-,\,N,\,Z\}\).
- Geben Sie für die Kennzeichen
H-AB123,HAN-A0,B-XYZ1das Wort über \(\Sigma\) an und entscheiden Sie, ob das Format stimmt. (3 BE) - Entwerfen Sie einen DEA, der genau die Kennzeichen im beschriebenen Format akzeptiert. Stellen Sie ihn als vollständige Übergangstabelle dar und geben Sie die Bedeutung der Zustände an. (7 BE)
- Berechnen Sie, wie viele Übergänge der vollständige Automat hat und wie viele davon in den Fehlerzustand zF führen. Geben Sie an, ob man zF im Zustandsgraphen besser weglässt. (3 BE)
- Tatsächlich dürfen Kennzeichen höchstens 8 Zeichen haben (Bindestrich nicht mitgezählt). Beurteilen Sie, ob Ihr Automat diese Regel bereits einhält, und wie er gegebenenfalls angepasst werden müsste. (4 BE)
Hinweise
Hinweis zu Aufgabe a)
Hinweis zu Aufgabe b)
Hinweis zu Aufgabe c)
Hinweis zu Aufgabe d)
Erwartungshorizont
Erwartungshorizont zu Aufgabe a)
| Kennzeichen | Wort über Σ | Format korrekt? |
|---|---|---|
H-AB123 | B-BBZZZ | ja |
HAN-A0 | BBB-BN | nein |
B-XYZ1 | B-BBBZ | nein |
HAN-A0: Die erste Ziffer ist 0. B-XYZ1: Nach dem Bindestrich stehen drei Buchstaben.
Erwartungshorizont zu Aufgabe b)
| Zustand | B | - | N | Z | Bedeutung |
|---|---|---|---|---|---|
| z0 | z1 | zF | zF | zF | noch nichts |
| z1 | z2 | z4 | zF | zF | 1 Buchstabe vor - |
| z2 | z3 | z4 | zF | zF | 2 Buchstaben vor - |
| z3 | zF | z4 | zF | zF | 3 Buchstaben vor - |
| z4 | z5 | zF | zF | zF | Bindestrich gelesen |
| z5 | z6 | zF | zF | z7 | 1 Buchstabe nach - |
| z6 | zF | zF | zF | z7 | 2 Buchstaben nach - |
| z7 | zF | zF | z8 | z8 | 1 Ziffer |
| z8 | zF | zF | z9 | z9 | 2 Ziffern |
| z9 | zF | zF | z10 | z10 | 3 Ziffern |
| z10 | zF | zF | zF | zF | 4 Ziffern |
| zF | zF | zF | zF | zF | ungültig |
(→ Startzustand, doppelt unterstrichen: Endzustände z7 bis z10.) Die Unterscheidung von N und Z ist nur in z5 und z6 wichtig: Die erste Ziffer darf keine 0 sein, danach sind beide erlaubt.
Erwartungshorizont zu Aufgabe c)
\(|Z|=12\) (z0 bis z10 und zF), \(|\Sigma|=4\): \(12\cdot4=48\) Übergänge.
Nicht nach zF führen \(1+2+2+1+1+2+1+2+2+2+0=16\); also führen \(48-16=32\) Übergänge nach zF (davon 4 Schleifen an zF).
Im Graphen wären zwei Drittel der Pfeile Fehlerpfeile. Es ist übersichtlicher, zF wegzulassen und dies ausdrücklich zu vermerken.
Erwartungshorizont zu Aufgabe d)
Der Automat hält die Regel nicht ein: Er akzeptiert z. B. BBB-BBZZZZ mit \(3+2+4=9\) Zeichen.
Betroffen ist nur der Fall mit 3 + 2 = 5 Buchstaben; dann sind höchstens 3 Ziffern erlaubt. Der Automat muss sich also ab dem Bindestrich zusätzlich merken, ob vorn 3 Buchstaben standen. Anpassung: z3 \(\xrightarrow{-}\) z4′ statt z4, dazu eine Kopie des weiteren Wegs: z4′ \(\xrightarrow{B}\) z5′, z5′ \(\xrightarrow{Z}\) z7 (4 Buchstaben, bis zu 4 Ziffern bleiben erlaubt), z5′ \(\xrightarrow{B}\) z6′ (5 Buchstaben), z6′ \(\xrightarrow{Z}\) z7′ \(\xrightarrow{N,Z}\) z8′ \(\xrightarrow{N,Z}\) z9′ mit z7′, z8′, z9′ als Endzuständen; aus z9′ führt jede Ziffer nach zF. Das sind 6 zusätzliche Zustände.
Beurteilung: Die Regel ist mit einem DEA umsetzbar, weil nur endlich viele Fälle zu unterscheiden sind; der Automat wächst aber schnell und wird unübersichtlich. Bei weiteren Längenregeln prüft man die Gesamtlänge in der Praxis besser zusätzlich im Programm.