branch: externals/parser-generator
commit 0e075d7ebb9269d82088415b63883d64ef223c8b
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Fixed issue with algorithm 5.9
---
parser.el | 18 +++++++++---------
test/parser-test.el | 24 +++++++++++++++++++-----
2 files changed, 28 insertions(+), 14 deletions(-)
diff --git a/parser.el b/parser.el
index 7717d9a..181afd4 100644
--- a/parser.el
+++ b/parser.el
@@ -662,7 +662,7 @@
(let ((e-set (parser--lr-items-for-prefix parser--e-identifier)))
;;(1) Place V(e) in S. The set V(e) is initially unmarked.
- (setq unmarked-lr-items (append unmarked-lr-items e-set)))
+ (setq unmarked-lr-items e-set))
;; (2) If a set of items a in S is unmarked
;; (3) Repeat step (2) until all sets of items in S are marked.
@@ -672,30 +672,30 @@
;; (2) Mark a
(setq lr-item (pop unmarked-lr-items))
(puthash lr-item t marked-lr-items)
- (setq lr-items (append lr-items lr-item))
-
- (message "lr-item: %s" lr-item)
+ (push lr-item lr-items)
+ ;; (message "lr-item: %s" lr-item)
;; (2) By computing for each X in N u E, GOTO (a, X). (Algorithm 5.8
can be used here.)
;; V(X1,...,Xi) = GOTO(V(X1,...,Xi-1), Xi)
(dolist (symbol symbols)
- (message "symbol: %s" symbol)
+ ;; (message "symbol: %s" symbol)
(let ((prefix-lr-items (parser--lr-items-for-goto (list lr-item)
symbol)))
- (message "GOTO(%s, %s) = %s" lr-item symbol prefix-lr-items)
+ (parser--debug
+ (message "GOTO(%s, %s) = %s" lr-item symbol prefix-lr-items))
;; If a' = GOTO(a, X) is nonempty
(when prefix-lr-items
(dolist (prefix-lr-item prefix-lr-items)
+ ;; (message "prefix-lr-item: %s" prefix-lr-item)
;; and is not already in S
(unless (gethash prefix-lr-item marked-lr-items)
-
;; Note that GOTO(a, X) will always be empty if all items in
a
;; have the dot at the right end of the production
-
+
;; then add a' to S as an unmarked set of items
- (push unmarked-lr-items prefix-lr-item))))))))
+ (push prefix-lr-item unmarked-lr-items))))))))
lr-items))
diff --git a/test/parser-test.el b/test/parser-test.el
index 90aca30..08d8156 100644
--- a/test/parser-test.el
+++ b/test/parser-test.el
@@ -231,15 +231,29 @@
(parser--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e)) Sp))
(parser--set-look-ahead-number 1)
- (message "LR-items for grammar: %s" (parser--lr-items-for-grammar))
-
(should
(equal
- '((S nil (S a S b) (a))
+ '((Sp (S) nil (e))
+ (Sp nil (S) (e))
+ (S nil nil (e))
+ (S nil nil (a))
+ (S (S a S b) nil (e))
+ (S (S a S) (b) (e))
+ (S (S a) (S b) (e))
+ (S (S) (a S b) (e))
(S nil (S a S b) (e))
+ (S (S a S b) nil (a))
+ (S (S a S) (b) (a))
+ (S (S a) (S b) (a))
+ (S (S a S b) nil (b))
+ (S (S a S) (b) (b))
+ (S (S a) (S b) (b))
+ (S (S) (a S b) (b))
+ (S nil (S a S b) (b))
(S nil nil (a))
- (S nil nil (e))
- (Sp nil (S) (e)))
+ (S nil nil (b))
+ (S (S) (a S b) (a))
+ (S nil (S a S b) (a)))
(parser--lr-items-for-grammar)))
(message "Passed LR-items for example 5.30")
