|YACC, going the other way firstname.lastname@example.org (1991-04-15)|
|Re: YACC, going the other way email@example.com (1991-04-23)|
|Re: YACC, going the other way carlton@aldebaran.Berkeley.EDU (1991-04-23)|
|Re: YACC, going the other way firstname.lastname@example.org (Walter Underwood) (1991-04-24)|
|Re: YACC, going the other way email@example.com (1991-04-25)|
|Re: YACC, going the other way jimad@microsoft.UUCP (1991-04-26)|
|Re: YACC, going the other way firstname.lastname@example.org (1991-05-01)|
|From:||email@example.com (Gene Ressler)|
|Summary:||Deterministic enumeration of CFLs|
|Keywords:||yacc, testing, Lisp, theory|
|Organization:||Cornell Univ. CS Dept, Ithaca NY 14853|
|Date:||Wed, 1 May 1991 02:21:40 GMT|
In article <1991Apr23.firstname.lastname@example.org> email@example.com (Edwin Lewis King +1 614 860 3394) writes:
>I'm interesting in generating strings that are described by a BNF (OK,
Many decidablility results rely on Turing machines enumerating CFLs, so
we'd better be able to do it without random numbers! I know this may not
be what you want for testing, but I think it's interesting anyway.
Following is a rough hack in Common Lisp (runs under Lucid) that keeps a
queue of sentential forms sorted by length, pulling off the shortest one
to expand next. `Expand' means replace each non-terminal A by the rhs of
each A-production in all combinations. If a resulting form has only
non-terminals, print it; otherwise queue it for deeper expansion. If you
have no epsilon productions, this generates strings of strictly
; Enumerate strings generated by a CFL.
; Warning: Rough and probably buggy code.
(let ((look-ahead nil)
(defmacro lex ()
`(setq look-ahead (read stream nil)))
(defun parse (in-stream)
; set up
(setq stream in-stream)
; assume first sym is start sym
(setq start look-ahead)
; done when lex returns nil for eof
; look ahead is lhs. gather rhs.
(let ((prod look-ahead)
(unless (eq look-ahead '->)
(error "missing ->"))
; gather up to ! or !! (`or' or end of prod)
(when (member look-ahead '(! !! ->))
(push look-ahead rhs)
; put production in rules hash table indexed by lhs
; (prod) so each entry is a list of rhs's
(push (reverse rhs) (gethash prod rules))
(!! (lex) (return))
(t (error "unexpected ~A" look-ahead)))
; start new rhs for same lhs (prod)
(setq rhs nil))))
; check for undefined symbols
(maphash #'(lambda (prod rhss)
(declare (ignore prod))
(dolist (rhs rhss)
(dolist (x rhs)
(unless (or (stringp x)
(gethash x rules))
(error "~A undefined" rhs)))))
; return start symbol
; don't put any sentential form longer than this on the queue
(defparameter *cutoff-length* 10)
; insert form in queue sorted ascending by length
(defun enq (s-form)
(when (< (list-length s-form) *cutoff-length*)
(setq q (merge 'list
(list s-form) q
#'(lambda (x y)
(< (list-length x)
; get shortest sentential form from queue
(defmacro qpop () `(pop q))
; expand rhs every way that is possible by
; expanding each non-terminal exactly once.
; accumulate result in `sofar'. when rhs
; is gone, look at `sofar' to see if it's all
; terminals (strings). if so, print it; if not,
; queue it for deeper expansion.
(defun expand (rhs sofar)
(if (every #'stringp sofar)
(format t "~&~A"
(reduce #'(lambda (x y)
(concatenate 'string x y))
(enq (reverse sofar))))
((stringp (car rhs))
(expand (cdr rhs) (cons (car rhs) sofar)))
(t (dolist (rrhs (gethash (car rhs) rules))
(expand (cdr rhs) (revappend rrhs sofar))))))
; expand start symbol, iterate (expand)
; until the queue is empty.
(defun enum (start)
(setq q nil)
(dolist (rhs (gethash start rules))
(expand rhs nil))
(let ((rhs (qpop)))
(unless rhs (return))
(expand rhs nil))))
) ; end (let (look-ahead ...
; tester assumes a grammar is in file "grammar"
(defun test ()
(with-open-file (grammar "grammar" :direction :input)
(enum (parse grammar))))
; a sample grammar.
; if you need epsilon, just say "".
S -> expr
expr -> term
! expr "+" term
term -> factor
! term "*" factor
factor -> "1"
! "(" expr ")"
Return to the
Search the comp.compilers archives again.