branch: externals/parser-generator
commit 80f99cfac85791dca2d2243eedf9c35f3a74d0ec
Author: Christian Johansson <christ...@cvj.se>
Commit: Christian Johansson <christ...@cvj.se>
Added failing unit test for lr-items set k=2
---
parser-generator-lr.el | 37 ++++++++++++++++++++-----------
test/parser-generator-lr-test.el | 47 ++++++++++++++++++++++++++++++++++------
2 files changed, 64 insertions(+), 20 deletions(-)
diff --git a/parser-generator-lr.el b/parser-generator-lr.el
index 13cd8be..886f3eb 100644
--- a/parser-generator-lr.el
+++ b/parser-generator-lr.el
@@ -188,15 +188,19 @@
(make-hash-table :test 'equal))
(next-symbols)
(next-symbols-found (make-hash-table :test 'equal))
- (table-lr-items (make-hash-table :test 'equal))
- (e-list parser-generator--e-identifier))
+ (table-lr-items (make-hash-table :test 'equal)))
(let ((e-set
(parser-generator-lr--items-for-prefix
- e-list)))
+ parser-generator--e-identifier)))
+
;;(1) Place V(e) in S. The set V(e) is initially unmarked.
- (push `(,lr-item-set-new-index ,e-set) unmarked-lr-item-sets)
- (setq lr-item-set-new-index (1+ lr-item-set-new-index)))
+ (push
+ `(,lr-item-set-new-index ,e-set)
+ unmarked-lr-item-sets)
+ (setq
+ lr-item-set-new-index
+ (1+ lr-item-set-new-index)))
;; (2) If a set of items a in S is unmarked
;; (3) Repeat step (2) until all sets of items in S are marked.
@@ -215,21 +219,29 @@
(message "popped-item: %s" popped-item))
;; (2) Mark a
- (puthash lr-items lr-item-set-index marked-lr-item-sets)
+ (puthash
+ lr-items
+ lr-item-set-index
+ marked-lr-item-sets)
- (puthash lr-item-set-index lr-items table-lr-items)
+ (puthash
+ lr-item-set-index
+ lr-items
+ table-lr-items)
(setq goto-table-table nil)
- ;; Build list of possible next-symbols here that follows lr-items set
+ ;; Build list of possible next-symbols
+ ;; here that follows current set
(setq next-symbols nil)
(dolist (lr-item lr-items)
(let ((symbols (nth 2 lr-item)))
(when symbols
(let ((next-symbol (car symbols)))
- (when (and
- (or
- (parser-generator--valid-terminal-p next-symbol)
- (parser-generator--valid-non-terminal-p next-symbol))
+ (when
+ (and
+ (or
+ (parser-generator--valid-terminal-p next-symbol)
+ (parser-generator--valid-non-terminal-p next-symbol))
(not
(gethash
(list
@@ -253,7 +265,6 @@
(sort
next-symbols
'string-lessp)))))
-
(parser-generator--debug
(message "next-symbols: %s" next-symbols))
diff --git a/test/parser-generator-lr-test.el b/test/parser-generator-lr-test.el
index c5b32bd..1b35c2d 100644
--- a/test/parser-generator-lr-test.el
+++ b/test/parser-generator-lr-test.el
@@ -480,18 +480,27 @@
(should
(equal
- '(
- (0 (
+ '((0 (
((R) nil (a b T) ($ $))
((R) nil (a b T) (a b))
((S) nil (R) ($ $))
((S) nil (R S) ($ $))
- ((Sp) nil (S) ($ $)))
- )
+ ((Sp) nil (S) ($ $))
+ ))
(1 (
- ((R) (a) (b T) ($ $))
- ((R) (a) (b T) (a b))))
+ ((R) nil (a b T) ($ $))
+ ((R) nil (a b T) (a b))
+ ((S) (R) (S) ($ $))
+ ((S) (R) nil ($ $))
+ ((S) nil (R) ($ $))
+ ((S) nil (R S) ($ $))))
(2 (
+ ((Sp) (S) nil ($ $))))
+ (3 (
+ ((R) (a) (b T) ($ $))
+ ((R) (a) (b T) (a b))
+ ))
+ (4 (
((R) (a b) (T) ($ $))
((R) (a b) (T) (a b))
((T) nil (a T) ($ $))
@@ -499,7 +508,31 @@
((T) nil (c) ($ $))
((T) nil (c) (a b))
((T) nil nil ($ $))
- ((T) nil nil (a b)))))
+ ((T) nil nil (a b))
+ ))
+ (5 (
+ ((R) (a b T) nil ($ $))
+ ((R) (a b T) nil (a b))
+ ))
+ (6 (
+ ((T) (a) (T) ($ $))
+ ((T) (a) (T) (a b))
+ ((T) nil (a T) ($ $))
+ ((T) nil (a T) (a b))
+ ((T) nil (c) ($ $))
+ ((T) nil (c) (a b))
+ ((T) nil nil ($ $))
+ ((T) nil nil (a b))
+ ))
+ (7 (
+ ((T) (c) nil ($ $))
+ ((T) (c) nil (a b))
+ ))
+ (8 (
+ ((T) (a T) nil ($ $))
+ ((T) (a T) nil (a b))))
+ (9 (
+ ((S) (R S) nil ($ $)))))
(parser-generator--hash-to-list
lr-items)))
(message "Passed LR-items k = 2")
