1

I have implemented a problem which determines the non-productive or inaccessible elements from a Grammar (Vn;Vt;P;S) where Vn - set of variables; Vt- set of terminals and P - production rules, and S - start symbol.

;;; Defining a grammar
(defvar *VN* '(A B C D S)) ; non-terminal variables
(defvar *VT* '(k m n)) ; terminal
(defvar *P* '((S A B) ; set of production rules
              (S C D)
              (S A k)
              (A k)
              (B m)
              (B D m D)
              (C n)))

;;; FINDING PRODUCTIVE ELEMENTS

(defun PROD-STEP (VT P PRODS)
  ;;(format t "P = ~S~%" P)
  ;;(format t "PRODS = ~S~%" PRODS)
  (if (null P)
      PRODS
      (if (subsetp (rest (first P)) (union VT PRODS))
          (PROD-STEP VT (rest P) (union (cons (first (first P)) nil) PRODS))
          (PROD-STEP VT (rest P) PRODS))))

(defun PROD-AUX (VT P PRODS oldLength)
  (if (= (length PRODS) oldLength)
      PRODS
      (PROD-AUX VT P (PROD-STEP VT P PRODS) (length PRODS))))

(defun PROD (VT P)
    (PROD-AUX VT P nil -1))

;;; END OF FINDING PROD ELEMENTS

(trace PROD-STEP)
(trace PROD-AUX)
(trace PROD)
(PROD *VT* *P*)

;;; FINDING ACCESSIBLE ELEMENTS

(defun ACCESS-STEP (P ACC)
  ;;(format t "Pacc = ~S~%" P)
  ;;(format t "ACC = ~S~%" ACC)
  (if (null P)
      ACC
      (if (member (first (first P)) ACC)
          (ACCESS-STEP (rest P) (union (rest (first P)) ACC))
          (ACCESS-STEP (rest P) ACC))))

(defun ACCESS-AUX (P ACC oldLength)
  (if (= (length ACC) oldLength)
      ACC
      (ACCESS-AUX P (ACCESS-STEP P ACC) (length ACC))))

(defun ACCESS (P S)
  ;;(format t "Paccess = ~S~%" P)
  (ACCESS-AUX P (cons S nil) 0))

 ;;; END OF FINDING ACCESSIBLE ELEMENTS

(trace ACCESS-STEP)
(trace ACCESS-AUX)
(trace ACCESS)
(ACCESS *P* 'S)

;;; REMOVING INACCESSIBLE AND NOT PRODUCTIVE ELEMENTS

(defun BuildRules-AUX (VT ACCS PRODS P newP)
  ;;(format t "newP = ~S~%" newP)
  (if (null P)
      newP
      ;; VN' = (ACCESS(G) INTERSECT PROD(G))
      ;; VT' = (VT INTERSECT ACCESS(G))
      ;; DACA REGULA ESTE A->X, A = (first (first P)) SI X = (rest (first P))
      ;; VERIFICAM DACA A APARTINE VN' SI X APARTINE (VT' UNION VN')
      (if (and (member (first (first P)) (intersection PRODS ACCS))
               (subsetp (rest (first P))
                        (union (intersection ACCS PRODS)
                               (intersection VT ACCS))))
          (BuildRules-AUX VT ACCS PRODS (rest P) (union newP 
                                                        (cons (first P) nil)))
          (BuildRules-AUX VT ACCS PRODS (rest P) newP))))

(defun BuildRules (VT ACCS PRODS P)
  (BuildRules-AUX VT ACCS PRODS P nil))

(trace BuildRules-AUX)
(trace BuildRules)

(BuildRules *VT* (ACCESS *P* 'S) (PROD *VT* *P*)*P*)

(defun SIMPL-AUX (VN VT P S ACCS PRODS)
  (setq ACCS (ACCESS P S))
  (setq PRODS (PROD VT P))
  (if (and (null (set-difference (union VN VT) ACCS))
           (null (set-difference VN PRODS)))
      (cons VN (cons VT (cons P S)))
      (SIMPL-AUX (intersection ACCS PRODS)
                 (intersection VT ACCS)
                 (BuildRules VT ACCS PRODS P)
                 S
                 ACCS
                 PRODS)))

(defun SIMPL (VN VT P S)
  (SIMPL-AUX *VN* *VT* *P* 'S nil nil))

;;; END OF REMOVING INACCESSIBLE AND NOT PRODUCTIVE ELEMENTS

;;; GETTING THE RESULTS

(SIMPL *VN* *VT* *P* 'S)

But now I'm stuck with getting some intermediate results.

For productive and accessible it's clear that I would use PROD and ACCESS,

(PROD *VT* *P*) 
(ACCESS *P* 'S)

but I'm not sure how to get some intermediate results for:

  1. Non-productive
  2. Not-accessible

as I have only one function for this:

(BuildRules *VT* (ACCESS *P* 'S) (PROD *VT* *P*) *P*)

Can you please help to figure this out?

2
  • 4
    you have asked a similar question already, but your code is still not properly indented. Please do it. Also document what the arguments to your functions are. May 6, 2012 at 6:30
  • 1
    I took the liberty to format the code. You should still give your variables less cryptic names, e.g. terminals instead of VT, or production-rules instead of P.
    – Svante
    May 6, 2012 at 15:49

1 Answer 1

0

You just need to use a replacement build-rules function that only filters for one kind of predicate. That could be written much clearer using remove-if-not, by the way.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.