LISP implementation of a top-down left-right non-deterministic backtracking context-free recogniser

The depth-first of search strategy illustrated in this implementation is sometimes known as ``recursive descent''.

The grammar and string traversal strategy used in the recogniser is top-down left-right. Note that top-down left-right strategies have a serious weakness - they do not terminate with left-recursion, i.e. with grammars grammar which contain recursive left-branching rules. For this reason, left-branching rules are avoided in this example (and in similar examples which follow).

Task:

Why do t-d l-r algorithms not terminate on left-branching structures?

Requirements:

Input:

• a string to be parsed (in the form of a list of symbols)
• a derivation list

Note: The terminal and nonterminal symbol sets, and the rules, are represented in functions in the program.

Output:
true or false (in LISP notation)

Design:

The recogniser is modular, each module containing a function:

parse:

handles input, derivation, and reduction or prediction strategy

predict:

handles alternative predictions (rewrite rules)

membership:

handles check for terminal or nonterminal symbol in derivation

grammar:

defines grammar rules

terminal:

defines terminal symbols

nonterminal:

defines nonterminal symbols

initial:

defines initial symbol

Implementation:

The implementation is in Scheme, a modern dialect of LISP. LISP is a functional programming language, and the LISP programming style in this implementation is based on truth-functions (Boolean operators) in order to make the constraints on search decisions as clear as possible.

The implementation was written and tested using the LispMe interpreter for PalmOS handheld devices.

; cf_td_lr_recursive_descent.lm
; D.Gibbon, 11.11.2001

(define (initial)
	's
)

(define (nonterminal? sym)
	(member?
		sym
		'(s np vp n det v)
	)
)

(define (terminal? sym)
	(member?
		sym
		'(dog cat this the big black saw met)
	)
)

(define (grammar lhs)
	(cdr
		(assoc
			lhs
			'(
				(s	(np vp)
				)
				(vp	(v np)
					(v)
				)
				(np	(det n)
					(n)
				)
				(n	(dog)
					(cat)
				)
				(det	(this)
					(the)
				)
				(v	(saw)
					(met)
				)
			)
		)
	)
)


(define (parse input agenda)
	(or
		(and
			(null? input)
			(null? agenda)
		)
		(and
			(pair? agenda)
			(pair? input)
			(or
				(and
					(terminal? (car agenda))
					(eq?
						(car input)
						(car agenda)
					)
					(parse
						(cdr input)
						(cdr agenda)
					)
				)
				(and
					(nonterminal? (car agenda))
					(predict
						input
						(grammar (car agenda))
						(cdr agenda)
					)
				)
			)
		)
	)
)

(define (predict input rhsset agenda)
	(and
		(pair? rhsset)
		(or
			(parse input
				(append
					(car rhsset)
					agenda
				)
			)
			(predict
				input
				(cdr rhsset)
				agenda
			)
		)
	)
)