[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[elpa] externals/parser-generator 5957fad 076/434: First implementation
From: |
ELPA Syncer |
Subject: |
[elpa] externals/parser-generator 5957fad 076/434: First implementation of generating LR-items for grammar |
Date: |
Mon, 29 Nov 2021 15:59:12 -0500 (EST) |
branch: externals/parser-generator
commit 5957fad0945875c7bbb42f439073e0b7c78f8306
Author: Christian Johansson <christian@cvj.se>
Commit: Christian Johansson <christian@cvj.se>
First implementation of generating LR-items for grammar
---
parser.el | 70 ++++++++++++++++++++++++++++++++++++-----------------
test/parser-test.el | 14 ++++++++++-
2 files changed, 61 insertions(+), 23 deletions(-)
diff --git a/parser.el b/parser.el
index 97e64d0..7dab2dc 100644
--- a/parser.el
+++ b/parser.el
@@ -653,32 +653,58 @@
follow-set))
;; Algorithm 5.9, p. 389
-(defun parser-test--lr-items-for-grammar ()
+(defun parser--lr-items-for-grammar ()
"Calculate set of valid LR(k) items for grammar."
- (let ((S)
- (marked-sets (make-hash-table :test 'equal))
+ (let ((prefixes)
+ (marked-prefixes (make-hash-table :test 'equal))
+ (lr-items)
(symbols (append (parser--get-grammar-non-terminals)
(parser--get-grammar-terminals))))
+
(let ((e-set (parser--lr-items-for-prefix parser--e-identifier)))
;;(1) Place V(e) in S. The set V(e) is initially unmarked.
- (push `(,e-set nil) S))
- (let ((found-unmarked t))
-
- ;; (3) Repeat step (2) until all sets of items in S are marked.
- (while found-unmarked
- (setq found-unmarked nil)
- (dolist (set S)
- ;; (2) If a set of items a in S is unmarked
- (unless (car (cdr set))
- ;; TODO (2) Mark a by computing for each X in N u E, GOTO (a, X).
(Algorithm 5.8 can be used here.)
- ;; If a' = GOTO(a, X) is nonempty and is not already in S,
- ;; then add a' to S as an unmarked set of items
- (dolist (symbol symbols)
-
- )
-
- (setq found-unmarked t)))))
-
- S))
+ (push e-set lr-items)
+ (push `(,parser--e-identifier) prefixes))
+
+ ;; (3) Repeat step (2) until all sets of items in S are marked.
+ (let ((prefix))
+
+ ;; (2) If a set of items a in S is unmarked
+ (while prefixes
+
+ ;; (2) Mark a by computing for each X in N u E, GOTO (a, X).
(Algorithm 5.8 can be used here.)
+ (setq prefix (pop prefixes))
+
+ ;; e-identifier is converted to nil prefix
+ (when (and
+ (= (length prefix) 1)
+ (parser--valid-e-p (car prefix)))
+ (setq prefix nil))
+
+ (message "prefix: %s" prefix)
+
+ (puthash prefix t marked-prefixes)
+
+ ;; V(X1,...,Xi) = GOTO(V(X1,...,Xi-1), Xi)
+ (dolist (symbol symbols)
+ (let ((alternative-prefix (append prefix (list symbol))))
+ (message "alternative-prefix: %s" alternative-prefix)
+
+ ;; and is not already in S
+ (unless (gethash alternative-prefix marked-prefixes)
+ (let ((prefix-lr-items (parser--lr-items-for-prefix
alternative-prefix)))
+
+ (message "V%s = %s" alternative-prefix prefix-lr-items)
+
+ ;; If a' = GOTO(a, X) is nonempty
+ (when prefix-lr-items
+
+ (message "Added to stack.")
+
+ ;; then add a' to S as an unmarked set of items
+ (push alternative-prefix prefixes)
+ (push prefix-lr-items lr-items))))))))
+
+ lr-items))
;; Algorithm 5.8, p. 386
(defun parser--lr-items-for-prefix (γ)
diff --git a/test/parser-test.el b/test/parser-test.el
index 711d48a..9ca16d3 100644
--- a/test/parser-test.el
+++ b/test/parser-test.el
@@ -227,7 +227,19 @@
"Test `parser--lr-items-for-grammar'."
(message "Starting tests for (parser--lr-items-for-grammar)")
- ;; TODO Do tests here
+ ;; Example 5.30, p. 389
+ (parser--set-grammar '((Sp S) (a b) ((Sp S) (S (S a S b)) (S e)) Sp))
+ (parser--set-look-ahead-number 1)
+
+ (should
+ (equal
+ '((S nil (S a S b) (a))
+ (S nil (S a S b) (e))
+ (S nil nil (a))
+ (S nil nil (e))
+ (Sp nil (S) (e)))
+ (parser--lr-items-for-grammar)))
+ (message "Passed LR-items for example 5.30")
(message "Passed tests for (parser--lr-items-for-grammar)"))
- [elpa] externals/parser-generator b8d6476 038/434: Setting look-ahead-number clears cache storage, (continued)
- [elpa] externals/parser-generator b8d6476 038/434: Setting look-ahead-number clears cache storage, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 2829d36 039/434: More work on FOLLOW, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 0f8b422 043/434: Added another unit test for follow function, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator f8f5fe2 046/434: Started on function to calculate lk-items for a viable prefix, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 8d0a93e 053/434: More work on algorithm, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 6d2e231 059/434: Added two more failing valid LR-set calculation tests, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 15dc472 067/434: Added TODO items, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 44eb5a3 062/434: Passing unit test for V(e) and V(S), ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator a7d1cc0 070/434: Updated README, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 3373881 085/434: More work on GOTO-table generation, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 5957fad 076/434: First implementation of generating LR-items for grammar,
ELPA Syncer <=
- [elpa] externals/parser-generator 7689ec5 086/434: More work, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator c992a54 093/434: Added info in README.md about LR-items, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 4c75f65 101/434: Added TODO items, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 6ee548e 005/434: Updated README, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 5150b91 075/434: Started working on lr-items for grammar function, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 59aea4d 077/434: More tweaking new algorithm, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator d0c9663 082/434: Passing test for distinct LR-items for grammar, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 7a48197 084/434: Removed obsolete variable, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator 7fe7318 087/434: Passed test for distinct LR-items for grammar, ELPA Syncer, 2021/11/29
- [elpa] externals/parser-generator ba95bff 094/434: Started on new algorithm, ELPA Syncer, 2021/11/29