Next: Einbindung in das Up: Pro2Lisp: Reader für Previous: Transformationen

Scanner und Parser

Betrachtet man die Grammatikregel so mag es verwundern, daß sie nicht transformiert wurde, obwohl jede Alternative mit einem Nichtterminal beginnt. Der Grund liegt darin, daß der Parser den Quelltext nicht zeichenweise liest, sondern in Form von lexikalisch zusammenhängenden Einheiten (Tokens). Ein Token besteht etwa aus allen Ziffern einer Zahl oder aus allen Zeichen eines Strings. Die Arbeit, Tokens zu bilden, ist Aufgabe des Scanners. Der Scanner liefert dazu bei jedem Aufruf ein Datum folgenden Typs:
(defstruct token
type ; dom = {number, constant, variable,
; round-left, round-right, sqr-left, square-right
; point, comma, ampersand,
; implies, implies-amper,
; is, empty}
value ; used with number, constant, variable
x-pos ; to report an error-position
y-pos
)

Durch die Transformation der Grammatik wird der Parser sehr einfach. Er ist nach dem Prinzip des rekursiven Abstiegs konstruiert. Für jedes Nichtterminal wird eine Funktion definiert, deren Aufgabe es ist, die entsprechende Regel zu erkennen und Aktionen einzuleiten, um die abstrakte Syntax zu generieren. Diese Funktion wird nur aufgerufen, wenn feststeht, daß die korrespondierende Regel anwendbar ist.

Normalerweise gestaltet sich die Zusammenarbeit von Scanner und Parser so:
(defun scanner ()
;
; Lispcode zum Erkennen von Tokens
;
)
(defun parse-term ()
;
; Lispcode zur Verarbeitung der Regel term.
; Dazu wird der Scanner aufgerufen,
; um Tokens aus dem Eingabetext zu lesen.
;
)

Der Nachteil dieser Lösung ist die große Anzahl globaler Variablen. So benötigt man mindestens eine Variable last-token, die das zuletzt gelesene Token aufnimmt. Weiterhin werden Variablen für die aktuelle Zeilen- und Spaltennummer gebraucht.

Dieser Nachteil läßt sich vermeiden, indem man last-token und Verwandte zu privaten Variablen des Scanners macht. Aus der Sicht der objektorientierten Programmierung wird der Scanner dadurch zu einem Objekt. Man kann ihm nun eine Nachricht (z.B. next-token) senden, um eine seiner Dienstleistungen auszuwählen. Implementierungstechnisch erreicht man dies dadurch, daß für jeden zu lesenden Quelltext eine Funktion scanner zur Laufzeit des Programms erzeugt wird []:
(defun gen-scanner (input-stream)
(let ((last-token init-value)
(x-pos init-value)
;
; weitere Variablen, die vormals global waren
;
)
#'(lambda (message)
(case message
(last-token last-token)
(next-token ...) ;Code, um das nächste Token zu liefern.
;
; weitere Nachrichten
;
))))

(defun parse-term (scanner)
; Lispcode, um zu verarbeiten.
; Dabei wird der Scanner in der Form
; (funcall scanner 'next-token)
; aufgerufen
)

Allen Parserfunktionen wird also der Scanner als Argument übergeben. Der objekt-orientierte Eindruck wird syntaktisch leider durch die Verwendung von funcall etwas getrübt.



Next: Einbindung in das Up: Pro2Lisp: Reader für Previous: Transformationen


Harold Boley & Michael Herfert (herfert@dfki.uni-kl.de)