Function: ebnf-optimize

ebnf-optimize is an autoloaded and byte-compiled function defined in ebnf-otz.el.gz.

Signature

(ebnf-optimize SYNTAX-LIST)

Documentation

Syntactic chart optimizer.

Source Code

;; Defined in /usr/src/emacs/lisp/progmodes/ebnf-otz.el.gz
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Optimizations


;; *To be implemented*:
;;    left recursion:
;;    A = B | A C B | A C D.   ==>   A = B {C (B | D)}*.

;;    right recursion:
;;    A = B | C A.             ==>   A = {C}* B.
;;    A = B | D | C A | E A.   ==>   A = { C | E }* ( B | D ).

;;    optional:
;;    A = B | C B.             ==>   A = [C] B.
;;    A = B | B C.             ==>   A = B [C].
;;    A = D | B D | B C D.     ==>   A = [B [C]] D.


;; *Already implemented*:
;;    left recursion:
;;    A = B | A C.             ==>   A = B {C}*.
;;    A = B | A B.             ==>   A = {B}+.
;;    A =   | A B.             ==>   A = {B}*.
;;    A = B | A C B.           ==>   A = {B || C}+.
;;    A = B | D | A C | A E.   ==>   A = ( B | D ) { C | E }*.

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

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

;;    none:
;;    A = B | C | .            ==>   A = B | C | .
;;    A = B | C A D.           ==>   A = B | C A D.

(defun ebnf-optimize (syntax-list)
  "Syntactic chart optimizer."
  (if (not ebnf-optimize)
      syntax-list
    (let ((ebnf-total (length syntax-list))
	  (ebnf-nprod 0)
	  new)
      (while syntax-list
	(setq new (cons (ebnf-optimize1 (car syntax-list)) new)
	      syntax-list (cdr syntax-list)))
      (nreverse new))))