AtoCC

Übungsaufgaben

In nachfolgender Abbildung ist ein NEA gezeigt der grob den Aufbau (Syntax) der deutschen Sprache wiedergibt.

Entwickeln sie zunächst den obigen Automaten mit AutoEdit (dabei verwenden sie die Wortklassen als Alphabetszeichen).

Generieren sie nun einen Scheme Quellcode für diesen NEA und betrachten sie diesen in SchemeEdit genauer.

(q1 (lambda (tape)
             (printf "~a: ~a~n" 'q1 (tape '(show)))
             (case (tape '(read))
               ((Adjektiv) (tape '(right!)) (q1 tape))
               ((Substantiv) (tape '(right!)) (q2 tape))
               (else #f))))

Betrachten sie den Codeausschnitt und überlegen sie wie sie mit Hilfe der Wortklassen (fett hervorgehoben) eine Reihe von Wort-Instanzen mit diesem Automaten verarbeiten könnten.

Verwenden sie dafür die folgenden Wörter:

Artikel    : der, die, das
Substantiv : Mann, Frau, Hund, Tiere
Verb       : denkt, singt, bellt, rennen
Adjektiv   : große, schöne, sabbernde, wilde
Adverb     : ununterbrochen, leise, laut,  schnell

Implementieren sie für jede Wortklasse eine Funktion die #t zurückgibt wenn ein Wort w zu dieser Wortklasse gehört:

(define Artikel
  (lambda (w)
    (cond ((equal? w "das") #t)
               …
              (else #f))))

Verändern sie nun den Automaten so, dass das gelesene Zeichen mit Hilfe der Wortklassenfunktionen überprüft wird.

Tip: Case kann hier am günstigsten durch ein "let" + "cond" ersetzt werden:

           (case (tape '(read))
               ((Adjektiv) (tape '(right!)) (q1 tape))
               ((Substantiv) (tape '(right!)) (q2 tape))
               (else #f))))

wird zu:

          (let ((w (tape '(read))))
               (cond
                  ((Adjektiv w) (tape '(right!)) (q1 tape))
                  ((Substantiv w) (tape '(right!)) (q2 tape))
               (else #f)))))

Testen sie das Verhalten des Automaten mit verschiedenen Eingaben wie:

(NFA '("der" "Hund" "bellt" "laut")) oder
(NFA '("die" "schöne" "Frau" "singt")) oder aber
(NFA '("Tiere" "die" "schnell" "rennen"))

Wie schnell zu erkennen ist, kann dieser Automat aber nicht entscheiden ob "das Hund" eine sinnvolle Zusammensetzung darstellt. Um dies entscheiden zu können müsste er "zurückschauen" können, was mit einem NEA aber nicht realisierbar ist. Aus diesem Grund werden im Compilerbau Kellerautomaten eingesetzt.

[Lösung] [Lösung Scheme]