4.7 Programmierprojekt: Reguläre Sprachen anwenden

Abgabetermin: Montag, 8. Mai 2023

Aufgaben: Die in diesem Teilkapitel (4.7) als Testataufgabe gekennzeichneten Aufgaben.

Format: Je nach Aufgabe als Text/PDF/Word oder als kompilierfähige Elm-Quelldatei. Ich werde bei jeder Testataufgabe darauf extra eingehen.

Material: Eine Auflistung aller Elm-Quelltextdateien (und kompilierter Beispielanwendungen), die ich Ihnen für dieses Projekt zur Verfügung stelle, finden Sie ganz am Ende dieses Teilkapitels.

Fragen: Es ist mir klar, dass die für dieses Projekt Dinge tun müssen, die Sie wahrscheinlich noch nicht können, z.B. mit Elm eine Tabelle für die Webseite erstellen. Aber um solche Fragen zu beantworten bin ja ich da.

Um zur mündlichen Prüfung zugelassen zu werden, müssen Sie als Vorleistung mehrere kleinere Programmierprojekte erfolgreich abschließen. Dieses ist das erste davon. Ziel ist es, mittels regulärer Grammatiken einen Eingabe-String in bestimmte, sinnvolle Bestandteile zu zerlegen und diese dann farbig unterlegt darzustellen. Notwendig zum Erlangen des Testats ist, dass Sie die Testataufgaben in diesem Teilkapitel zufriedenstellend lösen. Hierfür brauchen Sie eine lauffähige Elm-Umgebung. In Rechnerraum GII/303 ist diese bereits installiert. Bei Elm handelt es sich um eine funktionale Programmiersprache (also ähnlich wie Racket, aber einerseits strenger und andererseits mit freundlicherer Syntax), die speziell für die Entwicklung client-seitiger Web-Anwendungen geschaffen wurde. Als "Endprodukt" können Sie also Ihr Elm-Programm in eine Webseite kompilieren, die Sie dann einfach mit einem Browser öffnen können.

Elm

Elm ist im Raum GII/303 bereits installiert. Ich empfehle Ihnen natürlich, es auch bei sich auf Ihrem Laptop (sofern vorhanden) zu installieren. Zur Einführung in Elm empfehle ich Ihnen

• elmprogramming.com, ein ausführliches und gut lesbares Online-Buch.
• elm-lang.org, die offizielle Webseite;
• Kapitel 6 und 7 in meinen Vorlesungsskript zum Kurs Programmierparadigmen

Falls Sie Schwierigkeiten haben, Elm-Programme zum Laufen zu bringen, setzen Sie sich bitte frühzeitig mit mir in Verbindung.

Endliche Automaten in Elm

Nehmen wir als Beispiel den endlichen Automaten für die Noxy-Sprache ("no \(xy\)"):

Ich will nun ein Elm-Programm für die Noxy-Sprache schreiben. Große Teile meines Codes werden aber für jeden Automaten, den ich implementieren will, identisch sein. Diesen lagere ich aus in eine Datei FiniteStateMachine.elm. Als erstes definieren wir einen Datenytp Fsm (als Abkürzung für finite state machine:

module FiniteStateMachine exposing (Fsm, parse)


type alias Fsm state =
    { startState : state
    , transition : state -> Char -> state
    , acceptingStates : List state
    }

Der Datentyp Fsm hat eine Typenvariable state; dies rührt daher, dass wir im Allgemeinen ja nicht wissen, was die Zustandsmenge \(Q\) ist; diese ist von Automat zu Automat verschieden. Eigentlich bräuchte unser Automat noch ein Eingabealphabet \(\Sigma\), ich könnte also zwei Typenvariablen verwenden

Allerdings verzichte ich der Einfachheit halber darauf und nehme immer den Datentyp Char; langfristig mag es aber vorteilhaft sein, alternative Alphabete zuzulassen. Hier ist meine Implementierung von \(\hat{\delta}\), der erweiterten Zustandsübergangsfunktion:

deltaHat : Fsm state -> state -> List Char -> state
deltaHat machine state list =
    case list of
        [] ->
            state

        c :: rest ->
            deltaHat machine (machine.transition state c) rest

und schließlich die Funktion parse, die einen String entgegennimmt und dann ausgibt, ob der zur Sprache gehört:

parse : Fsm state -> String -> Bool
parse machine inputString =
    let
        charList =
            String.toList inputString

        finalState =
            deltaHat machine machine.startState charList
    in
    List.member finalState machine.acceptingStates

Soweit der Code, der wohl für alle endlichen Automaten, ob einfach oder kompliziert, identisch ist. Um den endlichen Automaten für die Noxy-Sprache zur vervollständigen, müssen wir noch \(\qstart\), \(F\) und \(\delta\) spezifizieren, also startState, delta, acceptingStates. Dies habe ich in der Datei FsmNoxy.elm getan:

module Noxy exposing (..)

import FiniteStateMachine as Fsm exposing (Fsm)


type State
    = S
    | X
    | Y


noxyFsm : Fsm State
noxyFsm =
    { startState = S
    , acceptingStates = [ X ]
    , transition = transition
    }


parse : String -> Bool
parse inputString =
    Fsm.parse noxyFsm inputString


transition : State -> Char -> State
transition q c =
    case ( q, c ) of
        ( S, 'y' ) ->
            S

        ( S, 'z' ) ->
            S

        ( S, 'x' ) ->
            X

        ( X, 'x' ) ->
            X

        ( X, 'y' ) ->
            Y

        ( X, 'z' ) ->
            S

        ( Y, _ ) ->
            Y

        _ ->
            Y

                        

Der problemspezifische Code besteht also fast ausschließlich aus dem Code für transition.

elm repl
import Noxy exposing (..)
parse "xzyxzyx"
True : Bool
parse "xzyxyxx"
False : Bool

Als zweites Beispiel implementiere ich einen Parser für die aa:aaa.aa-a-aa-Sprache, die ich von nun an die ColonDashPeriod-Sprache nenne, nach den englischen Namen der Zeichen :-. Hier ist der endliche Automat aus Kapitel 4.4, allerdings habe ich die Zustände umbenannt, damit sie mehr Sinn ergeben:

Eine Grammatik für Single Quotes und Double Quotes

Jetzt sind Sie an der Reihe. In Programmiersprachen wie zum Beispiel Javascript dürfen Sie Strings mit einem Double Quote umranden, also

                            "I'm Dominik", 
                            he said. "How are you doing?"
                        

                            String x = "hello
                            my friend"; 
                        

Automaten mit Ausgabe

Endlicher Automaten, so wie wir sie bis jetzt betrachtet haben, geben einfach nur ja oder nein aus, d.h., Sie überprüfen einfach nur, ob das Eingabewort in der Sprache ist oder nicht. In der Praxis ist das uns nicht genug: die reguläre Grammatik dient auch dazu, das Eingabewort in sinnvolle logische Bestandteile zu zerlegen. In der Quotes-Grammatik könnte das zum Beispiel bedeuten, das Eingabewort anhand des Anführungszeichen zu zerlegen; in der Web-Anwendung könnet das bedeuten, diese Teile farbig zu markieren, zum Beispiel

Definieren wir erst einmal das zugrundeliegende theoretische Konzept.

Beispiel. Betrachten wir die Sprache \(L\) aller Wörter \(\alpha \in \{a,b,c\}\), in denen gerade viele \(a\)'s und beliebig viele \(b\)'s vorkommen. Hier ist ein endlicher Automat:

Wir wollen nun zusätzlich bei jedem Zeichen wissen, ob wir bis jetzt gerade viele oder ungerade viele \(a\)'s gelesen haben (ob wir also "innerhalb" oder "außerhalb" eines \(a\)-Blocks sind); eine farbliche Markierung könnte so aussehen:

bcbabcbbbcabbcbababbcb

Eine solche farbliche Markierung können wir bequem mit einem Mealy-Automaten erzeugen:

parse evenAmachine "bcaccac"                            
[('b',"black"), ('c',"black"), ('a',"red"), ('c',"green"), ('c',"green"),  ('a',"red"), ('c',"black")] : List (Char, String)

parseAndMerge evenAmachine "bcaccac"                            
[("bc","black"), ("a","red"), ("cc", "green"),  ("a","red"), ("c","black")] : List (Char, String)

import YourSpecificMachine exposing (..)

Html.span [ Html.Attributes.style "color" "red"
          , Html.Attributes.style "backgroundColor" "pink" ] 
          [Html.text "dies ist ein Text"]

Material

• FiniteStateMachine.elm
• FsmNoxy.elm
• FsmColonDashPeriod.elm
• WebsiteForFiniteStateMachines.elm
• colondashperiod.html
• quotes.html
• CSVVisualizer.html