zadanie nr 12 termin realizacji: 6 czerwiec 2005

C++

automaty skończone (algorytmy) studia dzienne

Automat skończony FA możemy zdefiniować jako piątkę uporządkowaną (Q, Σ, δ, q_{0}, F), gdzie Q jest skończonym zbiorem stanów, Σ jest skończonym alfabetem wejściowym, q_{0} ∈ Q jest stanem początkowym, F ⊆ Q jest zbiorem stanów końcowych, a δ : Q × Σ ↦ Q jest funkcją przejścia. Mówimy, że ciąg x ∈ Σ^{∗} jest akceptowany przez automat skończony M = (Q, Σ, δ, q_{0}, F), jeśli δ(q_{0}, x) ∈ F.

Zdefiniuj klasę FA reprezentującą automat skończony. Obiekt klasy FA powinien działać dwufazowo: najpierw jest inicjalizowany (zbiór stanów, alfabet, funkcja przejścia), a potem pracuje na strumienu danych wejściowych. Jeśli automat będąc w jakimś stanie przeczyta symbol spoza alfabetu, albo symbol dla którego funkcja przejścia nie będzie zdefiniowana, to powinien zostać zgłoszony wyjątek (funkcja przejścia nie musi więc być zdefiniowana w całości). Rozbuduj swój automat o pamięć, tak aby przeczytane znaki były jakoś zapamiętywane (może w strumieniu osstream), oraz o dodatkową aktywność prześć, tak by w trakcie przechodzenia automatu od stanu do stanu były wykonywane jakieś akcje (opróżnienie bufora przeczytanych do tej pory znaków, wysłanie ich do innego strumienia, itp.).

Następnie napisz programy, które będą potrafiły analizować programy napisane w języku C++ przy pomocy odpowiednio nainicjalizowanej klasy FA:

• program wypisujący treść programu w C++ z pominięciem wszystkich komentarzy (uwaga na literały napisowe, przykładowo: "/*...", "...*/", "//...");

• program wypisujący wszystkie literały zawarte w treśi programu w C++: liczby całkowite, liczby rzeczywiste, stałe znakowe, łańcuchy znaków, wartości logiczne (uwaga na komentarze i literały postaci j23 czy k_true).

Przyjmij, że dane są podawane na standardowe wejście, a wyniki zapisuj na standardowe wyjście. Zakładamy dodatkowo, że programy analizowane przez automaty są napisane bezbłędnie.

Powodzenia!

Uniwersytet Wrocławski Paweł Rzechonek Instytut Informatyki ul. Przesmyckiego 20 PL-51-151 Wrocław