21.6 Example

The following example shows a simple grammar for a very small subset of English.

(defpackage "ENGLISH-PARSER"
  (:use "PARSERGEN")
  (:add-use-defaults t))
(in-package "ENGLISH-PARSER") 
 
;;; Define the parser itself.
 
(defparser english-parser  
  ((<input> <sentence>) $1) 
  ((<sentence> <noun-phrase> <verb-phrase>) `(,$1 ,$2))  
  ((<basic-noun-phrase> :adj <basic-noun-phrase>) `(,$1 ,$2))  
  ((<basic-noun-phrase> <basic-noun-phrase> <relational>) `(,$1 ,$2)) 
  ((<basic-noun-phrase> :noun) $1)  
  ((<relational> :rel <verb-phrase>) `(,$1 ,$2))  
  ((<verb-phrase> :verb <noun-phrase> <locative>) `(,$1 ,$2 ,$3))  
  ((<verb-phrase> :verb <locative>) `(,$1 ,$2))  
  ((<verb-phrase> :verb <noun-phrase>) `(,$1 ,$2)) 
  ((<verb-phrase> :verb) $1)  
  ((<noun-phrase> :art <basic-noun-phrase> <locative>) `(,$1 ,$2 ,$3)) 
  ((<noun-phrase> :art <basic-noun-phrase>) `(,$1 ,$2))  
  ((<noun-phrase> <basic-noun-phrase>) $1) 
  ((<locative> :loc <noun-phrase>) `(,$1 ,$2)))
 
;;; The lexer function.
 
;;; The basic lexing function
 
(defvar *input*)
(defun lex-english () 
  (let ((symbol (pop *input*))) 
    (if symbol (get-lex-class symbol)   
      nil)))
 
;;; Getting syntactic categories.
 
(defparameter *words* 
  '((the :art)(a :art)(some :art)(ate :verb)(hit :verb)
    (cat :noun)(rat :noun)(mat :noun)(which :rel)(that :rel)
    (who :rel)(man :noun)(big :adj)(small :adj)(brown :adj)
    (dog :noun)(on :loc)(with :loc)(behind :loc)(door :noun)
    (sat :verb)(floor :noun)))
 
(defun get-lex-class (word)
  (values (or (cadr (assoc word *words*))
              :unknown)
          word))
 
;;; The main function -- note bindings of globals (these
;;; are exported from the parsergen package).
 
(defun parse-english (input)
  (let ((*input* input))
    (english-parser #'lex-english)))

The following example session shows the parsing of some sentences.

ENGLISH-PARSER 34 > (parse-english '(the cat sat on the
                       mat)) 
((THE CAT) (SAT (ON (THE MAT))))
 
ENGLISH-PARSER 35 > (parse-english '(the big brown dog
                        behind the door ate the cat
                        which sat on the floor)) 
((THE (BIG (BROWN DOG)) (BEHIND (THE DOOR))) 
 (ATE (THE (CAT (WHICH (SAT (ON (THE FLOOR))))))))