1

文法 (Vn;Vt;P;S) から非生産的またはアクセスできない要素を決定する問題を実装しました。ここで、Vn - 変数のセット。Vt- ターミナルのセットと P - プロダクション ルール、および S - スタート シンボル。

;;; 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)

しかし今、私はいくつかの中間結果を得ることに固執しています。

PROD生産的でアクセスしやすいようにするために、 andを使用することは明らかですACCESS。

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

しかし、次の中間結果を取得する方法がわかりません。

  1. 非生産的
  2. 接続できない

これには関数が1つしかないため:

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

これを理解するのを手伝ってもらえますか？

4

1 に答える 1

0

build-rules1 種類の述語のみをフィルター処理する置換関数を使用するだけです。ちなみに、これは を使用するとより明確に記述できますremove-if-not。

于 2012-05-06T16:03:28.310 に答える