Function: ebnf-optimize1

ebnf-optimize1 is a byte-compiled function defined in ebnf-otz.el.gz.

Signature

(ebnf-optimize1 PROD)

Source Code

;; Defined in /usr/src/emacs/lisp/progmodes/ebnf-otz.el.gz
;; left recursion:
;; 1.  A = B | A C.             ==>   A = B {C}*.
;; 2.  A = B | A B.             ==>   A = {B}+.
;; 3.  A =   | A B.             ==>   A = {B}*.
;; 4.  A = B | A C B.           ==>   A = {B || C}+.
;; 5.  A = B | D | A C | A E.   ==>   A = ( B | D ) { C | E }*.

;; optional:
;; 6.  A = B | .                ==>   A = [B].
;; 7.  A =   | B .              ==>   A = [B].

;; factorization:
;; 8.  A = B C | B D.           ==>   A = B (C | D).
;; 9.  A = C B | D B.           ==>   A = (C | D) B.
;; 10. A = B C E | B D E.       ==>   A = B (C | D) E.

(defun ebnf-optimize1 (prod)
  (ebnf-message-info "Optimizing syntactic chart")
  (let ((production (ebnf-node-production prod)))
    (and (eq (ebnf-node-kind production) 'ebnf-generate-alternative)
	 (let* ((hlist (ebnf-split-header-prefix
			(ebnf-node-list production)
			(ebnf-node-name prod)))
		(nlist (car hlist))
		(zlist (cdr hlist))
		(elist (ebnf-split-header-suffix nlist zlist)))
	   (ebnf-node-production
	    prod
	    (cond
	     ;; cases 2., 4.
	     (elist
	      (and (eq elist t)
		   (setq elist nil))
	      (setq elist (or (ebnf-prefix-suffix elist)
			      elist))
	      (let* ((nl (ebnf-extract-empty nlist))
		     (el (or (ebnf-prefix-suffix (cdr nl))
			     (ebnf-create-alternative (cdr nl)))))
		(if (car nl)
		    (ebnf-make-zero-or-more el elist)
		  (ebnf-make-one-or-more el elist))))
	     ;; cases 1., 3., 5.
	     (zlist
	      (let* ((xlist (cdr (ebnf-extract-empty zlist)))
		     (znode (ebnf-make-zero-or-more
			     (or (ebnf-prefix-suffix xlist)
				 (ebnf-create-alternative xlist))))
		     (nnode (ebnf-map-list-to-optional nlist)))
		(and nnode
		     (setq nlist (list nnode)))
		(if (or (null nlist)
			(and (= (length nlist) 1)
			     (eq (ebnf-node-kind (car nlist))
				 'ebnf-generate-empty)))
		    znode
		  (ebnf-make-sequence
		   (list (or (ebnf-prefix-suffix nlist)
			     (ebnf-create-alternative nlist))
			 znode)))))
	     ;; cases 6., 7.
	     ((ebnf-map-node-to-optional production)
	      )
	     ;; cases 8., 9., 10.
	     ((ebnf-prefix-suffix nlist)
	      )
	     ;; none
	     (t
	      production)
	     ))))
    prod))