readme.txt

CYK-Algorithmus

Robert Pfeiffer

Um das Programm auszuführen, brauchen Sie Java 1.5 oder 1.6. Die Implementierung des CYK-Algortihmus verwendet die Programmiersprache Clojure, ein Jarfile der aktuellen Entwicklungsversion von Clojure liegt bei.

Starten Sie das Programm mit "java -jar clojure.jar cyk.clj"

Die Eingabe erfolgt im S-Expression-Format, ein Beispiel mit Kommentaren ist in der Datei aufgabe.grammar.clj

Der Befehl zum Ausführen des Beispiels lautet dementsprechend "java -jar clojure.jar cyk.clj < aufgabe.grammar.clj".

aufgabe.grammar.clj

;Grammatik in CNF als Clojure-S-Expression
;nur die Produktionen, S ist immer Startsymbol
;Vektor von Produktionen der Form [Nichtterminalsymbol Ableitung]
;Ableitungen sind * einzelne Zeichen (terminalsymbol)
;                 * Vektoren mit 2 Symbolen (nichtterminale)
[[S [A A]]
 [S [A C]]
 [A  \a]
 [B  \b]
 [C [B S]]
 [S [C T]]
 [T [A A]]]

;zu parsende Wörter, Anführungszeichen sind wichtig
"aabba"
"abbaaaa"
"ababaa"

cyk.clj

(ns de.robertpfeiffervz.parser)

(defn returning [x f]
  (f x)
  x)

(defn times [n fun arg]
  (if (> n 0) (recur (dec n) fun (fun arg))
              arg))

(defn sum-pair [row column]
  (for [i (range 0 row)]
    [[i column] [(- row i 1) (+ column i 1)]]))

(defn all-derivs [as bs grammar]
  (set (for [a as b bs [nonterminal production] grammar
	     :when (= [a b] production)]
	 nonterminal)))

(defn cyk-first [word grammar]
  (vec (for [char word]
      (set (for [[nonterminal production] grammar :when (= production char)]
	     nonterminal)))))

(defn cyk-next [tabl grammar]
  (let [row (count tabl)]
    (vec (for [column (range 0 (- (count (last tabl)) 1))]
	   (set (apply concat (for [[[i1 j1] [i2 j2]] (sum-pair row column)]
				(all-derivs ((tabl i1) j1) ((tabl i2) j2) grammar))))))))

(defn cyk-parsetable [word grammar]
  (times (dec (count word)) #(conj % (cyk-next % grammar)) [(cyk-first word grammar)]))

(defn cyk-parses? [word grammar]
  (io!(if (= word "") (some '[S ""] grammar)
	  (boolean (-> (cyk-parsetable word grammar)
		   (doto #(doseq [a %] (prn a)))
		   (last)
		   (first)
		   (get 'S))))))

(let [grammar  (do (print "grammatik> ") (flush) (read))]
  (loop [word (do (print "wort> ") (flush) (read))]
    (when (string? word)
      (println word "\n" (if (cyk-parses? word grammar)
		 "gültig" "ungültig"))
      (recur (do (print "> ") (flush) (read *in* false nil))))))