2

文法 (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)

プログラムは期待どおりに動作しています。「a」ターミナルと「A」非ターミナルを区別したいので、入力データを文字列に変換する方法を尋ねたい唯一の質問です。

入力「a」、「k」、「*」、「begin」などのように、そのようなものを使用する必要があると思います.

前もって感謝します...

4

1 に答える 1

1

記号を使用できます: |これは依然として記号であり、その大文字と小文字を保持します|

|分| と M は両方とも記号です。異なるシンボル。

于 2012-05-01T07:34:13.520 に答える