branch: externals/parser-generator
commit a54061c43b3e2b955047a806e9d0bfaf3e4f5ec7
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Debugging of new algorithm
---
parser.el | 24 +++++++++++++++++-------
test/parser-test.el | 36 +++++++++++++++++-------------------
2 files changed, 34 insertions(+), 26 deletions(-)
diff --git a/parser.el b/parser.el
index 94fe211..3e44b1b 100644
--- a/parser.el
+++ b/parser.el
@@ -653,11 +653,12 @@
(start-productions (parser--get-grammar-rhs start)))
;; (a)
- (dolist (production-rhs start-productions)
- (dolist (rhs production-rhs)
- ;; Add [S -> . α] to V(e)
- (push `(,start nil ,rhs e) lr-items-e)
- (puthash `(e ,start nil ,rhs e) t lr-item-exists)))
+ (dolist (rhs start-productions)
+ ;; Add [S -> . α] to V(e)
+ (push `(,start nil ,rhs e) lr-items-e)
+ (puthash `(e ,start nil ,rhs e) t lr-item-exists))
+
+ (message "V(e): %s" lr-items-e)
;; (b) Iterate every item in v-set(e), if [A -> . Bα, u] is an item
and B -> β is in P
;; then for each x in FIRST(αu) add [B -> . β, x] to v-set(e),
provided it is not already there
@@ -673,6 +674,11 @@
(rhs (nth 2 item))
(suffix (nth 3 item)))
+ (message "item: %s" item)
+ (message "prefix: %s" prefix)
+ (message "rhs: %s" rhs)
+ (message "suffix: %s" suffix)
+
;; Without prefix
(unless prefix
@@ -697,7 +703,6 @@
;; (c) Repeat (b) until no more items can be
added to v-set(e)
(setq found-new t))))))))))))))
-
(puthash 'e lr-items-e lr-items))
;; 2 Suppose that we have constructed V(X1,X2,...,Xi-1) we construct
V(X1,X2,...,Xi) as follows:
@@ -706,6 +711,9 @@
(dolist (prefix γ)
(let ((lr-new-item))
(setq prefix-acc (append prefix-acc prefix))
+ (unless (listp prefix-acc)
+ (setq prefix-acc (list prefix-acc)))
+ (message "prefix-acc: %s" prefix-acc)
(dolist (lr-item prefix-previous)
(let ((lr-item-lhs (nth 0 lr-item))
@@ -747,13 +755,15 @@
;; then add [B -> . D, x] to V(X1,...,Xi) for
each x in FIRST(bu)
;; provided it is not already there
(unless (gethash `(,prefix-acc
,lr-item-suffix-first nil ,sub-rhs ,f) lr-item-exists)
+ (setq added-new t)
(puthash `(,prefix-acc ,lr-item-suffix-first
nil ,sub-rhs ,f) t lr-item-exists)
(push `(,lr-item-suffix-first nil ,sub-rhs
,f) lr-new-item))))))))))))
+ (message "V%s = %s" prefix-acc lr-new-item)
(setq prefix-previous prefix-acc)
(puthash prefix-acc lr-new-item lr-items))))
- lr-items)))
+ (gethash γ lr-items))))
(provide 'parser)
diff --git a/test/parser-test.el b/test/parser-test.el
index 0b12126..01b6481 100644
--- a/test/parser-test.el
+++ b/test/parser-test.el
@@ -223,23 +223,22 @@
(message "Passed tests for (parser--empty-free-first)"))
-;; (defun parser-test--v-set ()
-;; "Test `parser--v-set'."
-;; (message "Starting tests for (parser-test--v-set)")
-
-;; ;; Example 5.29 p 407
-;; (should
-;; (equal
-;; '("ca" "cb")
-;; (parser--v-set
-;; 'e
-;; '((S' S)
-;; (S SaSb)
-;; (S e))
-;; 'S')))
-;; (message "Passed empty-free-first 2 with complex grammar")
-
-;; (message "Passed tests for (parser-test--v-set)"))
+(defun parser-test--lr-items ()
+ "Test `parser--lr-items'."
+ (message "Starting tests for (parser--lr-items)")
+
+ ;; Example 5.29 p 387
+ (parser--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e)) Sp))
+ (parser--set-look-ahead-number 2)
+ (message "Loaded grammar")
+ (should
+ (equal
+ '((Sp (S) nil nil e)
+ (S (S) nil (a S b) a)
+ (S (S) nil (a S b) e))
+ (parser--lr-items 'S)))
+
+ (message "Passed tests for (parser--lr-items)"))
(defun parser-test--valid-grammar-p ()
"Test function `parser--valid-grammar-p'."
@@ -376,8 +375,7 @@
(parser-test--first)
(parser-test--e-free-first)
(parser-test--follow)
- ;; (parser-test--v-set)
- )
+ (parser-test--lr-items))
(provide 'parser-test)
