The following example shows a simple grammar for a very small subset of English.
(defpackage "ENGLISH-PARSER")
(in-package "ENGLISH-PARSER")
(use-package '(parsergen))
;;; Define the parser itself.
(defparser english-parser
((bs s) $1)
((s np vp)
`(,$1 ,$2))
((bnp :adj bnp)
`(,$1 ,$2))
((bnp bnp relp)
`(,$1 ,$2))
((bnp :noun) $1)
((relp :rel vp)
`(,$1 ,$2))
((vp :verb np locp)
`(,$1 ,$2 ,$3))
((vp :verb locp)
`(,$1 ,$2))
((vp :verb np)
`(,$1 ,$2))
((vp :verb)
$1)
((np :art bnp locp)
`(,$1 ,$2 ,$3))
((np :art bnp)
`(,$1 ,$2))
((np bnp) $1)
((locp :loc np)
`(,$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))))))))