Prof. Franz Schweiggert Abteilung Angewandte
Informationsverarbeitung 5. November 2002
Christian Ehrhardt Blatt 2
Allgemeine Informatik (WS 2002/2003)
Abgabetermin 3.9.2002
Die Aufgabe dieses Blattes ist es, ein C-Programm zu schreiben, das
selbst wieder ein C-Programm von der Standardeingabe liest und
darin alle Stringkonstanten daraufhin überprüft, ob sie einen
korrekten Formatstring für (eine vereinfachte Version von) printf
darstellen. Mit anderen Worten: Es ist ein Programm zu schreiben, das
feststellt, ob die Eingabe durch den in der Abbildung dargestellten
endlichen Automaten erkannt wird. Außerdem soll jedes Mal beim
Zustandsübergang von A nach Start der Text ``OK''
und beim Übergang von Error nach Start der Text ``Error''
ausgegeben werden. Wenn sich der Automat am Ende der Eingabe nicht
im Zustand Start befindet soll der Text ``Unterminated''
ausgegeben werden. C Syntax, die über den Automaten hinausgeht muß
nicht gesondert berücksichtigt werden (z.B. ein einzelnes Anführungszeichen
in einem Kommentar).
Hinweis: Die switch-Anweisung kann recht hilfreich sein, um
endliche Automaten zu implementieren.
Ein endlicher Automat besteht aus verschiedenen Zuständen und einer
Übergangfunktion. Zu Beginn befindet sich der Automat im Zustand
Start und bei jedem gelesenen Zeichen findet ein Zustandsübergang
zu einem neuen Zustand statt. Der neue Zustand hängt dabei nur vom
alten Zustand und vom gelesenen Zeichen ab.
In der oben gezeigten Grafik sind die Kreise die Zustände und die
Zustandsübergänge werden durch Pfeile beschrieben. Wenn sich der
Automat z.B. in Zustand Esc befindet und das Zeichen ``a'' gelesen
wurde, findet ein Zustandsübergang zu Zustand A statt. Wäre
dagegen das Zeichen ``x'' gelesen worden, so würde ein Zustandsübergang
zu Error stattfinden.
Um zu überprüfen, ob das Programm korrekt arbeitet sollte es zunächst
mit sich selbst als Eingabe getestet werden. Die Ausgabe muß dabei
nicht zwangsläufig nur aus ``OK''s bestehen, aber falls das nicht
der Fall ist solltet Ihr erklären können, warum der Automat mit
eurem Programm nicht richtig umgehen kann. Eine Datei mit weiteren
Testfällen gibt es bei den Ergänzungen zu diesem Blatt.
Christian Ehrhardt
2002-11-05