branch: externals/parser-generator
commit ef60d962e7701c761560d2f543a4bbcbb1b13106
Author: Christian Johansson <[email protected]>
Commit: Christian Johansson <[email protected]>
Added failing test for new function the generates grammar prefixes
---
parser-generator.el | 48 +++++++++++++++++++++++++++++++++++++++++++
test/parser-generator-test.el | 16 +++++++++++++++
2 files changed, 64 insertions(+)
diff --git a/parser-generator.el b/parser-generator.el
index 2157d04..2b26858 100644
--- a/parser-generator.el
+++ b/parser-generator.el
@@ -160,6 +160,54 @@
(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)
+ (added-prefixes (make-hash-table :test 'equal))
+ (k parser-generator--look-ahead-number)
+ (indexes)
+ (index)
+ (prefix)
+ (prefix-indexes))
+ (let ((symbols-length (length symbols))
+ (i 0)
+ (found-new t))
+
+ ;; Initialize indexes
+ (while (< i k)
+ (push 0 indexes)
+ (setq i (1+ i)))
+
+ (while found-new
+ ;; Reset variables
+ (setq found-new nil)
+ (setq i 0)
+ (setq prefix nil)
+ (setq prefix-indexes nil)
+
+ ;; Build prefix and prefix-indexes from actual state
+ (while (< i k)
+ (setq index (nth i indexes))
+ (push (nth index symbols) prefix)
+ (push index prefix-indexes)
+ (setq i (1+ i)))
+
+ (message "prefix: %s" prefix)
+
+ ;; If prefix is new add to list
+ (unless (gethash prefix-indexes added-prefixes)
+ (push prefix prefixes)
+ (puthash prefix-indexes t added-prefixes))
+
+ ;; TODO Try to find a new index here
+
+ ))
+ (sort prefixes 'parser-generator--sort-list)))
+
(defun parser-generator--get-grammar-production-number (production)
"If PRODUCTION exist, return it's number."
(unless parser-generator--table-productions-number
diff --git a/test/parser-generator-test.el b/test/parser-generator-test.el
index ec8e1b8..5d74105 100644
--- a/test/parser-generator-test.el
+++ b/test/parser-generator-test.el
@@ -694,6 +694,21 @@
(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)")
+
+ (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))
+ (parser-generator-process-grammar)
+
+ (should
+ (equal
+ '(("a") (A) ("b") (B) (S))
+ (parser-generator--get-grammar-prefixes)))
+
+ (message "Passed tests for (parser-generator--get-grammar-prefixes)"))
+
(defun parser-generator-test ()
"Run test."
;; (setq debug-on-error t)
@@ -711,6 +726,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)
;; Algorithms
(parser-generator-test--first)
