Wednesday, July 27, 2005

Parser-Generator

Am Samstag habe ich mir überlegt habe wie ein Fragebogen aufgebaut sein soll und mir dazu eine CF-Grammatik aufgeschrieben, dabei kam mir die Idee einen Parser dafür zu schreiben. Ich habe zuerst die Grammatik in Lisp notiert, wollte dann anfangen die Funktionen zu schreiben, bis mir auffiel das ich ja auch die Grammatik selber parsen und einen Parser-Generator schreiben kann. Jetzt ist das Ding fertig und scheint zu funktionieren, ich habe es noch nicht mit der Fragebogen-Grammatik getestet.

Die Fragebogen-Grammatik:

   ((fragebogen  (+ gruppe))
    (gruppe      ueberschrift (+ element))
    (element     (+ (/ text area checkboxen radios)) frage)
    (checkboxen  (+ checkbox antwort))
    (radios      (+ radio antwort))
    (ueberschrift "<h2>" (+ zeichen) "</h2>")
    (text "<input type=\"text\" name=\"" (+ zeichen) "\">")
    (area "<textarea name=\"" (+ zeichen) "\"></textarea>")
    (frage (+ zeichen) "?")
    (radio "<input type=\"radio\" name=\"" (+ zeichen) "\" value=\"" (+ zeichen) "\">")
    (checkbox "<input type=\"checkbox\" name=\"" (+ zeichen) "\" value=\"" (+ zeichen) "\">")
    (antwort (+ zeichen))
    (zeichen (/ "A" "B" "C" "D" "E" "F" "G" "H" "I" "J" "K" "L" "M"
                "N" "O" "P" "Q" "R" "S" "T" "U" "V" "W" "X" "Y" "Z"
                "a" "b" "c" "d" "e" "f" "g" "h" "i" "j" "k" "l" "m"
                "n" "o" "p" "q" "r" "s" "t" "u" "v" "w" "x" "y" "z"
                "Ä" "Ö" "Ü"
                "ä" "ö" "ü"
                "0" "1" "2" "3" "4" "5" "6" "7" "8" "9"
                "ß" "-"
                "\n" "\t")))

Das Herzstück des Parser-Generators:

(defmacro parse-production (production)
  (let ((results
         (loop for thing in production
            collect
            (if (listp thing)
                (cond ((eql '/ (car thing))
                       `(parse/ ,(cdr thing)))
                      ((eql '+ (car thing))
                       `(parse+ ,(cdr thing)))
                      ((eql '* (car thing))
                       `(parse* ,(cdr thing)))
                      (t
                       `(parse-production ,thing)))
                (cond ((stringp thing)
                       `(literal stream ,thing))
                      ((atom thing)
                       `(,thing stream)))))))
    (if (= (list-length production) 1)
        (car results)
        `(progn ,@results))))

Code: grammatik.lisp