4. Compilerbau (LK)

Im Themengebiet der Theoretischen Informatik (meist abkürzend als Automaten bezeichnet) muss im LK auch der Bau eines Compilers behandelt werden. Obwohl beim Compilerbau zur Beschreibung formaler Sprachen wie z.B. Programmiersprachen meist kontextfreie Sprachen eingesetzt werden, wird für das Zentralabitur lediglich verlangt, einen Parser für eine reguläre Sprache entwickeln zu können.

An dieser Stelle werden wir einen einfachen Parser entwickeln, der genau die Sprache akzeptiert, die auch der folgende Endliche Automat akzeptiert:

Die schrittweise Umsetzung nummeriert die Zustände durch und repräsentiert sie als fortlaufende int-Zahlen. Da die Eingaben Ziffern sind, kann die Eingabe ganz einfach Buchstabe für Buchstabe verarbeitet werden. Jeder Zustandswechsel findet sich in einer der geschachtelten switch-Anweisungen wieder. (Bemerkung: Die switch-Anweisungen werden lediglich verwendet, weil sie eine übersichtliche Lösung ermöglichen. Analog können selbstverständlich auch geschachtelte if-else-Anweisungen zum Einsatz kommen.)

public class Automat {

    public boolean parse(String wort) {

        int zustand = 0; // Startzustand
        int zaehler = 0; // Beginn beim 0-ten Symbol

        while (zaehler < wort.length()) {

            char symbol = wort.charAt(zaehler); // aktuelles Symbol

            switch (zustand) {
                case 0: { switch (symbol) {
                            case '0': { zustand = 1; break; }
                            case '1': { zustand = 0; break; }
                          }
                          break;
                        }
                case 1: { switch (symbol) {
                            case '0': { zustand = 2; break; }
                            case '1': { zustand = 0; break; }
                          }                          
                          break;
                        }
                case 2: { switch (symbol) {
                            case '0': { zustand = 3; break; }
                            case '1': { zustand = 0; break; }
                          }                          
                          break;
                        }
                case 3: { switch (symbol) {
                            case '0': { zustand = 3; break; }
                            case '1': { zustand = 0; break; }
                          }                          
                          break;
                        }
            }

            zaehler = zaehler + 1; // naechstes Symbol

        }

        if (zustand==3) { return true; } // Endzustand?
        else { return false; }

    }

}