Implementierung eines NSR-Algorithmus in Scheme

Es gibt für die NSR verschiedene Algorithmen und damit auch verschiedene Implementierungsmöglichkeiten:

1. Der hier implementierte Algorithmus verarbeitet den Baum top-down und links-rechts: Inititialisierungswerte für Endwerte und Nicht-End-Werte (die der Baumtiefe entsprechen) werden durch den Baum propagiert und den Blättern zugewiesen.
2. Die traditionelle Formulierung ist bottom-up: Initialisierungswerte werden den Blättern zugewiesen, die Konstituenten werden auf jeder Ebene von unten nach oben verschmolzen und dabei die Werte korrigiert. Dieser traditionelle nonmonotone Algorithmus von Chomsky und Halle ist meines Erachtens gegenüber einem Top-Down-Algorithmus, wie er hier implementiert wird, etwas unbeholfen.
3. Es gibt auch einen anderen Algorithmen von Liberman, in dem Knoten des Baums danach beschriftet werden, ob sie in den Konstituenten am weitesten rechts sind oder nicht. Dann werden die Längen der Baumpfade ab dem ersten Knoten, der nicht am weitesten rechts ist (wobei der Wurzelknoten auch als solcher zählt). Die Pfadlängen ergeben die Zahlen.

Zwei Zuordnungen aus zwei verschiedenen Baumstrukturen (die letzten Wörter in jeder Konstituente sind ohne Punkte zusammengestellt):

(3 . great) (3 . big) (2 john) (3 . nearly) (4 . saw) (5 . tiny) (5 . little) (2 mary) (5 . in) (1 town))

((3 . great) (3 . big) (2 john) (4 . nearly) (2 saw) (4 . tiny) (4 . little) (2 mary) (4 . in) (1 town))

Der Scheme-Code:

; nsr.lm
; D. Gibbon
; 2 December 2001

; Demo calling function:

(define (demo)
  (display (nsr *eg0* 1 1))
  (display "#0a")
  (display (nsr *eg1* 1 1))
  (display "#0a")
  #n)

; Main function:

(define (nsr instr depthval endval)
(cond
  ((nonfinal-leaf? instr)
   (attach-value depthval instr))
  ((final-constituent? instr)
   (if
     (final-leaf? instr)
     (attach-value endval instr)
     (nsr
        (first instr)
        (+ depthval 1)
        endval
        )))
  ((nonfinal-tree? instr)
   (append
     (nsr
        (first instr)
        (+ depthval 1)
        (+ endval 1)
        )
     (nsr
        (rest instr)
        depthval
        endval
        )))
  ((error?)
   '())))

; Definitions of the semantically named special cases:

(define (nonfinal-leaf? instr)
  (symbol? instr))

(define (final-constituent? instr)
  (and
     (pair? instr)
     (null? (rest instr))))

(define (final-leaf? instr)
  (symbol? (first instr)))

(define (nonfinal-tree? instr)
  (pair? instr))

(define (error?)
  #t)

(define (attach-value value leaf)
  (list
    (cons
       value
       leaf)))

(define (first x)
  (car x))

(define (rest x)
  (cdr x))

; Examples:

(define *eg0*
'((great big John)(nearly (saw (tiny little mary) (in town)))))

(define *eg1*
'((great big John)((nearly saw) (tiny little mary) (in town))))