Wörter von formalen Sprachen erkennen
Eine formale Sprache ist eine Menge von Wörtern. Wenn diese Menge von Wörtern durch Aufzählen ihrer Elemente angegeben ist, dann ist die Überprüfung eines vorgelegten Wortes auf die Zugehörigkeit zur Sprache trivial.
Bei interessanten Sprachen ist die Menge der Wörter aber unendlich, so dass nicht alle aufgezählt werden können. Die Sprache kann dann z.B. anhand von Regeln definiert werden, wie mit der EBNF (Extended Backus Naur Form). Die EBNF definiert eine Sprache anhand von einfacheren Sprachen mit einigen Konstrukten:
Wort A = "W" - die Sprache A besteht nur aus dem Wort W,
Konkatenation A = B C - ein Wort der Sprache A ergibt sich,
wenn ein beliebiges Wort der Sprache B mit einem beliebigem
Wort der Sprache C konkateniert wird,
Vereinigung A = B | C - ein Wort gehört zur Sprache A,
wenn es zur Sprache B oder zur Sprache C gehört,
Wiederholung A = {B} - ein Wort der Sprache A besteht aus
beliebig vielen (auch 0) Konkatenationen von Wörtern aus
der Sprache B,
Option A = [B] - die Sprache A enthält zusätzlich zu
allen Worten der Sprache B noch das leere Wort.
Die Konstrukte finden sich in einem Programm zur Erkennung von Wörtern wieder. Das Programm basiert auf Parsern. Das sind hier Funktionen, die eine Liste von Wortteilen als Eingabe erwarten, deren Anfang überprüfen und dann entweder einen anwendungsspezifischen Wert und die restlichen Wortteile zurückgeben oder einer Fehler signalisieren.
Der Funktion consumer-of erzeugt Parser, die prüfen, ob ein gegebener Wortteil am Anfang der Liste steht.
(defproc consumer-of (token value)
(lambda (stream)
(if
(and stream (= (first stream) token))
(list value (rest stream))
(throw (quote fail) nil))))
Die Funktion concatenation liefert einen Parser, der nacheinander mehrere andere Parser aufruft und im Erfolgsfall deren Ergebnisse kombiniert. Zwischen den Bestandteilen des Wortes, die von den einzelnen Parsern untersucht werden, dürfen beliebig viele Leerzeichen stehen. Diese werden ignoriert.
(defproc concatenation (parsers combiner)
(lambda (stream)
(let
((results nil))
(dolist (parser parsers
(list
(apply combiner (reverse results))
stream))
(let
((pair (parser (remove-ws stream))))
(progn
(push (get-result pair) results)
(setq stream (remove-ws (get-stream pair)))))))))
(defproc remove-ws (stream)
(if
(and stream (is-ws? (first stream)))
(remove-ws (rest stream))
stream))
(defproc is-ws? (token)
(<= token " "))
(setq get-result first)
(setq get-stream second)
Das Funktion choice erzeugt einen Parser, der mehrere andere Parser der Reihe nach auf eine Eingabe anwendet und das Resultat des ersten liefert, der Erfolg hat.
(defproc choice (parsers)
(lambda (stream)
(let
((stream (remove-ws stream))
(parsers parsers))
(loop
(when (null? parsers)
(throw (quote fail) nil))
(catch (quote fail)
(return ((first parsers) stream)))
(pop parsers)))))
Die Funktion one-or-more liefert einen Parser, der prüft, ob ein anderer Parser wiederholt erfolgreich angewendet werden kann. Die Wiederholungen sind durch ein Trennzeichen separiert.
(defproc one-or-more (parser separator combiner)
(lambda (stream)
(let
((pair (parser (remove-ws stream)))
(results nil))
(loop
(push (get-result pair) results)
(setq stream (remove-ws (get-stream pair)))
(when
(or
(null? stream)
(not (equal? (first stream) separator)))
(return (list (combiner (reverse results)) stream)))
(setq pair (parser (remove-ws (rest stream))))))))
Die Funktion zero-or-one macht einen Parser optional.
(defproc zero-or-one (parser)
(choice
(list
parser
(lambda (stream) (list nil stream)))))
Das Macro defined-later gibt einen Parser zurück, der einen anderen anhand eines Namens zur Laufzeit identifiziert und aufruft.
(defmacro defined-later args
(let
((stream (gensym)))
(quasi-quote
(lambda ((unquote stream))
((unquote (first args)) (unquote stream))))))
Diese Funktionen können benutzt werden, um z.B. arithmetische Ausdrücke aus der Infix-Notation in Lisp zu übersetzen. Die Regeln in EBNF sehen so aus:
NUMBER = <Ganzzahl, Folge von Ziffern an deren Anfang nicht die 0 steht>
NAME = <Bezeichner, Folge von Kleinbuchstaben>
ARGUMENTS = EXPRESSION { "," EXPRESSION }
CALL = NAME "(" ARGUMENTS ")"
BRACKETED-EXPRESSION = "(" EXPRESSION ")"
FACTOR = BRACKETED-EXPRESSION | NUMBER | CALL | NAME
PRODUCT = FACTOR { "*" FACTOR }
QUOTIENT = FACTOR "/" FACTOR
PRODUCT-OR-QUOTIENT = PRODUCT | QUOTIENT
SUM = PRODUCT-OR-QUOTIENT { "+" PRODUCT-OR-QUOTIENT }
DIFFERENCE = PRODUCT-OR-QUOTIENT "-" PRODUCT-OR-QUOTIENT
EXPRESSION = DIFFERENCE | SUM
Jede dieser Regeln wird durch einen Parser realisiert. Die Parser für NUMBER und NAME sind speziell entwickelt. Die anderen basieren auf den oben beschriebenen Funktionen, die den Konstrukten der EBNF entsprechen.
(defproc translate-number (a)
(if
(and a (starts-with-digit? (first a)))
(list
(read-from-string (first a))
(rest a))
(throw (quote fail) nil)))
(defproc starts-with-digit? (token)
(member?
(substring token 1 1)
(list "0" "1" "2" "3" "4" "5" "6" "7" "8" "9")))
(defproc translate-name (a)
(if
(and a (starts-with-char? (first a)))
(list
(let
((name (first a)))
(if (equal? name "nil")
nil
(intern name)))
(rest a))
(throw (quote fail) nil)))
(defproc starts-with-char? (token)
(let
((char (substring token 1 1)))
(and
(>= char "a"))
(<= char "z")))
(setq translate-arguments
(one-or-more
(defined-later translate-expression)
","
identity))
(setq translate-call
(concatenation
(list
translate-name
(consumer-of "(" nil)
translate-arguments
(consumer-of ")" nil))
(lambda (name o args c) (cons name args))))
(setq translate-bracketed-expression
(concatenation
(list
(consumer-of "(" nil)
(defined-later translate-expression)
(consumer-of ")" nil))
(lambda (o expression c) expression)))
(setq translate-factor
(choice
(list
translate-bracketed-expression
translate-number
translate-call
translate-name)))
(setq translate-product
(one-or-more
translate-factor
"*"
(lambda (args)
(if (single? args)
(first args)
(cons (quote *) args)))))
(setq translate-quotient
(concatenation
(list
translate-factor
(consumer-of "/" (quote /))
translate-factor)
(lambda (s1 op s2) (list op s1 s2))))
(setq translate-product-or-quotient
(choice
(list
translate-quotient
translate-product)))
(setq translate-sum
(one-or-more
translate-product-or-quotient
"+"
(lambda (args)
(if (single? args)
(first args)
(cons (quote +) args)))))
(setq translate-difference
(concatenation
(list
translate-product-or-quotient
(consumer-of "-" (quote -))
translate-product-or-quotient)
(lambda (s1 op s2) (list op s1 s2))))
(setq translate-expression
(choice
(list
translate-difference
translate-sum)))
Angewendet wird der Parser translate-expression. Dieser bekommt eine zerlegte Zeichenkette vorgesetzt, wie hier im Beispiel
(get-result
(translate-expression
(tokenize-string
"(1 + 1) * 2 * 3"
" (),;:=+-*/"
t)))
und liefert dann das Lisp Codefragment
(* (+ 1 1) 2 3).
Bei interessanten Sprachen ist die Menge der Wörter aber unendlich, so dass nicht alle aufgezählt werden können. Die Sprache kann dann z.B. anhand von Regeln definiert werden, wie mit der EBNF (Extended Backus Naur Form). Die EBNF definiert eine Sprache anhand von einfacheren Sprachen mit einigen Konstrukten:
Wort A = "W" - die Sprache A besteht nur aus dem Wort W,
Konkatenation A = B C - ein Wort der Sprache A ergibt sich,
wenn ein beliebiges Wort der Sprache B mit einem beliebigem
Wort der Sprache C konkateniert wird,
Vereinigung A = B | C - ein Wort gehört zur Sprache A,
wenn es zur Sprache B oder zur Sprache C gehört,
Wiederholung A = {B} - ein Wort der Sprache A besteht aus
beliebig vielen (auch 0) Konkatenationen von Wörtern aus
der Sprache B,
Option A = [B] - die Sprache A enthält zusätzlich zu
allen Worten der Sprache B noch das leere Wort.
Die Konstrukte finden sich in einem Programm zur Erkennung von Wörtern wieder. Das Programm basiert auf Parsern. Das sind hier Funktionen, die eine Liste von Wortteilen als Eingabe erwarten, deren Anfang überprüfen und dann entweder einen anwendungsspezifischen Wert und die restlichen Wortteile zurückgeben oder einer Fehler signalisieren.
Der Funktion consumer-of erzeugt Parser, die prüfen, ob ein gegebener Wortteil am Anfang der Liste steht.
(defproc consumer-of (token value)
(lambda (stream)
(if
(and stream (= (first stream) token))
(list value (rest stream))
(throw (quote fail) nil))))
Die Funktion concatenation liefert einen Parser, der nacheinander mehrere andere Parser aufruft und im Erfolgsfall deren Ergebnisse kombiniert. Zwischen den Bestandteilen des Wortes, die von den einzelnen Parsern untersucht werden, dürfen beliebig viele Leerzeichen stehen. Diese werden ignoriert.
(defproc concatenation (parsers combiner)
(lambda (stream)
(let
((results nil))
(dolist (parser parsers
(list
(apply combiner (reverse results))
stream))
(let
((pair (parser (remove-ws stream))))
(progn
(push (get-result pair) results)
(setq stream (remove-ws (get-stream pair)))))))))
(defproc remove-ws (stream)
(if
(and stream (is-ws? (first stream)))
(remove-ws (rest stream))
stream))
(defproc is-ws? (token)
(<= token " "))
(setq get-result first)
(setq get-stream second)
Das Funktion choice erzeugt einen Parser, der mehrere andere Parser der Reihe nach auf eine Eingabe anwendet und das Resultat des ersten liefert, der Erfolg hat.
(defproc choice (parsers)
(lambda (stream)
(let
((stream (remove-ws stream))
(parsers parsers))
(loop
(when (null? parsers)
(throw (quote fail) nil))
(catch (quote fail)
(return ((first parsers) stream)))
(pop parsers)))))
Die Funktion one-or-more liefert einen Parser, der prüft, ob ein anderer Parser wiederholt erfolgreich angewendet werden kann. Die Wiederholungen sind durch ein Trennzeichen separiert.
(defproc one-or-more (parser separator combiner)
(lambda (stream)
(let
((pair (parser (remove-ws stream)))
(results nil))
(loop
(push (get-result pair) results)
(setq stream (remove-ws (get-stream pair)))
(when
(or
(null? stream)
(not (equal? (first stream) separator)))
(return (list (combiner (reverse results)) stream)))
(setq pair (parser (remove-ws (rest stream))))))))
Die Funktion zero-or-one macht einen Parser optional.
(defproc zero-or-one (parser)
(choice
(list
parser
(lambda (stream) (list nil stream)))))
Das Macro defined-later gibt einen Parser zurück, der einen anderen anhand eines Namens zur Laufzeit identifiziert und aufruft.
(defmacro defined-later args
(let
((stream (gensym)))
(quasi-quote
(lambda ((unquote stream))
((unquote (first args)) (unquote stream))))))
Diese Funktionen können benutzt werden, um z.B. arithmetische Ausdrücke aus der Infix-Notation in Lisp zu übersetzen. Die Regeln in EBNF sehen so aus:
NUMBER = <Ganzzahl, Folge von Ziffern an deren Anfang nicht die 0 steht>
NAME = <Bezeichner, Folge von Kleinbuchstaben>
ARGUMENTS = EXPRESSION { "," EXPRESSION }
CALL = NAME "(" ARGUMENTS ")"
BRACKETED-EXPRESSION = "(" EXPRESSION ")"
FACTOR = BRACKETED-EXPRESSION | NUMBER | CALL | NAME
PRODUCT = FACTOR { "*" FACTOR }
QUOTIENT = FACTOR "/" FACTOR
PRODUCT-OR-QUOTIENT = PRODUCT | QUOTIENT
SUM = PRODUCT-OR-QUOTIENT { "+" PRODUCT-OR-QUOTIENT }
DIFFERENCE = PRODUCT-OR-QUOTIENT "-" PRODUCT-OR-QUOTIENT
EXPRESSION = DIFFERENCE | SUM
Jede dieser Regeln wird durch einen Parser realisiert. Die Parser für NUMBER und NAME sind speziell entwickelt. Die anderen basieren auf den oben beschriebenen Funktionen, die den Konstrukten der EBNF entsprechen.
(defproc translate-number (a)
(if
(and a (starts-with-digit? (first a)))
(list
(read-from-string (first a))
(rest a))
(throw (quote fail) nil)))
(defproc starts-with-digit? (token)
(member?
(substring token 1 1)
(list "0" "1" "2" "3" "4" "5" "6" "7" "8" "9")))
(defproc translate-name (a)
(if
(and a (starts-with-char? (first a)))
(list
(let
((name (first a)))
(if (equal? name "nil")
nil
(intern name)))
(rest a))
(throw (quote fail) nil)))
(defproc starts-with-char? (token)
(let
((char (substring token 1 1)))
(and
(>= char "a"))
(<= char "z")))
(setq translate-arguments
(one-or-more
(defined-later translate-expression)
","
identity))
(setq translate-call
(concatenation
(list
translate-name
(consumer-of "(" nil)
translate-arguments
(consumer-of ")" nil))
(lambda (name o args c) (cons name args))))
(setq translate-bracketed-expression
(concatenation
(list
(consumer-of "(" nil)
(defined-later translate-expression)
(consumer-of ")" nil))
(lambda (o expression c) expression)))
(setq translate-factor
(choice
(list
translate-bracketed-expression
translate-number
translate-call
translate-name)))
(setq translate-product
(one-or-more
translate-factor
"*"
(lambda (args)
(if (single? args)
(first args)
(cons (quote *) args)))))
(setq translate-quotient
(concatenation
(list
translate-factor
(consumer-of "/" (quote /))
translate-factor)
(lambda (s1 op s2) (list op s1 s2))))
(setq translate-product-or-quotient
(choice
(list
translate-quotient
translate-product)))
(setq translate-sum
(one-or-more
translate-product-or-quotient
"+"
(lambda (args)
(if (single? args)
(first args)
(cons (quote +) args)))))
(setq translate-difference
(concatenation
(list
translate-product-or-quotient
(consumer-of "-" (quote -))
translate-product-or-quotient)
(lambda (s1 op s2) (list op s1 s2))))
(setq translate-expression
(choice
(list
translate-difference
translate-sum)))
Angewendet wird der Parser translate-expression. Dieser bekommt eine zerlegte Zeichenkette vorgesetzt, wie hier im Beispiel
(get-result
(translate-expression
(tokenize-string
"(1 + 1) * 2 * 3"
" (),;:=+-*/"
t)))
und liefert dann das Lisp Codefragment
(* (+ 1 1) 2 3).