branch: externals/parser-generator
commit 13d76aee9293e8b3acf92268e87f81fc41c0bc67
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Passed tests for generating list permutations of length k
---
parser-generator.el | 116 ++++++++++--------------------------------
test/parser-generator-test.el | 37 +++++++++++---
2 files changed, 56 insertions(+), 97 deletions(-)
diff --git a/parser-generator.el b/parser-generator.el
index 9a95db5..b4111e3 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -160,98 +160,36 @@
(error "No grammar G defined!")))
(nth 0 G))
-(defun parser-generator--get-grammar-prefixes ()
- "Return all prefixes of length look-ahead number of terminals and
non-terminals."
- (let ((symbols
- (append
- (parser-generator--get-grammar-terminals)
- (parser-generator--get-grammar-non-terminals)))
- (prefixes)
- (k parser-generator--look-ahead-number)
- (indexes (make-hash-table :test 'equal))
- (index)
- (prefix)
- (stack)
- (increment-index)
- (include))
- (let ((symbols-length (length symbols))
+(defun parser-generator--get-list-permutations (list k)
+ "Return all possible LIST permutations length K."
+ (let ((permutations)
+ (permutations-length 1))
+ (let ((list-length (length list))
(i 0))
-
- ;; Reset all indexes
(while (< i k)
- (puthash i 0 indexes)
- (push 0 index)
- (setq i (1+ i)))
-
- ;; Build stack of all indexes that needs to be processed
- (let ((index-remains t))
- (while index-remains
-
- (setq i 0)
- (setq prefix nil)
- (setq include t)
- (while (< i k)
- (setq index (gethash i indexes))
-
- (when increment-index
- (when (= i increment-index)
- (if (and
- (= index (1- symbols-length))
- (= increment-index (1- k)))
- (progn
-
- ;; Iterate columns and see if any is less than
- ;; max index, in that case increment it and re-do
- ;; last column
- (let ((found-not-incremented)
- (i-2 0))
- (while (and
- (< i-2 (1- k))
- (not found-not-incremented))
- (unless (= (gethash i-2 indexes) (1- symbols-length))
- (puthash i-2 (1+ (gethash i-2 indexes)) indexes)
- (puthash i -1 indexes)
- (setq include nil)
- (setq found-not-incremented t))
- (setq i-2 (1+ i-2)))
-
- (unless found-not-incremented
- (setq index-remains nil))))
- (if (= index (1- symbols-length))
- (progn
- (setq index 0)
- (setq increment-index (1+ increment-index)))
- (setq index (1+ index)))
- (puthash i index indexes))))
-
- (when index-remains
- (push index prefix))
- (setq i (1+ i)))
- (unless increment-index
- (setq increment-index (1- k)))
-
- (when (and
- index-remains
- include)
- (setq prefix (nreverse prefix))
- (push prefix stack))
- ))
-
- (while stack
- (let ((index-list (pop stack)))
- ;; Reset variables
- (setq i 0)
- (setq prefix nil)
-
- ;; Build prefix and prefix-indexes from actual state
- (while (< i k)
- (setq index (nth i index-list))
- (push (nth index symbols) prefix)
- (setq i (1+ i)))
-
- (push prefix prefixes))))
- (sort prefixes 'parser-generator--sort-list)))
+ (let ((times (expt list-length (- k (1+ i))))
+ (global-i 0))
+ (while (< global-i permutations-length)
+ ;; For each list..
+ (let ((list-i 0))
+ (while (< list-i list-length)
+
+ ;; Add it |list| ^ (k - i) times to list
+ (let ((times-i 0))
+ (while (< times-i times)
+ (if (= i 0)
+ (push (list (nth list-i list)) permutations)
+ (push (nth list-i list) (nth global-i permutations)))
+ (setq global-i (1+ global-i))
+ (setq times-i (1+ times-i))))
+ (setq list-i (1+ list-i))))
+
+ (when (= i 0)
+ (setq permutations-length (length permutations)))))
+
+ (setq i (1+ i))))
+ (sort permutations 'parser-generator--sort-list)))
(defun parser-generator--get-grammar-production-number (production)
"If PRODUCTION exist, return it's number."
diff --git a/test/parser-generator-test.el b/test/parser-generator-test.el
index c6647f5..ea3195dc 100644
--- a/test/parser-generator-test.el
+++ b/test/parser-generator-test.el
@@ -674,7 +674,7 @@
(defun parser-generator-test--merge-max-terminals ()
"Test `parser-generator--merge-max-terminals'."
- (message "Passed tests for (parser-generator--merge-max-terminals)")
+ (message "Starting tests for (parser-generator--merge-max-terminals)")
(should
(equal
@@ -694,9 +694,9 @@
(message "Passed tests for (parser-generator--merge-max-terminals)"))
-(defun parser-generator-test--get-grammar-prefixes ()
- "Test `parser-generator--get-grammar-prefixes'."
- (message "Passed tests for (parser-generator--get-grammar-prefixes)")
+(defun parser-generator-test--get-list-permutations ()
+ "Test `parser-generator--get-list-permutations'."
+ (message "Starting tests for (parser-generator--get-list-permutations)")
(parser-generator-set-look-ahead-number 1)
(parser-generator-set-grammar '((S A B) ("a" "b") ((S A) (S (B)) (B "a") (A
"a") (A ("b" "a"))) S))
@@ -705,7 +705,12 @@
(should
(equal
'((A) (B) (S) ("a") ("b"))
- (parser-generator--get-grammar-prefixes)))
+ (parser-generator--get-list-permutations
+ (append
+ (parser-generator--get-grammar-terminals)
+ (parser-generator--get-grammar-non-terminals))
+ parser-generator--look-ahead-number)))
+ (message "Passed test for list permutations of length 1")
(parser-generator-set-look-ahead-number 2)
(should
@@ -715,9 +720,25 @@
(S A) (S B) (S S) (S "a") (S "b")
("a" A) ("a" B) ("a" S) ("a" "a") ("a" "b")
("b" A) ("b" B) ("b" S) ("b" "a") ("b" "b"))
- (parser-generator--get-grammar-prefixes)))
+ (parser-generator--get-list-permutations
+ (append
+ (parser-generator--get-grammar-terminals)
+ (parser-generator--get-grammar-non-terminals))
+ parser-generator--look-ahead-number)))
+ (message "Passed test for list permutations of length 2")
- (message "Passed tests for (parser-generator--get-grammar-prefixes)"))
+ (parser-generator-set-look-ahead-number 3)
+ (should
+ (equal
+ '((A A A) (A A B) (A A S) (A A "a") (A A "b") (A B A) (A B B) (A B S) (A B
"a") (A B "b") (A S A) (A S B) (A S S) (A S "a") (A S "b") (A "a" A) (A "a" B)
(A "a" S) (A "a" "a") (A "a" "b") (A "b" A) (A "b" B) (A "b" S) (A "b" "a") (A
"b" "b") (B A A) (B A B) (B A S) (B A "a") (B A "b") (B B A) (B B B) (B B S) (B
B "a") (B B "b") (B S A) (B S B) (B S S) (B S "a") (B S "b") (B "a" A) (B "a"
B) (B "a" S) (B "a" "a") (B "a" "b") (B "b" A) (B "b" B) (B "b" S) (B "b" "a")
(B "b" "b") (S A A [...]
+ (parser-generator--get-list-permutations
+ (append
+ (parser-generator--get-grammar-terminals)
+ (parser-generator--get-grammar-non-terminals))
+ parser-generator--look-ahead-number)))
+ (message "Passed test for list permutations of length 3")
+
+ (message "Passed tests for (parser-generator--get-list-permutations)"))
(defun parser-generator-test ()
"Run test."
@@ -736,7 +757,7 @@
(parser-generator-test--get-grammar-rhs)
(parser-generator-test--get-grammar-look-aheads)
(parser-generator-test--merge-max-terminals)
- (parser-generator-test--get-grammar-prefixes)
+ (parser-generator-test--get-list-permutations)
;; Algorithms
(parser-generator-test--first)
